Operating System - Wait-For Graph

What is a Wait-For Graph?

A Wait-for Graph is a directed graph used to represent which processes are waiting for which other processes to release resources.

  • Nodes: Represent processes only (e.g., P1, P2).

  • Edges:

    • An edge from P1 → P2 means P1 is waiting for a resource held by P2.

It's derived from a Resource Allocation Graph (RAG) by removing the resource nodes and directly connecting the waiting relationships.

 When Does Deadlock Occur?

  • If the Wait-for Graph contains a cycle, then a deadlock exists.

  • In systems with one instance per resource type, a cycle is a definite deadlock.

 Example: No Deadlock

Scenario:

Process Holding Waiting for
P1 R1 —
P2 R2 R1 (held by P1)
P3 R3 R2 (held by P2)

Wait-for Graph:

P2 → P1  
P3 → P2

Visualization:

P3 → P2 → P1

  • No cycle → ✅ No deadlock

 Example: Deadlock Exists

Scenario:

Process Holding Waiting for
P1 R1 R2 (held by P2)
P2 R2 R3 (held by P3)
P3 R3 R1 (held by P1)

Wait-for Graph:

P1 → P2  
P2 → P3  
P3 → P1

Visualization:

P1 → P2 → P3 → P1

  • Cycle exists → ❌ Deadlock detected

 Why Use Wait-for Graphs?

  • Simpler than Resource Allocation Graphs when only one instance per resource exists.

  • Makes it easy to detect cycles (i.e., deadlocks).

  • Often used in real-time deadlock detection algorithms.

 Cycle Detection

  • You can detect deadlocks by running a cycle detection algorithm (like DFS) on the Wait-for Graph.