OS Notes

Resource Allocation Graph

Understanding Resource Allocation Graphs (RAG) for deadlock detection including graph construction, cycle detection, single vs multiple instance resources, and graph reduction algorithm.

Introduction

How do you visualize deadlock? Drawing a picture is worth a thousand words, and the Resource Allocation Graph (RAG) is exactly that picture. It is a directed graph that shows which processes hold which resources and which processes are waiting for which resources. If this graph contains a cycle, deadlock may exist.

Resource Allocation Graphs were introduced by Holt in 1972 and provide an elegant visual and mathematical way to detect deadlocks. For systems with single-instance resources, a cycle in the RAG means deadlock is certain. For multi-instance resources, a cycle is necessary but not sufficient — further analysis is needed.

Graph Components

A Resource Allocation Graph has two types of nodes and two types of edges:

Nodes

Process nodes (circles): Represented as ○ P1, ○ P2, etc.
Resource nodes (rectangles): Represented as □ R1, □ R2, etc. Dots inside indicate instances.

Edges

Request edge (Process → Resource): Pi → Rj means Pi is waiting for Rj
Assignment edge (Resource → Process): Rj → Pi means an instance of Rj is held by Pi

Legend

○ = Process □ = Resource (with dots for instances)

──→ = Request edge (process wants resource)

←── = Assignment edge (resource assigned to process)

Example RAG

○ P1 ──→ □ R1 (●) ──→ ○ P2 ──→ □ R2 (●) ──→ ○ P1

P1 wants R1, R1 is held by P2

P2 wants R2, R2 is held by P1

CYCLE EXISTS → DEADLOCK (single instances)

Constructing a RAG — Step by Step

Consider this scenario:

Resource R1: 1 instance (held by P2)
Resource R2: 2 instances (one held by P1, one held by P2)
Resource R3: 1 instance (held by P3)
P1 requests R1
P3 requests R2

┌───	│ R1 │───→ ○ P2
Assignment edges: R1	P2, R2→P1, R2→P2, R3→P3
Request edges: P1	R1, P3→R2

Detecting Deadlock Using RAG

Case 1: Single-Instance Resources

When each resource type has exactly one instance, the rule is simple:

A cycle in the RAG ⟺ Deadlock exists

If there is a cycle, the processes in the cycle are deadlocked. If there is no cycle, no deadlock.

Case 2: Multiple-Instance Resources

When resources have multiple instances, a cycle is necessary but NOT sufficient for deadlock:

○ P1 ──	□ R1 (●●) ──→ ○ P3
└──	○ P2 ──→ □ R2 (●) ──→ ○ P1
R1 has 2 instances	one held by P2, one held by P3
R2 has 1 instance	held by P1
P1 requests R1 (cycle: P1	R1→P3... but wait)

For multiple instances, you need the graph reduction algorithm or the Banker's Algorithm to determine if deadlock truly exists.

Graph Reduction Algorithm

This algorithm simulates what happens when processes complete:

Find a process whose requests can ALL be satisfied by available resources
Assume that process runs to completion and releases all its resources
Remove all edges to/from that process
Repeat until no more processes can be reduced
If all processes are reduced → no deadlock
If some processes remain → those processes are deadlocked

- Available	R1=0, R2=1
Step 1: P2 has no outstanding requests	reduce P2
Available becomes	R1=0, R2=2 (P2 released R2)
Step 2: P1 requests R2(1), available R2=2	can satisfy!
Reduce P1. Available	R1=1, R2=2
Step 3: P3 requests R1(1), available R1=1	can satisfy!
Reduce P3. All processes reduced	NO DEADLOCK.

Wait-For Graph

For systems with only single-instance resources, the RAG can be simplified into a Wait-For Graph. Remove the resource nodes and draw edges directly between processes:

Edge Pi → Pj means "Pi is waiting for a resource held by Pj"

Example

RAG: P1 → R1 → P2 → R2 → P3 → R3 → P1 Wait-For Graph: P1 → P2 → P3 → P1 (cycle = deadlock)

The wait-for graph is simpler and faster to analyze. Cycle detection in the wait-for graph takes O(n²) time where n is the number of processes.

Practical Implementation

Example

// Simple cycle detection using DFS #define MAX_PROC 100 int adj[MAX_PROC][MAX_PROC]; // Adjacency matrix (wait-for graph) int visited[MAX_PROC]; // 0=unvisited, 1=in current path, 2=done int n_processes; int has_cycle_dfs(int node) { visited[node] = 1; // Mark as in-progress for (int i = 0; i < n_processes; i++) { if (adj[node][i]) { // Edge exists if (visited[i] == 1) return 1; // Back edge = cycle! if (visited[i] == 0 && has_cycle_dfs(i)) return 1; } } visited[node] = 2; // Mark as completed return 0; } int detect_deadlock() { memset(visited, 0, sizeof(visited)); for (int i = 0; i < n_processes; i++) { if (visited[i] == 0) { if (has_cycle_dfs(i)) return 1; // Deadlock found } } return 0; // No deadlock }

Real-World Analogy

Think of the RAG like a debt diagram between friends. Each person is a process, and money owed is a resource. If Alice owes Bob $50, draw an edge from Alice to Bob. If there is a cycle (Alice owes Bob, Bob owes Carol, Carol owes Alice) AND nobody has external income (no additional resource instances), nobody can pay anyone — deadlock. But if any person in the cycle has money from elsewhere (like R2 having extra instances), the cycle can be broken.

Key Takeaways

