デッドロックとは何ですか。4つの条件は何で、どのように防ぎますか。

Question

IT Interview Practice · Accepted Answer

**デッドロックは、2つ以上のスレッドがそれぞれ他方の保持するリソースを永遠に待ち、どれも先へ進めない状態です。** 4つの条件（Coffman条件）が同時に成り立つことを要します。

## 4つの条件

1. **mutual exclusion（相互排他）** — リソースが排他的に保持される。
2. **hold and wait（保持と待機）** — スレッドが1つのリソースを保持したまま別のリソースを待つ。
3. **no preemption（横取りなし）** — リソースを強制的に取り上げることができない。
4. **circular wait（循環待ち）** — 各スレッドが次のスレッドを待つ循環。

どれか1つを崩せば、デッドロックは起こりえません。

```text
Thread 1 holds A, wants B ─┐
                           ├─ circular wait → deadlock
Thread 2 holds B, wants A ─┘
```

## 例と対処

```python
# DEADLOCK: threads lock in opposite orders
def t1():
    with lockA:
        with lockB: ...     # T1: A then B
def t2():
    with lockB:
        with lockA: ...     # T2: B then A  ← cycle!

# FIX: impose a global lock ordering (always A before B)
def safe():
    with lockA:
        with lockB: ...     # everyone acquires in the same order
```

## 予防と検出

- **ロック順序**: 常に一貫したグローバルな順序でロックを取得する — circular waitを崩す。
- **タイムアウト / try-lock**: `tryAcquire(timeout)`でバックオフしてリトライする — hold-and-waitを崩す。
- **粗いロック1つ**、またはlock-freeな構造は、問題を完全に回避する。
- **検出**: ウォッチドッグがwait-forグラフを構築して循環を探し、犠牲となるスレッドをkill/再起動する。

## なぜ重要なのか

デッドロックはシステムを静かに凍りつかせます。クラッシュはなく、ただリクエストがハングします。4つの条件を挙げられることは、*なぜ*起こるのかを筋道立てて考え、ロックをやみくもにばらまいて祈るのではなく、的を絞った予防策（たいていは一貫したロック順序）を選べることを示します。

4つの条件

例と対処

予防と検出

なぜ重要なのか

関連する質問