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 they are available. The OS then periodically runs an algorithm to determine if a deadlock has occurred.

If a deadlock is detected, the OS must initiate a recovery procedure to break the circular wait.

Detection Algorithm

The detection algorithm is similar to the safety check in the Banker’s algorithm, but it uses current requests rather than maximum claims:

1. Mark all processes with zero allocation as “finished.”
2. Initialize $W=V$ (available resources).
3. Find an unmarked process $P_k$ whose current requests $Q_k$ can be satisfied by $W$:
   $\forall j:Q_{kj}\le W_j$
4. If such a process is found, assume it completes, add its allocation to $W$ ($W=W+A_k$), mark it as “finished,” and return to Step 3.
5. If any processes remain unmarked at the end, they are deadlocked.

Detection as a Snapshot

Deadlock detection is a momentary assessment of the system state. A finding that the system is currently deadlock-free is not a guarantee against future deadlocks; it only confirms that the current set of resource allocations and pending requests is resolvable.

Frequency of Detection

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

• At every resource request (highest precision, highest overhead).
• Periodically (e.g., every few minutes).
• When CPU utilisation drops below a certain threshold (suspecting processes are blocked).