Resource Allocation Graph - Learning Module

Loading content...

0/240

Cycle Detection

Finding the Circular Trap

Deadlock manifests as a cycle in the Resource Allocation Graph—a closed loop where every process in the cycle is waiting for a resource held by the next process. Cycle detection is therefore the algorithmic heart of deadlock detection for single-instance resource systems.

But how do we efficiently find cycles in a graph? This page explores the classic depth-first search approach, its application to RAGs, the derivation of wait-for graphs that simplify detection, and the time and space complexity considerations that matter for real systems.

For single-instance resources, finding a cycle is finding a deadlock. For multi-instance resources, it's a necessary first step before more sophisticated analysis.

What You Will Learn

By the end of this page, you will understand: depth-first search for cycle detection, coloring schemes to track visit state, the wait-for graph simplification, complexity analysis, and when to trigger detection versus continuous monitoring.

Depth-First Search for Cycle Detection

Depth-First Search (DFS) is the classic algorithm for cycle detection in directed graphs. The key insight is that a cycle exists if and only if we encounter a vertex that is currently on the DFS recursion stack—a back edge.

Algorithm Overview:

Maintain three states for each vertex: WHITE (unvisited), GRAY (visiting/in recursion stack), BLACK (finished)
Start DFS from each unvisited vertex
When entering a vertex, color it GRAY
Explore all outgoing edges recursively
If we encounter a GRAY vertex, we've found a back edge (cycle!)
After exploring all edges, color the vertex BLACK

Why This Works:

A vertex colored GRAY is currently on the path we're exploring. If an edge leads to a GRAY vertex, we've found a path that loops back to itself—the definition of a cycle.

A vertex colored BLACK has been fully explored; its subtree has no cycles that we haven't already detected.

dfs_cycle_detection.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
"""
DFS-based Cycle Detection for Directed Graphs
"""
 
from enum import Enum
from typing import Dict, List, Optional, Set, Tuple
 
 
class Color(Enum):
    WHITE = 0  # Unvisited
    GRAY = 1   # Currently visiting (on recursion stack)
    BLACK = 2  # Finished
 
 
def detect_cycle_dfs(graph: Dict[str, List[str]]) -> Optional[List[str]]:
    """
    Detect a cycle in a directed graph using DFS.
    
    Args:
        graph: Adjacency list representation {vertex: [neighbors]}
    
    Returns:
        List of vertices forming a cycle, or None if no cycle exists.
    """
    color: Dict[str, Color] = {v: Color.WHITE for v in graph}
    parent: Dict[str, Optional[str]] = {v: None for v in graph}
    
    def dfs(vertex: str, path: List[str]) -> Optional[List[str]]:
        """DFS with cycle detection and path tracking."""
        color[vertex] = Color.GRAY
        path.append(vertex)
        
        for neighbor in graph.get(vertex, []):
            if color[neighbor] == Color.GRAY:
                # Back edge found - extract cycle
                cycle_start = path.index(neighbor)
                return path[cycle_start:] + [neighbor]
            
            if color[neighbor] == Color.WHITE:
                result = dfs(neighbor, path)
                if result:
                    return result
        
        path.pop()
        color[vertex] = Color.BLACK
        return None
    
    # Try DFS from each unvisited vertex
    for vertex in graph:
        if color[vertex] == Color.WHITE:
            cycle = dfs(vertex, [])
            if cycle:
                return cycle
    
    return None  # No cycle found
 
 
# Example usage with a simple graph
def demonstrate_cycle_detection():
    # Graph with cycle: A -> B -> C -> A
    graph_with_cycle = {
        'A': ['B'],
        'B': ['C'],
        'C': ['A'],  # Back edge creates cycle
        'D': ['E'],
        'E': []
    }
    
    cycle = detect_cycle_dfs(graph_with_cycle)
    print(f"Cycle found: {cycle}")  # ['A', 'B', 'C', 'A']
    
    # Graph without cycle
    graph_no_cycle = {
        'A': ['B', 'C'],
        'B': ['D'],
        'C': ['D'],
        'D': []
    }
    
    cycle = detect_cycle_dfs(graph_no_cycle)
    print(f"Cycle found: {cycle}")  # None
 
 
