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 неприятен тем, что по логам может казаться: «всё работает». Просто некоторые операции начинают «иногда очень долго думать». Это обычно диагностируется по симптомам:

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

И почти всегда причина — слишком широкая критическая секция или тяжёлая работа внутри 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, любое исключение, любая логика «if не получилось» — и вы рискуете не отпустить замок. Один забытый unlock() превращает систему в «вечное ожидание» и делает причину плохо воспроизводимой.

Ошибка №5: бороться с livelock одинаковыми стратегиями с обеих сторон.
Если две корутины «вежливо уступают» одинаково, они могут синхронно уступать бесконечно. Livelock лечится асимметрией: единым порядком захвата, случайным бэк-оффом, или архитектурным решением, где конкуренции за ресурс просто нет (confinement/actor).

Ошибка №6: считать, что раз мы используем Mutex, то «оно справедливо распределит очередь».
Mutex даёт взаимное исключение, но не гарантирует, что каждая корутина получит ресурс вовремя. Если одна часть кода постоянно захватывает замок надолго или очень часто, другие могут голодать. Поэтому Mutex — это инструмент корректности, а «справедливость» и «пропускная способность» остаются на совести дизайна.