Deadlock w programowaniu mobilnym: co to jest, przyczyny powstawania i sposoby unikania wzajemnego blokowania

Co to jest Deadlock?

Deadlock (wzajemne blokowanie) — to sytuacja w programowaniu wielowątkowym, w której dwa lub więcej wątków trwale blokują się nawzajem. Każdy wątek utrzymuje zasób potrzebny innemu wątkowi i nie zwalnia go, oczekując na przejęcie brakującego zasobu. W rezultacie żaden z wątków nie może kontynuować działania.

W programowaniu mobilnym Deadlock jest szczególnie krytyczny, ponieważ nie powoduje wyjątków ani awarii. Aplikacja po prostu przestaje reagować na działania użytkownika (ANR — Application Not Responding), a jedynym wyjściem jest wymuszone zakończenie procesu. Według danych Google (Android Performance Patterns, 2023), około 15% raportów ANR w Google Play Console jest związanych ze wzajemnymi blokadami w wątkach tła.

Kluczowa różnica Deadlocka od innych problemów współbieżności — jego nieodwracalność bez zewnętrznej interwencji. Wątki nie zwolnią zasobów samodzielnie, ponieważ planista systemu operacyjnego nie może przymusowo odebrać blokady. To odróżnia Deadlock od Livelocka, gdzie wątki są aktywne, ale nie wykonują użytecznej pracy.

Warunki wystąpienia Deadlocka

W 1971 roku Edward G. Coffman sformułował cztery obowiązkowe warunki niezbędne do wystąpienia Deadlocka. Jeśli choć jeden z nich jest nieobecny, wzajemne blokowanie jest niemożliwe. Te warunki są znane jako warunki Coffmana i leżą u podstaw wszystkich algorytmów zapobiegania Deadlockowi.

Wzajemne wykluczanie (Mutual Exclusion)

Zasób może być przejęty tylko przez jeden wątek w każdej chwili. Jeśli zasób dopuszcza jednoczesne odczytywanie przez kilka wątków (na przykład ReadWriteLock w trybie odczytu), Deadlock nie występuje. Ten warunek wynika z samej natury Mutexa i blokad.

Utrzymywanie i oczekiwanie (Hold and Wait)

Wątek utrzymuje już przejęty zasób i jednocześnie oczekuje na przejęcie innego zasobu. Jeśli wątek może zwolnić bieżący zasób przed żądaniem następnego (poprzez dwufazowe blokowanie), warunek Hold and Wait jest naruszony. W Androidzie objawia się to często, gdy wątek trzyma blokadę bazy danych i próbuje przejąć blokadę SharedPreferences.

Brak przymusowego wywłaszczenia (No Preemption)

System operacyjny nie może przymusowo odebrać blokady wątkowi. Zasób jest zwalniany tylko wtedy, gdy wątek sam go zwolni. W niektórych systemach (na przykład SQLite WAL mode) zaimplementowano przymusowe wywłaszczenie na poziomie poszczególnych operacji, co zmniejsza ryzyko Deadlocka.

Oczekiwanie cykliczne (Circular Wait)

Istnieje zamknięty łańcuch wątków, z których każdy oczekuje na zasób utrzymywany przez następnego w łańcuchu. Na przykład wątek A trzyma zasób 1 i czeka na zasób 2, wątek B trzyma zasób 2 i czeka na zasób 1. To jedyny warunek, który programista może wyeliminować architektonicznie — poprzez hierarchię blokad. Jeśli wszystkie wątki przejmują zasoby w ściśle okrelonym globalnym porządku, cykl jest fizycznie niemożliwy.

W praktyce w aplikacjach Android Deadlock najczęściej powstaje z powodu niejawnego krzyżowania blokad różnych poziomów: blokady bazy danych (Room), blokady SharedPreferences i blokady kolekcji w pamięci. Każda z tych blokad jest zarządzana przez inne komponenty i bez scentralizowanego protokołu kolejności przejmowania programiści nieświadomie tworzą cykle.

Przykład Deadlocka w kodzie Kotlin

Rozważmy klasyczny przykład wzajemnego blokowania — dwa wątki przejmują blokady w różnej kolejności. Jeśli pierwszy wątek blokuje zasób A i próbuje przejąć B, a drugi — blokuje B i próbuje przejąć A, powstaje Deadlock.

class DeadlockExample {
    private val lockA = Any()
    private val lockB = Any()

    fun operationA() {
        synchronized(lockA) {
            Thread.sleep(50)  // symulacja działania
            synchronized(lockB) {
                println("operationA wykonana")
            }
        }
    }

    fun operationB() {
        synchronized(lockB) {  // odwrotna kolejność!
            Thread.sleep(50)
            synchronized(lockA) {
                println("operationB wykonana")
            }
        }
    }
}

fun main() {
    val ex = DeadlockExample()
    Thread { ex.operationA() }.start()
    Thread { ex.operationB() }.start()
    // Aplikacja zawiesi się na zawsze — Deadlock!
}