if __name__ == "__main__":
    demonstrate_cycle_detection()

DFS Vertex Colors
Color	Meaning	Implication of Edge to This Color
WHITE	Unvisited	Tree edge - explore it
GRAY	In current path (on stack)	Back edge - CYCLE FOUND
BLACK	Fully explored	Forward/cross edge - no new cycle

Cycle Detection in Resource Allocation Graphs

Applying DFS to a RAG requires understanding the graph's bipartite structure. Cycles in a RAG alternate between process and resource vertices.

RAG Edge Traversal:

From a process P:

Follow request edges P → R (find resources P wants)

From a resource R:

Follow assignment edges R → P (find processes holding R)

The Alternating Pattern:

A cycle in a RAG has the form:

P₁ → R₁ → P₂ → R₂ → ... → Pₖ → Rₖ → P₁

The length is always even (alternating P and R), and the cycle includes exactly as many processes as resources.

Adaptation of DFS:

We can simplify the search by focusing only on processes:

From process Pᵢ, find all resources it requests
For each requested resource Rⱼ, find all processes holding Rⱼ
These are the "effective neighbors" of Pᵢ in deadlock terms
Apply standard DFS cycle detection

rag_cycle_detection.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
def detect_cycle_in_rag(rag: 'ResourceAllocationGraph') -> Optional[List[str]]:
    """
    Detect a cycle in a Resource Allocation Graph.
    
    This implementation traverses the bipartite graph by following
    request edges (P→R) and assignment edges (R→P).
    
    Returns:
        List of process names in the cycle, or None.
    """
    
    def get_blocking_processes(process_name: str) -> List[str]:
        """
        Get processes that are blocking this process.
        
        Process P1 is blocked by P2 if:
        - P1 requests some resource R
        - P2 holds an instance of R
        """
        blocking = set()
        process = rag.processes[process_name]
        
        for resource_name, count in process.requested_resources.items():
            if count > 0:
                resource = rag.resources[resource_name]
                for holder, held_count in resource.allocated_instances.items():
                    if held_count > 0 and holder != process_name:
                        blocking.add(holder)
        
        return list(blocking)
    
    # Standard DFS with colors
    color = {p: Color.WHITE for p in rag.processes}
    
    def dfs(proc: str, path: List[str]) -> Optional[List[str]]:
        color[proc] = Color.GRAY
        path.append(proc)
        
        for blocking_proc in get_blocking_processes(proc):
            if color[blocking_proc] == Color.GRAY:
                # Cycle found
                cycle_start = path.index(blocking_proc)
                return path[cycle_start:]
            
            if color[blocking_proc] == Color.WHITE:
                result = dfs(blocking_proc, path)
                if result:
                    return result
        
        path.pop()
        color[proc] = Color.BLACK
        return None
    
    # DFS from each process
    for process in rag.processes:
        if color[process] == Color.WHITE:
            cycle = dfs(process, [])
            if cycle:
                return cycle
    
    return None
 
 
def get_full_rag_cycle(rag, process_cycle: List[str]) -> List[str]:
    """
    Expand a process-only cycle to include resources.
    
    Input: ['P1', 'P2', 'P3']
    Output: ['P1', 'R1', 'P2', 'R2', 'P3', 'R3', 'P1']
    """
    full_cycle = []
    
    for i, proc in enumerate(process_cycle):
        full_cycle.append(proc)
        
        next_proc = process_cycle[(i + 1) % len(process_cycle)]
        
        # Find the resource connecting proc to next_proc
        process = rag.processes[proc]
        for resource_name in process.requested_resources:
            resource = rag.resources[resource_name]
            if next_proc in resource.allocated_instances:
                full_cycle.append(resource_name)
                break
    
    full_cycle.append(process_cycle[0])  # Complete the cycle
    return full_cycle

