教授、情報処理技術者試験で「待ちグラフ」というものが出てきたのですが・・
待ちグラフはデッドロックを見抜くための定番ツールだね。
トランザクションを点で、待ち関係を矢印で表すだけのシンプルなものだ。
シンプルですね！
ポイントは「循環（サイクル）があるかどうか」だけ。
試験では必ず得点しよう！
第1章：待ちグラフとは何か？
「グラフ」とは？
待ちグラフの説明に入る前に、まず「グラフ」という言葉について確認しましょう。
多くの人は「グラフ」と聞くと、折れ線グラフや棒グラフを思い浮かべるでしょう。
しかし、待ちグラフの「グラフ」は数学のグラフ理論で使われる用語です。
グラフ理論におけるグラフとは、点（ノード）と線（辺）で構成される図形のことです。
これは統計データを表示するグラフとは全く別の概念になります。
トランザクションとノードの関係
待ちグラフとは、データベースにおけるトランザクション同士の「待ち関係」をグラフで表現したものです。
グラフ上では、各トランザクションを「ノード（点）」として表します。
たとえば T1、T2、T3 といったトランザクションが存在すると、それぞれが 1 つのノードになります。
待ち状態を矢印で表す仕組み
ノード同士の関係は「矢印（有向辺）」で示します。
具体的には、トランザクション T1 がトランザクション T2 のロック解放を待っている場合、
T1 → T2 という矢印を描きます。この矢印は「T1 は T2 に依存している」という意味になります。
第2章：待ちグラフでデッドロックを検出する
循環があるかどうかが判断のカギ
待ちグラフを用いたデッドロック検出では、循環（サイクル）の有無が最も重要なポイントです。
グラフの中で矢印がぐるりと一周して元のノードに戻る関係が存在すれば、
それはデッドロックを意味します。
逆に、循環が存在しない場合、処理は問題なく進行します。
サイクル検出の具体例
例を挙げてみましょう。
– T1 → T2、T2 → T3 の場合
：循環は存在せず、T3 が処理を終えて資源を解放すれば T2、続いて T1 が進めるため、デッドロックにはなりません。
– T1 → T2、T2 → T3、T3 → T1の場合
：T1 が T2 、T2がT3、T3がT1を待っているため、循環が発生しデッドロックとなります。
試験での問われ方と対策
待ちグラフに関する問題は、各情報処理技術者試験で頻出です。
単に知識として覚えるだけでなく、「図を見てすぐにサイクルを発見できる」 実践力が求められます。
データベーススペシャリスト試験では、午後問題で取り上げられることもあります。
4-1. 出題パターン
- 待ちグラフが与えられる形式
- ノードと矢印で描かれたグラフを見て、
「永久待ちのトランザクション」を判定させる。
- ノードと矢印で描かれたグラフを見て、
- 用語形式
- デッドロックの判定に使われるもの ⇒ 待ちグラフ
を答えさせる。
- デッドロックの判定に使われるもの ⇒ 待ちグラフ
- 一番オーソドックスな例 (解答は4-2へ)
トランザクションA~Gの待ちグラフにおいて, 永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで, 待ちグラフのX→Yは, トランザクションXはトランザクションYがロックしている資源のアンロックを待っていることを表す。
令和6年秋期 午前2 問13
4-2. 回答の鉄則
- サイクルがある → デッドロック発生
- サイクルがない → デッドロックではない
これを明確に言い切れるようにしておくことが重要です。
4-1-3の問題については、
上図のように、B,C,Dでサイクルがあります。
そのため、B,C,Dでデッドロックが発生しています。
Fはデッドロックが発生しているDの資源開放を待つので、いつまでも獲得できません。
よって解答はB,C,D,Fとなります。
4-3. 効率的な対策法
- ステップごとに確認
- 矢印を1つずつたどり、ぐるっと戻るかどうかを確認する
- サイクルを見つけたら「即デッドロック」と判断してよい
- 練習問題で慣れる
過去問を数問解くだけで、「この形はデッドロックだ」とパターン認識できるようになります。
まとめ
待ちグラフは「理屈としての理解」よりも「図で素早く見抜く力」が試験突破に直結します。
データベーススペシャリストの午後試験で問われやすいのは次の2点です
- 待ちグラフを正しく描けるか
- サイクルを発見してデッドロックを判定できるか
ここまでを押さえれば、待ちグラフ問題は得点源にできます！
