Deadlock, livelock і starvation: як вони виникають та як не потрапити в пастку

1. Прогрес: коли «помилки немає», але все погано

Якщо ви звикли до однопотокового коду, у вас проста модель світу: якщо програма зламалася — буде виняток. Якщо винятку немає — отже, працює. Конкурентний код грубо ламає цю логіку. Програма може не падати, не лаятися, не писати нічого підозрілого — і водночас ніколи не завершити роботу, або завершити її вдесятеро повільніше, або «залипнути» в дивному стані.

Щоб говорити про це предметно, нам потрібен критерій: прогрес. Прогрес — це коли система робить корисні кроки: обробляє команди, переказує гроші, оновлює лічильник, завершує задачі. Якщо корутини живі, але прогресу немає (або він трапляється хіба на свята) — це симптом проблем синхронізації або дизайну.

Зручно тримати в голові три «антипрогреси»:

Далі ми розберемо кожну проблему на невеликих прикладах Kotlin із корутинами та Mutex.

2. Deadlock: «ти перший» — «ні, ви перші»

Deadlock звучить як назва рок-гурту, але насправді це радше жанр трагікомедії. У deadlockʼу у вас є кілька учасників (корутини або потоки), які захопили ресурси (наприклад, Mutex) і тепер чекають на ресурси одне одного. Ніхто не відпускає те, що вже тримає, бо «мені ще потрібно», а отримати це «ще» неможливо: воно в іншого — і він теж чекає.

Класичний спосіб отримати deadlock — захоплювати кілька блокувань у різному порядку в різних місцях програми. Це не «екзотика», а цілком буденна ситуація: наприклад, у вас є переказ між двома рахунками, і треба заблокувати обидва, щоб переказ був атомарним.

Уявімо наш практичний міні-застосунок: «мінібанк» у консолі, де є рахунки та перекази. Для кожного рахунку буде свій Mutex.

Заготовка: рахунок і два Mutex

Зробімо просту модель. Тут важливо, що Account зберігає mutex поруч із балансом — так ми одразу підкреслюємо ідею «один стан — один замок».

import kotlinx.coroutines.sync.Mutex

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

Тепер створимо пару рахунків і функцію, що переказує гроші. Важливо: переказ — це інваріант рівня двох об’єктів («зняли з одного й поклали на інший»), тож нам потрібно контролювати обидві сторони.

Приклад deadlock: два перекази назустріч

Ось «погана» версія переказу: вона спочатку блокує from, а потім — to. На перший погляд це виглядає логічно.

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 -> B і 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}") // інколи не надрукується взагалі
}

Чому «інколи»? Тому що deadlock часто залежить від розкладу: якщо j1 встиг заблокувати a, а j2 — b, то далі:

• j1 чекає b.mutex
• j2 чекає a.mutex

І все. Прогресу немає.

Це можна зобразити так:

flowchart LR
    J1["j1 тримає lock(A)"] -->|"хоче lock(B)"| B["lock(B) зайнятий"]
    J2["j2 тримає lock(B)"] -->|"хоче lock(A)"| A["lock(A) зайнятий"]
    B -->|"тримає j2"| J2
    A -->|"тримає j1"| J1

Ключова думка: deadlock — це не помилка виконання, а помилка дизайну порядку захоплення. У цьому сенсі він підступніший за винятки: стек-трейсу немає — просто «тиша».

Профілактика: єдиний порядок захоплення

Найпростіше й водночас найсильніше правило проти deadlockʼів із кількома замками: скрізь у коді захоплювати замки в одному й тому самому порядку.

Наприклад, завжди спочатку блокуємо рахунок із меншим id, а потім — із більшим. Тоді в системі просто не може зʼявитися цикл очікування «A чекає B, B чекає A», бо всі рухаються в одному напрямку.

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
        }
    }
}

І запуск:

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 (або навпаки за сумою)
}

Зверніть увагу: ми не робили delay() «для надійності». Deadlock не лікується «чарівним сном» — він лікується строгими правилами.

3. Starvation: «усі працюють», але хтось — майже ніколи

Starvation (голодування) — це ситуація, коли система загалом ніби рухається, але конкретна задача або корутина постійно не отримує доступу до ресурсу (або отримує його так рідко, що бізнес-логіка «помирає повільно»). У житті це схоже на чергу в кавʼярні, де хтось постійно вклинюється, а ви вже третю годину тримаєте в руках один і той самий талончик.

