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

待ちグラフ【午前2解説】

正解の理由

解法ステップ

1. 問題文のキーワード「デッドロック検出」に注目する。
2. 各選択肢が何を表すかを把握する：
   • 資源割当表：割当状況の記録（表形式）
   • 時刻印順管理表：タイムスタンプ順制御の記録
   • 優先順管理表：優先度や順序の管理
   • 待ちグラフ：トランザクション間の待ち関係をグラフ化
3. デッドロック検出は「待ち関係の循環」を調べることなので、待ち関係を直接表現できる「待ちグラフ」を選ぶ。

選択肢別の誤答解説

• ア: 資源割当表
  • 単なる表（割当状況のリスト）は誰が誰を待っているかを直ちに示さないため、直接のサイクル検出には不向きです。ただし、資源とトランザクションをノードとした資源割当グラフ（Resource Allocation Graph, RAG）に変換すれば、サイクル検出によりデッドロック検出が可能です。よって「資源割当表は全く使えない」との誤解は避ける必要があります。
• イ: 時刻印順管理表
  • タイムスタンプ順方式は競合の解決・再実行方針に関わる記録であり、直接デッドロックの検出に用いるものではありません。
• ウ: トランザクションの優先順管理表
  • 優先順はスケジューリングやプリエンプションに関する情報で、デッドロックの構造（循環）を表す手段ではありません。
• エ: 待ちグラフ
  • トランザクション間の「待ち」関係を有向辺で表し、サイクル検出によってデッドロックの存在を判定できるため正解です。

よくある誤解

• 資源割当表は「全く役に立たない」
  • 単なる表形式の資源割当表だけでは直接サイクル検出が難しいことは事実ですが、RAG（資源とトランザクションをノードとするグラフ）や待ちグラフに変換すればデッドロック検出が可能です。
• サイクル＝必ずデッドロック（資源が複数インスタンスのとき）
  • 資源が複数インスタンスある場合、RAGでのサイクルが即デッドロックを意味しない場合があります（追加のチェックが必要）。ただし、待ちグラフ（トランザクション間の直接的な待ち関係）であればサイクルはデッドロックを意味します。
• デッドロックは常に防止すべきで検出は不要
  • 実運用では防止・回避・検出＋回復のいずれかを選択することが多く、検出手法（待ちグラフによる監視）は実用的かつ頻用されます。

補足コラム

• 待ちグラフの構造
  • 待ちグラフ（wait-for graph）：ノードがトランザクション、辺は「Ti が Tj の保持している資源を待っている」ことを表す。サイクルの有無でデッドロック判定。
  • 資源割当グラフ（RAG）：トランザクションノードと資源ノードを両方持ち、資源からトランザクションへは割当（割り当て）辺、トランザクションから資源へは要求（Request）辺を引く。単一インスタンス資源ならRAGのサイクル＝デッドロック。
• 検出アルゴリズム例
  • 深さ優先探索（DFS）でサイクルを検出する方法が一般的で、時間計算量は $O(V+E)$。Tarjanの強連結成分アルゴリズムも利用可能です。
• 回復方法
  • デッドロック検出後はトランザクションの巻き戻し（ロールバック）や強制終了などで循環を解消します。

def has_cycle(graph):
    # graph: {node: [neighbors]}
    visited, stack = set(), set()
    def dfs(v):
        visited.add(v); stack.add(v)
        for w in graph.get(v, []):
            if w not in visited:
                if dfs(w): return True
            elif w in stack:
                return True
        stack.remove(v)
        return False
    return any(dfs(v) for v in graph if v not in visited)

FAQ