Operating System - Resource Allocation Graph

What is a Resource Allocation Graph?

A Resource Allocation Graph (RAG) is a directed graph used to represent the relationship between processes and resources in a system.

• Processes: Represented as circles (e.g., P1, P2).

• Resources: Represented as squares (e.g., R1, R2).

• Edges:

  • Request edge (from process to resource): P → R
    Means the process is waiting for the resource.

  • Assignment edge (from resource to process): R → P
    Means the resource is allocated to the process.

 When Does Deadlock Occur?

If the graph has a cycle, a deadlock may exist:

• Single instance per resource type: A cycle always means deadlock.

• Multiple instances: A cycle might not mean deadlock.

 Example: No Deadlock

Scenario:

• Processes: P1, P2

• Resources: R1, R2 (1 instance each)

Conditions:

• P1 is holding R1

• P2 is holding R2

• P1 is requesting R2

Graph:

P1 → R2  
R1 → P1  
R2 → P2

Visualization:

P1   P2
↓     ↓
R2   R1
↑     ↑
    ←

• There is no cycle → ❌ No deadlock

 Example: Deadlock Exists

Scenario:

• Processes: P1, P2

• Resources: R1, R2 (1 instance each)

Conditions:

• P1 holds R1 and requests R2

• P2 holds R2 and requests R1

Graph:

P1 → R2  
R1 → P1  
P2 → R1  
R2 → P2

Visualization:

P1 → R2 → P2 → R1 → P1

• There is a cycle → ✅ Deadlock exists

 Why Use RAG?

• It provides a clear, visual representation of process-resource relationships.

• Helps detect potential or actual deadlocks.

• Useful in systems with single-instance resources.

 RAG in Dynamic Systems

• The graph changes over time as processes request and release resources.

• The OS can monitor the graph to prevent or resolve deadlocks.