У корутинах starvation часто виникає не тому, що хтось «злий», а тому що ми:

• тримаємо Mutex надто довго,
• виконуємо під замком тривалу операцію,
• або просто влаштували «гарячий цикл» навколо замка.

Важливо розуміти: Mutex захищає коректність, але не гарантує справедливості в сенсі «кожному порівну й вчасно». Тому дизайн критичної секції — це не лише про правильність, а й про продуктивність.

Поганий приклад: довгий delay() під Mutex

Повернімося до нашого мінібанку. Припустімо, є операція «нарахувати бонус» (умовно), яка навіщось робить затримку (наприклад, чекає на якийсь зовнішній крок). Сам факт затримки — не проблема. Проблема починається тоді, коли затримка всередині withLock.

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

suspend fun bonusBad(account: Account) {
    account.mutex.withLock {
        delay(200)           // тримаємо замок, поки "чекаємо"
        account.balance += 1
    }
}

Якщо паралельно йдуть перекази, вони почнуть «голодувати»: кожен переказ чекатиме, поки бонус «поспить». Ніби ніхто не помер, але програма стає вʼязкою, як IDE на старому ноутбуці.

Хороший стиль: коротка критична секція

Часто правильна думка така: «Якщо я чекаю, значить, я нічого не змінюю. Тоді навіщо мені тримати замок?»

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

suspend fun bonusGood(account: Account) {
    delay(200) // чекаємо зовні
    account.mutex.withLock {
        account.balance += 1
    }
}

Так, це можливо не завжди: інколи «чекати» потрібно саме між читанням і записом, і тоді інваріант складніший. Але в більшості звичних випадків це пряме поліпшення.

Як starvation виглядає «на око»

Starvation неприємний тим, що за логами може здаватися: «усе працює». Просто деякі операції починають «інколи дуже довго думати». Зазвичай це діагностують за симптомами:

• одні корутини стабільно завершуються швидко,
• інші «висять» непропорційно довго,
• загальна пропускна здатність падає.

І майже завжди причина — надто широка критична секція або важка робота всередині withLock.

4. Livelock: «ввічливі» корутини без результату

Livelock схожий на deadlock тим, що прогресу немає, але відрізняється драматургією: у deadlock усе завмерло, а в livelock — усе активно рухається, просто марно.

Часта причина livelock — спроба бути «надто ввічливим»: «якщо не вийшло — відпущу й спробую пізніше». Проблема в тому, що обидві сторони роблять це синхронно й нескінченно заважають одна одній.

Щоб показати livelock, нам знадобиться tryLock(): це спроба захопити Mutex без очікування. Якщо замок зайнятий — повернеться false. Це вже знайома ідея з атоміків: «спробував — не вийшло — відкотився», тільки на рівні замків.

Наївний «ввічливий» переказ із tryLock()

Зробімо переказ, який намагається захопити обидва замки. Якщо не вийшло — звільняє те, що захопив, і повторює спробу.

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) // "поступаємося", щоб не крутити CPU
    }
}

Код виглядає розумно, але тепер уявіть дві корутини:

• перша хоче A -> B,
• друга хоче B -> A.

Обидві можуть потрапляти в один ритм:

1. захопили «свій» перший замок
2. другий замок не дістався
3. відпустили й зачекали delay(1)
4. повторили одночасно

Вони не стоять — вони бігають по колу. Прогресу — нуль.

Як відрізнити livelock від deadlock

Deadlock часто виглядає як «тиша»: зависло — і все.

Livelock частіше виглядає як «щось відбувається»: CPU може бути помітно зайнятий, логи можуть «спамитися», але стан не змінюється.

Якщо ви додасте налагоджувальний println("try..."), може вийти нескінченний потік рядків. Це, до речі, окремий біль: логування саме по собі стає причиною гальм, і ви починаєте лікувати симптоми, а не першопричину.

Профілактика livelock: асиметрія

Livelock ламається, якщо ми додаємо асиметрію. Способів багато, але думка одна: обидві сторони не повинні поводитися однаково.

Найпростіший і практичний варіант для навчального рівня — єдиний порядок захоплення (як і для deadlock). Тоді навіть із tryLock() ви не отримаєте нескінченної «ввічливої боротьби»: усі намагаються спочатку взяти first, а потім — second.

