Livelock und Starvation: Definitionen, Beispiele

1. Einführung in Livelock

Wenn deadlock bedeutet, dass Threads stehen bleiben und sich gegenseitig ewig warten lassen, dann ist livelock (lebendige Blockierung) der Fall, wenn Threads zwar „leben“, ständig etwas tun, einander ausweichen, aber … niemand macht Fortschritte! Stellen Sie sich zwei höfliche Menschen in einem engen Flur vor: „Oh, bitte, gehen Sie vor!“ – „Nein, Sie!“ – „Nein, Sie!“ – und so weiter bis ins Unendliche.

Formale Definition

Livelock ist eine Situation, in der Threads nicht blockiert sind, aber aufgrund ständiger Zustandsänderungen als Reaktion auf die Aktionen anderer Threads ihre Arbeit nicht beenden können. Sie sind „lebendig“, reagieren aktiv, verrichten jedoch keine nützliche Arbeit.

Wie sieht das in der Praxis aus?

• Threads werden nicht für immer blockiert, stecken aber in einer Endlosschleife des Ausweichens fest.
• Das System hängt nicht, erledigt aber auch nicht das, was es soll.

Beispiel aus dem Alltag

• Zwei Roboter, die sich in einem engen Gang ausweichen sollen, und beide machen jedes Mal gleichzeitig einen Schritt zur Seite – und behindern sich wieder.
• Zwei Threads, die jedes Mal feststellen, dass eine Ressource belegt ist, und einander den Vortritt lassen … endlos.

2. Livelock‑Beispiel in Java

Lassen Sie uns livelock im Code modellieren. Der Einfachheit halber nehmen wir zwei „Arbeiter“, die einen einzigen Löffel brauchen. Im Unterschied zu deadlock geben sie, wenn der Löffel belegt ist, höflich nach und versuchen es erneut – jedoch gemeinsam, synchron.

Codebeispiel: „Höfliche Arbeiter“

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() {
            // Löffel verwenden (macht nichts)
        }
    }

    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) {
                // Wenn der Löffel nicht bei mir ist – warte ich
                if (spoon.getOwner() != this) {
                    try {
                        Thread.sleep(1); // Wir warten, bis der Löffel frei wird
                    } catch (InterruptedException ignored) {}
                    continue;
                }
                // Wenn der andere hungrig ist – gebe ich den Löffel ab
                if (other.isHungry()) {
                    System.out.println(name + ": Ich überlasse den Löffel " + other.getName());
                    spoon.setOwner(other);
                    continue;
                }
                // Ich esse!
                System.out.println(name + ": Ich esse!");
                spoon.use();
                isHungry = false;
                System.out.println(name + ": Ich bin satt!");
                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();
    }
}

Was passiert hier?

• Alice und Bob sind beide hungrig, der Löffel ist zunächst bei Alice.
• Alice sieht, dass Bob ebenfalls hungrig ist, und überlässt ihm den Löffel.
• Nun hat Bob den Löffel, sieht aber, dass Alice hungrig ist, und gibt ihn ihr.
• Der Löffel „wandert“ zwischen den Arbeitern hin und her, aber niemand isst – kein Fortschritt.

Wie sieht die Ausgabe aus?

Alice: Ich überlasse den Löffel Bob
Bob: Ich überlasse den Löffel Alice
Alice: Ich überlasse den Löffel Bob
Bob: Ich überlasse den Löffel Alice
...

Wie wird man Livelock los?

Man kann livelock vermeiden, indem man die „Höflichkeit“ der Threads etwas auflockert. Es hilft, vor einem erneuten Versuch eine zufällige Pause einzubauen (z. B. über Thread.sleep) – so reagieren die Threads nicht mehr synchron. Ebenfalls wirksam ist eine „hartnäckigere“ Strategie: Wer bereits nachgegeben hat, wartet vor dem nächsten Versuch länger. Und übertreiben Sie es nicht mit Gentlemen-Gebaren in Algorithmen – übermäßiges Nachgeben führt ebenfalls zu Stillständen.

3. Starvation (Verhungern des Threads)

Wenn livelock „ewige Höflichkeit“ ist, dann ist starvation (Verhungern) der Fall, wenn ein oder mehrere Threads überhaupt keinen Zugriff auf eine Ressource oder die CPU bekommen, weil andere sie ständig überholen.

Formale Definition

Starvation ist eine Situation, in der ein Thread keinen Zugriff auf die benötigte Ressource (CPU, Speicher, Sperre) erhält, weil andere Threads ihn fortlaufend überholen. Infolgedessen wird der „verhungernde“ Thread entweder extrem selten oder gar nicht ausgeführt.

Ursachen für Starvation

• Unfaire Sperren. Zum Beispiel garantiert ein gewöhnlicher synchronized-Block nicht, dass der Thread, der am längsten wartet, zuerst hinein darf.
• Thread-Prioritäten. Wenn Threads mit hoher Priorität die CPU ständig besetzen, können Threads mit niedriger Priorität „verhungern“ (setPriority).
• Endlosschleifen in anderen Threads. Wenn jemand die CPU nicht freigibt (kein Thread.sleep oder Thread.yield() aufruft), bekommen andere Threads womöglich keine Laufzeit.

4. Starvation‑Beispiel in Java

Beispiel: Thread mit niedriger Priorität wird nicht ausgeführt