The Wait-For Graph Simplification

For single-instance resources, we can derive a simpler graph that makes cycle detection more direct: the Wait-For Graph.

Definition:

The wait-for graph G' = (P, E') contains:

Vertices: Only processes (no resources)
Edges: Pᵢ → Pⱼ iff Pᵢ is waiting for a resource held by Pⱼ

Construction:

For each process pair (Pᵢ, Pⱼ):

Add edge Pᵢ → Pⱼ iff ∃ resource R such that:
  - Pᵢ → R is a request edge in the RAG, AND
  - R → Pⱼ is an assignment edge in the RAG

Why This Works (Single-Instance Only):

For single-instance resources, each resource has at most one assignment edge. If Pᵢ requests R and R is assigned to Pⱼ, then Pᵢ is definitively waiting for Pⱼ.

Advantages of Wait-For Graph:

Smaller graph — Only n vertices (processes) instead of n + m (processes + resources)
Faster detection — Fewer edges to traverse
Simpler semantics — Direct "waits-for" relationship
Same result — A cycle in the wait-for graph ↔ a cycle in the RAG (for single-instance resources)

wait_for_graph.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class WaitForGraph:
    """
    A simplified graph showing only wait-for relationships
    between processes. Derived from a RAG.
    
    Note: Only valid for single-instance resources!
    """
    
    def __init__(self):
        self.edges: Dict[str, Set[str]] = {}
    
    @classmethod
    def from_rag(cls, rag: 'ResourceAllocationGraph') -> 'WaitForGraph':
        """
        Construct a wait-for graph from a RAG.
        
        For each request edge P→R and assignment edge R→Q (where P≠Q),
        add edge P→Q to the wait-for graph.
        """
        wfg = cls()
        
        # Initialize edges for all processes
        for process in rag.processes:
            wfg.edges[process] = set()
        
        # Build wait-for edges
        for process_name, process in rag.processes.items():
            for resource_name, count in process.requested_resources.items():
                if count > 0:
                    resource = rag.resources[resource_name]
                    
                    # Find who holds this resource
                    for holder, held in resource.allocated_instances.items():
                        if held > 0 and holder != process_name:
                            wfg.edges[process_name].add(holder)
        
        return wfg
    
    def detect_cycle(self) -> Optional[List[str]]:
        """Detect a cycle using DFS."""
        color = {p: Color.WHITE for p in self.edges}
        
        def dfs(vertex: str, path: List[str]) -> Optional[List[str]]:
            color[vertex] = Color.GRAY
            path.append(vertex)
            
            for neighbor in self.edges.get(vertex, []):
                if color[neighbor] == Color.GRAY:
                    cycle_start = path.index(neighbor)
                    return path[cycle_start:]
                if color[neighbor] == Color.WHITE:
                    result = dfs(neighbor, path)
                    if result:
                        return result
            
            path.pop()
            color[vertex] = Color.BLACK
            return None
        
        for vertex in self.edges:
            if color[vertex] == Color.WHITE:
                cycle = dfs(vertex, [])
                if cycle:
                    return cycle
        
        return None
    
    def __str__(self):
        lines = ["Wait-For Graph:"]
        for proc, waits_for in sorted(self.edges.items()):
            if waits_for:
                lines.append(f"  {proc} waits for: {', '.join(sorted(waits_for))}")
        return "
