デッドロックとは何で、どうやって防止・回避・検出しますか?

Question

IT Interview Practice · Accepted Answer

**デッドロック (deadlock)** は、2 つ以上のスレッドがそれぞれ **永遠にブロック** され、各々が他が保持するリソースを待っている状態です。何も進みません。

## 4 つの必要 (Coffman) 条件

4 つすべてが同時に成り立たねばなりません — どれか 1 つを取り除けばデッドロックは不可能です:

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

## デッドロックへの対処

- **防止 (prevention)** — 1 つの条件が決して成り立たないよう設計する。最も実践的なのは、**グローバルな lock 順序** を課して **循環待ち (circular wait)** を潰すこと (常に A を B より先に獲得)。あるいは必要な lock を一度にすべて掴んで **hold-and-wait** を攻める。
- **回避 (avoidance)** — すべてのスレッドがまだ完了できる「安全な」状態にとどまる場合のみ要求を許可する (**Banker のアルゴリズム**)。各スレッドの最大リソース需要を事前に必要とするため、実際にはめったに使われません。
- **検出と回復 (detection & recovery)** — デッドロックを起こさせておき、定期的に **wait-for graph** を走査してサイクルを探し、犠牲者をキルまたはロールバックして回復します。データベースはまさにこれを行います: デッドロックを検出し、1 つのトランザクションを「deadlock victim」エラーで中断します。
- **無視 (「ダチョウアルゴリズム」)** — デッドロックが稀なら、単に再起動する。多くの OS は一部のリソースについてこれを受け入れます。

## なぜ重要なのか

デッドロックは定番の面接トピックです。4 条件のフレームワークが正確な診断ツールだからです: ハングに遭遇したら「どの条件を壊せるか?」と問えます。実システムでの定番の答えは **一貫した lock 順序** (循環待ちを防ぐ) — 複数の lock を取るたびに適用するルールです。データベースが deadlock-victim エラーを投げることを認識し、そのトランザクションを単に retry すればよいと知っていることは、直接的な実践応用です。

4 つの必要 (Coffman) 条件

デッドロックへの対処

なぜ重要なのか

関連する質問