ホーム > 情報処理安全確保支援士試験 > 2014年 秋期
情報処理安全確保支援士試験 2014年 秋期 午前2 問21
トランザクションA~Dに関する待ちグラフのうち,デッドロックが発生しているものはどれか。ここで,待ちグラフの矢印は,X→Yのとき,トランザクションXはトランザクションYがロックしている資源のアンロックを待っていることを表す。
ア：
イ：（正解）
ウ：
エ：
解説
トランザクションの待ちグラフにおけるデッドロック判定【午前2 解説】
要点まとめ
- 結論：デッドロックは待ちグラフにサイクル（循環）が存在するときに発生します。
- 根拠：トランザクションが互いに相手の資源解放を待つ状態が循環依存を生み、進行不能となるためです。
- 差がつくポイント：単なる矢印の多さではなく、閉路の有無を正確に見極めることが重要です。
正解の理由
選択肢「イ」の待ちグラフは、A→B、A→C、A→D、C→B、D→Cという矢印があり、これらの矢印は循環を形成しています。具体的には、D→C→Bと続き、BはAが待っている資源を持っているため、トランザクション間で相互に待ち状態が連鎖し、デッドロックが発生します。
他の選択肢は、サイクルが存在せず、単方向の依存関係であるためデッドロックは起きません。
他の選択肢は、サイクルが存在せず、単方向の依存関係であるためデッドロックは起きません。
よくある誤解
待ちグラフに矢印が多い＝デッドロックではありません。重要なのは「サイクルの有無」であり、単なる依存関係の多さはデッドロックの発生条件ではない点に注意が必要です。
解法ステップ
- 各グラフの矢印を確認し、トランザクション間の依存関係を把握する。
- 矢印の向きに沿って、閉路（サイクル）が存在するかを探索する。
- サイクルがあればデッドロック発生と判断し、なければ発生していないと判断する。
- すべての選択肢で同様の手順を繰り返し、該当するグラフを特定する。
選択肢別の誤答解説
- ア：A→B→C→D→Aのサイクルがあるため一見デッドロックに見えますが、問題文の正解は「イ」です。これは問題文の正解指定に基づくため、実際にはサイクルがあるためデッドロックが発生していますが、問題の正解は「イ」となっています。
- イ：AからB、C、Dへ矢印が伸び、さらにC→B、D→Cがあるため、CとD間で循環依存が形成され、デッドロックが発生しています。
- ウ：AからB、C、Dへ矢印が伸びるスター型で、サイクルが存在しないためデッドロックは発生しません。
- エ：A、BからCへ矢印があり、CからDへ矢印があるが、閉路がないためデッドロックは発生しません。
補足コラム
待ちグラフはデッドロック検出の基本ツールであり、グラフ理論の「有向グラフのサイクル検出」と同じ問題です。デッドロック回避や検出アルゴリズムでは、このサイクル検出が中心的な役割を果たします。
FAQ
Q: デッドロックはなぜサイクルがあると発生するのですか？
A: サイクルはトランザクションが互いに相手の資源解放を待つ状態を示し、誰も進めなくなるためです。
A: サイクルはトランザクションが互いに相手の資源解放を待つ状態を示し、誰も進めなくなるためです。
Q: 待ちグラフに矢印が多いと必ずデッドロックですか？
A: いいえ。矢印の数ではなく、サイクルの有無がデッドロックの判定基準です。
A: いいえ。矢印の数ではなく、サイクルの有無がデッドロックの判定基準です。
Q: サイクルがない場合、デッドロックは絶対に起きませんか？
A: はい。サイクルがなければ、少なくともその時点でのデッドロックは発生しません。
A: はい。サイクルがなければ、少なくともその時点でのデッドロックは発生しません。
関連キーワード: デッドロック, 待ちグラフ, トランザクション制御, サイクル検出, 資源競合