Deadlock Detection

operating-systems concurrency

Definition

Deadlock Detection

Deadlock detection is an optimistic strategy where the operating system grants all resource requests as long as resources are available, then periodically runs an algorithm to determine if a deadlock has occurred.

If detected, the OS initiates recovery to break the circular wait.

Algorithm

The detection algorithm mirrors the Banker’s algorithm safety check but uses current requests rather than maximum claims:

1. Mark all processes with zero allocation as “finished.”
2. Initialise $W=V$ (available resources).
3. Find an unmarked process $P_k$ whose current requests $Q_k$ satisfy $Q_k\le W$.
4. If found, assume completion: $W=W+A_k$, mark as “finished,” return to Step 3.
5. If any processes remain unmarked, they are deadlocked.

Snapshot Assessment

Detection is a momentary assessment of system state. A deadlock-free finding does not guarantee future safety—it only confirms the current resource allocations and pending requests are resolvable.

Frequency

Detection Overhead

The detection algorithm is CPU-intensive. The OS may run it:

• At every request: highest precision, highest overhead
• Periodically: e.g., every few minutes
• On low CPU utilisation: suspecting blocked processes