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

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

ア：資源割当表

イ：時刻印順管理表

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

エ：待ちグラフ（正解）

解説

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

要点まとめ

結論：デッドロック検出には「待ちグラフ」が用いられます。
根拠：待ちグラフはトランザクション間の資源の待ち関係を有向グラフで表現し、サイクル検出でデッドロックを判定します。
差がつくポイント：資源割当表や時刻印順管理表は管理目的が異なり、デッドロック検出には直接使われません。

正解の理由

デッドロックは複数のトランザクションが互いに相手の資源解放を待つ状態で、これを検出するにはトランザクション間の待ち関係を明示的に表現する必要があります。待ちグラフはノードにトランザクションを、エッジに「待ち」の関係を示し、グラフにサイクルが存在すればデッドロックと判定します。したがって、デッドロック検出に最適なデータ構造は「待ちグラフ」です。

よくある誤解

資源割当表は資源の割当状況を示すだけで、待ち関係の循環を検出できません。時刻印順管理表はトランザクションの順序管理に使われ、デッドロック検出とは直接関係ありません。

解法ステップ

デッドロックの定義を確認する（トランザクション間の相互待ち状態）。
デッドロック検出に必要な情報は「誰が誰を待っているか」の関係であると理解する。
それを表現できるデータ構造を選択肢から探す。
待ちグラフはトランザクションをノード、待ち関係をエッジで表現し、サイクル検出が可能。
よって「待ちグラフ」が正解と判断する。

選択肢別の誤答解説

ア: 資源割当表
資源の割当状況を示す表で、待ち関係の循環検出には不向きです。
イ: 時刻印順管理表
トランザクションの実行順序を管理するためのもので、デッドロック検出には使いません。
ウ: トランザクションの優先順管理表
優先度管理に関するもので、待ち関係の循環検出とは無関係です。
エ: 待ちグラフ
トランザクション間の待ち関係をグラフで表し、サイクル検出でデッドロックを判定できるため正解です。

補足コラム

デッドロック検出はDBMSの並行制御で重要な役割を果たします。待ちグラフにサイクルがある場合、どのトランザクションを中断するかを決める「デッドロック回復」処理も必要です。これによりシステムの停止や性能低下を防ぎます。

FAQ

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

Q: デッドロック回避と検出の違いは何ですか？
A: 回避はデッドロックが起きないように事前に資源割当を制御し、検出は発生後にサイクルを見つけて対処します。

関連キーワード: デッドロック, 待ちグラフ, 並行制御, トランザクション管理, DBMS

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

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

解説