- Year not given
Deadlock detection with examples
Short answer
Deadlock detection uses a wait-for graph for single-instance resources where a cycle indicates deadlock, or a matrix algorithm for multiple instances where processes are marked if their requests can be satisfied by available resources. In the example with three processes and resources (3,2,2), all processes finish so no deadlock exists; if all requested (1,0,0), none could proceed and all would be deadlocked.
How can you detect deadlock? Explain with examples.
Deadlock detection lets the system enter deadlock, then uses an algorithm to find the deadlocked processes and recovers afterwards.
1. Single instance of each resource: wait-for graph / RAG
Edges: resource → process (allocated), process → resource (requested). A cycle means deadlock.
Example: P1 holds R1 and wants R2; P2 holds R2 and wants R1.
R1 --> P1 --> R2 --> P2 --> R1 (cycle)
The graph has a cycle, so P1 and P2 are deadlocked.
2. Multiple instances: matrix algorithm
Data: Available, Allocation, Request.
- Work = Available. Finish[i] = true if Allocation[i] is zero, else false.
- Find a process i with Finish[i] = false and Request[i] ≤ Work.
- Work = Work + Allocation[i]; Finish[i] = true; go to step 2.
- Processes with Finish = false are deadlocked.
Example: 3 processes, resource types A, B, C with 3, 2, 2 instances.
| Process | Allocation (A B C) | Request (A B C) |
|---|---|---|
| P0 | 1 0 0 | 0 1 1 |
| P1 | 1 1 0 | 1 0 0 |
| P2 | 1 0 1 | 0 0 1 |
Available = total − allocated = (3,2,2) − (3,1,1) = (0,1,1).
- Work = (0,1,1). P0 requests (0,1,1) ≤ Work, so P0 finishes: Work = (1,1,1).
- P1 requests (1,0,0) ≤ (1,1,1), so it finishes: Work = (2,2,1).
- P2 requests (0,0,1) ≤ (2,2,1), so it finishes: Work = (3,2,2).
All processes finish, so there is no deadlock. If instead every process requested (1,0,0), then Work = (0,1,1) has A = 0, so no request could be met; no process could be marked and P0, P1 and P2 would all be reported as deadlocked.
When to run
At every request (costly), at fixed intervals, or when CPU utilisation falls (many processes blocked).
After detection, recover by terminating processes or preempting resources.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Deadlock conditions, detection, action · Operating System, chapter 7
- Deadlock conditions; detection with example · Operating System, chapter 7
- Deadlock detection with allocation matrices · Operating System, chapter 7
- Avoidance, detection, prevention techniques · Operating System, chapter 7
- Back-face detection algorithm · Computer Graphics, chapter 7 · asked 8×
- Distributed deadlock; two-phase commit · Distributed System, chapter 8
- Parallelism, IPC deadlock and OS role · Microprocessor, chapter 6
- Event types; airport weapon detection Bayes · Probability and Statistics, chapter 1