Resource allocation graph in Operating Systems - Step-by-Step Execution

Concept Flow - Resource allocation graph

Initial: Allocate resources

↓

Add allocation edge: R -> P

↓

Process requests another resource

↓

Add request edge: P -> R'

↓

Check for cycles

↓

System safe

The graph shows allocation (R -> P) and request (P -> R) edges. Cycles indicate circular wait leading to deadlock.

Execution Sample

Operating Systems

R1 allocated to P1
Add edge R1->P1
P1 requests R2
Add edge P1->R2
R2 allocated to P2
Add edge R2->P2
P2 requests R1
Add edge P2->R1
Check graph for cycles

Edges added for allocations and requests. Cycle forms at the end, indicating deadlock.

Analysis Table

Step	Action	Graph Edges	Cycle Detected	Result
1	R1 allocated to P1	R1 -> P1	No	Allocation edge added
2	P1 requests R2	R1 -> P1, P1 -> R2	No	Request edge added
3	R2 allocated to P2	R1 -> P1, P1 -> R2, R2 -> P2	No	Allocation edge added
4	P2 requests R1	R1 -> P1, P1 -> R2, R2 -> P2, P2 -> R1	Yes	Cycle detected (P1 -> R2 -> P2 -> R1 -> P1)
5	P1 releases R1	P1 -> R2, R2 -> P2, P2 -> R1	No	Cycle broken by removing R1 -> P1
6	P2 allocates R1	P1 -> R2, R2 -> P2, R1 -> P2	No	No cycle, system progressing

💡 In resource allocation graphs (single-instance resources), cycle indicates deadlock; breaking cycle via release resolves it.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
Graph Edges	None	R1->P1	R1->P1, P1->R2	R1->P1, P1->R2, R2->P2	R1->P1, P1->R2, R2->P2, P2->R1	P1->R2, R2->P2, P2->R1	P1->R2, R2->P2, R1->P2
Cycle Detected	No	No	No	No	Yes	No	No
Deadlock State	No	No	No	No	Detected	Resolved	Safe

Key Insights - 3 Insights

Why does step 4 create a cycle?

Edges form a loop: P1 -> R2 -> P2 -> R1 -> P1, indicating circular wait.

Does a cycle always mean deadlock?

In resource allocation graphs with single-instance resources per type, yes, a cycle indicates deadlock.

How is deadlock resolved?

By a process releasing a resource (remove allocation edge), breaking the cycle, as in step 5.

Visual Quiz - 3 Questions

At step 4 in execution_table, is there a cycle?

A No

B Only self-loop

C Yes

D No edges

💡 Hint

Check 'Cycle Detected' column at step 4.

At which step is the cycle first detected?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look for first 'Yes' in 'Cycle Detected'.

After step 5 (P1 releases R1), what is the deadlock state?

A Detected

B Resolved

C Confirmed

D Worse

💡 Hint

See 'Deadlock State' in variable_tracker after step 5.

Concept Snapshot

Resource Allocation Graph:
- Nodes: Processes (circles), Resources (squares)
- Allocation edges: Resource -> Process (holding)
- Request edges: Process -> Resource (waiting)
- Cycle = deadlock (for single-instance resources)
- Detect/analyze deadlocks in OS resource management

Full Transcript

Resource allocation graphs model processes and resources. Allocation edges (R -> P) show held resources; request edges (P -> R) show waits. A cycle means circular waiting: no progress, deadlock. Used in OS to detect deadlocks via cycle detection algorithms. Resolution: resource release breaks cycles.