W tym przykładzie operationA przejmuje lockA, a operationB przejmuje lockB. Następnie każdy próbuje przejąć drugą blokadę — i oba czekają w nieskończoność. Program zawiesza się bez komunikatu o błędzie. Jedynym sposobem naprawy jest zagwarantowanie jednakowej kolejności przejmowania blokad we wszystkich metodach.

Deadlock vs Starvation vs Livelock

Te trzy problemy współbieżności są często mylone, ale ich mechanizmy i skutki są zasadniczo różne. Deadlock — całkowite zatrzymanie, Starvation — nieskończone oczekiwanie na zasób, Livelock — aktywne bezczynność. Zrozumienie różnic jest krytyczne dla wyboru właciwej strategii eliminacji.

Starvation (głodzenie) powstaje, gdy planista stale odwleka wykonanie wątku o niskim priorytecie na korzyść innych. W przeciwieństwie do Deadlocka, wątek nie jest zablokowany — jest gotowy do wykonania, ale nie otrzymuje czasu procesora. W Androidzie typowy scenariusz — wątek tła z niskim priorytetem nigdy się nie wykonuje, jeśli wątki UI i Service są stale aktywne.

Livelock (aktywne blokowanie) — sytuacja, w której wątki nie są zablokowane, ale nieskończenie reagują na działania siebie nawzajem, nie wykonując użytecznej pracy. Klasyczna analogia — dwie osoby spotykają się w korytarzu i obie próbują ustąpić drogi, poruszając się w tę samą stronę. W przeciwieństwie do Deadlocka, wątki w Livelocku zużywają CPU, rozładowując baterię urządzenia.

Jak wykryć Deadlocka

Thread Dump (zrzut wątków) — główne narzędzie wykrywania wzajemnych blokad w JVM i Android Runtime. Podczas zrzutu JVM automatycznie analizuje graf zależności między monitorami i oznacza cykle Deadlocka. W Android Studio zrzut wątków można uzyskać przez Android Profiler lub komendę kill -3 PID z ADB Shell.

Automatyczne wykrywanie Deadlocka w czasie wykonania realizuje się przez Watchdog-liczniki czasu. Jeśli wątek nie kończy operacji w zadanym limicie czasu, watchdog inicjuje wykonanie zrzutu i wysyła raport do systemu raportowania awarii (Firebase Crashlytics, Sentry). Według danych Sentry (Issue Resolution Report, 2024), konfiguracja watchdog-a skraca czas diagnozowania Deadlocka z tygodni do kilku godzin.

Na etapie rozwoju skuteczne są statyczne analizatory ThreadSafe od JetBrains i Checker Framework z modułem Lock Checker. Te narzędzia analizują kolejność przejmowania blokad na poziomie kodu źródłowego i ostrzegają o potencjalnych cyklach. Dodatkowo zaleca się używanie Test-Driven Deadlock Detection — testów obciążeniowych, które uruchamiają operacje z różnymi kolejnościami blokad w setkach wątków.

Osobnej uwagi zasługuje Cooperative Deadlock Detection — metoda, w której wątki wymieniają się informacjami o przejętych blokadach przez globalny rejestr. Jeśli wątek wykryje potencjalny cykl, zwalnia wszystkie zasoby i powtarza operację. To podejście jest używane w systemach rozproszonych (Apache ZooKeeper, Google Chubby) i stopniowo jest wdrażane w programowaniu mobilnym przez biblioteki takie jak Jetpack Sync.

Metody zapobiegania wzajemnemu blokowaniu

Hierarchia blokad (Lock Ordering)

Najbardziej niezawodny sposób — ustanowić globalny porządek przejmowania blokad w całej aplikacji. Jeśli wszystkie wątki zawsze przejmują najpierw blokadę z mniejszym numerem, a następnie z większym, oczekiwanie cykliczne (warunek Circular Wait) jest niemożliwe. W dużych projektach porządek jest ustalany w dokumentacji i weryfikowany przez przegląd kodu.

TryLock z limitem czasu

TryLock — metoda blokowania, która nie blokuje wątku nieskończenie, a zwraca false, jeśli blokada nie została uzyskana w zadanym czasie. W Javie jest to zaimplementowane przez ReentrantLock.tryLock(timeout, TimeUnit), w Kotlin Coroutines — przez Mutex.withLock z limitem czasu. W razie niepowodzenia wątek zwalnia wszystkie przejęte zasoby i ponawia próbę później.

Algorytm bankiera (Banker’s Algorithm)

Algorytm bankiera — teoretyczna metoda zapobiegania Deadlockowi, zaproponowana przez Edsgera Dijkstrę. Modeluje on dystrybucję zasobów jako transakcje bankowe: system nie przydziela zasobu, jeśli może to prowadzić do niebezpiecznego stanu (deadlock). W praktyce algorytm rzadko jest stosowany w programowaniu mobilnym ze względu na złożoność wstępnego poznania maksymalnych potrzeb wątków, ale jego zasady są używane w bazach danych SQLite i systemach plików.