待ちグラフとは？まちグラフ
待ちグラフとは、デッドロックが起きているかどうかを、人の見当ではなく閉路の有無という機械判定に落とすための図。各トランザクションを点、「先に確保された資源の解放を待っている」関係を矢印で表し、矢印をたどって元へ戻れる経路があれば互いに待ち合っている。DBMSが周期的に走らせる検出処理の内部表現でもある。
最終更新：2026-10-06
この語が出る過去問を解く →背景
ロックは同時実行の正しさを守るが、確保の順序を各処理が勝手に決めると待ちが輪になり、正しさを守った結果として誰も進めなくなる。起こりうる組合せを事前に全部禁じると並行度が落ちるため、多くのDBMSは起きてから直す方針を採り、その判定手段として待ち状態をグラフへ写す。設計側は、どちらが巻き戻されても業務が破綻しない作りにしておく必要がある。
具体例
PostgreSQLはロック待ちが deadlock_timeout（既定1秒）を超えると待ち状態を検査し、輪を見つけると片方のトランザクションを中断してエラーを返す。アプリケーション側は、このエラーを検知して同じ処理を再実行する作りにしておく。
試験での引っ掛け
検出の道具であって回避策ではない点。回避側はタイムスタンプで待つか殺すかを決める wait-die／wound-wait や、資源に一意な順序を決めて全員が同じ向きに確保する規約。矢印が引かれているだけなら正常な待ちで、閉路になって初めてデッドロックである。
関連用語
出た過去問
出典：令和4年度 春期 システムアーキテクト試験 午前Ⅱ 問24（IPA）
t1～t10の時刻でスケジュールされたトランザクションT1～T4がある。時刻t10でT1がcommitを発行する直前の、トランザクションの待ちグラフを作成した。…
正解：T2
要点：待ちグラフは各資源のロック保持者と待機者の関係から決まる
各資源のロック状態を時系列で追うと、AはT1とT4が共有ロック、BはT2とT3が共有ロック、CはT1とT2が共有ロックを保持する。その後、T4のupdate(B)はT2とT3を待ち、T2のupdate(C)はT1を待ち、T3のupdate(A)はT1とT4を待つ。待ちの矢印が出ておらず二つ流入する頂点がT1（図のd）、そこへ向かう矢印を1本だけ出しつつ1本受ける頂点がT2であり、aはT2となる。
出典：令和6年度 春期 システムアーキテクト試験 午前Ⅱ 問24（IPA）
DBMS において、デッドロックを検出するために使われるデータ構造はどれか。
正解：待ちグラフ
要点：待ちグラフの閉路の有無でデッドロックを検出する
待ちグラフは、トランザクションを頂点とし、あるトランザクションが別のトランザクションの保持するロックの解放を待っている関係を有向辺で表したものである。このグラフに閉路が現れれば互いに待ち合う状態、すなわちデッドロックが発生していると判定できる。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。