Что такое дедлок простыми словами

Представьте узкий мост, по которому помещается одна машина. С двух сторон одновременно въезжают две машины и встречаются ровно посередине. Первой нужно, чтобы вторая сдала назад. Второй — чтобы сдала назад первая. Никто не уступает. Обе стоят навечно. Движение умерло.

Дедлок (deadlock, взаимоблокировка) — это ситуация, когда два или более потока навсегда застряли, потому что каждый ждёт ресурс, который держит другой. Никто не двигается, никто не отпускает, ждать можно вечность.

Слово «ресурс» здесь широкое: это может быть мьютекс (см. locks-hardware), семафор (см. semaphores), строка в таблице БД, файл, сетевое соединение — что угодно, что захватывается монопольно.

Важно не путать с обычной долгой блокировкой. Если поток ждёт лок, который кто-то скоро отпустит, — это нормально, он подождёт и поедет дальше. Дедлок — это когда отпускать некому, потому что все звенья в кольце ждут друг друга.

Классика: два лока в разном порядке

Самый частый дедлок в реальном коде — две блокировки, которые два потока берут в разном порядке. Допустим, нужно перевести деньги со счёта A на счёт B. Поток 1 переводит A → B, поток 2 переводит B → A. Каждый блокирует сначала «свой» счёт-источник, потом счёт-получатель.

   Поток 1  (перевод A→B)        Поток 2  (перевод B→A)
   ─────────────────────         ─────────────────────
   шаг 1: lock(A)   ✔ взял        шаг 1: lock(B)   ✔ взял
   шаг 2: lock(B)   ✖ занят →     шаг 2: lock(A)   ✖ занят →
          ждёт поток 2                   ждёт поток 1
 
            ┌──────────────────────────────┐
            │   П1 держит A, хочет B        │
            │   П2 держит B, хочет A        │
            │   → оба ждут вечно. КЛИН.     │
            └──────────────────────────────┘

Что нарисовано: два потока успели захватить по одному локу (A и B), а второй лок у каждого занят соседом. Ни один не отпустит свой лок, пока не возьмёт второй, — а второй ему никто не отдаст. Это и есть классический клин.

Коварство в том, что код выглядит абсолютно правильно: каждый поток берёт и отпускает оба лока, всё аккуратно. Баг проявляется только при определённом переплетении (interleaving): П1 должен успеть взять A, а П2 — взять B, прежде чем кто-то возьмёт второй. На тестах и на ноутбуке может не воспроизводиться месяцами, а в проде под нагрузкой — стрельнуть. Это «гейзенбаг»: трудноуловимый и недетерминированный.

Четыре условия Коффмана

Эдвард Коффман в 1971 году сформулировал четыре условия, которые должны выполняться ВСЕ ОДНОВРЕМЕННО, чтобы дедлок стал возможен. Это ключ к борьбе: достаточно сломать хотя бы одно — и дедлок физически невозможен.

   ┌─────────────────────────────────────────────────────────────┐
   │ 1. Mutual exclusion (взаимное исключение)                     │
   │    Ресурс монопольный: либо у одного, либо ни у кого.         │
   │    Два потока не могут держать один мьютекс сразу.            │
   ├─────────────────────────────────────────────────────────────┤
   │ 2. Hold and wait (удержание и ожидание)                       │
   │    Поток ДЕРЖИТ уже захваченное И ЖДЁТ ещё один ресурс,       │
   │    не отпуская то, что взял.                                  │
   ├─────────────────────────────────────────────────────────────┤
   │ 3. No preemption (отсутствие вытеснения)                      │
   │    Ресурс нельзя отнять силой. Только владелец сам отпускает. │
   ├─────────────────────────────────────────────────────────────┤
   │ 4. Circular wait (круговое ожидание)                          │
   │    Есть кольцо: П1 ждёт П2, П2 ждёт П3, ... , Пn ждёт П1.     │
   └─────────────────────────────────────────────────────────────┘
 
   Дедлок  ⇔  (1) И (2) И (3) И (4) — все четыре сразу.
   Убери любое одно условие → дедлок невозможен.

Что нарисовано: четыре «кирпича», на которых стоит дедлок. Запомните как мантру — на собесе их спрашивают почти всегда. Аналогия с мостом: монопольность (мост на одну машину), удержание-и-ожидание (стою на мосту и жду, не сдавая назад), без вытеснения (никто не может телепортировать чужую машину), кольцо (две машины лоб в лоб — это кольцо из двух звеньев).

Граф ожидания: дедлок = цикл

Чтобы формально увидеть дедлок, рисуют wait-for граф (граф ожидания): узлы — потоки, стрелка «П1 → П2» означает «П1 ждёт ресурс, который держит П2».

   Нормальная работа (нет цикла):        Дедлок (есть цикл):
 
      П1 ──→ П2                              П1 ──→ П2
              │                              ▲       │
              ▼                              │       ▼
             П3   (тупик ожидания            П4 ←── П3
                   рассосётся,             ────────────────
                   П3 ничего не ждёт)       кольцо: П1→П2→П3→П4→П1

Что нарисовано: слева — цепочка без кольца, П3 никого не ждёт, значит он доработает, отпустит ресурс, разблокирует П2, потом П1. Справа — замкнутое кольцо: каждый ждёт следующего, выхода нет. Правило: дедлок тогда и только тогда, когда в графе ожидания есть цикл. Именно поиск цикла используют детекторы дедлоков (и задачу «найди цикл в графе» вы решите отдельно на Go).

Способ 1: предотвращение — ломаем условие

