コンピューターサイエンス：アルゴリズム / OS / ネットワーク / DB
デッドロック
デッドロック
このレッスンで分かること
- デッドロックは「複数のスレッドが 互いに相手の持つロックを待ち合う ことで永久停止する状態」です
- 成立には 4 つの必要条件（相互排除、保持と待機、横取り不可、循環待ち）がすべて揃う必要があります
- 防止策は「ロック獲得順序を固定する」「タイムアウト付き取得」「リソースをまとめて確保」など複数あります
デッドロック とは
デッドロック。本レッスンでは、デッドロック の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
どんな状態か
スレッド A が「ロック X を持ったまま Y を欲しがる」、同時にスレッド B が「ロック Y を持ったまま X を欲しがる」――この瞬間、両者とも相手が手放すまで動けません。動かなければ手放さない、というデッドループが完成します。
Python
import threading
import time
lock_a = threading.Lock()
lock_b = threading.Lock()
def task1():
with lock_a:
time.sleep(0.1)
with lock_b: # task2 が持っていれば永遠に待つ
pass
def task2():
with lock_b:
time.sleep(0.1)
with lock_a: # task1 が持っていれば永遠に待つ
pass
t1 = threading.Thread(target=task1)
t2 = threading.Thread(target=task2)
t1.start()
t2.start()
t1.join()
t2.join()図解
矢印が 循環 している状態が成立要件です。デッドロックの検出は、待ちグラフのサイクル検出問題と言い換えられます。
4 つの必要条件（Coffman 条件）
| 条件 | 説明 | 破る策の例 |
|---|---|---|
| 相互排除 | 資源は同時に 1 人しか使えない | 読み取り共有資源にする |
| 保持と待機 | 何か持ったまま別を待つ | 全部一度にまとめて取る |
| 横取り不可 | 強制的に取り上げられない | タイムアウトでロールバック |
| 循環待ち | 待ちの輪ができる | ロック取得順序の固定 |
4 つすべてが成立しないとデッドロックは起きません。逆に言えば、どれか 1 つを潰せば防げます。
防止策
ロック取得順序を固定する
「常にアルファベット順、ID 順、アドレス順に取る」というルールを全コードで守れば、循環待ちは生じません。
Python
def transfer(account_a, account_b, amount):
first, second = sorted([account_a, account_b], key=lambda x: x.id)
with first.lock:
with second.lock:
account_a.balance -= amount
account_b.balance += amountタイムアウト付き取得
lock.acquire(timeout=2) で 2 秒待っても取れなければ諦める → ロールバックしてリトライ。データベースのトランザクションでよく使われます。
Try-Lock パターン
Python
if lock_b.acquire(blocking=False):
try:
...
finally:
lock_b.release()
else:
# 取れなかったのでロック X を一旦手放してリトライ
...デッドロックを発見する道具
- gdb で全スレッドのスタックトレース を取る
thread apply all bt jstack（Java） で各スレッドの待ち状態をダンプpstackやpy-spy（Python） で実行中のスタックを覗く- データベースは デッドロック検出機能 を内蔵し、犠牲者を選んでロールバックする
関連現象
| 名前 | 違い |
|---|---|
| ライブロック | 互いに譲り合いを繰り返して進まない（廊下で右に避けたら相手も右、左に避けたら相手も左の繰り返し） |
| スターベーション（飢餓） | 優先度の低いスレッドが永久に資源を取れない |
| 優先度逆転 | 低優先度がロックを持ち、中優先度が CPU を独占し、高優先度が待たされる |
火星探査機 Pathfinder（1997）が優先度逆転でリセットを繰り返したのは有名な事故です。
トレードオフ
- ロック獲得順序の徹底は確実ですが、コード上の制約が増えます。複雑な分散システムでは「ロックが分散している」ため徹底が難しい
- タイムアウトは万能薬に見えますが、復旧ロジック（ロールバック・リトライ）の設計コストがかかります
よくある誤解
- 「ロックを 1 つしか使わなければデッドロックは起きない」――半分正解で、同じロックを再度取ろうとする 自己デッドロック（再入不可ロックで自分自身が止まる）が存在します。再入可能ロック（reentrant mutex）なら回避できます
- 「分散システムにもデッドロックがある」――その通りです。分散ロックは検出が更に難しく、Zookeeper や etcd で順序を強制する設計が普及しています
やってみよう
冒頭の Python サンプルを python -X faulthandler スクリプト名.py で起動してください。デッドロックで停止したら別ターミナルから kill -SIGUSR1 <PID> を送ると、faulthandler が全スレッドのスタックトレースを stderr に出力し、両スレッドが acquire で止まっていることが見えます。または py-spy dump --pid <PID> でも同様に確認できます。次に取得順を sorted で固定するとデッドロックが消えるのを確認しましょう。
よくある質問
Q. デッドロックを未然に防ぐには？
A. ロック取得順を全コードで統一する、トランザクションを短くする、ロック数を最小化する、タイムアウトを設定するなどが定石です。DB なら SELECT FOR UPDATE の順番を主キー昇順にそろえると衝突確率が大きく下がります。
Q. デッドロックが起きたら DB はどうしますか？
A. MySQL/PostgreSQL は片方のトランザクションを自動でロールバックして解消します。アプリは ERROR 1213 / SerializationFailure を catch して、指数バックオフで再試行する実装が定石です。再試行回数の上限を必ず設けてください。
Q. ロック粒度はどうやって決めますか？
A. 粗いロック（テーブル全体）は競合が増え、細かいロック（行レベル）は管理コストが増えます。OLTP は行ロック、バッチ処理はテーブルロックという使い分けが一般的です。負荷テストで競合率を計測しながら段階的に細かくしていくのが現実的です
次のレッスン
次は 非同期と並行 で、デッドロック を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- デッドロック の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. デッドロック とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン