Deadlock, livelock i starvation: skad sie biora i jak nie wpasc w pulapke

1. Postep: kiedy „nie ma bledu”, ale wszystko jest zle

Jesli jestes przyzwyczajony do kodu jednowatkowego, masz prosty model swiata: jesli program sie zepsul — bedzie wyjatek. Jesli nie ma wyjatku — znaczy, ze dziala. Kod wspolbiezny brutalnie lamie te logike. Program moze nie crashowac, nie narzekac, nie wypisywac nic podejrzanego — a jednoczesnie nigdy nie skonczyc pracy, albo skonczyc, ale dziesiec razy wolniej, albo „utknac” w dziwnym stanie.

Zeby rozmawiac o tym konkretnie, potrzebujemy kryterium: postep. Postep to sytuacja, w ktorej system wykonuje uzyteczne kroki: obsluguje polecenia, przelewa pieniadze, aktualizuje licznik, konczy zadania. Jesli korutyny zyja, ale postepu nie ma (albo pojawia sie „od swieta”) — to symptom problemow z synchronizacja albo z projektem.

Warto miec w glowie trzy „anty-postepy”:

Dalej omowimy kazde z nich na malych przykladach w Kotlinie z korutynami i Mutex.

2. Deadlock: „ty pierwszy” — „nie, ty pierwszy”

Deadlock brzmi jak nazwa zespolu rockowego, ale to raczej gatunek tragikomedii. W deadlocku masz kilku uczestnikow (korutyny/watki), ktorzy przejeli zasoby (np. Mutex) i teraz czekaja na zasoby siebie nawzajem. Nikt nie oddaje tego, co juz trzyma, bo „jeszcze mi potrzeba”, a dostac „jeszcze” sie nie da, bo jest u kogos innego — i on tez czeka.

Klasyczny sposob na deadlock to przejmowanie kilku blokad w roznej kolejnosci w roznych miejscach programu. To nie „egzotyka”, tylko zwykla sytuacja z zycia: masz przelew miedzy dwoma kontami — trzeba zablokowac oba konta, zeby przelew byl atomowy.

Wyobrazmy sobie nasze praktyczne mini-aplikacje: „mini-bank” w konsoli, gdzie sa konta i przelewy. Kazde konto bedzie mialo swoj Mutex.

Szkielet: konto i dwa Mutex

Zrobmy prosty model. Istotne jest to, ze Account trzyma mutex obok salda — w ten sposob od razu pokazujemy idee „jeden stan — jeden zamek”.

import kotlinx.coroutines.sync.Mutex

data class Account(
    val id: Int,
    var balance: Int,
    val mutex: Mutex = Mutex()
)

Teraz stworzymy pare kont i funkcje, ktora przelewa pieniadze. Wazne: przelew to inwariant na poziomie dwoch obiektow („zabrales z jednego i dodales do drugiego”), wiec musimy miec pod kontrola obie strony.

Przyklad deadlock: dwa przelewy na przeciw siebie

Oto „zla” wersja przelewu: najpierw blokuje from, potem to. Na pierwszy rzut oka — logiczne.

import kotlinx.coroutines.sync.withLock

suspend fun transferDeadlock(from: Account, to: Account, amount: Int) {
    from.mutex.withLock {
        to.mutex.withLock {
            from.balance -= amount
            to.balance += amount
        }
    }
}

A teraz uruchamiamy dwa przelewy rownolegle: A -> B oraz B -> A.

import kotlinx.coroutines.Dispatchers
import kotlinx.coroutines.launch
import kotlinx.coroutines.runBlocking

fun main() = runBlocking {
    val a = Account(id = 1, balance = 100)
    val b = Account(id = 2, balance = 100)

    val j1 = launch(Dispatchers.Default) { transferDeadlock(a, b, 10) }
    val j2 = launch(Dispatchers.Default) { transferDeadlock(b, a, 20) }

    j1.join()
    j2.join()
    println("a=${a.balance}, b=${b.balance}") // czasem nie wydrukuje sie w ogole
}

Dlaczego „czasem”? Bo deadlock to czesto wyscig po harmonogramie: jesli j1 zdazyl zablokowac a, a j2 zdazyl zablokowac b, to dalej:

• j1 czeka na b.mutex
• j2 czeka na a.mutex

I tyle. Nie ma postepu.

Moze to wygladac tak:

flowchart LR
    J1["j1 trzyma lock(A)"] -->|"chce lock(B)"| B["lock(B) zajety"]
    J2["j2 trzyma lock(B)"] -->|"chce lock(A)"| A["lock(A) zajety"]
    B -->|"trzyma j2"| J2
    A -->|"trzyma j1"| J1

