Что такое deadlock, и как его предотвратить, избежать или обнаружить?

Question

IT Interview Practice · Accepted Answer

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

## Четыре необходимых условия (Коффмана)

Все четыре должны выполняться одновременно — устраните любое одно, и deadlock невозможен:

```text
1. Mutual exclusion   → a resource is held exclusively (only one holder at a time)
2. Hold and wait      → a thread holds one resource while waiting to acquire another
3. No preemption      → resources can't be forcibly taken; only released voluntarily
4. Circular wait      → a cycle: T1 waits for R2 (held by T2), T2 waits for R1 (held by T1)
```

```text
   T1 ──holds──▶ R1        T1 wants R2 ──▶ (held by T2)
   T2 ──holds──▶ R2        T2 wants R1 ──▶ (held by T1)   ← cycle = deadlock
```

## Обработка deadlock

- **Предотвращение (prevention)** — проектируйте так, чтобы одно из условий никогда не выполнялось. Самое практичное: убить **circular wait**, навязав **глобальный порядок блокировок** (всегда захватывать A перед B). Или атаковать **hold-and-wait**, захватывая все нужные блокировки сразу.
- **Избегание (avoidance)** — удовлетворять запрос только если система остаётся в «безопасном» состоянии, где каждый поток всё ещё может завершиться (**алгоритм банкира, Banker's algorithm**). Ему нужны заранее известные максимальные потребности каждого потока в ресурсах, поэтому на практике он применяется редко.
- **Обнаружение и восстановление (detection & recovery)** — позвольте deadlock'ам случаться, периодически сканируйте **wait-for graph** на наличие цикла, затем восстанавливайтесь, убивая или откатывая «жертву». Базы данных делают именно это: они обнаруживают deadlock и прерывают одну транзакцию с ошибкой «deadlock victim».
- **Игнорирование («алгоритм страуса»)** — если deadlock'и редки, просто перезапускайте; многие ОС принимают такой подход для некоторых ресурсов.

## Почему это важно

Deadlock — классическая тема собеседований, потому что схема из четырёх условий — это точный диагностический инструмент: столкнувшись с зависанием, вы можете спросить «какое условие я могу нарушить?» В реальных системах ходовой ответ — **согласованный порядок блокировок** (который предотвращает circular wait) — правило, которое вы применяете каждый раз, когда берёте больше одной блокировки. Понимание того, что ваша база данных выбрасывает ошибки deadlock-victim, и знание, что нужно просто повторить эту транзакцию, — прямое практическое применение.

Четыре необходимых условия (Коффмана)

Обработка deadlock

Почему это важно

Похожие вопросы