Inne problemy: Livelock i Starvation

1. Wprowadzenie

Livelock — to sytuacja w aplikacji wielowątkowej, kiedy dwa lub więcej wątków próbują uniknąć wzajemnego zablokowania (Deadlock), ale w efekcie tylko bez końca reagują na działania siebie nawzajem, nie posuwając się do przodu. W przeciwieństwie do Deadlock, gdzie wątki zatrzymały się i nic nie mogą zrobić, przy Livelock program wygląda na żywy: wątki wykonują się, ale żaden nie wykonuje użytecznej pracy.

To jakbyś ty i kolega w wąskim korytarzu ciągle robili krok w tył, żeby przepuścić drugą osobę, i przez to nigdy nie przechodziliście dalej. Śmieszne z zewnątrz, ale fatalne w programie.

Przykład Livelock: programiści w drzwiach

Wyobraźcie sobie dwóch bardzo uprzejmych programistów, którzy idą naprzeciw siebie w wąskim korytarzu. Oboje jednocześnie stają przed drzwiami i obaj postanawiają ustąpić: robią krok w bok, żeby przepuścić drugiego. Oboje znów widzą, że sytuacja się nie zmieniła, i znowu próbują ustąpić — w nieskończoność. Nikt nie stoi, wszyscy się poruszają, ale nikt nie przechodzi przez drzwi.

W programie wielowątkowym wygląda to tak: wątek widzi zasób zajęty, cofa się, sprawdza jeszcze raz, znowu ustępuje, i tak bez końca.

2. Livelock w praktyce

Zaimplementujmy analogiczną sytuację w kodzie. Załóżmy, że mamy dwa zasoby (np. dwa konta bankowe), i dwa wątki jednocześnie próbują przelać pieniądze do siebie nawzajem, starając się nie „zablokować się”.

class Account
{
    public int Balance { get; set; }
    public object LockObj { get; } = new object();
}

public class Program
{
    static void Transfer(Account from, Account to, int amount)
    {
        while (true)
        {
            bool lockedFrom = false;
            bool lockedTo = false;
            try
            {
                Monitor.TryEnter(from.LockObj, 100, ref lockedFrom); 
                Monitor.TryEnter(to.LockObj, 100, ref lockedTo);

                if (lockedFrom && lockedTo)
                {
                    from.Balance -= amount;
                    to.Balance += amount;
                    break; // Perevod vipolnen!
                }
            }
            finally
            {
                if (lockedFrom) Monitor.Exit(from.LockObj);
                if (lockedTo) Monitor.Exit(to.LockObj);
            }
            // Ne poluchilos'? Odshto i poprobuyem snova — vezhlivo!
            Thread.Sleep(1);
        }
    }
    // ... Zapusk dvuh potokov s Transfer(A, B, ...); Transfer(B, A, ...);
}

W tym przykładzie oba wątki wielokrotnie próbują złapać zamki. Ale jeśli oba cały czas widzą, że zamki są zajęte i ustępują, to wszystko sprowadza się do „uprzejmego” ustępowania i żadnego przelewu pieniędzy nie ma. Poleganie na losowości planisty to zła strategia dla niezawodnego programu. Dodawaj pauzy i backoff, nie twórz krótkich „pustych” pętli wokół Monitor.TryEnter i Thread.Sleep.

Porównanie Livelock vs Deadlock

3. Starvation (głodzenie): kiedy do zasobu nie dociera kolejka

Starvation (dosłownie „głodzenie”) — to sytuacja, kiedy jeden lub kilka wątków ciągle są pomijane i nie dostają dostępu do potrzebnego zasobu, ponieważ inne wątki cały czas są przed nimi.

W przeciwieństwie do Deadlock i Livelock, tutaj nikt nie jest zablokowany na zawsze i nikt nie ustępuje w nieskończoność — po prostu niektórym wątkom ciągle nie przypada „kawałek ciasta”.

Ilustracja: analogia z realnego życia

