デッドロック検出方法のうち、資源グラフについて具体的に説明してください: 犬小屋は、終わらない(IT)

2025年06月20日

デッドロック検出方法のうち、資源グラフについて具体的に説明してください

質問

デッドロック検出方法のうち、資源グラフについて具体的に説明してください

解答

デッドロック検出方法の一つである「資源グラフ（Resource Allocation Graph, RAG）」は、プロセスと資源の関係を有向グラフで表し、循環（サイクル）があるかどうかでデッドロックの可能性を判断する手法です。

資源グラフは、以下の2種類のノード（点）と矢印（辺）で構成されます：

たとえば、次のような状況を考えます。

これを資源グラフにすると：

P1 → R2↑     ↓R1 ← P2

→ このグラフにはサイクル（循環）が存在しています。

サイクルが存在する＝デッドロックの可能性あり
- ただし、資源が1つずつしかない（単一インスタンス）場合は、
  - サイクル＝デッドロック確定
複数インスタンスがある資源の場合は、
- サイクルがあっても即デッドロックとは限らない
  → より高度なアルゴリズム（例：バンカーズアルゴリズム）が必要

項目	内容
メリット	デッドロックの可視化がしやすい、理論的に分かりやすい
デメリット	資源やプロセスが増えるとグラフが複雑になりやすい、動的な検出は難しい