Livelock i Starvation: definicje, przykłady

1. Wprowadzenie do Livelock

Jeśli deadlock — to sytuacja, gdy wątki stoją i czekają na siebie w nieskończoność, to livelock (ożywiona blokada) — to sytuacja, gdy wątki niby żyją, stale coś robią, ustępują sobie, ale... nikt nie posuwa się naprzód! Wyobraź sobie dwoje uprzejmych ludzi w wąskim korytarzu: „Proszę, przejdź!” — „Nie, proszę!” — „Nie, proszę!” — i tak w nieskończoność.

Formalna definicja

Livelock — sytuacja, w której wątki nie są zablokowane, ale z powodu ciągłych zmian swojego stanu w reakcji na działania innych wątków nie mogą zakończyć pracy. Są „żywe”, aktywnie reagują, ale nie wykonują pożytecznej pracy.

Jak to wygląda w praktyce?

• Wątki nie blokują się na zawsze, ale utknęły w nieskończonej pętli ustępstw.
• System nie wisi, ale też nie robi tego, co powinien.

Przykład z życia

• Dwa roboty, które powinny się minąć w wąskim przejściu, i za każdym razem równocześnie robią krok w stronę siebie — i znów sobie przeszkadzają.
• Dwa wątki, które za każdym razem wykrywają, że zasób jest zajęty, i ustępują sobie... w nieskończoność.

2. Przykład livelock w Javie

Zasymulujmy livelock w kodzie. Dla prostoty weźmiemy dwóch „pracowników”, którym potrzebna jest jedna łyżka. W odróżnieniu od deadlock, jeśli łyżka jest zajęta, uprzejmie ustępują i próbują ponownie — ale równocześnie, synchronicznie.

Przykład kodu: „Uprzejmi pracownicy”

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() {
            // Użycie łyżki (nic nie robi)
        }
    }

    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) {
                // Jeśli łyżka nie jest u mnie — czekam
                if (spoon.getOwner() != this) {
                    try {
                        Thread.sleep(1); // Czekamy, aż łyżka się zwolni
                    } catch (InterruptedException ignored) {}
                    continue;
                }
                // Jeśli drugi jest głodny — ustępuję łyżkę
                if (other.isHungry()) {
                    System.out.println(name + ": Ustępuję łyżkę " + other.getName());
                    spoon.setOwner(other);
                    continue;
                }
                // Jem!
                System.out.println(name + ": Jem!");
                spoon.use();
                isHungry = false;
                System.out.println(name + ": Najadłem się!");
                spoon.setOwner(other);
            }
        }
    }

    public static void main(String[] args) {
        final Worker alice = new Worker("Alicja");
        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();
    }
}

Co się dzieje?

• Alicja i Bob są głodni, łyżka początkowo jest u Alicji.
• Alicja widzi, że Bob też jest głodny, i ustępuje łyżkę.
• Teraz łyżka jest u Boba, ale on widzi, że Alicja jest głodna, i ustępuje jej.
• Łyżka „biega” między pracownikami, a nikt nie je — brak postępu.

Jak wygląda wypis na konsoli?

Alicja: Ustępuję łyżkę Bob
Bob: Ustępuję łyżkę Alicja
Alicja: Ustępuję łyżkę Bob
Bob: Ustępuję łyżkę Alicja
...

Jak pozbyć się livelock?

Można się pozbyć livelock, jeśli trochę „rozrzedzimy” uprzejmość wątków. Pomaga dodanie losowej pauzy przed ponowną próbą (na przykład przez Thread.sleep) — wtedy wątki przestaną reagować synchronicznie. Działa też bardziej „stanowcza” strategia: jeśli już ustąpiłeś, odczekaj dłużej przed kolejną próbą. I nie przesadzajcie z uprzejmością w algorytmach — nadmierne ustępstwa także prowadzą do zacięć.

3. Starvation (głodzenie wątku)

Jeśli livelock to „wieczna uprzejmość”, to starvation (głodzenie) — to sytuacja, gdy jeden lub kilka wątków w ogóle nie dostaje dostępu do zasobu lub procesora, ponieważ inne cały czas je wyprzedzają.

Formalna definicja

Starvation — sytuacja, w której wątek nie może uzyskać dostępu do potrzebnego zasobu (CPU, pamięci, blokady), ponieważ inne wątki stale go wyprzedzają. W rezultacie „głodujący” wątek wykonuje się bardzo rzadko albo wcale.

Przyczyny starvation

• Niesprawiedliwe blokady. Na przykład zwykły blok synchronized nie gwarantuje, że wątek, który czeka najdłużej, wejdzie pierwszy.
• Priorytety wątków. Jeśli wątki o wysokim priorytecie ciągle zajmują procesor, niskopriorytetowe mogą „głodować” (setPriority).
• Nieskończone pętle w innych wątkach. Jeśli ktoś nie ustępuje CPU (nie wywołuje Thread.sleep ani Thread.yield()), inne wątki mogą nie dostać czasu wykonania.

