Livelock e Starvation: definizione ed esempi

1. Introduzione al Livelock

Se deadlock — è quando i thread restano fermi ad aspettarsi all’infinito, livelock (blocco “vivente”) — è quando i thread sono vivi, fanno continuamente qualcosa, si cedono il passo a vicenda, ma... nessuno avanza! Immaginate due persone educate in un corridoio stretto: «Prego, passi lei!» — «No, passi lei!» — «No, passi lei!» — e così all’infinito.

Definizione formale

Livelock — situazione in cui i thread non sono bloccati, ma, a causa dei continui cambiamenti del proprio stato in risposta alle azioni di altri thread, non riescono a completare il lavoro. Sono “vivi”, reagiscono attivamente, ma non svolgono lavoro utile.

Com’è nella pratica?

• I thread non restano bloccati per sempre, ma si incastrano in un ciclo infinito di concessioni.
• Il sistema non è in freeze, ma non fa ciò che dovrebbe.

Esempi dalla vita reale

• Due robot che devono incrociarsi in un passaggio stretto e ogni volta fanno contemporaneamente un passo nella stessa direzione — e si intralciano di nuovo.
• Due thread che ogni volta rilevano che la risorsa è occupata e cedono il passo l’uno all’altro... all’infinito.

2. Esempio di livelock in Java

Simuliamo un livelock nel codice. Per semplicità prendiamo due «lavoratori» che hanno bisogno di un solo cucchiaio. A differenza del deadlock, se il cucchiaio è occupato, cedono educatamente e riprovano — ma insieme, in modo sincrono.

Esempio di codice: «Lavoratori educati»

public class LivelockDemo {
    static class Spoon {
        private Worker owner;

        public Spoon(Worker owner) {
            this.owner = owner;
        }

        public Worker getOwner() {
            return owner;
        }

        public synchronized void setOwner(Worker owner) {
            this.owner = owner;
        }

        public synchronized void use() {
            // Uso del cucchiaio (non fa nulla)
        }
    }

    static class Worker {
        private final String name;
        private boolean isHungry = true;

        public Worker(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public boolean isHungry() {
            return isHungry;
        }

        public void eatWith(Spoon spoon, Worker other) {
            while (isHungry) {
                // Se il cucchiaio non è mio — aspetto
                if (spoon.getOwner() != this) {
                    try {
                        Thread.sleep(1); // Aspettiamo che il cucchiaio si liberi
                    } catch (InterruptedException ignored) {}
                    continue;
                }
                // Se l’altro è affamato — cedo il cucchiaio
                if (other.isHungry()) {
                    System.out.println(name + ": cedo il cucchiaio a " + other.getName());
                    spoon.setOwner(other);
                    continue;
                }
                // Mangio!
                System.out.println(name + ": sto mangiando!");
                spoon.use();
                isHungry = false;
                System.out.println(name + ": sono sazio!");
                spoon.setOwner(other);
            }
        }
    }

    public static void main(String[] args) {
        final Worker alice = new Worker("Alice");
        final Worker bob = new Worker("Bob");
        final Spoon spoon = new Spoon(alice);

        Thread t1 = new Thread(() -> alice.eatWith(spoon, bob));
        Thread t2 = new Thread(() -> bob.eatWith(spoon, alice));

        t1.start();
        t2.start();
    }
}

Cosa succede?

• Alice e Bob sono entrambi affamati, il cucchiaio inizialmente è di Alice.
• Alice vede che anche Bob è affamato e gli cede il cucchiaio.
• Ora il cucchiaio è di Bob, ma lui vede che Alice è affamata e lo cede a lei.
• Il cucchiaio “corre” tra i lavoratori, ma nessuno mangia — nessun progresso.

Come appare nell’output?

Alice: cedo il cucchiaio a Bob
Bob: cedo il cucchiaio ad Alice
Alice: cedo il cucchiaio a Bob
Bob: cedo il cucchiaio ad Alice
...

Come eliminare il livelock?

Si può evitare il livelock attenuando un po’ la “cortesia” dei thread. Aiuta aggiungere una pausa casuale prima del nuovo tentativo (ad esempio, tramite Thread.sleep) — così i thread smettono di reagire in sincronia. Funziona anche una strategia più “decisa”: se hai appena ceduto, aspetta più a lungo prima di riprovare. E non esagerate con la cavalleria negli algoritmi — concessioni eccessive possono portare a stalli.

3. Starvation (fame del thread)

Se il livelock è “cortesia eterna”, la starvation (fame) è quando uno o più thread non ottengono affatto accesso a una risorsa o alla CPU perché altri li superano continuamente.

Definizione formale

Starvation — situazione in cui un thread non riesce a ottenere accesso alla risorsa necessaria (CPU, memoria, lock) perché gli altri thread lo precedono costantemente. Di conseguenza, il thread “affamato” o viene eseguito molto di rado, oppure non viene eseguito affatto.

Cause della starvation

• Lock non equi. Ad esempio, un blocco synchronized normale non garantisce che il thread che aspetta da più tempo entri per primo.
• Priorità dei thread. Se i thread ad alta priorità occupano continuamente la CPU, quelli a bassa priorità possono “morire di fame” (setPriority).
• Cicli infiniti in altri thread. Se qualcuno non cede la CPU (non chiama Thread.sleep o Thread.yield()), gli altri thread potrebbero non ottenere tempo di esecuzione.

4. Esempio di starvation in Java

Esempio: un thread a bassa priorità non viene eseguito

public class StarvationDemo {
    public static void main(String[] args) {
        Runnable highPriorityTask = () -> {
            while (true) {
                // Lavoro intensivo, non cede la CPU
            }
        };

        Runnable lowPriorityTask = () -> {
            while (true) {
                System.out.println("Sono un thread a bassa priorità!");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException ignored) {}
            }
        };

