Deadlock & the 4 Necessary Conditions
Scenario
Two threads each grab one lock, then each waits forever for the lock the other is holding. The program just... stops. No crash, no error.
What exactly has to be true for this freeze to be possible - and which single condition is easiest to break?
Mental model
A deadlock is four cars at a 4-way stop, each waiting for the car on its right to go first.
Nobody is broken; everyone is just politely waiting on someone who is also waiting. The system is alive but frozen. Break any single link in the waiting cycle and traffic flows again.
Explanation
Start with the simplest case: two threads and two locks. Thread 1 grabs Lock A and, partway through its work, finds it also needs Lock B to finish. At that exact moment Thread 2 has already grabbed Lock B and now needs Lock A. Neither will release what it holds until it finishes - but neither can finish without the lock the other is sitting on. They wait on each other forever. The program hasn't crashed; it is still 'running'. It just produces permanent silence.
That frozen state is a deadlock: a set of processes, each blocked waiting for a resource that another process in the same set is holding. With more threads the waiting doesn't just pair up - it forms a closed loop, exactly the ring in the animation above, where A waits on B, B on C, C on D, and D back on A.
In 1971 Coffman showed this can happen ONLY when four conditions are all true at the same time. Mutual exclusion: a resource can be held by just one process at a time. Hold-and-wait: a process keeps the resources it already holds while requesting more. No preemption: the system cannot forcibly take a resource back - the holder must release it voluntarily. Circular wait: there is a closed chain of processes, each waiting for a resource the next one holds.
Here is why those four matter so much: because ALL of them are required, you only have to break ONE to make deadlock impossible. That single fact is the entire basis of deadlock prevention. In practice the easiest condition to attack is circular wait - if every thread must acquire locks in the same global order (say, always A before B), a closed loop can never form.
Finally, don't confuse deadlock with starvation. In starvation the system as a whole keeps making progress; one unlucky process just keeps getting passed over. In deadlock, nothing in the stuck set ever moves again.
Key points
- Mutual exclusion: At least one resource is held in a non-shareable mode - only one process can use it at a time.
- Hold and wait: A process holding at least one resource is waiting to acquire additional resources held by others.
- No preemption: A resource cannot be forcibly taken away; it is released only voluntarily by the process holding it.
- Circular wait: A closed chain of processes exists where each is waiting for a resource that the next one in the chain holds.
Common mistakes
- Confusing deadlock with starvation: Deadlock = a cycle where every process in the set is stuck forever. Starvation = one process keeps getting passed over while the system overall still progresses.
- Thinking the four conditions are independent: All four must hold AT ONCE. Prevention works by making just ONE of them impossible - usually circular wait, via a global resource-ordering rule.
Glossary
- deadlock
- A permanent state where two or more programs are completely stuck because each is waiting for the other to release a resource, causing everything to freeze.
- thread
- A small sequence of instructions or tasks within a program that the computer can execute independently.
- lock
- A software mechanism that prevents multiple programs from accessing the exact same piece of data or resource at the exact same time.
Recall questions
- Name the four necessary conditions for deadlock.
- Why does breaking circular wait prevent deadlock?
- Deadlock vs starvation - the one-line difference?
Questions & answers
How would you prevent deadlock in a system that uses multiple locks?
Impose a global lock-acquisition order so a circular wait can never form; alternatively use try-lock with backoff or lock-free structures.
Approach: Anchor the answer to breaking ONE Coffman condition - resource ordering kills circular wait and is the cleanest, most common real fix.
A web server hangs intermittently under load with no error. How do you suspect and confirm a deadlock?
Symptoms: threads blocked, CPU idle, no progress. Confirm with a thread dump showing a cycle of threads each waiting on a lock another holds.
Approach: Distinguish deadlock (idle CPU, cyclic wait) from a livelock or thrashing (busy CPU, no progress).