Process Deadlocks – Conditions, Detection, Prevention, Avoidance & Recovery

1. Introduction to Deadlocks

A deadlock is a situation in a multiprogramming environment where a group of processes cannot proceed because each process is waiting for a resource that another process in the group holds. The system becomes permanently blocked unless external action is taken.

Deadlocks are distinct from starvation (or indefinite postponement). Starvation occurs when a process never gets the CPU or a resource because the scheduling policy continuously favors other processes, even though the system as a whole is still making progress.

1.1 Real‑world analogies

2. Coffman Conditions

For a deadlock to occur, all of the following conditions must hold simultaneously (Coffman et al., 1971):

If any one condition is eliminated, deadlock cannot arise.

3. Resource‑Allocation Graph (RAG)

A Resource‑Allocation Graph is a directed bipartite graph $G=(P\cup R,E)$ where

• $P=\{P_1,P_2,\dots \}$ are process vertices.
• $R=\{R_1,R_2,\dots \}$ are resource‑type vertices.

Edges are of two kinds:

• Request edge $P_i\to R_j$ (process $P_i$ is requesting an instance of $R_j$).
• Assignment edge $R_j\to P_i$ (resource instance of $R_j$ is allocated to $P_i$).

3.1 Single‑Instance Resources

If each resource type has exactly one instance, a cycle in the RAG is both necessary and sufficient for deadlock.

Example

P0 --> R1 --> P1 --> R2 --> P0

The cycle indicates that P0 holds R1 and waits for R2, while P1 holds R2 and waits for R1 → deadlock.

3.2 Multiple‑Instance Resources

When resources have multiple instances, a cycle is necessary but not sufficient. The graph must be examined with the available vector and allocation matrix to determine a deadlocked set.

4. Deadlock Detection

Detection is performed after the system has entered a possibly unsafe state. Two major cases:

4.1 Single‑Instance Resources (Cycle Detection)

Algorithm: Depth‑First Search (DFS) on the RAG. If a cycle is found, the processes in the cycle are deadlocked.

Complexity: $O(|P|+|R|+|E|)$.

4.2 Multiple‑Instance Resources (Banker‑style Detection)

Data structures:

• Available vector $A$ – number of free instances of each resource type.
• Max matrix $M$ – maximum demand of each process.
• Allocation matrix $C$ – current allocation.
• Need matrix $N=M-C$.

Detection Algorithm (similar to safety algorithm):

1. Initialize Work = $A$ and Finish[i] = false for all processes.
2. Find a process $i$ such that Finish[i] = false and $N_i\le Work$.
3. If found, set $Work=Work+C_i$ and Finish[i] = true; repeat step 2.
4. If no such process exists, all processes with Finish = false are deadlocked.

Worked Example

Consider three resource types $R=\{A,B,C\}$ with total instances $(6,5,7)$.

Current state:

Step 1: Compute Available = Total – ΣAllocation = (6‑7, 5‑2, 7‑4) = $(-1,3,3)$. Since Available for A is negative, we made a mistake; adjust totals to (10,5,7) → Available = (10‑7, 5‑2, 7‑4) = (3,3,3).

Step 2: Need = Max – Allocation

• P0 Need = (3,1,2)
• P1 Need = (4,1,3)
• P2 Need = (0,0,0)
• P3 Need = (2,1,1)

Step 3: Find a process whose Need ≤ Work (3,3,3).

• P2 Need = (0,0,0) ≤ Work → finish P2, Work = Work + Allocation(P2) = (3,3,3) + (3,0,3) = (6,3,6).

Now check remaining:

• P0 Need (3,1,2) ≤ (6,3,6) → finish P0, Work = (6,3,6)+(0,1,0) = (6,4,6).
• P1 Need (4,1,3) ≤ (6,4,6) → finish P1, Work = (6,4,6)+(2,0,0) = (8,4,6).
• P3 Need (2,1,1) ≤ (8,4,6) → finish P3.

All processes can finish → no deadlock.

If at any stage no process satisfies the condition, the unfinished processes constitute a deadlocked set.

5. Deadlock Recovery

When a deadlock is detected, the system must take action to break it.

5.1 Choosing a Victim

Common heuristics:

• Minimum number of resources held.
• Shortest remaining execution time.
• Lowest priority.
• Least recent CPU usage.

6. Deadlock Prevention

Prevention guarantees that at least one Coffman condition can never hold.

Prevention often reduces system concurrency and throughput, because it restricts how resources can be requested.

7. Deadlock Avoidance

Avoidance algorithms make dynamic decisions based on the future request pattern. The classic method is the Banker’s Algorithm (for multiple instances).

7.1 Banker’s Algorithm Overview

1. Safety Check before granting a request: simulate allocation and run the safety algorithm (same as detection).
2. If the resulting state is safe, grant the request; otherwise, the process must wait.

