待ちグラフとは？

待ちグラフの意味

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

待ちグラフの具体例

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

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

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

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

• デッドロック

待ちグラフが出た過去問

• DBMSにおいて、トランザクション間でデッドロックが発生していることを検出するために使用するものはどれか。

  正解：待ちグラフ

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

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

  出典：平成28年度 春期 データベーススペシャリスト試験 am2 問13（IPA）

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

  正解：待ちグラフ

  要点：待ちグラフの閉路がデッドロックの判定材料になる

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

  出典：平成30年度 春期 データベーススペシャリスト試験 am2 問16（IPA）

• t1〜t10の時刻でスケジュールされたトランザクションT1〜T4がある。時刻t10でT1がcommitを発行する直前の、トランザクションの待ちグラフを作成した。…

  正解：T2

  要点：専有ロック要求が既存の共有ロックの解放を待つ関係を辺にする

  共有ロックのままなら共存できるが、専有ロックを掛けようとすると他者の共有ロックの解放を待つことになる。BへのT4の更新はT2の共有ロックを、CへのT2の更新とAへのT3の更新はいずれもT1の共有ロックを待つ。したがって待ちの向きはT4→T2、T2→T1、T3→T1となり、矢印を1本出しつつ1本受けている位置に入るのはT2である。

  出典：令和1年度 春期 データベーススペシャリスト試験 am2 問10（IPA）

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

  正解：B, C, D, F

  要点：永久待ちは待ちグラフの閉路とそこへ到達する待ち全部

  待ちグラフに閉路があると、その閉路上のトランザクションは互いのアンロックを待ち続けるためデッドロックとなる。さらに、閉路上のトランザクションを待っているトランザクションも、閉路が解消されない限り永久に待たされる。したがって永久待ちは閉路の構成メンバーと、そこへ到達する矢印を持つものの合計になる。閉路に含まれず一方向に待つだけのものは、いずれ解放されるので永久待ちではない。

  出典：令和6年度 秋期 データベーススペシャリスト試験 am2 問13（IPA）

• DBMSにおいて、トランザクション間でデッドロックが発生していることを検出するために使用するものはどれか。

  正解：待ちグラフ

  要点：デッドロックの検出は待ちグラフの閉路で判定する

  待ちグラフは、各トランザクションをノードとし、あるトランザクションが別のトランザクションの保持するロックの解放を待っている関係を辺として表した有向グラフである。このグラフに閉路が現れれば、互いに待ち合って進めない状態、すなわちデッドロックが発生していると判定できる。検出後はいずれかを強制終了して閉路を断つ。

  出典：令和7年度 秋期 データベーススペシャリスト試験 am2 問17（IPA）