Kluczowa mysl: deadlock to nie blad wykonania, tylko blad projektu kolejnosci przejmowania blokad. I w tym sensie jest bardziej podstepny niz wyjatki: nie ma stack trace’a, jest po prostu „cisza”.

Profilaktyka: jednolity porzadek przejmowania

Najprostsza i najmocniejsza zasada przeciw deadlockom z wieloma zamkami: wszędzie w kodzie przejmowac zamki w tej samej kolejnosci.

Na przyklad: zawsze najpierw blokujemy konto z mniejszym id, potem — z wiekszym. Wtedy w systemie po prostu nie moze pojawic sie cykl oczekiwania „A czeka na B, B czeka na A”, bo wszyscy ida w jednym kierunku.

import kotlinx.coroutines.sync.withLock

suspend fun transferOrdered(a1: Account, a2: Account, amount: Int) {
    val first = if (a1.id <= a2.id) a1 else a2
    val second = if (a1.id <= a2.id) a2 else a1

    first.mutex.withLock {
        second.mutex.withLock {
            a1.balance -= amount
            a2.balance += amount
        }
    }
}

I uruchomienie:

import kotlinx.coroutines.Dispatchers
import kotlinx.coroutines.launch
import kotlinx.coroutines.runBlocking

fun main() = runBlocking {
    val a = Account(1, 100)
    val b = Account(2, 100)

    val j1 = launch(Dispatchers.Default) { transferOrdered(a, b, 10) }
    val j2 = launch(Dispatchers.Default) { transferOrdered(b, a, 20) }

    j1.join(); j2.join()
    println("a=${a.balance}, b=${b.balance}") // a=110, b=90 (albo odwrotnie co do sumy)
}

Zauwaz: nie robilismy delay() „dla pewnosci”. Deadlock nie leczy sie „magicznym snem”; leczy sie scislymi zasadami.

3. Starvation: „wszyscy pracuja”, ale ktos prawie nigdy

Starvation (glodzenie) to sytuacja, gdy system jako calosc niby sie porusza, ale konkretne zadanie/korutyna stale nie dostaje dostepu do zasobu albo dostaje go tak rzadko, ze logika biznesowa „umiera powoli”. W zyciu wyglada to jak kolejka w kawiarni, w ktorej ktos stale sie wpycha, a ty juz trzecia godzine trzymasz w reku ten sam numerek.

W korutynach starvation czesto powstaje nie dlatego, ze ktos jest zly, tylko dlatego, ze:

• trzymamy Mutex zbyt dlugo,
• wykonujemy pod zamkiem dluga operacje,
• albo po prostu urzadzilismy „goraca petle” wokol zamka.

Wazne: Mutex chroni poprawnosc, ale nie gwarantuje sprawiedliwosci w sensie „kazdemu po rowno i na czas”. Dlatego projekt sekcji krytycznej to nie tylko poprawnosc, ale tez wydajnosc.

Zly przyklad: dlugi delay() pod Mutex

Wrocmy do naszego mini-banku. Zalozmy, ze jest operacja „nalicz bonus” (umownie), ktora z jakiegos powodu robi opoznienie (np. czeka na jakis zewnetrzny krok). Sam fakt opoznienia nie jest problemem. Problem jest wtedy, gdy opoznienie jest wewnatrz withLock.

import kotlinx.coroutines.delay
import kotlinx.coroutines.sync.withLock

suspend fun bonusBad(account: Account) {
    account.mutex.withLock {
        delay(200)           // trzymamy zamek, kiedy "czekamy"
        account.balance += 1
    }
}

Jesli rownolegle ida przelewy, zaczna „glodowac”: kazdy przelew bedzie czekal, az bonus „pospi”. Niby nikt nie umarl, ale program robi sie lepki, jak IDE na starym laptopie.

Dobry styl: krotka sekcja krytyczna

Czesto poprawna mysl jest taka: „Jesli czekam — to znaczy, ze nic nie zmieniam. To po co mam trzymac zamek?”

import kotlinx.coroutines.delay
import kotlinx.coroutines.sync.withLock

suspend fun bonusGood(account: Account) {
    delay(200) // czekamy na zewnatrz
    account.mutex.withLock {
        account.balance += 1
    }
}

Tak, nie zawsze jest to mozliwe: czasem „czekac” trzeba wlasnie pomiedzy odczytem a zapisem i wtedy inwariant jest trudniejszy. Ale w wiekszosci codziennych przypadkow — to bezposrednia poprawa.

Jak starvation wyglada „na oko”

