Livelock v mobilním vývoji: co to je, rozdíl od vzájemného blokování a princip fungování

Co je Livelock?

Livelock (aktivní blokování) — je situace v vícevláknovém systému, kdy vlákna nejsou blokována, ale ani nevykonávají užitečnou práci. Každé vlákno zjistí, že nemůže pokračovat v práci, a snaží se to napravit, ale jeho akce vyvolávají stejnou reakci u ostatních vláken. Výsledkem je, že systém nekonečně přepíná mezi stavy bez dosažení pokroku.

Klasická analogie Livelock — dva lidé se setkají v úzké chodbě. Každý se snaží uhnout z cesty, ale oba současně provedou stejný pohyb a jsou opět proti sobě. Nestojí na místě (to by byl Deadlock), ale aktivně se pohybují a stále se nemohou rozejít. V programování to odpovídá vláknům, která neustále uvolňují a znovu zabírají zdroje.

V mobilním vývoji je Livelock obzvláště nebezpečný, protože je pro uživatele neviditelný: aplikace nezmrzne, rozhraní se neblokuje, ale baterie se vybíjí 2-3krát rychleji kvůli 100% zatížení CPU vlákny na pozadí. Podle testů Google (Android Battery Optimization, 2023) může Livelock na pozadí Service zkrátit dobu provozu zařízení na baterii až o 40%.

Jak vzniká Livelock

Synchronní reakce na konflikt

Livelock vzniká, když několik vláken používá stejnou strategii reakce na konflikt. Pokud vlákno A nemůže získat zdroj a uvolní svůj aktuální zdroj, a vlákno B dělá totéž současně, obě opakují cyklus — a situace se nekonečně opakuje. To je zvláště charakteristické pro algoritmy s TryLock a automatickým uvolněním při neúspěchu.

Nedostatek náhodnosti v opakovaných pokusech

Když vlákna používají pevné zpoždění před opakovaným pokusem, mohou vstoupit do synchronního cyklu. Pokud obě vlákna čekají stejně dlouho, znovu se současně pokusí získat zdroj a současně ho uvolní. Problém se řeší pomocí exponential backoff s náhodnou složkou (jitter), jako v algoritmu CSMA/CD v Ethernetu.

Nesprávný návrh front

V mobilním vývoji Livelock často vzniká při nesprávné implementaci front úloh. Například když pracovní vlákno dokončí zpracování zprávy, ale kvůli logice prioritizace neustále předává řízení jinému pracovníkovi, který dělá totéž. Takové situace jsou typické pro vlastní ThreadPoolExecutory s nestandardní politikou RejectedExecutionHandler.

Příklad Livelock v kódu Kotlin

Podívejme se na situaci, kdy dvě vlákna používají TryLock a uvolňují zdroj při neúspěchu. Aktivní blokování vzniká, protože obě vlákna aplikují stejnou logiku a synchronně opakují pokusy.

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 — provedeno!")
                    lock2.unlock()
                    lock1.unlock()
                    return
                } else {
                    lock1.unlock()  // uvolňujeme a opakujeme
                }
            }
            Thread.sleep(50)  // pevné zpoždění — klíčový faktor Livelock
        }
    }
}

Pokud dvě instance LivelockWorker spustíme s odlišným pořadím získávání lock1 a lock2, vstoupí do aktivního blokování. Každá získá první zdroj, nedostane druhý, uvolní první, počká 50 ms a opakuje — nekonečně, spotřebovávajíc CPU. Oprava — přidání náhodné složky ke zpoždění (jitter) a omezení počtu opakovaných pokusů.

Opravená verze používá exponential backoff s náhodným jitter. Po každém neúspěšném pokusu se doba čekání zvyšuje s přidáním náhodného násobitele, což ničí synchronizaci mezi vlákny.

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

    while (attempts < 5) {
        if (lock1.tryLock(delay, TimeUnit.MILLISECONDS)) {
            if (lock2.tryLock(delay, TimeUnit.MILLISECONDS)) {
                println("Úspěch!")
                lock2.unlock(); lock1.unlock()
                return
            }
            lock1.unlock()
        }
        delay = (delay * 2 + (0..50).random())
        attempts++
    }
    println("Po 5 pokusech se nezdařilo")
}