7.2 Example of a Safe vs. Unsafe Request

Using the previous example’s state (Available = (3,3,3)), suppose P1 now requests an additional (1,0,2).

• Tentative Allocation: New Available = (2,3,1).
• New Need for P1 = (3,1,1).

Run safety algorithm:

• P2 can finish (Need = 0) → Work = (2,3,1)+(3,0,3) = (5,3,4).
• P0 Need (3,1,2) ≤ Work → finish → Work = (5,3,4)+(0,1,0) = (5,4,4).
• P1 Need (3,1,1) ≤ Work → finish → Work = (5,4,4)+(2,0,0) = (7,4,4).
• P3 Need (2,1,1) ≤ Work → finish.

All can finish → safe; request granted.

If instead P1 requested (3,0,3), new Available = (0,3,0) and Need(P1) = (3,1,0). No process other than P2 can finish (P2 Need = 0). After P2 finishes, Work = (0,3,0)+(3,0,3) = (3,3,3). Now P0 Need (3,1,2) ≤ Work? No, because Need C=2 > Work C=3? Actually 2 ≤ 3, so yes. Continue... eventually all may finish; but if a request leaves no process able to proceed, the state is unsafe and the request is denied.

7.3 Limitations

• Requires a priori knowledge of maximum demand for each process.
• Overhead of safety checks for every request.
• Not suitable for systems with highly dynamic or unknown resource needs.

8. Comparison of Detection, Prevention, and Avoidance

9. Practical Considerations in Modern OS

• Linux: Uses Ostrich algorithm – assumes deadlocks are rare; provides limited detection via /proc/locks and tools like deadlock in glibc.
• Windows: Provides deadlock detection for certain kernel objects (e.g., mutexes) and a resource‑ordering guideline for driver developers.
• Database systems: Employ two‑phase locking (2PL) and wait‑die or wound‑wait schemes to avoid deadlocks.
• Distributed systems: Use wait‑for graphs and probe messages (e.g., Chandy‑Misra‑Haas algorithm) for detection.

10. Worked Trace: Round‑Robin vs. Priority Scheduling (Related to Past Exam)

Although not a deadlock topic, understanding scheduling helps answer exam questions that combine concepts.

10.1 Round‑Robin (Quantum = 4)

Waiting times:

• P0: (Start 0) + (wait 4) = 4 → WT = 4
• P1: start at 4, arrival 2 → WT = 2
• P2: first run at 12, arrival 4 → WT = 8 (plus later wait 4) = 12? Actually total waiting = (12‑4) + (20‑16) = 8 + 4 = 12.
• P3: first run at 16, arrival 6 → WT = 10 (plus later wait 4) = 14? Wait: after first quantum (16‑20) remaining 1, then runs at 24‑25, so extra wait = 4. Total WT = (16‑6) + (24‑20) = 10 + 4 = 14.

Turnaround times (completion – arrival):

• P0: 12‑0 = 12
• P1: 8‑2 = 6
• P2: 26‑4 = 22
• P3: 25‑6 = 19

Average WT = (4+2+12+14)/4 = 8.0
Average TT = (12+6+22+19)/4 = 14.75

10.2 Non‑preemptive Priority (lower number = higher priority)

Order of execution: P1 (priority 1), P0 & P3 (priority 2, FCFS), P2 (priority 3).

Average WT = (0+6+8+15)/4 = 7.25
Average TT = (4+14+13+24)/4 = 13.75

These numbers illustrate how different policies affect waiting and turnaround times – a typical exam computation.

11. Summary Checklist

• Know the four Coffman conditions and how to break each.
• Be able to draw and interpret a Resource‑Allocation Graph for both single‑ and multiple‑instance resources.
• Perform deadlock detection using cycle detection (single instance) and the safety‑algorithm style (multiple instances).
• Understand recovery options and their trade‑offs.
• Distinguish between prevention (policy‑based) and avoidance (dynamic safety check).
• Apply the Banker’s algorithm to a given state and decide whether a request is safe.

Exam tip

• Past papers often ask you to differentiate deadlock vs. starvation; memorize the key distinction (progress vs. indefinite waiting).
• For graph‑based questions, draw the RAG clearly, label request/assignment edges, and immediately check for cycles.
• When a multiple‑instance detection problem is given, write down Available, Allocation, Max, and compute Need; then run the safety algorithm step‑by‑step – marking processes that can finish.
• In Banker’s questions, the examiner expects you to show the tentative allocation, recompute Available and Need, and then run the safety test. Highlight the safe sequence if one exists.
• For recovery questions, list at least two methods, discuss their pros/cons, and give a short example (e.g., aborting the process holding the most resources).
• Time‑management tip: allocate ~5 minutes to sketch the graph, ~10 minutes to run the detection algorithm, and the remaining time to write concise explanations and a short conclusion.

---