Deadlock Detection

Definition

Deadlock Detection is the process of identifying whether a deadlock currently exists in the system. Unlike prevention and avoidance (which prevent deadlock upfront), detection monitors system and identifies deadlock after it occurs. Combined with recovery strategy, creates detection-and-recovery approach to deadlock.

When to Use Detection

Detection vs Prevention/Avoidance

Detection Techniques

Method 1: Resource Allocation Graph

Idea: Build graph of resource allocations, detect cycles

Nodes:

• Process nodes (circles): P1, P2, …, Pn
• Resource nodes (squares): R1, R2, …, Rm

Edges:

• P → R: Process requests resource (request edge)
• R → P: Resource allocated to process (assignment edge)

Cycle = Deadlock (for single instance resources)

Example

System state:

         P1 ───→ R1 ───→ P2
         ↓
         R2 ←──────┘

Graph interpretation:
- P1 holds R2, requests R1
- R1 held by P2
- P2 requests R2

Cycle exists: P1 → R1 → P2 → R2 → P1

DEADLOCK DETECTED!

Algorithm: Cycle Detection

function detect_deadlock():
    // Build resource allocation graph
    graph = build_graph()

    // Try to find topological sort
    // If can sort all nodes → No cycle (no deadlock)
    // If can't → Cycle exists (deadlock)

    for each node n:
        if (!visited[n]):
            if (dfs(n, visited, rec_stack)):
                return true  // Cycle found

    return false  // No cycle

function dfs(node, visited, rec_stack):
    visited[node] = true
    rec_stack[node] = true

    for each neighbor of node:
        if (!visited[neighbor]):
            if (dfs(neighbor, visited, rec_stack)):
                return true
        else if (rec_stack[neighbor]):
            return true  // Back edge found (cycle)

    rec_stack[node] = false
    return false

Time Complexity: O(n + m) where n=processes, m=resources

Method 2: Wait-For Graph

For systems with multiple instances of resources, use simplified wait-for graph:

Idea: Processes only, edges show which process waits for which

Original Resource Allocation Graph:
P1 → R1 → P2
P2 → R2 → P3
P3 → R3 → P1

Simplified Wait-For Graph:
P1 → P2 → P3 → P1

Cycle exists → Deadlock!

Construction:

If P1 holds resource R
And P2 is waiting for R
Add edge: P2 → P1 (P2 waits for P1)

Advantage: Simpler graph (only n nodes) Disadvantage: Only works for single-resource-instance systems

Detection Algorithm for Multiple Resources

Banker’s Algorithm (Detection Version)

Similar to avoidance, but check if safe sequence exists:

function detect_deadlock():
    WORK = AVAILABLE
    FINISH[i] = false for all i

    while (exists process i: FINISH[i]==false AND NEED[i] <= WORK):
        // Can this process finish?
        WORK += ALLOCATED[i]
        FINISH[i] = true

    for each process i:
        if (FINISH[i] == false):
            return true  // Deadlock: process i can't finish

    return false  // No deadlock

When to Check for Deadlock

Option 1: Check Every Resource Request

When: After every resource allocation

Advantage: Detect immediately Disadvantage: High overhead (expensive algorithm every request)

Option 2: Check Periodically

When: Every N seconds, or every N resource requests

Advantage: Reduced overhead Disadvantage: Delayed detection (deadlock exists for N seconds before detection)

Option 3: Check on Demand

When: When system seems hung (CPU idle, no progress)

Advantage: Minimal overhead (only when needed) Disadvantage: User must trigger (or heuristic to detect hanging)

Practical Choice

Most systems use periodic checking:

// Check every 1 second or every 1000 allocations
// Balances overhead and detection delay

Deadlock Conditions from Detection

What Graph Tells Us

1. Which processes are deadlocked:

   • Processes in cycle are deadlocked
   • Other processes may continue

2. Which resources involved:

   • Resources in cycle part of deadlock
   • Can focus recovery on these

3. Cycle structure:

   • Simple cycle: P1 → R1 → P2 → R2 → P1
   • Complex: Multiple interlocking cycles

Example: Multi-Resource Deadlock Detection

System:
- 3 units of Disk
- 2 units of Printer

Process:        MAX     ALLOCATED    NEED      AVAILABLE
P1:        (2D,2P)  (1D,1P)      (1D,1P)     D:1, P:0
P2:        (2D,1P)  (2D,0P)      (0D,1P)
P3:        (1D,1P)  (0D,1P)      (1D,0P)

Safety check:
- P3 needs 1D, has 1 available? NO (only 1 available, could finish if has it)
- P1 needs 1D+1P, has? NO (needs P, have none)
- P2 needs 1P, has? NO
- No one can finish!

Result: DEADLOCK DETECTED!

Handling Detection Results

If Deadlock Detected

Must activate recovery strategy:

1. Identify processes involved
2. Decide which to kill/preempt
3. Execute recovery

(See Deadlock-Recovery for details)

Multiple Detection Cycles

One-Shot vs Continuous

One-Shot:

Check once
Find deadlock (or not)
Report

Continuous:

while (system running):
    Check for deadlock
    if (found):
        Execute recovery

        // Continue checking

Most systems use continuous monitoring.

Advantages of Detection

1. Deadlock Possible: System can temporarily deadlock
2. Better Concurrency: No prevention overhead
3. Resource Utilization: Full use possible
4. Flexibility: Allocation decisions simpler
5. No Knowledge Needed: Don’t need to know max resource needs

Disadvantages

1. Deadlock Occurs: System makes no progress during deadlock
2. Recovery Expensive: Killing processes, losing work
3. Detection Overhead: Checking algorithm has cost
4. Recovery Complexity: Must decide what to kill

Detection Overhead Analysis

Time Complexity

• Building graph: O(n + m)
• Cycle detection: O(n²) (DFS/BFS)
• For multiple resource types: O(n × m)

Where n = processes, m = resources

For small systems:

• Acceptable to check every request

For large systems:

• Too expensive
• Must check periodically

Real-World Example

System with 1000 processes, 100 resources
Every allocation needs cycle detection: 1000² = too slow!
Every 1000 allocations: 1M allocations/second ÷ 1000 = 1000 checks/sec
Better: Every 1 second check (1000 checks/sec acceptable)

Comparison with Other Strategies

Summary

Deadlock Detection checks if deadlock exists after it occurs. Uses resource allocation graph or wait-for graph with cycle detection. Can check every request (expensive) or periodically (practical). When detected, recovery strategy triggered. Allows maximum concurrency but requires recovery mechanism. Many practical systems use detection for infrequent deadlocks, prevention for critical resources. Understanding detection is essential for complete deadlock handling strategy.