Starvation jest nieprzyjemny, bo po logach moze sie wydawac: „wszystko dziala”. Po prostu niektore operacje zaczynaja „czasem bardzo dlugo myslec”. Zwykle diagnozuje sie to po objawach:

• jedne korutyny stabilnie koncza sie szybko,
• inne „wisia” nieproporcjonalnie dlugo,
• ogolny throughput spada.

I prawie zawsze przyczyna to zbyt szeroka sekcja krytyczna albo ciezka praca wewnatrz withLock.

4. Livelock: „uprzejme” korutyny bez rezultatu

Livelock jest podobny do deadlocka tym, ze nie ma postepu, ale rozni sie dramaturgia: w deadlocku wszystko zamarlo, a w livelocku wszystko aktywnie sie rusza, tylko bez sensu.

Czesta przyczyna livelocka to proba bycia „zbyt uprzejmym”: „jesli sie nie udalo — puszcze i sprobuje pozniej”, ale obie strony robia to synchronicznie i przeszkadzaja sobie bez konca.

Zeby pokazac livelock, przyda nam sie tryLock(): to proba przejecia Mutex bez czekania. Jesli zamek jest zajety — zwroci false. To znana juz idea z atomikow: „sprobowalem — nie wyszlo — wycofalem sie”, tylko na poziomie zamkow.

Naiwny „uprzejmy” przelew z tryLock()

Zrobmy przelew, ktory probuje przejac oba zamki. Jesli sie nie udalo — zwalnia to, co przejal, i powtarza.

import kotlinx.coroutines.delay

suspend fun transferLivelock(from: Account, to: Account, amount: Int) {
    while (true) {
        if (from.mutex.tryLock()) {
            try {
                if (to.mutex.tryLock()) {
                    try {
                        from.balance -= amount
                        to.balance += amount
                        return
                    } finally {
                        to.mutex.unlock()
                    }
                }
            } finally {
                from.mutex.unlock()
            }
        }
        delay(1) // "ustepujemy", zeby nie krecic CPU
    }
}

Kod wyglada rozsadnie, ale teraz wyobraz sobie dwie korutyny:

• pierwsza chce A -> B,
• druga chce B -> A.

Obie moga wpasowac sie w rytm:

1. przejely „swoj” pierwszy zamek
2. drugiego zamka nie dostaly
3. puszczaja i czekaja delay(1)
4. powtarzaja jednoczesnie

One nie stoja, one biegaja w kolko. Postep — zero.

Jak odroznic livelock od deadlocka

Deadlock czesto wyglada jak „cisza”: zawiesilo sie i tyle.

Livelock czesciej wyglada jak „cos sie dzieje”: CPU moze byc wyraznie obciazony, logi moga spamowac, ale stan sie nie zmienia.

Jesli dodasz debugowe println("try..."), moze wyjsc nieskonczony strumien linii. To, swoja droga, osobny bol: logowanie samo w sobie staje sie przyczyna spowolnien, i zaczynasz leczyc objawy, a nie przyczyne.

Profilaktyka livelocka: asymetria

Livelock sie lamie, gdy dodajemy asymetrie. Sposobow jest wiele, ale mysl jest jedna: obie strony nie powinny zachowywac sie identycznie.

Najprostszy i najbardziej praktyczny wariant na poziomie nauki — jednolity porzadek przejmowania (jak przy deadlocku). Wtedy nawet z tryLock() nie dostaniesz nieskonczonej „uprzejmej walki”: wszyscy probuja najpierw wziasc first, potem second.

Zrobmy wersje z porzadkowaniem po id i niewielkim losowym back-offem, zeby zerwac synchronicznosc powtorzen:

import kotlin.random.Random
import kotlinx.coroutines.delay

suspend fun transferTryOrdered(a1: Account, a2: Account, amount: Int) {
    val first = if (a1.id <= a2.id) a1 else a2
    val second = if (a1.id <= a2.id) a2 else a1

    while (true) {
        if (first.mutex.tryLock()) {
            try {
                if (second.mutex.tryLock()) {
                    try {
                        a1.balance -= amount
                        a2.balance += amount
                        return
                    } finally {
                        second.mutex.unlock()
                    }
                }
            } finally {
                first.mutex.unlock()
            }
        }
        delay(Random.nextLong(1, 5)) // zrywamy "defiladowy krok"
    }
}

Tak, to jest troche bardziej zlozone niz po prostu withLock. I to tez wazna moral: jesli zaczales „reczne sterowanie” przejmowaniem blokad, jestes w strefie podwyzszonej uwagi. Czasem prosciej wrocic do withLock i scislego porzadku.

