Detection
If we run with no prevention or avoidance, we must periodically check whether deadlock has actually formed.
Single Instance per Resource Type
Build a wait-for graph by collapsing the resource-allocation graph: edge P → Q means P is waiting for a resource held by Q. Cycle → deadlock.
P1 → P2 → P3 → P1 forms a cycle, so {P1,P2,P3} are deadlocked. P4 is just waiting.
Multiple Instances
Use a Banker-style detection:
- Available[m], Allocation[n][m], Request[n][m].
- Same safety idea but with current Request instead of Need.
- Any process whose Finish[i] remains false at the end is deadlocked.
When to Run Detection?
- On every request — costly but immediate.
- Periodically (e.g., every hour) — cheaper, deadlock lingers a while.
- When CPU utilization drops — symptom of many waiting processes.
Recovery
Once deadlock is detected:
Option 1 — Process Termination
- Abort all deadlocked processes — drastic but simple.
- Abort one at a time until the cycle breaks. Choose the victim using:
- Priority.
- CPU time consumed and remaining.
- Resources used / needed.
- Number of processes that would need rollback.
- Whether interactive or batch.
Option 2 — Resource Preemption
Take resources from some processes and hand them to others. Three issues:
- Selecting a victim — minimize cost.
- Rollback — return the victim to a safe state. Either total rollback (restart) or partial rollback to a checkpoint.
- Starvation — same process must not always be the victim. Use a count of victim-selections in cost calculations.
Practical Considerations
- Database transaction systems use deadlock detection and rollback heavily — transactions are designed to be redoable.
- Operating systems usually rely on prevention (resource ordering) plus the ostrich algorithm for the rare slip.
Worked Example
Suppose A=7, B=2, C=6 instances. Processes:
| Process | Allocation A,B,C | Request A,B,C |
|---|---|---|
| P0 | 0,1,0 | 0,0,0 |
| P1 | 2,0,0 | 2,0,2 |
| P2 | 3,0,3 | 0,0,0 |
| P3 | 2,1,1 | 1,0,0 |
| P4 | 0,0,2 | 0,0,2 |
Available = 7-7, 2-2, 6-6 = (0,0,0). Run detection: P0 and P2 have zero requests → can finish, freeing (3,1,3). Now check P1 (2,0,2) ≤ (3,1,3) → finish, free (5,1,3). P3 (1,0,0) → finish (7,2,4). P4 (0,0,2) → finish. All finish — no deadlock.
If instead P1 had request (2,0,2) and P2 had request (0,0,1), the algorithm would find no candidate after P0, leaving P1, P3, P4, P2 as deadlocked.
Summary
- Detection runs a Banker-style algorithm on current requests.
- Recovery either kills processes or preempts resources, balancing cost and starvation.
- Detection-and-recover is the practical default in most servers and DBMSs.