データベーススペシャリスト試験 2010年午前2 問17

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

ア：資源割当表

イ：時刻印順管理表

ウ：トランザクションの優先順管理表

エ：待ちグラフ（正解）

解説

DBMSにおけるデッドロック検出のためのデータ構造【午前2 解説】

要点まとめ

結論：デッドロック検出には「待ちグラフ」が用いられます。
根拠：待ちグラフはトランザクション間の資源の待ち関係を表現し、循環があればデッドロックと判定可能です。
差がつくポイント：資源割当表や時刻印順管理表は資源管理やスケジューリングに使われ、デッドロック検出には直接関係しません。

正解の理由

デッドロックは複数のトランザクションが互いに相手の資源解放を待っている状態で、これを検出するにはトランザクション間の「待ち関係」を可視化する必要があります。待ちグラフはノードにトランザクションを、エッジに「待ち」を表し、グラフに循環（サイクル）が存在するかを調べることでデッドロックの有無を判定します。したがって、デッドロック検出に最も適したデータ構造は「待ちグラフ」です。

よくある誤解

資源割当表は資源の割当状況を示すため、デッドロックの検出には使えないと誤解されがちです。時刻印順管理表はスケジューリングの整合性維持に用いられ、デッドロック検出とは役割が異なります。

解法ステップ

デッドロックの定義を理解する（複数トランザクションが互いに資源を待つ状態）。
デッドロック検出に必要な情報は「誰が誰を待っているか」の関係であると認識する。
待ち関係を表現できるデータ構造を選ぶ。
選択肢の中で「待ちグラフ」が待ち関係を表現するグラフ構造であることを確認する。
待ちグラフの循環検出がデッドロック検出の基本手法であることを踏まえ、正解を選ぶ。

選択肢別の誤答解説

ア: 資源割当表
資源の割当状況を示す表であり、待ち関係や循環検出には不向きです。
イ: 時刻印順管理表
トランザクションの実行順序管理に使われ、デッドロック検出の役割はありません。
ウ: トランザクションの優先順管理表
優先度によるスケジューリングに関するもので、デッドロック検出には直接関係しません。
エ: 待ちグラフ
トランザクション間の待ち関係をグラフで表し、循環検出によりデッドロックを判定できるため正解です。

補足コラム

待ちグラフはデッドロック検出の代表的な手法ですが、実際のDBMSでは検出だけでなく回避や予防のためのアルゴリズムも併用されます。例えば、資源割当表と待ちグラフを組み合わせて効率的に管理することもあります。また、デッドロック回避では「銀行家アルゴリズム」などの理論的手法も知られています。

FAQ

Q: 待ちグラフの循環検出はどのように行いますか？
A: 深さ優先探索（DFS）などのグラフ探索アルゴリズムでサイクルの有無を判定します。

Q: 資源割当表と待ちグラフはどう違いますか？
A: 資源割当表は資源の割当状況を示す表で、待ちグラフはトランザクション間の待ち関係を表すグラフ構造です。

関連キーワード: デッドロック, 待ちグラフ, トランザクション管理, DBMS, 資源割当表, 時刻印順, デッドロック検出

← 前の問題へ次の問題へ →

データベーススペシャリスト試験 2010年 午前2 問17

解説