Livelock et Starvation : définition, exemples

1. Introduction à Livelock

Si un deadlock est le cas où les threads se bloquent et s’attendent mutuellement indéfiniment, un livelock (blocage vivant) est le cas où les threads sont vivants, font constamment quelque chose, se cèdent la place, mais… personne n’avance ! Imaginez deux personnes polies dans un couloir étroit : « Oh, passez, je vous en prie ! » — « Non, vous ! » — « Non, vous ! » — et ainsi de suite à l’infini.

Définition formelle

Livelock : situation où les threads ne sont pas bloqués, mais en raison de changements constants de leur état en réponse aux actions des autres threads, ils ne peuvent pas terminer leur travail. Ils sont « vivants », réagissent activement, mais n’accomplissent pas de travail utile.

À quoi cela ressemble-t-il en pratique ?

• Les threads ne se bloquent pas pour toujours, mais restent coincés dans une boucle infinie de concessions.
• Le système ne gèle pas, mais il ne fait pas non plus ce qu’il doit faire.

Exemple de la vie réelle

• Deux robots qui doivent se croiser dans un passage étroit, et tous deux font à chaque fois simultanément un pas du même côté — et se gênent à nouveau.
• Deux threads qui constatent chaque fois que la ressource est occupée et se cèdent mutuellement… à l’infini.

2. Exemple de livelock en Java

Modélisons un livelock dans le code. Pour simplifier, prenons deux « travailleurs » qui ont besoin d’une seule cuillère. Contrairement au deadlock, si la cuillère est occupée, ils cèdent poliment et réessaient — mais ensemble, de façon synchrone.

Exemple de code : « Travailleurs polis »

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() {
            // Utilisation de la cuillère (ne fait rien)
        }
    }

    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) {
                // Si la cuillère n'est pas à moi — j'attends
                if (spoon.getOwner() != this) {
                    try {
                        Thread.sleep(1); // On attend que la cuillère se libère
                    } catch (InterruptedException ignored) {}
                    continue;
                }
                // Si l'autre a faim — je cède la cuillère
                if (other.isHungry()) {
                    System.out.println(name + ": Je cède la cuillère à " + other.getName());
                    spoon.setOwner(other);
                    continue;
                }
                // Je mange !
                System.out.println(name + ": Je mange !");
                spoon.use();
                isHungry = false;
                System.out.println(name + ": Je suis rassasié !");
                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();
    }
}

Que se passe-t-il ?

• Alice et Bob ont tous deux faim, la cuillère est d’abord chez Alice.
• Alice voit que Bob a aussi faim et lui cède la cuillère.
• La cuillère est maintenant chez Bob, mais il voit qu’Alice a faim et la lui cède.
• La cuillère « circule » entre les travailleurs, et personne ne mange — aucun progrès.

À quoi ressemble la sortie ?

Alice: Je cède la cuillère à Bob
Bob: Je cède la cuillère à Alice
Alice: Je cède la cuillère à Bob
Bob: Je cède la cuillère à Alice
...

Comment éliminer un livelock ?

On peut éliminer un livelock en atténuant un peu la « politesse » des threads. Ajouter une pause aléatoire avant une nouvelle tentative (par exemple via Thread.sleep) aide à éviter des réactions synchrones. Une stratégie plus « tenace » fonctionne aussi : si vous avez déjà cédé, attendez plus longtemps avant de réessayer. Et n’abusez pas de la galanterie dans les algorithmes — des concessions excessives mènent également à des blocages.

3. Starvation (affamement de thread)

Si le livelock est une « politesse éternelle », la starvation (affamement) est le cas où un ou plusieurs threads n’obtiennent jamais l’accès à une ressource ou au processeur, parce que d’autres les devancent en permanence.

Définition formelle

Starvation : situation où un thread ne peut pas obtenir l’accès à la ressource nécessaire (CPU, mémoire, verrou), parce que d’autres threads le devancent constamment. En conséquence, le thread « affamé » s’exécute très rarement, voire pas du tout.

Causes de la starvation

• Verrous non équitables. Par exemple, un bloc synchronized classique ne garantit pas que le thread qui a attendu le plus entrera en premier.
• Priorités des threads. Si des threads à haute priorité monopolisent le processeur, ceux à faible priorité peuvent « mourir de faim » (setPriority).
• Boucles infinies dans d’autres threads. Si quelqu’un ne cède pas le CPU (ne fait pas appel à Thread.sleep ou Thread.yield()), d’autres threads peuvent ne pas obtenir de temps processeur.

4. Exemple de starvation en Java

