Livelock w programowaniu mobilnym: co to jest, różnica od wzajemnego blokowania i zasada działania

Co to jest Livelock?

Livelock (aktywne blokowanie) — to sytuacja w systemie wielowątkowym, w której wątki nie są zablokowane, ale też nie wykonują użytecznej pracy. Każdy wątek odkrywa, że nie może kontynuować pracy i próbuje to naprawić, ale jego działania wywołują taką samą reakcję u innych wątków. W rezultacie system nieskończenie przełącza się między stanami, nie osiągając postępu.

Klasyczna analogia Livelock — dwie osoby spotykają się w wąskim korytarzu. Każda próbuje ustąpić drogi, cofając się w bok, ale obie jednocześnie wykonują ten sam ruch i znów stają naprzeciw siebie. Nie stoją w miejscu (to byłby Deadlock), ale aktywnie się poruszają i wciąż nie mogą się rozejść. W programowaniu odpowiada to wątkom, które stale zwalniają i ponownie przechwytują zasoby.

W programowaniu mobilnym Livelock jest szczególnie niebezpieczny, ponieważ jest niewidoczny dla użytkownika: aplikacja nie zawiesza się, interfejs nie blokuje, ale bateria rozładowuje się 2-3 razy szybciej z powodu 100% obciążenia CPU przez wątki tła. Według testów Google (Android Battery Optimization, 2023), Livelock w usłudze tła może skrócić czas pracy urządzenia na baterii o 40%.

Jak powstaje Livelock

Synchroniczna reakcja na konflikt

Livelock powstaje, gdy kilka wątków używa tej samej strategii reakcji na konflikt. Jeśli Wątek A nie może przechwycić zasobu i zwalnia swój bieżący zasób, a Wątek B robi to samo jednocześnie, oba powtarzają cykl — i sytuacja powtarza się nieskończenie. Jest to szczególnie charakterystyczne dla algorytmów z TryLock i automatycznym zwalnianiem przy niepowodzeniu.

Brak losowości w ponownych próbach

Gdy wątki używają stałego opóźnienia przed ponowną próbą, mogą wejść w synchroniczny cykl. Jeśli oba wątki czekają tak samo długo, ponownie jednocześnie spróbują przechwycić zasób i jednocześnie go zwolnią. Problem rozwiązuje się używając exponential backoff z losowym składnikiem (jitter), jak w algorytmie CSMA/CD w Ethernet.

Nieprawidłowy projekt kolejek

W programowaniu mobilnym Livelock często powstaje przy nieprawidłowej implementacji kolejek zadań. Na przykład, gdy wątek roboczy kończy przetwarzanie wiadomości, ale z powodu logiki priorytetyzacji stale przekazuje sterowanie innemu workerowi, który robi to samo. Takie sytuacje są typowe dla niestandardowych ThreadPoolExecutor z niestandardową polityką RejectedExecutionHandler.

Przykład Livelock w kodzie Kotlin

Rozpatrzmy sytuację, gdy dwa wątki używają TryLock i zwalniają zasób przy niepowodzeniu. Aktywne blokowanie powstaje, ponieważ oba wątki stosują tę samą logikę i synchronicznie powtarzają próby.

import java.util.concurrent.locks.ReentrantLock
import java.util.concurrent.TimeUnit

class LivelockWorker(private val name: String,
                     private val lock1: ReentrantLock,
                     private val lock2: ReentrantLock) {

    fun execute() {
        while (true) {
            if (lock1.tryLock(50, TimeUnit.MILLISECONDS)) {
                if (lock2.tryLock(50, TimeUnit.MILLISECONDS)) {
                    println("$name — wykonano!")
                    lock2.unlock()
                    lock1.unlock()
                    return
                } else {
                    lock1.unlock()  // zwalniamy i powtarzamy
                }
            }
            Thread.sleep(50)  // stałe opóźnienie — kluczowy czynnik Livelock
        }
    }
}

Jeśli dwie instancje LivelockWorker uruchomić z różną kolejnością przechwytywania lock1 i lock2, wejdą w aktywne blokowanie. Każdy będzie przechwytywać pierwszy zasób, nie otrzymywać drugiego, zwalniać pierwszy, czekać 50 ms i powtarzać — nieskończenie, zużywając CPU. Poprawka — dodać losowy składnik do opóźnienia (jitter) i ograniczyć liczbę ponownych prób.

Poprawiona wersja używa exponential backoff z losowym jitter. Po każdej nieudanej próbie czas oczekiwania zwiększa się z dodatkiem losowego mnożnika, co niszczy synchroniczność między wątkami.

