Deadlock Detection

Introduction

If deadlock prevention is like banning all cars from intersections (too restrictive), and avoidance is like a traffic controller checking safety before every turn (computationally expensive), then deadlock detection is like installing cameras at intersections and dispatching help when a gridlock actually occurs.

Deadlock detection allows the system to run without restrictions on resource allocation. It does not prevent or avoid deadlocks. Instead, it periodically examines the system state to determine whether a deadlock has occurred. If detected, the system invokes a recovery mechanism. This approach makes sense when deadlocks are rare — why pay the cost of prevention if the problem only occurs once a week?

Detection for Single-Instance Resources

When each resource type has exactly one instance, we use a Wait-For Graph. This is a simplified version of the Resource Allocation Graph with resource nodes removed.

Construction: There is an edge from Pi to Pj if Pi is waiting for a resource currently held by Pj.

Detection: If the wait-for graph contains a cycle, the processes in the cycle are deadlocked.

Cycle Detection Algorithm (DFS-based)

Time complexity: O(n²) where n is the number of processes (we examine each edge once).

Detection for Multi-Instance Resources

When resource types have multiple instances, we need an algorithm similar to the Banker's safety algorithm but without the Maximum/Need matrices (since we are not doing avoidance — we do not know maximum demands).

Data Structures

The Detection Algorithm

Example: Multi-Instance Detection

System: 5 processes, 3 resource types (A=7, B=2, C=6 total)

Available = (7,2,6) - (7,2,6) = (0, 0, 0)

Running the algorithm:

• P0: Request(0,0,0) ≤ Work(0,0,0)? YES! Finish[P0]=T, Work=(0,1,0)
• P2: Request(0,0,0) ≤ Work(0,1,0)? YES! Finish[P2]=T, Work=(3,1,3)
• P3: Request(1,0,0) ≤ Work(3,1,3)? YES! Finish[P3]=T, Work=(5,2,4)
• P1: Request(2,0,2) ≤ Work(5,2,4)? YES! Finish[P1]=T, Work=(7,2,4)
• P4: Request(0,0,2) ≤ Work(7,2,4)? YES! Finish[P4]=T

All processes can finish → No deadlock!

Now suppose P2 requests one more instance of C: Request[P2] = (0, 0, 1)

Re-running: After P0, Work=(0,1,0). No other process's request can be satisfied (P2 needs C=1 but Work has C=0). P1, P2, P3, P4 are all deadlocked.

When to Invoke Detection

The frequency of detection involves a tradeoff:

A practical heuristic: invoke the detection algorithm when CPU utilization drops below 40%, which could indicate that many processes are blocked (possibly deadlocked).

Real-World Usage

Database systems are the primary users of deadlock detection. MySQL, PostgreSQL, and Oracle all maintain wait-for graphs and check for cycles. When a deadlock is detected, one transaction is chosen as the victim, rolled back, and restarted.

Operating systems rarely use detection for OS-level resources because the overhead is considered too high for the frequency of deadlocks. Instead, they rely on prevention (resource ordering) or simply ignore the problem.

Key Takeaways

• Deadlock detection allows unrestricted resource allocation and detects deadlocks after they occur
• For single-instance resources: detect cycles in the wait-for graph (O(n²))
• For multi-instance resources: use an algorithm similar to Banker's safety check with actual requests
• Detection frequency is a tradeoff between overhead and detection latency
• Database systems are the primary real-world users of deadlock detection
• After detection, a recovery mechanism must be invoked to resolve the deadlock