Exemple : un thread à faible priorité ne s’exécute pas

public class StarvationDemo {
    public static void main(String[] args) {
        Runnable highPriorityTask = () -> {
            while (true) {
                // Travail intensif, ne cède pas le CPU
            }
        };

        Runnable lowPriorityTask = () -> {
            while (true) {
                System.out.println("Je suis un thread de faible 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();
    }
}

Comment cela se manifeste-t-il ?

• Les threads à haute priorité sont occupés tout le temps, ne cèdent pas le CPU.
• Le thread à faible priorité s’exécute très peu (voire pas du tout).
• Sur les JVM/OS modernes, les priorités peuvent être lissées par l’ordonnanceur, mais sur certains systèmes l’affamement est notable.

Autre exemple : starvation due à un verrou non équitable

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

    public static void main(String[] args) {
        // 5 threads qui s'emparent du lock en permanence
        for (int i = 0; i < 5; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (lock) {
                        // On garde le lock longtemps
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException ignored) {}
                    }
                }
            }).start();
        }

        // Un thread affamé
        new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    System.out.println("Le thread affamé a obtenu le lock !");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException ignored) {}
                }
            }
        }).start();
    }
}

Dans cet exemple, le thread « affamé » peut attendre très longtemps avant d’obtenir l’accès au lock, si d’autres threads l’occupent en permanence.

5. Comment détecter et prévenir livelock et starvation

Comment détecter ?

• Livelock : le programme fonctionne, les threads ne se bloquent pas, mais il n’y a pas de progrès (pas de résultat, pas de sortie des boucles).
• Starvation : certains threads s’exécutent très peu (messages rares dans les logs ou absence de messages).

Outils

• Journalisation : marquez le début/la fin du travail, la prise/libération des ressources.
• Monitoring : VisualVM, Java Mission Control — vérifiez quels threads sont actifs et à quoi ils passent leur temps.
• Thread dump : vérifiez si des threads ne sont pas bloqués en attente d’un lock.

Comment éviter ?

Pour le livelock :

• N’exagérez pas les concessions « polies » — ajoutez un léger délai aléatoire avant une nouvelle tentative (Thread.sleep).
• Introduisez de l’aléatoire dans l’ordre des nouvelles tentatives pour éviter le comportement synchrone des threads.
• Utilisez des structures/algorithmes non bloquants (variables atomiques, approche CAS).

Pour la starvation :

• Utilisez des verrous « équitables ». Par exemple, ReentrantLock avec fairness :

java.util.concurrent.locks.ReentrantLock lock = new java.util.concurrent.locks.ReentrantLock(true); // mode équitable

• N’abusez pas des priorités de threads — laissez plus souvent la priorité par défaut.
• Minimisez le temps passé dans les sections critiques (synchronized/Lock).
• Utilisez des files de tâches dont le service est proche de FIFO.

Tableau : Deadlock, Livelock, Starvation — comparaison

Analogies et faits intéressants

• Livelock : comme deux personnes qui font simultanément un pas à gauche pour se croiser, et se percutent à nouveau.
• Starvation : comme une file d’attente au magasin où le caissier ne sert que « les siens », et les autres attendent indéfiniment.

Fait intéressant : le livelock est plus rare que le deadlock, mais plus difficile à détecter — le programme « ne gèle pas », il fait quelque chose !

6. Erreurs courantes avec le livelock et la starvation

Erreur n° 1 : concessions « polies » sans délai. Si les threads se cèdent trop souvent sans pause, ils peuvent tomber dans un livelock. Ajoutez un léger délai aléatoire avant une nouvelle tentative de prise de ressource (Thread.sleep).

Erreur n° 2 : se reposer uniquement sur synchronized, sans verrous équitables. Avec un grand nombre de threads, un synchronized classique ne garantit pas que « le plus affamé » obtiendra l’accès. Utilisez ReentrantLock avec fairness si c’est crucial.

Erreur n° 3 : abus des priorités de threads. Tenter « d’accélérer » des threads importants via setPriority conduit souvent à la starvation des autres. Ne touchez pas aux priorités sans réelle nécessité.

Erreur n° 4 : absence de monitoring et de journalisation. Livelock et starvation sont difficiles à remarquer sans logs : le programme « fonctionne », mais il n’y a pas de résultat. Journalisez les événements clés et utilisez des profileurs/dumps de threads.

Erreur n° 5 : sections critiques trop longues. Si un thread garde un lock trop longtemps, les autres attendront (ou « mourront de faim »). Réduisez au minimum le temps passé dans les blocs synchronized/Lock.