Resource Allocation Graphs visually represent which processes hold and want which resources
Request edges go from process to resource; assignment edges go from resource to process
For single-instance resources: cycle ⟺ deadlock (simple and definitive)
For multi-instance resources: cycle is necessary but not sufficient (use graph reduction)
Graph reduction removes processes that can complete, revealing true deadlocks
Wait-for graphs simplify single-instance analysis by removing resource nodes
RAGs are used by OS and database systems for runtime deadlock detection

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Resource Allocation Graph.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, deadlocks, resource, allocation, graph

Continue learning this concept

DeadlocksBanker\Complete explanation of the Banker\DeadlocksDeadlock AvoidanceUnderstanding deadlock avoidance through safe state analysis, safe sequences, and the concept of unsafe states that may lead to deadlock. Foundation for the Banker\DeadlocksDeadlock DetectionAlgorithms for detecting deadlocks in operating systems including single-instance detection using wait-for graphs, multi-instance detection algorithm, and when to invoke detection.DeadlocksIntroduction to DeadlocksUnderstanding deadlocks in operating systems — what they are, why they occur, real-world examples, system model, and overview of handling strategies including prevention, avoidance, and detection.DeadlocksDeadlock PreventionStrategies for deadlock prevention by eliminating each of the four necessary conditions: mutual exclusion, hold and wait, no preemption, and circular wait with practical implementation approaches.DeadlocksDeadlock RecoveryMethods for recovering from deadlocks including process termination strategies, resource preemption, rollback mechanisms, and selecting victim processes for minimum cost recovery.

PreviousNecessary Conditions for Deadlock NextContiguous Memory Allocation

OS Notes

Resource Allocation Graph

Understanding Resource Allocation Graphs (RAG) for deadlock detection including graph construction, cycle detection, single vs multiple instance resources, and graph reduction algorithm.

Introduction

Graph Components

A Resource Allocation Graph has two types of nodes and two types of edges:

Nodes

Process nodes (circles): Represented as ○ P1, ○ P2, etc.
Resource nodes (rectangles): Represented as □ R1, □ R2, etc. Dots inside indicate instances.

Edges

Request edge (Process → Resource): Pi → Rj means Pi is waiting for Rj
Assignment edge (Resource → Process): Rj → Pi means an instance of Rj is held by Pi

Legend

○ = Process □ = Resource (with dots for instances)

──→ = Request edge (process wants resource)

←── = Assignment edge (resource assigned to process)

Example RAG

○ P1 ──→ □ R1 (●) ──→ ○ P2 ──→ □ R2 (●) ──→ ○ P1

P1 wants R1, R1 is held by P2

P2 wants R2, R2 is held by P1

CYCLE EXISTS → DEADLOCK (single instances)

Constructing a RAG — Step by Step

Consider this scenario:

Resource R1: 1 instance (held by P2)
Resource R2: 2 instances (one held by P1, one held by P2)
Resource R3: 1 instance (held by P3)
P1 requests R1
P3 requests R2

┌───	│ R1 │───→ ○ P2
Assignment edges: R1	P2, R2→P1, R2→P2, R3→P3
Request edges: P1	R1, P3→R2

Detecting Deadlock Using RAG

Case 1: Single-Instance Resources

When each resource type has exactly one instance, the rule is simple:

A cycle in the RAG ⟺ Deadlock exists

If there is a cycle, the processes in the cycle are deadlocked. If there is no cycle, no deadlock.

Case 2: Multiple-Instance Resources

When resources have multiple instances, a cycle is necessary but NOT sufficient for deadlock:

○ P1 ──	□ R1 (●●) ──→ ○ P3
└──	○ P2 ──→ □ R2 (●) ──→ ○ P1
R1 has 2 instances	one held by P2, one held by P3
R2 has 1 instance	held by P1
P1 requests R1 (cycle: P1	R1→P3... but wait)

For multiple instances, you need the graph reduction algorithm or the Banker's Algorithm to determine if deadlock truly exists.

Graph Reduction Algorithm

This algorithm simulates what happens when processes complete:

Find a process whose requests can ALL be satisfied by available resources
Assume that process runs to completion and releases all its resources
Remove all edges to/from that process
Repeat until no more processes can be reduced
If all processes are reduced → no deadlock
If some processes remain → those processes are deadlocked

- Available	R1=0, R2=1
Step 1: P2 has no outstanding requests	reduce P2
Available becomes	R1=0, R2=2 (P2 released R2)
Step 2: P1 requests R2(1), available R2=2	can satisfy!
Reduce P1. Available	R1=1, R2=2
Step 3: P3 requests R1(1), available R1=1	can satisfy!
Reduce P3. All processes reduced	NO DEADLOCK.

Wait-For Graph

For systems with only single-instance resources, the RAG can be simplified into a Wait-For Graph. Remove the resource nodes and draw edges directly between processes:

Edge Pi → Pj means "Pi is waiting for a resource held by Pj"

Example

RAG: P1 → R1 → P2 → R2 → P3 → R3 → P1 Wait-For Graph: P1 → P2 → P3 → P1 (cycle = deadlock)

The wait-for graph is simpler and faster to analyze. Cycle detection in the wait-for graph takes O(n²) time where n is the number of processes.

Practical Implementation

Example

Real-World Analogy

Key Takeaways

Resource Allocation Graphs visually represent which processes hold and want which resources
Request edges go from process to resource; assignment edges go from resource to process
For single-instance resources: cycle ⟺ deadlock (simple and definitive)
For multi-instance resources: cycle is necessary but not sufficient (use graph reduction)
Graph reduction removes processes that can complete, revealing true deadlocks
Wait-for graphs simplify single-instance analysis by removing resource nodes
RAGs are used by OS and database systems for runtime deadlock detection

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Resource Allocation Graph.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, deadlocks, resource, allocation, graph

Continue learning this concept

PreviousNecessary Conditions for Deadlock NextContiguous Memory Allocation