A Resource Allocation Graph (RAG) is a directed graph used by the OS to model the allocation of resources to processes and to detect or prevent deadlocks. By representing requests and assignments explicitly, the OS can ensure that it never enters a state in which a cycle—and hence a potential deadlock—exists.

1. RAG Components

• Vertices (V): Partitioned into
  • P = {P₁, P₂, …, Pₙ}: the set of all processes
  • R = {R₁, R₂, …, Rₘ}: the set of all resource types
• Edges (E): Two kinds :
  1. Request edge (Pᵢ → Rⱼ): Process Pᵢ is requesting an instance of Rⱼ
  2. Assignment edge (Rⱼ → Pᵢ): An instance of Rⱼ has been allocated to Pᵢ

2. Cycle Detection and Deadlock

• A cycle in the RAG is necessary for a deadlock: if no cycle exists, no process can be permanently blocked.
• In the single-instance case, a cycle is also sufficient: any cycle means deadlock.
• In the multi-instance case, a cycle may indicate deadlock (it’s necessary but not sufficient) .

3. Preventing Deadlocks via RAG Acyclicity To prevent deadlocks, the OS enforces that the RAG remain acyclic at all times. The high-level algorithm is:

1. On a resource request Pᵢ → Rⱼ:
   • Temporarily add the request edge to the RAG.
   • Check for a cycle (e.g., via depth-first search).
2. Decision:
   • No cycle → grant the request: convert the request edge into an assignment edge (Rⱼ → Pᵢ).
   • Cycle detected → deny the request (process must wait).

By never allowing the RAG to become cyclic, the OS guarantees that deadlocks cannot occur.

4. Illustrative Example

• Before request: P₁ holds R₁ (R₁ → P₁), and P₂ holds R₂ (R₂ → P₂).

• P₁ requests R₂: add P₁ → R₂—no cycle, so grant (convert to R₂ → P₁).

• P₂ now requests R₁: add P₂ → R₁; this would create a cycle

  P₁ → R₂ → P₂ → R₁ → P₁
  
  

  OS denies P₂’s request, thereby preventing deadlock.