待ちグラフとは？

待ちグラフの意味

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

待ちグラフの具体例

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

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

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

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

• デッドロック

待ちグラフが出た過去問

• トランザクションA〜Gの待ちグラフにおいて、永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで、待ちグラフのX→Yは、トランザクション…

  正解：B, C, D, F

  要点：待ちグラフの閉路と、そこへ待ちが連なるものが永久待ち

  永久待ちになるのは、待ちグラフの閉路に含まれるトランザクションと、その閉路に向かって待っているトランザクションである。この待ちグラフではB→D→C→Bという閉路が成立しており、B・C・Dは互いのアンロックを待ち続ける。さらにFはDのアンロックを待っているため、Dが永久に解放されない以上Fも永久待ちとなる。

  出典：平成29年度 秋期 応用情報技術者試験 午前 問29（IPA）