待ちグラフとは？

待ちグラフの意味

トランザクションをノード、「AがBの保持するロックの解放を待っている」関係を有向辺として表した図。閉路があればデッドロックが生じている。

待ちグラフの具体例

T1→T2→T3→T1という閉路を検出したら、いずれかを強制的にロールバック（犠牲者選択）して解消する。

待ちグラフは試験でどう引っ掛けられる？

待ちグラフはデッドロックの検出の手法であって、予防（回避）ではない。予防側はタイムスタンプ順に待つか殺すかを決める方式（wait-die／wound-wait）や、資源への一方向の順序付け。閉路が「あれば」デッドロックであり、辺があるだけでは何も起きていない。

待ちグラフと関連する用語

• デッドロック

待ちグラフが出た過去問

• 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となる。

  出典：令和4年度 春期 システムアーキテクト試験 am2 問24（IPA）

• DBMS において、デッドロックを検出するために使われるデータ構造はどれか。

  正解：待ちグラフ

  要点：待ちグラフの閉路の有無でデッドロックを検出する

  待ちグラフは、トランザクションを頂点とし、あるトランザクションが別のトランザクションの保持するロックの解放を待っている関係を有向辺で表したものである。このグラフに閉路が現れれば互いに待ち合う状態、すなわちデッドロックが発生していると判定できる。

  出典：令和6年度 春期 システムアーキテクト試験 am2 問24（IPA）