デッドロック｜コンピュータ基礎

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：排他制御（ロック・セマフォ・ミューテックス）　|　関連：競合状態とクリティカルセクション・並行性のパターン

要点（BLUF）

デッドロックは、複数の実行が互いの保持する資源を待ち合い、全員が永久に進めなくなる状態。
発生には4条件がすべて同時に成立することが必要：相互排他・保持と待機・横取り不可・循環待ち。1つでも崩せば起きない。
実務の定石はロック取得順序を全スレッドで統一して「循環待ち」を構造的に消すこと。他に予防・回避（銀行家）・検出/回復の戦略がある。

概念 ── 待ち合いで固まる

排他制御（ロック・セマフォ・ミューテックス）のロックは諸刃の剣です。2つのロックを2スレッドが逆順に取りに行くと、こうなります。

flowchart LR
    T1["スレッドT1（ロックA保持中・Bを待つ）"] -->|"Bが欲しい"| B["ロックB"]
    B -->|"T2が保持"| T2["スレッドT2（ロックB保持中・Aを待つ）"]
    T2 -->|"Aが欲しい"| A["ロックA"]
    A -->|"T1が保持"| T1

T1はB待ち、T2はA待ち。互いに相手が手放すのを待つが、どちらも自分の持つものを手放さない。循環した待ちができ、永久に止まります。競合状態（壊れた値）と違い、デッドロックは何も進まないのが症状です。

仕組み ── デッドロックの4条件（Coffman条件）

デッドロックが起きるには、次の4つがすべて同時に成立する必要があります（必要条件）。

条件	意味
相互排他	資源は同時に1つの実行しか持てない
保持と待機	資源を持ったまま、別の資源を待つ
横取り不可	持っている資源を強制的に奪えない（自発解放のみ）
循環待ち	待ちの関係が輪を作る（A待ちB、B待ちC、…、待ちA）

重要なのは「すべて必要」＝どれか1つでも崩せばデッドロックは起きないこと。これが対策の指針になります。

仕組み ── 4つの戦略

1. 予防（prevention）── 4条件のどれかを構造的に潰す

循環待ちを潰す：全資源に番号を振り、常に番号の小さい順に取る。輪ができなくなる（最も実用的）。
保持と待機を潰す：必要な資源をまとめて一度に取る（取れなければ何も持たず待つ）。
横取り不可を潰す：取れないとき持っている資源を一旦手放す。

2. 回避（avoidance）── 危険な割り当てを事前に拒む

資源要求のたびに「この割り当てを認めると、将来デッドロックしうる（安全でない）状態になるか」を判定し、危険なら待たせる。銀行家のアルゴリズムが代表。ただし最大要求量を事前に知る必要があり、汎用OSでは重すぎてあまり使われません。

3. 検出と回復（detection & recovery）

デッドロックを許し、資源割り当てグラフに循環ができたら検出して回復する（プロセスを強制終了する、資源を横取りしてロールバックする）。データベースのトランザクションが採る方式（デッドロック検出→片方を中断）。

4. 無視（駝鳥アルゴリズム）

めったに起きないなら何もしないで、起きたら再起動。多くの汎用OSの実用的な割り切り。

具体例 ── 逆順ロックを再現し、順序統一で消す

固まると観察できないので、ラボでは acquire(timeout=...) で「取れない＝デッドロック」を検出します（[[#対応ラボ]] の 04-03_deadlock.py）。

def worker(name, first, second):
    first.acquire(); time.sleep(0.1)
    got = second.acquire(timeout=1.0)   # 取れなければデッドロックとみなす
    ...
# T1: A->B、T2: B->A（逆順＝循環待ち）

実行結果（実機）:

== 逆順ロック（デッドロックが起きる）==
T2: 2本目が取れない -> デッドロック検出（相手が手放さない）
T1: 2本目が取れない -> デッドロック検出（相手が手放さない）

== ロック順序を統一（A->Bに揃える）-> 回避 ==
T1: A->B の順で取得 -> 処理OK
T2: A->B の順で取得 -> 処理OK
循環待ちが消えるのでデッドロックしない

逆順だと両者が2本目を取れず固まる。取得順序をA→Bに統一するだけで循環待ちが消え、すんなり通ります。これが実務で最も使われる予防策です。

仕組みの直観 ── なぜこの設計か

順序統一が効く理由：循環待ちは「T1がA→B、T2がB→A」のように向きが食い違うから輪になる。全員が同じ向き（番号順）に取れば、輪を描けない（半順序に全順序を課す）。
回避が重い理由：将来の安全性判定には最大要求量の事前申告と毎回の判定が要る。汎用OSの動的なワークロードには合わない。だからDBなど制約の強い世界でだけ使う。
無視という選択がある理由：対策にもコストがある。発生頻度が極小なら、予防の常時オーバーヘッドより「起きたら直す」方が合理的なこともある（エンジニアリングの割り切り）。

⚠️ よくある誤解・落とし穴

「デッドロック＝プログラムが落ちる」→ 落ちずに固まる（無応答）。CPUは0%なのに進まない、が典型症状。
「ロックを増やせば安全」→ ロックが増えるほど取得順序の食い違いが生まれデッドロックしやすい。順序規約が要る。
「ライブロックは同じもの」→ 別物。ライブロックは「互いに譲り合って前進しない」（CPUは動いているが進まない）。
「タイムアウトを付ければ解決」→ 検出はできるが、闇雲な再試行は並行性のパターンのライブロックを招きうる。根本は順序設計。

対応ラボ

cs-foundations-study/labs/04-03_deadlock.py（実行して逆順での停止と、順序統一での回避を確認済み）。