A deadlock is a state where every process in a set is waiting for an event that only another process in the set can cause. In practice: process A holds resource 1 and waits for resource 2, process B holds resource 2 and waits for resource 1. Neither can proceed.
The Four Necessary Conditions (Coffman Conditions)
All four must hold simultaneously for a deadlock to occur:
| Condition | Meaning | How to break it |
|---|---|---|
| Mutual exclusion | Resources are non-sharable | Make resources sharable where possible |
| Hold and wait | Process holds a resource while waiting for another | Request all resources at start; or release before requesting again |
| No preemption | Resources can’t be forcibly taken | Allow preemption (take from one, give to another) |
| Circular wait | A cycle in the resource allocation graph | Impose a total order on resource types |
Handling Strategies
1. Prevention (Static)
Break one of the four conditions at design time:
- Eliminate hold-and-wait: require all processes to request all resources before starting — but this causes low utilization
- Eliminate circular wait: assign a global ordering to resources (e.g., always request resource 1 before resource 2)
2. Avoidance (Dynamic)
Requires advance knowledge of maximum resource needs. The Banker’s Algorithm simulates allocation to find a safe state — a sequence of processes that can all complete without deadlocking.
Banker’s Algorithm (simplified):
1. For each process, know: Allocation, Max, Available resources
2. Need = Max - Allocation
3. Find a process where Need <= Available
4. Assume it finishes: Available += Allocation
5. Repeat until all finish (safe) or no process can proceed (unsafe)3. Detection & Recovery
Allow deadlock to happen, then fix it:
- Detection: Build a wait-for graph; if there’s a cycle, there’s a deadlock
- Recovery: Kill processes (all at once or one by one), or preempt resources (roll back a process)
4. The Ostrich Algorithm
Ignore the problem. Most desktop OSes use this — deadlocks are rare enough that the overhead of prevention/avoidance isn’t justified.
Resource Allocation Graph
A directed graph:
- Circles = processes
- Squares = resources (dots inside = instances)
- Edge from process to resource = request
- Edge from resource to process = assignment
A cycle in this graph indicates a deadlock (if only one instance per resource type).
Q: What are the four necessary conditions for deadlock?
A: Mutual exclusion (non-sharable resource), hold and wait (holding one, waiting for another), no preemption (can’t take resource away), circular wait (a cycle of dependencies). All four must be true.
Q: What’s the difference between deadlock prevention and avoidance?
A: Prevention is static — ensure at least one of the four conditions never holds (e.g., resource ordering). Avoidance is dynamic — allow requests but check if granting them leads to an unsafe state using the Banker’s Algorithm.
Q: What is a safe state?
A: A state for which there exists a sequence of process executions that allows all processes to complete without deadlocking. An unsafe state may (but won’t necessarily) lead to deadlock.
Q: How does an OS recover from a deadlock?
A: (1) Kill all deadlocked processes (drastic but simple). (2) Kill one process at a time until the cycle breaks. (3) Preempt resources from a process and give them to others (may require rollback).
Q: What is the Banker’s Algorithm?
A: A deadlock avoidance algorithm that checks if granting a resource request would leave the system in a safe state. It requires each process to declare its maximum resource needs upfront. Named because a banker won’t approve a loan that could lead to insolvency.
Premium Content
Unlock Deadlock: Detection & Prevention and all premium lessons with a subscription.
From ₹199.99/year — See plans