データベーススペシャリスト 2016年 午前2 問13

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

正解の理由

解法ステップ

1. 問題が「デッドロックの検出」を求めていることを確認する。
2. 各選択肢の目的を素早く整理する：ロック方式（2相ロック）、時刻方式（タイムスタンプ）、チェックポイント（リカバリ用）、待ちグラフ（待機関係を表現）。
3. 「検出」に直結するのは「待機関係を可視化しサイクルを確認する手法」であると判断する。
4. よって待ちグラフ（エ）を選ぶ。

選択肢別の誤答解説

• ア: 2相ロック（2PL）
  2相ロックはロックの「成長相」と「収縮相」によって直列化（serializability）を保証するロックプロトコルです。重要点として、2相ロックはデッドロックを必ず防ぐものではなく、むしろデッドロックを発生させうる方式です（複数トランザクションが互いのロックを待つとデッドロックが発生する）。したがって、デッドロックの「検出」手段ではありません。検出は待ちグラフやタイムアウト等で行い、予防・回避には資源順序化やwait‑die/wound‑wait等の手法を使います。
• イ: 時刻印アルゴリズム（タイムスタンプ）
  タイムスタンプ方式はトランザクションに時刻（タイムスタンプ）を割り当てて競合を解決する方式で、待たせる代わりにロールバックを行うことが多く、基本的にはブロッキングを回避するためデッドロックは生じにくい（事実上デッドロック検出を必要としない）設計です。よって「検出」に使うものではありません。
• ウ: チェックポイント
  チェックポイントはデータベースの復旧（クラッシュ後のリカバリ）を高速化するための手法であり、トランザクションのデッドロック検出とは目的が異なります。
• エ: 待ちグラフ（正解）
  トランザクションの待ち関係をグラフで表し、グラフ上のサイクル検出によりデッドロックを検出します。分散環境では分割された待ちグラフの統合など実装上の工夫が必要ですが、基本概念は同じです。

よくある誤解

• 2相ロックはデッドロックを防ぐ／検出する方法である：誤りです。2相ロックは直列化を保証しますが、デッドロックを発生させ得ます。検出は別の仕組み（待ちグラフやタイムアウト）で行います。
• タイムスタンプ方式もデッドロック検出に使う：一般的にタイムスタンプ方式は待機を伴わない選択をするため、デッドロック検出を必要としないことが多い点が誤解されやすいです。
• 待ちグラフにサイクルが無ければ問題ない：通常は正しいですが、分散システムでは部分的にしか見えないグラフからは検出できないケースがあるため、グローバル検出の工夫が必要です。

補足コラム

• 待ちグラフの作り方：ノード＝トランザクション、辺＝「ロック待ちの依存関係（待っている→保持者）」です。周期があればデッドロック。
• 検出アルゴリズム例：単一ノードではDFSで十分、複数ノード／分散環境では部分グラフを収集して統合しサイクル検出を行うか、タイムアウトや分散検出アルゴリズムを用います。
• 解決方法：デッドロックを検出したら、いずれかのトランザクションを中止（ロールバック）してサイクルを破壊します。被害を小さくするための犠牲者選択基準としては「実行時間が短い／持っているロック数が少ない／再実行コストが小さい」などがあります。
• 防止手法の例：
  • 資源順序化（すべてのトランザクションが同じ固定順序で資源を要求する）
  • タイムアウト（一定時間待ったトランザクションを中止）
  • wait‑die / wound‑wait（タイムスタンプに基づく回避ルール）
• 参考計算量：グラフのサイクル検出は $O(V+E)$（頂点数 V、辺数 E）。

# graph: adjacency list, e.g. {'T1':['T2'], 'T2':['T3'], 'T3':['T1']}
def has_cycle(graph):
    visited = set()
    stack = set()
    def dfs(u):
        visited.add(u); stack.add(u)
        for v in graph.get(u, []):
            if v not in visited:
                if dfs(v): return True
            elif v in stack:
                return True
        stack.remove(u)
        return False
    for node in graph:
        if node not in visited:
            if dfs(node): return True
    return False

FAQ