public class StarvationDemo {
    public static void main(String[] args) {
        Runnable highPriorityTask = () -> {
            while (true) {
                // Intensive Arbeit, gibt die CPU nicht frei
            }
        };

        Runnable lowPriorityTask = () -> {
            while (true) {
                System.out.println("Ich bin ein Thread mit niedriger Priorität!");
                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();
    }
}

Wie zeigt sich das?

• Threads mit hoher Priorität sind die ganze Zeit beschäftigt und geben die CPU nicht frei.
• Der Thread mit niedriger Priorität wird kaum (oder gar nicht) ausgeführt.
• Auf modernen JVMs/OS können Prioritäten durch den Scheduler geglättet werden, aber auf manchen Systemen ist Starvation deutlich spürbar.

Noch ein Beispiel: Starvation durch eine unfaire Sperre

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

    public static void main(String[] args) {
        // 5 Threads, die das lock ständig belegen
        for (int i = 0; i < 5; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (lock) {
                        // Halten das lock lange
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException ignored) {}
                    }
                }
            }).start();
        }

        // Ein hungernder Thread
        new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    System.out.println("Der hungernde Thread hat das lock erhalten!");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException ignored) {}
                }
            }
        }).start();
    }
}

In diesem Beispiel kann der „verhungernde“ Thread sehr lange keinen Zugriff auf das lock bekommen, wenn die anderen Threads es ständig belegen.

5. Livelock und Starvation erkennen und verhindern

Wie erkennt man sie?

• Livelock: Das Programm läuft, Threads hängen nicht, aber es gibt keinen Fortschritt (kein Ergebnis, kein Verlassen von Schleifen).
• Starvation: Einige Threads werden kaum ausgeführt (seltene Meldungen in den Logs oder gar keine).

Werkzeuge

• Logging: Markieren Sie Beginn/Ende von Arbeiten sowie Erwerb/Freigabe von Ressourcen.
• Monitoring: VisualVM, Java Mission Control – schauen Sie, welche Threads aktiv sind und womit.
• Thread dump: Prüfen Sie, ob Threads nicht beim Warten auf ein lock festhängen.

Wie vermeidet man das?

Für Livelock:

• Machen Sie nicht zu „höfliche“ Zugeständnisse – fügen Sie vor einem erneuten Versuch eine kleine zufällige Verzögerung ein (Thread.sleep).
• Führen Sie Zufall in die Reihenfolge der erneuten Versuche ein, um synchrones Verhalten der Threads zu vermeiden.
• Verwenden Sie nicht blockierende Strukturen/Algorithmen (atomare Variablen, CAS-Ansatz).

Für Starvation:

• Verwenden Sie „faire“ Sperren. Zum Beispiel ReentrantLock mit fairness:

java.util.concurrent.locks.ReentrantLock lock = new java.util.concurrent.locks.ReentrantLock(true); // fairer Modus

• Missbrauchen Sie Thread-Prioritäten nicht – lassen Sie häufiger die Standardpriorität bestehen.
• Minimieren Sie die Zeit innerhalb kritischer Abschnitte (synchronized/Lock).
• Verwenden Sie Aufgabenwarteschlangen, deren Bedienung nahe an FIFO liegt.

Tabelle: Deadlock, Livelock, Starvation – Vergleich

Analogien und interessante Fakten

• Livelock – wie zwei Personen, die gleichzeitig einen Schritt nach links machen, um aneinander vorbeizukommen, und wieder zusammenstoßen.
• Starvation – wie eine Schlange im Laden, in der die Kassiererin nur „ihre Leute“ bedient und der Rest ewig wartet.

Interessante Tatsache: livelock tritt seltener auf als deadlock, ist aber schwerer zu entdecken – das Programm „hängt“ nicht, sondern tut etwas!

6. Typische Fehler beim Umgang mit Livelock und Starvation

Fehler Nr. 1: „Höfliche Zugeständnisse“ ohne Verzögerung. Wenn Threads sich zu oft ohne Pause gegenseitig den Vortritt lassen, können sie in einen livelock geraten. Fügen Sie vor dem erneuten Versuch, eine Ressource zu übernehmen, eine kleine zufällige Verzögerung ein (Thread.sleep).

Fehler Nr. 2: Warten nur mit synchronized, ohne faire Sperren. Bei vielen Threads garantiert ein gewöhnliches synchronized nicht, dass der „stärkste Hungernde“ Zugriff erhält. Verwenden Sie bei Bedarf ReentrantLock mit fairness.

Fehler Nr. 3: Missbrauch von Thread-Prioritäten. Der Versuch, wichtige Threads über setPriority „zu beschleunigen“, führt oft zu starvation anderer. Ändern Sie Prioritäten nur bei echter Notwendigkeit.

Fehler Nr. 4: Fehlendes Monitoring und Logging. Livelock und starvation sind ohne Logs schwer zu bemerken: Das Programm „läuft“, aber es gibt kein Ergebnis. Protokollieren Sie Schlüsselereignisse und nutzen Sie Profiler/Thread-Dumps.

Fehler Nr. 5: Zu lange kritische Abschnitte. Wenn ein Thread ein lock lange hält, warten die anderen (oder „verhungern“). Minimieren Sie die Zeit innerhalb von synchronized/Lock-Blöcken.