応用情報技術者 2017年 秋期 午前2 問29
問題文
トランザクション A〜Gの待ちグラフにおいて、永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで、待ちグラフの X→Y は、トランザクションXはトランザクション Yがロックしている資源のアンロックを待っていることを表す。
選択肢
ア：A, B, C, D
イ：B, C, D
ウ：B, C, D, F（正解）
エ：C, D, E, F, G
トランザクションA～Gの待ちグラフ【午前2 解説】
要点まとめ
- 結論：永久待ち（デッドロック）状態にあるトランザクションは、B, C, D, Fである。
- 根拠：待ちグラフのサイクル（閉路）が存在するノードが永久待ちの対象であり、B→D→C→BのサイクルとF→E→Gの関係からFも含む。
- 差がつくポイント：サイクルの有無だけでなく、待ち関係の連鎖を正確に読み取り、どのトランザクションがアンロック待ちかを見極めることが重要。
正解の理由
待ちグラフにおいて、永久待ち（デッドロック）はサイクルが存在するトランザクション群に限定されます。
左クラスターのB→D→C→Bは明確なサイクルで、これら3つは永久待ちです。
右クラスターではF→E→Gの矢印がありますが、EとGはサイクルに含まれず、FはEのアンロックを待っているため、Fも永久待ちに含まれます。
したがって、B, C, D, Fが永久待ちのトランザクションです。
左クラスターのB→D→C→Bは明確なサイクルで、これら3つは永久待ちです。
右クラスターではF→E→Gの矢印がありますが、EとGはサイクルに含まれず、FはEのアンロックを待っているため、Fも永久待ちに含まれます。
したがって、B, C, D, Fが永久待ちのトランザクションです。
よくある誤解
- サイクルに含まれないノードは永久待ちに含まれないと誤解しがちですが、待ち関係の連鎖で待たされているトランザクションも含まれます。
- 右クラスターのFが永久待ちに含まれる点を見落とすことが多いです。
解法ステップ
- 待ちグラフの矢印を確認し、トランザクション間の待ち関係を把握する。
- サイクル（閉路）が存在するかを探し、該当ノードを特定する。
- サイクルに含まれないが、サイクルのノードや待ち状態に影響されるトランザクションを検討する。
- 永久待ちのトランザクションをリストアップし、選択肢と照合する。
選択肢別の誤答解説
- ア: A, B, C, D
→ Aはサイクルに含まれておらず、永久待ちではないため誤り。 - イ: B, C, D
→ Fを含めていないため、右クラスターの待ち状態を見落としている。 - ウ: B, C, D, F
→ 正解。サイクルと待ち連鎖を正しく捉えている。 - エ: C, D, E, F, G
→ Bが抜けており、B→D→Cのサイクルを正しく認識できていない。
補足コラム
待ちグラフはデータベースやOSの資源管理で重要な概念です。
永久待ち（デッドロック）は、複数のトランザクションが互いに資源の解放を待ち続ける状態で、システムの停止や性能低下を招きます。
検出にはグラフのサイクル検出アルゴリズム（DFSなど）が用いられます。
永久待ち（デッドロック）は、複数のトランザクションが互いに資源の解放を待ち続ける状態で、システムの停止や性能低下を招きます。
検出にはグラフのサイクル検出アルゴリズム（DFSなど）が用いられます。
FAQ
Q: 永久待ちとサイクルの関係は？
A: 永久待ちは待ちグラフにサイクルが存在する場合に発生し、サイクル内のトランザクションは互いに資源を待ち続けます。
A: 永久待ちは待ちグラフにサイクルが存在する場合に発生し、サイクル内のトランザクションは互いに資源を待ち続けます。
Q: サイクルに含まれないトランザクションも永久待ちになることは？
A: 直接のサイクルに含まれなくても、サイクル内のトランザクションが解放しない資源を待っている場合、永久待ちに含まれます。
A: 直接のサイクルに含まれなくても、サイクル内のトランザクションが解放しない資源を待っている場合、永久待ちに含まれます。
関連キーワード: 待ちグラフ、デッドロック、永久待ち、トランザクション、資源管理、サイクル検出
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！