Wyobraź sobie stołówkę z dwiema kolejkami: „VIP” (np. kasa dla pracowników roku) i „dla wszystkich pozostałych”. Kolejka VIP jest krótka, ale tam zawsze ktoś zdąży wcześniej. „Zwykli” klienci stoją pół godziny i patrzą, jak VIP znowu przechodzi przed nimi. To jest właśnie Starvation!

4. Starvation w C#: praktyka i debug

Rozważmy sytuację z lock, kiedy jeden wątek o wysokim priorytecie stale zdąża wejść do sekcji krytycznej, a inny „zostaje w tyle”:

private static readonly object _locker = new object();

static void Greedy()
{
    while (true)
    {
        lock (_locker)
        {
            Console.WriteLine("Zhadny potok zahvatil resurs...");
            Thread.Sleep(10); // dl'she derzhit zamok
        }
        Thread.Sleep(1);
    }
}

static void Poor()
{
    while (true)
    {
        lock (_locker)
        {
            Console.WriteLine("Bedny potok popytalsya voiti...");
        }
    }
}

Jeśli uruchomicie oba wątki, to "Greedy" („Zachłanny”) długo trzyma zamek i szybko znowu go zdobywa, a "Poor" („Biedny”) prawie nie dostaje się do środka i właściwie „głoduje” bez zasobu. W rzeczywistych zadaniach starvation może być mniej oczywiste: np. jeśli jeden wątek ma niższy priorytet lub częściej jest wypychany przez OS.

Gdzie występuje starvation?

• W wątkach o niskim priorytecie.
• Przy niepoprawnej organizacji kolejek zadań (brak uczciwej polityki FIFO).
• W ReaderWriterLockSlim z domyślnymi ustawieniami: jeśli writer przychodzi rzadko, a czytelnicy idą w nieskończonym strumieniu, to writer będzie ciągle „głodował”, bo czytelnicy zajmują Read Lock i nie pozwalają zdobyć Write Lock.

5. Dlaczego Starvation — nie zawsze bug, ale zawsze problem

Starvation, w przeciwieństwie do Deadlock, nie prowadzi do pełnego zatrzymania programu, ale wynik działania staje się nieprzewidywalny i niesprawiedliwy: dane są przetwarzane nierównomiernie, niektóre zadania czekają w nieskończoność, wydajność spada. To szczególnie krytyczne w aplikacjach serwerowych, gdzie wszyscy powinni mieć równe szanse.

Jak wykryć i zdiagnozować Livelock i Starvation

• Zdecydowany wzrost zużycia CPU, ale zadanie „stoi w miejscu” — możliwy Livelock.
• Wątki wydają się działać, ale niektóre zadania nigdy się nie kończą — możliwe Starvation.
• Logi: jeśli dziennik pokazuje, że określone wątki lub zadania nigdy nie dostają dostępu do zasobu — sto procent „głodowanie”.

Jak uniknąć Livelock

• Nie ograniczaj się do prób złapania zasobów tylko przez „ustępliwe” non-blocking metody typu Monitor.TryEnter. Jeśli się nie uda, dodawaj losowe pauzy (Thread.Sleep(Random.Next(1, 10)))), żeby wątki nie były zsynchronizowane czasowo.
• Nie używaj stałych krótkich pętli z łapaniem zasobu — inaczej pętla „cofnął się — spróbował” stanie się nieskończona.
• Czasem pomaga zmienić algorytm: wprowadzić „prawo starszeństwa”, żeby tylko jeden wątek mógł ustępować, a drugi — nie.

Jak uniknąć Starvation

• Kontroluj priorytety wątków: zadania tła lub o wysokim priorytecie nie powinny na zawsze blokować innych.
• Używaj kolejek (ConcurrentQueue<T>, kanały, task queue) z uczciwą polityką FIFO, żeby zadania były obsługiwane po kolei.
• W ReaderWriterLockSlim można wstrzymać nowych czytelników na korzyść writerów, żeby writer w końcu dostał Write Lock.
• Stosuj timeouty i logi: jeśli wątek próbuje zdobyć zamek zbyt długo, wypisz ostrzeżenie.
• Zmniejszaj czas trzymania blokad i rozdzielaj sekcje krytyczne.

Porównanie Deadlock, Livelock i Starvation