Deadlocks
The four conditions, prevention vs avoidance vs detection, and the banker’s algorithm.
What is a Deadlock?
A deadlock is a cycle where each process holds a resource and waits for one another process holds — so none can proceed, forever. Two threads, two locks, grabbed in opposite order, is the textbook case.
Thread 1: lock(A) … lock(B) Thread 2: lock(B) … lock(A) If both grab their first lock, each now waits on the lock the other holds → stuck.
The Four Coffman Conditions
A deadlock is possible only if all four hold at once. Break any one and deadlock cannot occur:
| Condition | Meaning | Break it by… |
|---|---|---|
| Mutual exclusion | Resource held exclusively | Making resources shareable (not always possible) |
| Hold and wait | Hold one, wait for another | Grab all resources at once, or none |
| No preemption | Can’t force a release | Allowing the OS to preempt/rollback |
| Circular wait | A cycle of waiting | Ordering resources and always locking in that order |
Handle It: Prevent / Avoid / Detect
| Strategy | Idea | Cost |
|---|---|---|
| Prevention | Design so a Coffman condition can’t hold | Can waste resources |
| Avoidance | Grant only if system stays "safe" (Banker’s) | Needs max-need known upfront |
| Detection + recovery | Let it happen, find cycles, kill/rollback | Recovery is disruptive |
| Ostrich | Ignore it (reboot if rare) | What most OSes actually do |
Practical Fix: Lock Ordering
In real code, the cheapest prevention is a global lock ordering: every thread acquires locks in the same fixed order, which removes the circular-wait condition entirely.
- Always lock A before B, everywhere
- Thread 1 locks A→B, Thread 2 locks B→A
Interview Questions
Name the four conditions for deadlock.
Mutual exclusion, hold-and-wait, no preemption, and circular wait — all four must hold simultaneously.
Deadlock prevention vs avoidance?
Prevention structurally negates one of the four conditions upfront. Avoidance allows them but checks each allocation dynamically (Banker’s algorithm) to keep the system in a safe state.
Simplest way to prevent deadlock in application code?
Impose a global lock-acquisition order so no cycle can form (breaks circular wait). Also use lock timeouts / try-lock as a backstop.
What does the Banker’s algorithm need to know?
Each process’s maximum possible demand for each resource type, plus current allocations and availability, so it can test for a safe sequence.