情報処理安全確保支援士 2014年 秋期 午前2 問21

待ちグラフの閉路検出【午前2解説】

正解の理由

解法ステップ

1. 待ちグラフの定義を確認：X→Y は「X が Y の保持する資源の解放を待っている」ことを表す。
2. 各グラフについて「有向閉路（始点に戻る有向経路）」が存在するかを探す。
   • 単純にノードを辿ってループがあれば閉路あり。
   • 小問レベルなら目視で A→B→...→A のような戻りがあるかを確認する。
3. 閉路が見つかればそのグラフはデッドロックを示す。見つからなければデッドロックは発生していない（単一インスタンス前提）。

選択肢別の誤答解説

• ア：A→B→C→D→A の有向サイクルが明確に存在するためデッドロックが発生している。各トランザクションが次のトランザクションの解放を待っており、進行不能となる。
• イ：A→B、A→C、A→D、さらに C→B、D→C とあるが、どの経路も最終的に A に戻る有向経路を作っていない。例えば C→B からは B に行くが B からはどこへも出ておらず閉路にならない。したがって閉路はない。
• ウ：A から B,C,D へ放射状に矢印が出ているだけで、被辺が戻ってくる経路がないため閉路は存在しない。
• エ：A,B→C と C→D の流れで一方向に進むのみで、どこからも A や B に戻る矢印がないため閉路はない。

よくある誤解

• 閉路と単なる循環的な見かけのループを混同する：有向グラフでは必ず「有向経路で始点に戻れるか」を確認する必要がある（向きが重要）。
• 「どこかに戻る経路がある＝閉路」と早合点する誤り：部分的に戻るように見えても向きによっては始点に戻れない場合がある（例：C→B があっても B→A 等がなければ A に戻れない）。
• 資源の複数インスタンスを前提にして誤判定する：複数インスタンス資源では閉路があってもデッドロックにならないことがあるため、問題の前提を確認すること。

補足コラム

• 単一インスタンス資源モデル（各資源を1つだけ保持可能）では、待ちグラフに有向サイクルが存在することはデッドロックの必要十分条件です。
• 複数インスタンス資源がある場合は、閉路検出だけでデッドロック判定できないことがある（資源の割当状況に依存）。
• アルゴリズム的には DFS の3色法（未訪問→探索中→探索完了）で簡単に有向閉路を検出できます。計算量はノード数 N と辺数 E に対して O(N+E) です。

def has_cycle(graph):
    # graph: {node: [neighbors]}
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {u: WHITE for u in graph}
    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False
    return any(dfs(u) for u in graph if color[u] == WHITE)

FAQ