Deadlock in OS — System Model, Coffman Conditions & Handling
Press Next → or use ← → arrow keys
The Story That Explains Deadlock
Swap "cars" for processes and "bridge" for a shared resource — a printer, a disk, a database row, a lock — and you have a deadlock.
A set of processes is deadlocked when every process in the set is waiting for an event — usually a resource release — that can be caused only by another process in the same set. Since none can proceed, none will ever cause that event. The wait is permanent.
System Model — Resources & Their Life Cycle
The OS manages resource types (R₁, R₂, …) — CPU, memory, printers, files — each with one or more identical instances (e.g. 8 CPU cores, 3 printers). Every process follows the same cycle: request (and block if it's taken), use, then release. Trouble starts when a process holds one resource while blocking for another.
The Four Coffman Conditions
Deadlock is possible only when all four conditions hold simultaneously. This is the key insight: break any single one — by design or at runtime — and deadlock becomes impossible. Every prevention strategy is just an attack on one of these four.
Watch a Deadlock Form
P1 holds the printer (R1) and wants the scanner (R2). P2 holds the scanner and wants the printer. Each is waiting for exactly what the other is holding — the loop closes and neither can move. Every Coffman condition is present at once.
The Resource-Allocation Graph (RAG)
| What the graph shows | Conclusion |
|---|---|
| No cycle | No deadlock — guaranteed |
| Cycle + all resources single-instance | Deadlock exists — guaranteed |
| Cycle + some multi-instance resources | Deadlock may exist — run a detection algorithm |
A Cycle of Three — RAG Construction
Red dashed = a request, green solid = an assignment. Trace them clockwise and they close a cycle. Because every resource here has a single instance, this cycle guarantees deadlock.
Four Ways to Handle Deadlock
Prevention and avoidance pay up front in reduced concurrency and per-request checks; detection pays periodically; ignoring pays nothing until the rare crash. The right choice depends on how catastrophic a deadlock would be.
Prevention — Break One Condition
| Break… | How | Cost / Problem |
|---|---|---|
| Mutual Exclusion | Make resources sharable (read-only files, spooled printers) | Impossible for intrinsically non-sharable things like locks |
| Hold and Wait | Request everything at once, or release all before asking for more | Low utilisation; possible starvation |
| No Preemption | Forcibly reclaim held resources when a further request can't be met | Only works for state-saveable resources (CPU, memory) — not printers |
| Circular Wait | Number the resource types; require acquisition in increasing order | Most practical — widely used in real kernels |
Imposing a total order on resources and always locking in increasing order makes a cycle impossible — you can never wait "backwards." It's simple, cheap, and the technique production kernels and databases actually use.
Avoidance — The Safe State
A state is safe if there's some order — a safe sequence — in which every process can finish with the resources available. Avoidance grants a request only if the result stays safe. Note: unsafe ≠ deadlock — an unsafe state may lead to deadlock but doesn't guarantee it. The Banker's Algorithm is the classic safe-state check (its own tutorial).
Detection — Find the Cycle After the Fact
If you allow deadlocks, you must periodically check for them. The detection algorithm walks the Available, Allocation and Request matrices, simulating which processes could finish.
# Deadlock detection — m resource types Work = Available Finish[i] = (Allocation[i] == 0) # idle procs are trivially "finished" while ∃ i : Finish[i] == false and Request[i] <= Work: Work = Work + Allocation[i] # pretend it finishes and releases Finish[i] = true if ∃ i : Finish[i] == false: return "DEADLOCK" # those processes are stuck else: return "NO DEADLOCK"
Run it too rarely and deadlocks linger, wasting resources; too often and the algorithm's own cost bites. A
common trigger is "whenever a request can't be granted." Any process still marked Finish[i] == false
at the end is deadlocked.
Recovery — Break the Cycle
To recover, either terminate processes or preempt their resources. Pick the victim that costs least to lose — here P2 (cost 40). Killing it frees its resources, breaks the cycle, and the survivors proceed. Cap how often any one process can be the victim, or you risk starvation.
Which Method to Choose?
| Method | When to use | Overhead | Real-world example |
|---|---|---|---|
| 🛡️ Prevention | Safety-critical systems | Design-time discipline | Avionics, medical devices |
| 🧭 Avoidance | Max needs known in advance | High — check per request | Real-time systems, known workloads |
| 🔍 Detection | Long-running servers | Periodic algorithm cost | Oracle, PostgreSQL, MySQL |
| 🙈 Ignore | Consumer OS, deadlocks rare | Zero | Windows, macOS, Linux desktop |
Databases run millions of concurrent transactions, so they detect deadlocks and abort the cheapest transaction. Your laptop, where a deadlock is a once-in-a-blue-moon event, just lets you reboot — paying zero overhead every other day.
Seven Rules for Deadlock
Deadlock — Understood End to End
From the four conditions and the resource-allocation graph, through prevention, avoidance, detection and recovery — you can spot a potential deadlock, prove whether a graph is deadlocked, and choose the right handling strategy for the stakes involved.
The natural sequel is the Banker's Algorithm — the full safe-state check with Allocation, Max, Need and Available matrices worked out step by step, which turns "avoidance" from a concept into a procedure you can run.
🔒 End of tutorial · Press ← to review, or click Restart