Deadlock in Operating Systems for GATE CS
Coffman conditions, resource allocation graph, Banker’s algorithm, detection, prevention — with step-by-step GATE numerical examples.
Last updated: April 2026 | GATE CS 2024–2026 syllabus
Key Takeaways for GATE
- 4 Coffman conditions (all required for deadlock): Mutual Exclusion + Hold & Wait + No Preemption + Circular Wait.
- RAG cycle + single instances ⇒ deadlock. RAG cycle + multiple instances ⇒ possible deadlock (check further).
- Banker’s algorithm: Need = Max − Allocation. Find safe sequence by simulating completions.
- Safe state ⇒ no deadlock possible. Unsafe state ⇒ deadlock possible (not guaranteed).
- Prevention: break one condition (e.g., request all resources at once = no Hold & Wait).
- Avoidance: grant request only if resulting state is safe (Banker’s). Requires max claim in advance.
- Detection + Recovery: let deadlock occur, detect via wait-for graph, recover by killing or preempting.
1. Coffman Conditions (Necessary Conditions for Deadlock)
All four must hold simultaneously for deadlock to occur. Eliminating any one prevents deadlock.
| Condition | Definition | How to break |
|---|---|---|
| Mutual Exclusion | Resource held in non-shareable mode | Use shareable resources (not always possible) |
| Hold & Wait | Process holds resource while waiting for more | Request all resources at once (pre-allocation) |
| No Preemption | Resources released only voluntarily | Preempt resources (rollback required) |
| Circular Wait | Circular chain of processes each waiting for next | Impose total ordering on resource types |
2. Resource Allocation Graph (RAG)
Request edge: Pi → Rj (process waiting for resource).
Assignment edge: Rj → Pi (resource assigned to process).
Cycle analysis:
Single instance resources: cycle ⇒ deadlock (necessary and sufficient).
Multiple instance resources: cycle ⇒ possible deadlock (necessary but not sufficient).
Wait-for graph: Derived from RAG by removing resource nodes. Edge Pi→Pj means Pi waits for Pj. Deadlock ⇔ cycle in wait-for graph (single-instance resources).
3. Banker’s Algorithm
Data structures (n processes, m resource types):
Available[m]: currently available instances of each resource type.
Max[n][m]: maximum demand of each process.
Allocation[n][m]: currently allocated to each process.
Need[n][m] = Max − Allocation: remaining need of each process.
Safety algorithm:
Work = Available; Finish[i] = false for all i Repeat: Find i such that: Finish[i]=false AND Need[i] ≤ Work If found: Work = Work + Allocation[i]; Finish[i] = true If no such i and all Finish[i]=true: SAFE state If no such i and some Finish[i]=false: UNSAFE state
Resource-request algorithm (for request Ri):
If Request[i] ≤ Need[i]: proceed; else error (exceeds maximum) If Request[i] ≤ Available: proceed; else wait Simulate allocation: Available -= Request[i] Allocation[i] += Request[i] Need[i] -= Request[i] If resulting state is SAFE: grant request Else: rollback and wait
| Process | Max (A,B,C) | Alloc (A,B,C) | Need (A,B,C) |
|---|---|---|---|
| P0 | 7,5,3 | 0,1,0 | 7,4,3 |
| P1 | 3,2,2 | 2,0,0 | 1,2,2 |
| P2 | 9,0,2 | 3,0,2 | 6,0,0 |
| P3 | 2,2,2 | 2,1,1 | 0,1,1 |
| P4 | 4,3,3 | 0,0,2 | 4,3,1 |
Available = (3,3,2). Safety check:
P1: Need(1,2,2) ≤ Work(3,3,2)? Yes. Work=(3,3,2)+(2,0,0)=(5,3,2).
P3: Need(0,1,1) ≤ (5,3,2)? Yes. Work=(5,3,2)+(2,1,1)=(7,4,3).
P4: Need(4,3,1) ≤ (7,4,3)? Yes. Work=(7,4,3)+(0,0,2)=(7,4,5).
P0: Need(7,4,3) ≤ (7,4,5)? Yes. P2: Yes. Safe sequence: P1→P3→P4→P0→P2
4. Deadlock Detection
Multiple instances: Similar to Banker’s safety algorithm but using current requests:
Work = Available; Finish[i] = (Allocation[i] == 0) for each i.
Find i: Finish[i]=false AND Request[i] ≤ Work → Work += Allocation[i], Finish[i]=true. Repeat.
If any Finish[i]=false after algorithm: process i is deadlocked.
When to invoke: Periodically or when CPU utilisation drops below threshold.
5. Deadlock Prevention
| Condition Broken | Method | Drawback |
|---|---|---|
| Mutual Exclusion | Use only shareable resources (read-only files) | Not applicable to all resources |
| Hold & Wait | Request all resources at start, or release before requesting new | Low utilisation, starvation |
| No Preemption | Preempt resources from waiting process | Complex, rollback needed |
| Circular Wait | Total ordering of resources; request only in increasing order | May delay processes unnecessarily |
6. Deadlock Avoidance
Grant request only if resulting state is safe.
Safe state: there exists a safe sequence — a sequence in which every process can complete using currently available resources plus resources held by processes that complete earlier.
Safe state ⇒ no deadlock. Unsafe state ⇒ deadlock possible (but not guaranteed).
Algorithms:
Single instance: Resource-Allocation Graph algorithm (RAG with claim edges).
Multiple instances: Banker’s algorithm (O(n²m) per request).
7. Deadlock Recovery
(a) Abort all deadlocked processes — expensive (lose all progress).
(b) Abort one at a time until deadlock resolved — choose victim by cost (priority, computation done, resources held).
Resource preemption:
Preempt resources from deadlocked processes and give to others.
Issues: selecting victim, rollback (restart from checkpoint), starvation (same process always preempted).
8. GATE Examples
| Process | Allocation | Need |
|---|---|---|
| P0 | 0 1 0 | 7 4 3 |
| P1 | 2 0 0 | 1 2 2 |
| P2 | 3 0 2 | 6 0 0 |
Available = (2,3,0). P1 Need(1,2,2): col C needs 2 but Work[C]=0. Blocked.
P2 Need(6,0,0): A needs 6 but Work[A]=2. Blocked. P0: Need C=3 > 0. Blocked.
No safe sequence — unsafe state (deadlock possible).
n processes each need at most m resources of type R. Minimum total instances of R needed to guarantee no deadlock:
Formula: n(m−1) + 1
Reasoning: worst case, each process holds m−1 resources (one short of maximum). One extra resource allows one process to complete, releasing its resources, enabling others.
Options: (A) Circular wait (B) Mutual exclusion (C) Starvation (D) No preemption
Starvation is not a Coffman condition — a process can starve without a deadlock (e.g., priority scheduling). Answer: (C) Starvation
9. Common Mistakes
- Unsafe state ≠ deadlock: An unsafe state means deadlock is possible in the future, not that it has occurred. A safe state guarantees deadlock will NOT occur if processes request up to their maximum.
- Cycle in RAG with multiple instances: A cycle with multiple-instance resources does not guarantee deadlock. It is necessary but not sufficient. Must run the detection algorithm to confirm.
- Need matrix calculation error: Need = Max − Allocation. A common mistake is computing Need incorrectly, leading to wrong safety check. Always verify Need ≥ 0.
- Deadlock prevention vs avoidance: Prevention statically eliminates a condition (structural change). Avoidance dynamically checks each request. GATE often asks which technique requires advance knowledge (avoidance does).
- Minimum resources formula: For n processes each needing at most m resources, minimum to prevent deadlock is n(m−1)+1, NOT n×m. A common exam trap.
10. FAQ
- What are the four Coffman conditions for deadlock?
- Mutual Exclusion: at least one resource is non-shareable. Hold and Wait: a process holds resources while waiting for more. No Preemption: resources cannot be forcibly removed — only voluntarily released. Circular Wait: a circular chain of processes where P1 waits for P2, P2 waits for P3, …, Pn waits for P1. All four must hold simultaneously for deadlock to occur.
- How does Banker’s algorithm determine a safe state?
- Compute Need = Max − Allocation. Set Work = Available and Finish[i] = false. Find an unfinished process whose Need ≤ Work — it can complete. Add its Allocation to Work, mark it finished. Repeat until all finished (safe state with safe sequence found) or no process can proceed (unsafe state). The safe sequence is the order in which processes finish.
- What is the difference between deadlock prevention and deadlock avoidance?
- Prevention eliminates one Coffman condition structurally before any process runs — e.g., requiring all resources to be requested at once eliminates Hold and Wait. It is conservative and may reduce resource utilisation. Avoidance is dynamic — it allows resource requests but only grants them if the resulting state remains safe (Banker’s algorithm). Avoidance requires processes to declare their maximum resource needs in advance.
- When does a cycle in a resource allocation graph guarantee deadlock?
- Only when every resource type in the cycle has exactly one instance. In that case, each process in the cycle holds the resource the next one needs — circular wait with no way out. With multiple instances, a cycle is a necessary but not sufficient condition — it is possible for other instances of the same resource type to be available, allowing some processes to complete and break the cycle.