fun executeWithBackoff() {
    var delay = 10L
    var attempts = 0

    while (attempts < 5) {
        if (lock1.tryLock(delay, TimeUnit.MILLISECONDS)) {
            if (lock2.tryLock(delay, TimeUnit.MILLISECONDS)) {
                println("Sukces!")
                lock2.unlock(); lock1.unlock()
                return
            }
            lock1.unlock()
        }
        delay = (delay * 2 + (0..50).random())
        attempts++
    }
    println("Nie udało się po 5 próbach")
}

Livelock vs Deadlock: kluczowe różnice

Mimo zewnętrznego podobieństwa, Livelock i Deadlock mają zasadniczo różne mechanizmy i skutki. Przy Deadlock wątki są zablokowane i nie zużywają CPU — aplikacja po prostu zawiesza się. Przy Livelock wątki są aktywne, zużywają 100% CPU, ale nie wykonują użytecznej pracy. Wybór strategii eliminacji zależy od prawidłowego określenia rodzaju blokady.

W programowaniu mobilnym praktyczna różnica jest ogromna. Deadlock prowadzi do ANR i restartu aplikacji — jest wykrywany i zgłaszany przez Google Play Console. Livelock pozostaje niezauważony: aplikacja wygląda na działającą, ale bateria rozładowuje się w godzinę, a użytkownik po prostu usuwa aplikację. Według Firebase Analytics (App Retention Report, 2024), 68% użytkowników usuwa aplikację, jeśli nadmiernie zużywa baterię w tle.

Jak wykryć Livelock

Wykrywanie Livelock jest trudniejsze niż Deadlock, ponieważ system nie wysyła oczywistych sygnałów — nie ma wyjątków, ANR, komunikatów o błędach. Główna metoda diagnostyki — CPU Profiler w Android Studio. Jeśli wątek stale jest w stanie RUNNABLE, ale nie wykonuje użytecznych operacji wejścia-wyjścia ani obliczeń — to podejrzenie Livelock.

Dodatkowy objaw — anomalne zużycie baterii przy bezczynności aplikacji. Android Battery Historian (narzędzie z Android SDK) buduje wykresy zużycia energii według komponentów. Jeśli CPU Wakelock jest utrzymywany bez widocznej przyczyny — warto uruchomić Method Tracing i przeanalizować stos wywołań podejrzanych wątków.

Na poziomie kodu pomaga logowanie ponownych prób z podaniem threadId i czasu. Jeśli log pokazuje tysiące ponownych prób na sekundę bez ani jednego sukcesu — to Livelock. Zaleca się wdrożenie circuit breaker podobnego do Hystrix lub licznika retry z progiem zadziałania, który po przekroczeniu wyłącza operację i powiadamia dewelopera przez Crashlytics.

Metody zapobiegania aktywnemu blokowaniu

Licznik ponownych prób (Retry Limit)

Najprostszy i najbardziej niezawodny sposób — ograniczyć liczbę prób przechwycenia zasobu. Jeśli po N próbach operacja się nie powiodła, wątek przechodzi w stan błędu i powiadamia użytkownika. N dobiera się empirycznie: dla aplikacji mobilnych zwykle 3-5 prób. To całkowicie eliminuje nieskończony Livelock kosztem rzadkich fałszywych alarmów przy wysokim obciążeniu.

Exponential Backoff z Jitter

Zamiast stałego opóźnienia między próbami używana jest wykładniczo rosnąca pauza z losowym składnikiem. Wzór: delay = min(baseDelay * 2^attempt, maxDelay) + random(0, jitter). Takie podejście nie tylko niszczy synchroniczność wątków, ale także zmniejsza ogólne obciążenie systemu przy wysokiej konkurencji. Używane w algorytmach protokołów sieciowych i zalecane przez Google dla logiki ponownych prób Firebase Realtime Database.

Priorytet i asymetryczna logika

Przypisanie różnych strategii różnym wątkom eliminuje samą przyczynę Livelock — jednakową reakcję na konflikt. Na przykład, wątek o wysokim priorytecie otrzymuje zasób bez zwalniania, a niskopriorytetowy — zwalnia i czeka. W programowaniu mobilnym wątek UI może mieć priorytet przy przechwytywaniu blokad, a wątki robocze tła — używać TryLock z timeoutem.

Rezygnacja z cyklicznego zwalniania

W niektórych architekturach Livelock zapobiega się na poziomie projektu: zwalnianie zasobów tylko w jednym kierunku. Na przykład, jeśli wątek A zawsze przekazuje sterowanie do wątku B przez stały kanał (Channel), a B nigdy nie próbuje zwrócić sterowania do A — cykl reakcji jest niemożliwy. Architektura potokowa z jednokierunkowymi etapami przetwarzania całkowicie eliminuje Livelock między sąsiednimi etapami w Android CameraX i MediaPipe.