Зробімо версію з упорядкуванням за id і невеликим випадковим бекофом, щоб розірвати синхронність повторів:

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)) // розриваємо "стройовий крок"
    }
}

Так, це трохи складніше, ніж просто withLock. І це теж важлива мораль: якщо ви почали «ручне керування» захопленнями, ви в зоні підвищеної уваги. Іноді простіше повернутися до withLock і строгого порядку.

Як не спроєктувати пастку: звички, які рятують

Якщо звести профілактику deadlock/livelock/starvation до однієї ідеї, вона звучатиме так: зменшуйте кількість причин, через які корутинам узагалі доводиться сперечатися за ресурси.

У минулій лекції про confinement/actor ми вже бачили дизайн, де стан змінює один власник, а решта надсилають повідомлення. Такий дизайн часто «за конструкцією» знижує ризик deadlock і starvation, бо у вас немає ситуації «два замки, два власники, два порядки». Навіть якщо всередині власника є Mutex, це вже локальна історія, а не павутина взаємних очікувань.

Якщо ж ви лишаєтеся на Mutex, тоді найстабільніший набір звичок виглядає так:

flowchart TD
    A["Потрібна синхронізація?"] --> B["Можна прибрати shared state через confinement?"]
    B -->|так| C["Actor: один власник стану"]
    B -->|ні| D["Потрібні кілька замків одночасно?"]
    D -->|так| E["Єдиний порядок захоплення й мінімальна секція"]
    D -->|ні| F["Один Mutex і короткий withLock"]

Ця схема не «офіційна», але добре дисциплінує мислення: перш ніж додавати другий Mutex, варто спитати себе, чи не створюєте ви майбутній deadlock «у розстрочку».

5. Типові помилки

Помилка № 1: захоплювати кілька Mutex у різному порядку «в різних місцях потроху».
Це найчастіше джерело deadlockʼу. В одному методі ви блокуєте A, потім B, а в іншому — B, потім A, бо «так зручніше читати». А потім програма інколи зависає назавжди, і ви починаєте підозрювати все: GC, JIT, фазу Місяця й сусіда з мікрохвильовкою. Лікується це не налагодженням, а правилом: один порядок захоплення на весь проєкт (наприклад, за id).

Помилка № 2: тримати Mutex під час тривалих операцій (ввід/вивід, delay, важкі обчислення).
Так ви самі вирощуєте starvation. Навіть якщо deadlock неможливий, система деградуватиме: одна корутина тримає замок довго, решта чекають, і відчуття буде «все гальмує», хоча формально коректність дотримано. Правильне мислення таке: під замком залишаємо лише те, що справді має бути атомарним.

Помилка № 3: намагатися «полагодити зависання», додаючи delay() у випадкових місцях.
delay() може випадково замаскувати проблему (особливо гонки), а при deadlock інколи здаватиметься, що «стало краще», бо розклад корутин змінився. Це не розвʼязання. Розвʼязання — межі критичної секції, єдиний порядок замків або зміна дизайну на confinement.

Помилка № 4: вручну писати tryLock/unlock без try/finally.
У прикладах вище try/finally виглядає занудно, але це той випадок, коли занудство рятує. Будь-який ранній return, будь-який виняток, будь-яка логіка «якщо не вийшло» — і ви ризикуєте не відпустити замок. Один забутий unlock() перетворює систему на «вічне очікування» й робить причину погано відтворюваною.

Помилка № 5: боротися з livelock однаковими стратегіями з обох боків.
Якщо дві корутини «ввічливо поступаються» однаково, вони можуть синхронно поступатися нескінченно. Livelock лікується асиметрією: єдиним порядком захоплення, випадковим бекофом або архітектурним рішенням, де конкуренції за ресурс просто немає (confinement/actor).

Помилка № 6: вважати, що раз ми використовуємо Mutex, то «він справедливо розподілить чергу».
Mutex дає взаємне виключення, але не гарантує, що кожна корутина отримає ресурс вчасно. Якщо одна частина коду постійно захоплює замок надовго або робить це надто часто, інші можуть голодувати. Тому Mutex — це інструмент коректності, а «справедливість» і «пропускна здатність» лишаються на совісті дизайну.