        Thread high1 = new Thread(highPriorityTask);
        Thread high2 = new Thread(highPriorityTask);
        Thread low = new Thread(lowPriorityTask);

        high1.setPriority(Thread.MAX_PRIORITY); // 10
        high2.setPriority(Thread.MAX_PRIORITY); // 10
        low.setPriority(Thread.MIN_PRIORITY);   // 1

        high1.start();
        high2.start();
        low.start();
    }
}

Come si manifesta?

• I thread ad alta priorità sono sempre occupati a lavorare e non cedono la CPU.
• Il thread a bassa priorità quasi non viene eseguito (o non viene eseguito affatto).
• Su JVM/OS moderne le priorità possono essere mitigate dallo scheduler, ma su alcuni sistemi la starvation è evidente.

Un altro esempio: starvation dovuta a un lock non equo

public class StarvationLockDemo {
    private static final Object lock = new Object();

    public static void main(String[] args) {
        // 5 thread che acquisiscono continuamente il lock
        for (int i = 0; i < 5; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (lock) {
                        // Manteniamo il lock a lungo
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException ignored) {}
                    }
                }
            }).start();
        }

        // Un thread affamato
        new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    System.out.println("Il thread affamato ha ottenuto il lock!");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException ignored) {}
                }
            }
        }).start();
    }
}

In questo esempio il thread “affamato” può non ottenere accesso al lock per molto tempo se gli altri thread lo occupano continuamente.

5. Come individuare e prevenire livelock e starvation

Come individuarli?

• Livelock: l’applicazione gira, i thread non sono bloccati, ma non c’è progresso (nessun risultato, nessuna uscita dai cicli).
• Starvation: alcuni thread quasi non vengono eseguiti (messaggi rari nei log o assenti).

Strumenti

• Logging: annotate inizio/fine del lavoro, acquisizione/rilascio delle risorse.
• Monitoraggio: VisualVM, Java Mission Control — osservate quali thread sono attivi e cosa fanno.
• Thread dump: verificate che i thread non siano bloccati in attesa del lock.

Come evitarli?

Per il livelock:

• Non fate concessioni troppo “cortesi” — aggiungete un piccolo ritardo casuale prima di riprovare (Thread.sleep).
• Introducete casualità nell’ordine dei retry, per evitare comportamenti sincroni dei thread.
• Usate strutture/algoritmi non bloccanti (variabili atomiche, approccio CAS).

Per la starvation:

• Usate lock “equi”. Ad esempio, ReentrantLock con fairness:

java.util.concurrent.locks.ReentrantLock lock = new java.util.concurrent.locks.ReentrantLock(true); // modalità equa

• Non abusate delle priorità dei thread — spesso lasciate la priorità predefinita.
• Minimizzate il tempo dentro le sezioni critiche (synchronized/Lock).
• Usate code di lavoro in cui il servizio sia vicino a FIFO.

Tabella: Deadlock, Livelock, Starvation — confronto

Analoghi e fatti interessanti

• Livelock — come due persone che contemporaneamente fanno un passo a sinistra per evitarsi e si scontrano di nuovo.
• Starvation — come una fila al supermercato in cui il cassiere serve solo “i suoi”, e gli altri aspettano per sempre.

Curiosità: il livelock si incontra più raramente del deadlock, ma è più difficile da individuare — l’applicazione “non è bloccata”, eppure fa qualcosa!

6. Errori tipici nella gestione di livelock e starvation

Errore n. 1: “Concessioni cortesi” senza ritardo. Se i thread cedono il passo troppo spesso senza pausa, possono finire in livelock. Aggiungete un piccolo ritardo casuale prima di ritentare l’acquisizione della risorsa (Thread.sleep).

Errore n. 2: Affidarsi solo a synchronized, senza lock equi. Con molti thread, un normale synchronized non garantisce che “il più affamato” ottenga l’accesso. Usate ReentrantLock con fairness, se è critico.

Errore n. 3: Abuso delle priorità dei thread. Cercare di “accelerare” i thread importanti tramite setPriority spesso porta alla starvation degli altri. Non toccate le priorità senza reale necessità.

Errore n. 4: Mancanza di monitoraggio e logging. Livelock e starvation sono difficili da notare senza log: l’applicazione “gira”, ma non c’è risultato. Loggate gli eventi chiave e usate profiler/dump dei thread.

Errore n. 5: Sezioni critiche troppo lunghe. Se un thread detiene il lock troppo a lungo, gli altri aspetteranno (o “soffriranno la fame”). Minimizzate il tempo dentro i blocchi synchronized/Lock.