Livelock vs Deadlock: klíčové rozdíly

Navzdory vnější podobnosti mají Livelock a Deadlock zásadně odlišné mechanismy a důsledky. Při Deadlock jsou vlákna blokována a nespotřebovávají CPU — aplikace prostě zamrzne. Při Livelock jsou vlákna aktivní, spotřebovávají 100% CPU, ale nevykonávají užitečnou práci. Volba eliminační strategie závisí na správném určení typu blokování.

V mobilním vývoji je praktický rozdíl obrovský. Deadlock vede k ANR a restartu aplikace — je detekován a hlášen prostřednictvím Google Play Console. Livelock zůstává nepovšimnut: aplikace vypadá, že funguje, ale baterie se vybije za hodinu a uživatel jednoduše aplikaci smaže. Podle Firebase Analytics (App Retention Report, 2024) 68% uživatelů smaže aplikaci, pokud nadměrně spotřebovává baterii na pozadí.

Jak zjistit Livelock

Detekce Livelock je obtížnější než Deadlock, protože systém nevydává zřejmé signály — neexistují výjimky, ANR ani chybové zprávy. Hlavní diagnostická metoda — CPU Profiler v Android Studio. Pokud je vlákno neustále ve stavu RUNNABLE, ale neprovádí užitečné vstupně-výstupní operace ani výpočty — je to podezření na Livelock.

Další příznak — anomální spotřeba baterie při nečinnosti aplikace. Android Battery Historian (nástroj z Android SDK) vytváří grafy spotřeby energie podle komponent. Pokud je CPU Wakelock udržován bez zjevného důvodu — stojí za to spustit Method Tracing a analyzovat zásobník volání podezřelých vláken.

Na úrovni kódu pomáhá logování opakovaných pokusů s threadId a časem. Pokud log zobrazuje tisíce opakovaných pokusů za sekundu bez jediného úspěchu — jedná se o Livelock. Doporučuje se implementace circuit breaker podobného Hystrix nebo počítadla retry s prahem aktivace, který při překročení deaktivuje operaci a upozorní vývojáře prostřednictvím Crashlytics.

Metody prevence aktivního blokování

Počítadlo opakovaných pokusů (Retry Limit)

Nejjednodušší a nejspolehlivější způsob — omezit počet pokusů o získání zdroje. Pokud po N pokusech operace neuspěje, vlákno přejde do chybového stavu a upozorní uživatele. N se volí empiricky: pro mobilní aplikace obvykle 3-5 pokusů. To zcela eliminuje nekonečný Livelock za cenu vzácných falešných spuštění při vysokém zatížení.

Exponential Backoff s Jitter

Místo pevného zpoždění mezi pokusy se používá exponenciálně rostoucí pauza s náhodnou složkou. Vzorec: delay = min(baseDelay * 2^attempt, maxDelay) + random(0, jitter). Tento přístup nejen ničí synchronizaci vláken, ale také snižuje celkové zatížení systému při vysoké konkurenci. Používá se v algoritmech síťových protokolů a je doporučen společností Google pro logiku opakovaných pokusů Firebase Realtime Database.

Priorita a asymetrická logika

Přiřazení různých strategií různým vláknům odstraňuje samotnou příčinu Livelock — stejnou reakci na konflikt. Například vlákno s vysokou prioritou získává zdroj bez uvolnění, zatímco vlákno s nízkou prioritou uvolňuje a čeká. V mobilním vývoji může mít UI vlákno prioritu při získávání zámků a pracovní vlákna na pozadí mohou používat TryLock s časovým limitem.

Vyhnutí se cyklickému uvolňování

V některých architekturách je Livelock prevenci na úrovni návrhu: uvolňování zdrojů pouze jedním směrem. Například pokud vlákno A vždy předává řízení vláknu B prostřednictvím pevného kanálu (Channel) a B se nikdy nepokouší vrátit řízení A — cyklus reakce je nemožný. Pipeline architektura s jednosměrnými fázemi zpracování v Android CameraX a MediaPipe zcela eliminuje Livelock mezi sousedními fázemi.