Самый практичный подход — спроектировать систему так, чтобы дедлок был невозможен в принципе. Ломаем одно из четырёх условий.

Самый ходовой и важный приём — lock ordering (упорядочивание блокировок). Договариваемся о глобальном порядке: например, лок с меньшим адресом/ID берём первым. Тогда кольцо стать не может — все идут «в одну сторону».

   Было (дедлок):                  Стало (lock ordering):
   П1: lock(A) → lock(B)           правило: всегда сначала меньший ID
   П2: lock(B) → lock(A)           id(A) < id(B)
 
                                   П1: lock(A) → lock(B)
   разные направления →            П2: lock(A) → lock(B)   ← тот же порядок!
   кольцо возможно
                                   оба идут A→B. Кто первый взял A —
                                   тот и пройдёт. Кольца нет физически.

Что нарисовано: до фикса потоки шли «навстречу» (A→B и B→A) — возможно кольцо. После фикса оба идут в одну сторону A→B: тот, кто не успел взять A, просто ждёт на A, ничего пока не держа, — кольцу неоткуда взяться. В Go это правило ровно такое же: подробнее про практику см. Конкурентность Go: гонки и дедлоки.

Способ 2: избегание — алгоритм банкира

Избегание (avoidance) — система заранее знает, сколько ресурсов максимум запросит каждый поток, и перед каждой выдачей проверяет: «если я выдам этот ресурс, останусь ли я в безопасном состоянии — таком, из которого есть порядок завершить всех?». Если нет — заявку придерживают. Это алгоритм банкира (Дейкстра): банкир выдаёт кредиты, только если гарантированно сможет всех обслужить.

На практике в обычном бэкенде почти не применяется: нужно заранее знать максимумы запросов, что редко возможно. Знать про него полезно для собеса как «третий путь».

Способ 3: детект и восстановление (как в БД)

Иногда дешевле дать дедлоку случиться, а потом обнаружить и разрулить. Так делают почти все реляционные СУБД. База строит wait-for граф транзакций, периодически ищет в нём цикл. Нашла цикл — выбирает «жертву» (обычно ту, что сделала меньше работы / держит меньше локов), откатывает её транзакцию (ROLLBACK), освобождая локи. Остальные едут дальше. Приложение получает ошибку вида deadlock detected и должно просто повторить транзакцию.

   В СУБД:
   T1 держит row(1), хочет row(2)
   T2 держит row(2), хочет row(1)
        граф:  T1 ──→ T2 ──→ T1   (цикл!)
 
   детектор:  нашёл цикл → выбрал жертву T2 → ROLLBACK(T2)
              локи T2 освобождены → T1 берёт row(2) → едет дальше
              T2 получает "deadlock detected" → приложение делает retry

Что нарисовано: СУБД не предотвращает дедлок, а лечит постфактум — ломает кольцо, принудительно отняв ресурсы у жертвы (это, по сути, искусственное добавление вытеснения, которого не хватало). Поэтому код, работающий с БД, всегда должен быть готов поймать ошибку дедлока и повторить операцию. И всё равно: даже с БД полезно брать строки в одном порядке (например, ORDER BY id перед апдейтом) — чтобы дедлоки просто не возникали.

Livelock: заняты, но не двигаются

Livelock (живая блокировка) — потоки формально не заблокированы, они активно что-то делают, но прогресса ноль. Аналогия: два человека в коридоре, оба шагают в одну сторону, чтобы уступить, потом оба в другую — и так бесконечно «танцуют», но не расходятся.

   Дедлок:    оба СТОЯТ и ждут        →  CPU простаивает, потоки спят
   Livelock:  оба ДЕРГАЮТСЯ и уступают →  CPU на 100%, а толку ноль
 
   Частый источник: trylock-стратегия "не вышло — отпусти всё и повтори"
   П1: lock(A) ok, trylock(B) fail → release(A), retry
   П2: lock(B) ok, trylock(A) fail → release(B), retry
   ... и оба синхронно повторяют этот танец снова и снова

Что нарисовано: разница в том, что при дедлоке система «висит тихо», а при livelock — «висит шумно», жжёт процессор. Лечится добавлением случайной задержки (backoff) перед повтором, чтобы потоки рассинхронизировались и один проскочил.

Сводка подходов

Что спрашивают на собесе

• Назови 4 условия Коффмана и какое из них проще всего сломать на практике. Mutual exclusion, hold and wait, no preemption, circular wait — нужны все четыре сразу. Проще всего ломать circular wait через lock ordering (единый глобальный порядок захвата локов).
• Как воспроизвести классический дедлок на двух мьютексах? Два потока берут два лока в противоположном порядке (A→B и B→A); при «удачном» переплетении каждый держит первый лок и ждёт второй.
• Чем дедлок отличается от livelock? Дедлок — потоки спят и ждут (CPU простаивает); livelock — потоки активно работают/уступают, но не прогрессируют (CPU занят). Livelock часто лечат рандомизированным backoff.
• Как СУБД борется с дедлоками? Строит wait-for граф, ищет цикл, выбирает жертву и откатывает её транзакцию; приложение получает ошибку и делает retry. Профилактика — апдейтить строки в одном порядке (ORDER BY id).
• Что такое граф ожидания и как по нему понять, что есть дедлок? Узлы — потоки, рёбра — «кто кого ждёт». Дедлок ⇔ в графе есть цикл.
• В чём минусы trylock-подхода против дедлоков? Он убирает hold-and-wait (отпускаем всё при неудаче), но открывает дверь livelock и лишним откатам.