Jak nie zaprojektowac pulapki: nawyki, ktore ratuja

Jesli sprowadzic profilaktyke deadlock/livelock/starvation do jednej idei, brzmialaby tak: zmniejszaj liczbe powodow, dla ktorych korutyny w ogole musza rywalizowac o zasoby.

W poprzednim wykladzie o confinement/actor widzielismy juz projekt, w ktorym stan zmienia jeden wlasciciel, a reszta wysyla wiadomosci. Taki projekt czesto „z definicji” zmniejsza ryzyko deadlocka i starvation, bo nie masz sytuacji „dwa zamki, dwoch wlascicieli, dwa porzadki”. Nawet jesli wewnatrz wlasciciela jest Mutex, to jest to lokalna historia, a nie pajeczyna wzajemnych oczekiwan.

Jesli jednak zostajesz przy Mutex, to najbardziej stabilny zestaw nawykow wyglada tak:

flowchart TD
    A["Potrzebna synchronizacja?"] --> B["Czy mozna usunac shared state przez confinement?"]
    B -->|tak| C["Actor: jeden wlasciciel stanu"]
    B -->|nie| D["Czy potrzebujesz kilku zamkow jednoczesnie?"]
    D -->|tak| E["Jednolity porzadek przejmowania i minimalna sekcja"]
    D -->|nie| F["Jeden Mutex i krotki withLock"]

Ten schemat nie jest „oficjalny”, ale dobrze dyscyplinuje mysl: zanim dodasz drugi Mutex, warto zapytac siebie, czy nie tworzysz przyszlego deadlocka „na raty”.

5. Typowe bledy

Blad nr 1: przejmowanie kilku Mutex w roznej kolejnosci „w roznych miejscach po troche”.
To najczestsze zrodlo deadlocka. W jednej metodzie blokujesz A potem B, w innej — B potem A, bo „tak latwiej sie czyta”. A potem program czasem zawiesza sie na zawsze i zaczynasz podejrzewac wszystko: GC, JIT, faze ksiezyca i sasiada z mikrofalowka. Nie leczy sie tego debugowaniem, tylko zasada: jeden porzadek przejmowania na caly projekt (np. wedlug id).

Blad nr 2: trzymanie Mutex podczas dlugich operacji (I/O, delay, ciezkie obliczenia).
W ten sposob sam hodujesz starvation. Nawet jesli deadlock jest niemozliwy, system bedzie degradowal: jedna korutyna trzyma zamek dlugo, reszta czeka, i odczucie bedzie „wszystko muli”, chociaz formalnie poprawnosc jest zachowana. Poprawne myslenie: pod zamkiem zostawiamy tylko to, co naprawde musi byc atomowe.

Blad nr 3: proba „naprawiania zawieszen” przez dodawanie delay() w losowych miejscach.
delay() moze przypadkowo zamaskowac problem (zwlaszcza race condition), a przy deadlocku czasem bedzie sie wydawalo, ze „jest lepiej”, bo zmienil sie harmonogram korutyn. To nie jest rozwiazanie. Rozwiazanie to granice sekcji krytycznej, jednolity porzadek zamkow albo zmiana projektu na confinement.

Blad nr 4: reczne pisanie tryLock/unlock bez try/finally.
W przykladach powyzej try/finally wyglada jak pedanteria, ale to ten przypadek, gdy pedanteria ratuje. Kazdy wczesny return, kazdy wyjatek, kazda logika „jesli sie nie udalo” — i ryzykujesz, ze nie zwolnisz zamka. Jedno zapomniane unlock() zamienia system w „wieczne czekanie” i sprawia, ze przyczyna jest slabo odtwarzalna.

Blad nr 5: walka z livelockiem identycznymi strategiami po obu stronach.
Jesli dwie korutyny „uprzejmie ustepuja” tak samo, moga synchronicznie ustepowac w nieskonczonosc. Livelock leczy sie asymetria: jednolitym porzadkiem przejmowania, losowym back-offem albo rozwiazaniem architektonicznym, w ktorym konkurencji o zasob po prostu nie ma (confinement/actor).

Blad nr 6: zalozenie, ze skoro uzywamy Mutex, to „sprawiedliwie rozdzieli kolejke”.
Mutex daje wzajemne wykluczenie, ale nie gwarantuje, ze kazda korutyna dostanie zasob na czas. Jesli jedna czesc kodu stale przejmuje zamek na dlugo albo bardzo czesto, inne moga glodowac. Dlatego Mutex to narzedzie poprawnosci, a „sprawiedliwosc” i „przepustowosc” zostaja na sumieniu projektu.