Resource Allocation Graph Explained

A Visual Way to Represent Who's Waiting for What

A Resource Allocation Graph (RAG) is a diagram representing processes, resources, and the relationships between them - which process holds which resource, and which process is waiting for which resource - making deadlock conditions visually identifiable.

The Two Kinds of Nodes and Two Kinds of Edges

Process (drawn as a circle):     ( P1 )
Resource (drawn as a square):    [ R1 ]

Request edge (process wants a resource):   P1 ----> R1
Assignment edge (resource is held by):      R1 ----> P1

A Resource Allocation Graph Showing an Actual Deadlock

P1 ----> R1 ----> P2 ----> R2 ----> P1
(P1 wants R1, which is held by P2;
 P2 wants R2, which is held by P1 - a closed cycle)

P1 is waiting for R1, which P2 currently holds. P2 is waiting for R2, which P1 currently holds. Following the arrows traces a complete cycle back to where it started - visually, this is exactly what a deadlock looks like.

A Cycle Always Means Deadlock, With One Important Caveat

If every resource type in the graph has only a single instance, a cycle in the graph always means a deadlock exists. But if a resource type has multiple identical instances available, a cycle is still possible without necessarily being an actual deadlock - since a different instance of the same resource type might still become available to break the cycle.

Why Drawing This Out Genuinely Helps Understanding

Turning an abstract description of "who's waiting for what" into an actual visual graph makes the specific circular wait condition (covered in the necessary conditions note) far easier to spot and reason about, compared to just tracking the same relationships as a plain list or table.

How This Connects to Detection Algorithms

Deadlock detection algorithms (covered in the previous note) are, at their core, essentially automated cycle-detection over a structure exactly like a Resource Allocation Graph - the visual graph is a direct, intuitive way of understanding what those detection algorithms are actually computing under the hood.