Resource Allocation Graph (RAG)

Resource Allocation Graph (RAG)

A directed graph used in operating systems to visualize how processes are using resources and which resources they are waiting for.

Process Nodes

Circles (P1, P2, …) representing active processes in the system.

Resource Nodes

Rectangles (R1, R2, …) representing resource types, with dots indicating instances of that resource type.

Request Edge

A directed edge from a process to a resource (P → R), indicating that the process is requesting an instance of that resource.

Assignment Edge

A directed edge from a resource to a process (R → P), indicating that an instance of the resource has been allocated to the process.

Cycle Detection in RAGs

A method to detect potential deadlocks; a cycle may indicate a deadlock.

Deadlock Implies

If a resource type has only one instance, a cycle in the RAG implies that a deadlock has occurred.

Deadlock Possibility

If a resource type has multiple instances, a cycle in the RAG does not necessarily imply deadlock but indicates the possibility of it.