4. Przykład starvation w Javie

Przykład: wątek o niskim priorytecie się nie wykonuje

public class StarvationDemo {
    public static void main(String[] args) {
        Runnable highPriorityTask = () -> {
            while (true) {
                // Intensywna praca, nie ustępuje CPU
            }
        };

        Runnable lowPriorityTask = () -> {
            while (true) {
                System.out.println("Jestem wątkiem niskiego priorytetu!");
                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();
    }
}

Jak się to objawia?

• Wątki o wysokim priorytecie cały czas są zajęte pracą, nie ustępują CPU.
• Wątek o niskim priorytecie prawie się nie wykonuje (albo nie wykonuje się wcale).
• We współczesnych JVM/OS priorytety mogą być „wygładzane” przez scheduler, ale na niektórych systemach głodzenie jest zauważalne.

Jeszcze jeden przykład: starvation z powodu niesprawiedliwej blokady

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

    public static void main(String[] args) {
        // 5 wątków, które cały czas przechwytują lock
        for (int i = 0; i < 5; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (lock) {
                        // Zajmujemy lock na długo
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException ignored) {}
                    }
                }
            }).start();
        }

        // Jeden „głodujący” wątek
        new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    System.out.println("Głodujący wątek zdobył lock!");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException ignored) {}
                }
            }
        }).start();
    }
}

W tym przykładzie „głodujący” wątek może bardzo długo nie uzyskać dostępu do lock, jeśli inne wątki stale go zajmują.

5. Jak wykrywać i zapobiegać livelock oraz starvation

Jak wykryć?

• Livelock: program działa, wątki nie wiszą, ale nie ma postępu (brak wyniku, brak wyjścia z pętli).
• Starvation: niektóre wątki prawie się nie wykonują (rzadkie komunikaty w logach albo ich brak).

Narzędzia

• Logowanie: oznaczajcie początek/koniec pracy, przejęcie/zwolnienie zasobów.
• Monitoring: VisualVM, Java Mission Control — sprawdzajcie, które wątki są aktywne i czym się zajmują.
• Thread dump: sprawdźcie, czy wątki nie utknęły w oczekiwaniu na lock.

Jak unikać?

Dla livelock:

• Nie róbcie zbyt „uprzejmych” ustępstw — dodawajcie niewielkie losowe opóźnienie przed ponowną próbą (Thread.sleep).
• Wprowadźcie losowość do kolejności ponownych prób, aby uniknąć synchronicznych reakcji wątków.
• Używajcie struktur/algorytmów nieblokujących (zmienne atomowe, podejście CAS).

Dla starvation:

• Używajcie „sprawiedliwych” blokad. Na przykład ReentrantLock z fairness:

java.util.concurrent.locks.ReentrantLock lock = new java.util.concurrent.locks.ReentrantLock(true); // tryb sprawiedliwy

• Nie nadużywajcie priorytetów wątków — częściej zostawiajcie priorytet domyślny.
• Minimalizujcie czas wewnątrz sekcji krytycznych (synchronized/Lock).
• Używajcie kolejek zadań, gdzie obsługa jest zbliżona do FIFO.

Tabela: Deadlock, Livelock, Starvation — porównanie

Analogii i ciekawostki

• Livelock — jak dwoje ludzi, którzy jednocześnie robią krok w lewo, żeby się minąć, i znowu na siebie wpadają.
• Starvation — jak kolejka w sklepie, gdzie kasjer obsługuje tylko „swoich”, a pozostali stoją wiecznie.

Ciekawostka: livelock występuje rzadziej niż deadlock, ale trudniej go wykryć — program się „nie wiesza”, tylko coś robi!

6. Typowe błędy przy pracy z livelock i starvation

Błąd nr 1: „Uprzejme ustępstwa” bez opóźnienia. Jeśli wątki zbyt często ustępują sobie bez pauzy, mogą wpaść w livelock. Dodawajcie niewielkie losowe opóźnienie przed ponowną próbą przejęcia zasobu (Thread.sleep).

Błąd nr 2: Poleganie wyłącznie na synchronized, bez sprawiedliwych blokad. Przy dużej liczbie wątków zwykły synchronized nie gwarantuje, że „najbardziej głodujący” dostanie dostęp. Używajcie ReentrantLock z fairness, jeśli to krytyczne.

Błąd nr 3: Nadużywanie priorytetów wątków. Próba „przyspieszania” ważnych wątków przez setPriority często prowadzi do starvation innych. Nie zmieniajcie priorytetów bez realnej potrzeby.

Błąd nr 4: Brak monitoringu i logowania. Livelock i starvation trudno zauważyć bez logów: program „działa”, ale nie ma rezultatu. Logujcie kluczowe zdarzenia i używajcie profilerów/dumpów wątków.

Błąd nr 5: Zbyt długie sekcje krytyczne. Jeśli wątek długo trzyma lock, pozostałe będą czekać (albo „głodować”). Minimalizujcie czas wewnątrz bloków synchronized/Lock.