Home/Learn/Operating Systems/Resource Allocation Graph

Resource Allocation Graph

Intermediate

Deadlocks

A Resource Allocation Graph (RAG) is a directed graph used to represent the state of resource allocation and detect deadlocks in single- and multi-instance resource systems.

Overview

The RAG has two types of vertices: processes (circles) and resources (rectangles, with dots inside representing instances). A request edge (P → R) means a process is waiting for a resource. An assignment edge (R → P) means a resource instance is allocated to a process. For single-instance resources, a cycle in the RAG means deadlock is certain. For multi-instance resources, a cycle is necessary but not sufficient — you also need to apply the Banker's algorithm to confirm. RAGs provide a visual snapshot of system state and are the foundation for all deadlock detection algorithms.

Graph Structure and Cycle Detection

Build an adjacency list where processes and resources are nodes. Request edges go from process to resource; assignment edges go from resource to process. A DFS cycle check on single-instance resources directly reveals deadlock. With multi-instance resources, a cycle with available instances elsewhere means no deadlock yet.

Java — RAG adjacency list with DFS cycle detection

import java.util.*;

// RAG represented as adjacency list
// Nodes: "P1","P2","P3" = processes; "R1","R2" = resources (single-instance)
Map<String, List<String>> graph = new HashMap<>();

// Assignment edges (R → P): R1 assigned to P1, R2 assigned to P2
graph.put("R1", List.of("P1"));
graph.put("R2", List.of("P2"));

// Request edges (P → R): P2 wants R1, P3 wants R2, P1 wants R3 (cycle!)
graph.put("P1", List.of("R2"));   // P1 holds R1, wants R2
graph.put("P2", List.of("R1"));   // P2 holds R2, wants R1 → CYCLE
graph.put("P3", List.of());

// DFS cycle detection
Set<String> visited = new HashSet<>();
Set<String> inStack = new HashSet<>();

boolean hasCycle = false;
for (String node : graph.keySet()) {
    if (!visited.contains(node) && dfs(node, graph, visited, inStack)) {
        hasCycle = true;
        break;
    }
}
System.out.println("Deadlock detected: " + hasCycle); // true

static boolean dfs(String node, Map<String, List<String>> graph,
                   Set<String> visited, Set<String> inStack) {
    visited.add(node);
    inStack.add(node);
    for (String neighbor : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor) && dfs(neighbor, graph, visited, inStack)) return true;
        if (inStack.contains(neighbor)) return true;  // back edge = cycle
    }
    inStack.remove(node);
    return false;
}

Multi-Instance Resources: Cycle Without Deadlock

When a resource has multiple instances, a cycle does not guarantee deadlock. If R1 has two instances and both P1 and P2 each hold one, P3 requesting R1 creates a cycle but no deadlock — one of P1/P2 may finish and release. Multi-instance deadlock detection requires the reduction algorithm (similar to Banker's safety check).

Java — Multi-instance reduction pseudocode

// Multi-instance resource example
// R1 has 2 instances: assigned to P1 and P2
// P3 requests R1 — creates a "cycle" in RAG but NOT a deadlock
// because P1 or P2 can finish and release their instance

// Reduction algorithm (single pass):
// Allocation matrix:   P1=[1,0], P2=[0,1], P3=[0,0]
// Request matrix:      P1=[0,0], P2=[0,0], P3=[1,0]
// Available:           [0, 1]  (R2 has 1 free instance)

// Step 1: P3 can't run (needs R1=1, available R1=0) — skip
// Step 2: P1 request=[0,0] ≤ available=[0,1] → P1 can finish → release [1,0]
//         Available becomes [1,1]
// Step 3: P2 request=[0,0] ≤ available=[1,1] → P2 can finish → release [0,1]
//         Available becomes [1,2]
// Step 4: P3 request=[1,0] ≤ available=[1,2] → P3 can finish
// All processes can finish → NO DEADLOCK despite cycle in RAG

Key Points to Remember

1In a RAG, request edges go from process to resource; assignment edges go from resource to process.
2For single-instance resources, a cycle in the RAG is both necessary and sufficient for deadlock.
3For multi-instance resources, a cycle is necessary but not sufficient — use the reduction algorithm to confirm deadlock.
4Each dot inside a resource rectangle represents one instance; the number of dots equals total instances.
5The RAG can be converted to a wait-for graph (only processes) by collapsing resource nodes for simpler cycle detection.

Interview Questions

Draw a Resource Allocation Graph for three processes and two resources in a deadlock state.

EasyAmazon

Why does a cycle in a RAG with multi-instance resources not necessarily mean deadlock?

MediumGoogle

How would you convert a RAG to a wait-for graph, and when is this conversion useful?

MediumFlipkart

In a microservices system using distributed locks on Redis, how would you model a RAG to detect deadlocks?

HardNetflix

Ask Aria about Resource Allocation Graph

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Deadlock: Four Necessary Conditions

Deadlock Prevention