データベーススペシャリスト 2024年 午前2 問13
問題文
トランザクションA~Gの待ちグラフにおいて、永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで、待ちグラフのX→Yは、トランザクションXはトランザクションYがロックしている資源のアンロックを待っていることを表す。
選択肢
ア：A, B, C, D
イ：B, C, D
ウ：B, C, D, F（正解）
エ：C, D, E, F, G
トランザクションの待ちグラフにおける永久待ち判定【午前2 解説】
要点まとめ
- 結論：永久待ちは待ちグラフに存在するサイクルに含まれるトランザクション全てで発生する。
- 根拠：待ちグラフのサイクルは互いに資源の解放を待つ状態を示し、これが永久待ち（デッドロック）を意味する。
- 差がつくポイント：サイクルの検出と、サイクルに含まれないノードを誤って永久待ちと判断しないことが重要。
正解の理由
問題の待ちグラフを解析すると、トランザクションB→D→E→Gの流れは直線的でサイクルを形成していません。一方、トランザクションCはAとBを待ちつつ、BはDを待ち、DはEを待ち、EはGを待つため、これらはサイクルを形成しません。
しかし、トランザクションF→Dの矢印と、D→E→Gの流れを考慮すると、FがDを待ち、DがEを待ち、EがGを待つため、ここにもサイクルはありません。
よって、サイクルを形成しているのはB、C、D、Fの4つのトランザクションであり、これらが永久待ち状態にあると判断できます。
したがって、選択肢ウ「B, C, D, F」が正解です。
しかし、トランザクションF→Dの矢印と、D→E→Gの流れを考慮すると、FがDを待ち、DがEを待ち、EがGを待つため、ここにもサイクルはありません。
よって、サイクルを形成しているのはB、C、D、Fの4つのトランザクションであり、これらが永久待ち状態にあると判断できます。
したがって、選択肢ウ「B, C, D, F」が正解です。
よくある誤解
永久待ちは単に「待っている」状態ではなく、待ちグラフにおける「サイクルの存在」が必須条件です。サイクルがない場合は永久待ちとは言えません。
解法ステップ
- 待ちグラフのノードと矢印を整理し、各トランザクションの待ち関係を把握する。
- グラフ上でサイクル（閉路）が存在するかを探索する。
- サイクルに含まれる全トランザクションを特定する。
- サイクルに含まれないトランザクションは永久待ちではないと判断する。
- サイクルに含まれるトランザクションを選択肢と照合し、正解を選ぶ。
選択肢別の誤答解説
- ア: A, B, C, D
→ AはCから待たれているが、サイクルには含まれていないため永久待ちではない。 - イ: B, C, D
→ FがDを待っているため、Fもサイクルに含まれる可能性がある。Fを除外しているのは誤り。 - ウ: B, C, D, F
→ 正解。B, C, D, Fがサイクルを形成し、永久待ち状態にある。 - エ: C, D, E, F, G
→ EとGはサイクルに含まれておらず、永久待ちではない。誤り。
補足コラム
待ちグラフはデッドロック検出の基本ツールであり、トランザクション間の資源待ち関係を有向グラフで表現します。サイクル検出アルゴリズム（深さ優先探索など）を用いることで、効率的に永久待ちを判定可能です。デッドロック回避や検出はデータベースやOSの資源管理で重要な技術です。
FAQ
Q: 永久待ちと一時的な待ちの違いは何ですか？
A: 永久待ちはサイクルにより資源解放が永久に待たれる状態で、一時的な待ちは資源が解放されれば進行可能な状態です。
A: 永久待ちはサイクルにより資源解放が永久に待たれる状態で、一時的な待ちは資源が解放されれば進行可能な状態です。
Q: 待ちグラフにサイクルがなければ永久待ちは起きませんか？
A: はい。サイクルがなければ永久待ちは発生しません。待ちグラフのサイクル検出が永久待ち判定の基本です。
A: はい。サイクルがなければ永久待ちは発生しません。待ちグラフのサイクル検出が永久待ち判定の基本です。
関連キーワード: デッドロック、待ちグラフ、トランザクション管理、サイクル検出、資源競合
\ せっかくなら /
データベーススペシャリストを
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！