".join(lines)
 
 
# Example: RAG to Wait-For Graph transformation
def demonstrate_wait_for_graph():
    # Create RAG with deadlock
    rag = ResourceAllocationGraph()
    
    rag.add_process("P1")
    rag.add_process("P2")
    rag.add_process("P3")
    rag.add_resource("R1", 1)
    rag.add_resource("R2", 1)
    rag.add_resource("R3", 1)
    
    # Cycle: P1->R1->P2->R2->P3->R3->P1
    rag.add_assignment_edge("R1", "P2")
    rag.add_assignment_edge("R2", "P3")
    rag.add_assignment_edge("R3", "P1")
    rag.add_request_edge("P1", "R1")
    rag.add_request_edge("P2", "R2")
    rag.add_request_edge("P3", "R3")
    
    # Convert to wait-for graph
    wfg = WaitForGraph.from_rag(rag)
    print(wfg)
    # Output:
    # Wait-For Graph:
    #   P1 waits for: P2
    #   P2 waits for: P3
    #   P3 waits for: P1
    
    cycle = wfg.detect_cycle()
    print(f"
Cycle: {cycle}")  # ['P1', 'P2', 'P3']

Single-Instance Only!

The wait-for graph provides a correct deadlock characterization ONLY for single-instance resources. With multi-instance resources, a cycle in the wait-for graph does not necessarily imply deadlock because additional instances might satisfy waiting processes without conflict.

Complexity Analysis

Understanding the computational cost of cycle detection is essential for deciding when and how often to perform it.

Time Complexity:

DFS visits each vertex once and each edge once:

RAG: O(|P| + |R| + |E|) = O(n + m + e)
- n = number of processes
- m = number of resource types
- e = number of edges (requests + assignments)
Wait-For Graph: O(|P| + |E'|) = O(n + n²) = O(n²)
- In the worst case, every process waits for every other process
- Typically much sparser: O(n + e') where e' << n²

Space Complexity:

Color array: O(n) for processes (or O(n + m) for full RAG)
Recursion stack: O(n) maximum depth
Path tracking (for cycle extraction): O(n)

Total: O(n + m) for RAG, O(n) for wait-for graph

Practical Considerations:

In real systems with hundreds of processes and resources:

Detection takes microseconds
The bottleneck is usually acquiring locks to get a consistent snapshot
Incremental maintenance can avoid full-graph scans

Cycle Detection Complexity
Metric	RAG Direct	Wait-For Graph	Notes
Vertices	n + m	n	WFG eliminates resources
Edges (worst)	n × m	n²	Depends on request patterns
Time	O(n + m + e)	O(n + e')	e' typically << e
Space	O(n + m)	O(n)	Color + stack
Derivation cost	N/A	O(e)	One-time or incremental

Detection Strategies

When should the system check for deadlocks? Several strategies exist, each with tradeoffs.

Strategy 1: On Every Request (Eager)

Check for cycles immediately when a request edge is added.

Pros: Immediate detection, can prevent deadlock by denying requests
Cons: High overhead on every blocking request
Best for: Critical systems, small process counts

Strategy 2: Periodic (Lazy)

Run detection at regular intervals (every N seconds or M requests).

Pros: Amortized overhead, batches checks
Cons: Delayed detection, longer deadlock duration
Best for: General-purpose systems, large process counts

Strategy 3: On Symptom (Reactive)

Check only when deadlock symptoms appear (e.g., timeout, watchdog).

Pros: Minimal overhead when no problems
Cons: Detection may come late
Best for: Systems where deadlock is rare

Strategy 4: Incremental (Hybrid)

Maintain partial analysis state, update incrementally.

Pros: Low per-operation cost, quick final check
Cons: Complex implementation, state maintenance
Best for: High-performance systems with frequent operations

detection_strategies.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * Deadlock Detection Strategy Implementations
 */
 
/* Strategy 1: Eager - Check on every request */
int resource_request_eager(struct resource *res, struct task_struct *task)
{
    spin_lock(&res->lock);
    
    if (res->available > 0) {
        /* Fast path: grant immediately */
        res->available--;
        rag_add_assignment_edge(res, task);
        spin_unlock(&res->lock);
        return 0;
    }
    
    /* Would-block path: check for deadlock first */
    rag_add_request_edge(task, res);
    
    if (rag_detect_cycle_from(task)) {
        /* Would cause deadlock - reject request */
        rag_remove_request_edge(task, res);
        spin_unlock(&res->lock);
        return -EDEADLK;
    }
    
    /* Safe to wait */
    add_to_wait_queue(&res->waiters, task);
    set_current_state(TASK_UNINTERRUPTIBLE);
    spin_unlock(&res->lock);
    schedule();
    
    return 0;
}
 
/* Strategy 2: Periodic - Background detection thread */
static int deadlock_detector_thread(void *data)
{
    while (!kthread_should_stop()) {
        /* Sleep for detection interval */
        schedule_timeout_interruptible(DETECTION_INTERVAL_JIFFIES);
        
        /* Acquire RAG snapshot lock */
        spin_lock(&rag_lock);
        
        /* Run full cycle detection */
        struct deadlock_info *info = rag_detect_all_cycles();
        
        spin_unlock(&rag_lock);
        
        if (info) {
            /* Handle detected deadlock */
            handle_deadlock(info);
            free_deadlock_info(info);
        }
    }
    return 0;
}
 
/* Strategy 3: Reactive - Check on timeout */
int resource_request_with_timeout(struct resource *res, 
                                   struct task_struct *task,
                                   unsigned long timeout_jiffies)
{
    unsigned long deadline = jiffies + timeout_jiffies;
    
    spin_lock(&res->lock);
    
    /* ... usual request handling ... */
    
    while (res->available == 0) {
        if (time_after(jiffies, deadline)) {
            /* Timeout - possible deadlock symptom */
            
            /* Check for deadlock */
            if (rag_detect_cycle_from(task)) {
                handle_deadlock_victim(task);
            }
            
            /* Remove from wait queue */
            remove_from_wait_queue(&res->waiters, task);
            rag_remove_request_edge(task, res);
            spin_unlock(&res->lock);
            return -ETIMEDOUT;
        }
        
        spin_unlock(&res->lock);
        schedule_timeout(deadline - jiffies);
        spin_lock(&res->lock);
    }
    
    /* ... grant resource ... */
    
    spin_unlock(&res->lock);
    return 0;
}

Handling Detected Cycles

Once a cycle is detected, the system must take action. For single-instance resources, a cycle means definite deadlock. Options include:

Option 1: Process Termination

Select one or more processes in the cycle to terminate:

Immediately breaks the cycle
Forceful: process loses all work
Selection criteria: youngest, lowest priority, most resources held

Option 2: Resource Preemption

Forcibly take resources from some processes:

Only works for preemptible resources
Must rollback the victim process
May cause livelock if not careful

Option 3: Rollback to Checkpoint

If processes support checkpointing:

Roll back one process to a safe state before resource acquisition
Releases resources held since checkpoint
Allows forward progress without full termination

Option 4: Operator Intervention

In some systems, alert a human operator:

Appropriate for rare, critical situations
Allows informed decision making
Unacceptable for automated systems

Victim Selection Criteria

•Priority — Terminate lowest-priority process first
•CPU time consumed — Terminate process with least work done
•Resources held — Terminate process with most resources (releases most)
•Remaining time — Terminate process farthest from completion
•Number of rollbacks — Avoid repeatedly victimizing the same process

Summary: Cycle Detection

Key Takeaways

•DFS with color scheme — WHITE/GRAY/BLACK tracking enables O(V+E) detection
•RAG cycles alternate — Process→Resource→Process pattern reflects bipartite structure
•Wait-for graph simplifies — Collapse to process-only graph for single-instance resources
•Complexity is manageable — O(n²) worst case, typically much faster
•Multiple strategies exist — Eager, periodic, reactive, or incremental approaches

Page Complete

You now understand cycle detection algorithms for RAGs, the wait-for graph simplification, and strategies for when to perform detection. The final page will tie everything together with deadlock identification in complete systems.