Deadlocks: Conditions and Prevention
What a deadlock is, the four conditions that must all hold, how to prevent, avoid, detect and recover, and the simple lock-ordering fix that works in most real code.
A deadlock is a state where two or more threads wait for each other forever, each holding a resource the other needs. It can occur only when all four Coffman conditions hold: mutual exclusion, hold and wait, no preemption and circular wait. Interviewers expect the practical fix: acquire locks in one fixed global order to break circular wait.
A deadlock is a state where two or more threads wait for each other forever, each holding a resource the other needs. It can only occur if all four Coffman conditions hold: mutual exclusion, hold and wait, no preemption, and circular wait. Break any one and deadlock is impossible.
- A deadlock requires all four Coffman conditions at once: mutual exclusion, hold and wait, no preemption and circular wait, described by Coffman and colleagues in 1971.
- Acquiring every lock in one fixed global order prevents deadlock by breaking circular wait; for dynamic locks, order by a stable key such as account ID.
- The Banker's algorithm, by Dijkstra, grants a resource request only if the system stays in a safe state, where some order lets every process finish.
- An unsafe state in the Banker's algorithm does not mean a deadlock has happened, only that a deadlock is possible.
- Databases detect deadlocks by finding a cycle in the wait-for graph, then abort one victim transaction so the application can retry it.
- Lock timeouts are a deadlock recovery method, not a prevention design: they turn a silent hang into an error that can be handled by retrying.
01A deadlock in plain words
Two people each pick up one chair and need the second chair the other one is holding. Neither will put theirs down, and neither can proceed. That is a deadlock.
In code, thread 1 locks A and then tries to lock B. Thread 2 locks B and then tries to lock A. If each takes its first lock before the other asks for its second, both block forever. Nothing crashes and nothing is logged. The program just stops making progress, which makes deadlocks hard to notice and hard to reproduce.
02The four necessary conditions
Coffman and colleagues described these in 1971.
Mutual exclusion: a resource can be held by only one thread at a time.
Hold and wait: a thread holds some resources while waiting for others.
No preemption: a resource cannot be forcibly taken away; its holder must release it.
Circular wait: there is a cycle of threads, each waiting for a resource held by the next.
The first three describe the system. The fourth is the actual deadlock. Prevention strategies each attack one of these.
03Reproducing one safely
import threading
a, b = threading.Lock(), threading.Lock()
barrier = threading.Barrier(2) # make both threads take their first lock first
result = []
def t1():
with a:
barrier.wait()
got = b.acquire(timeout=0.5)
result.append(('t1 got b', got))
if got: b.release()
def t2():
with b:
barrier.wait()
got = a.acquire(timeout=0.5)
result.append(('t2 got a', got))
if got: a.release()
x, y = threading.Thread(target=t1), threading.Thread(target=t2)
x.start(); y.start(); x.join(); y.join()
print(sorted(result))With no timeout, both threads would block forever. With the 0.5 second timeout, at least one of them gives up (False), which releases its first lock and lets the other finish. Which thread gives up differs from run to run: in repeated runs sometimes t1 got b and t2 timed out, sometimes the reverse.
Timeouts are a way to recover, not a design. They turn a silent hang into an error you can handle by retrying.
04Prevention: break one of the conditions
The most practical fix is to break circular wait by giving every lock a fixed global order and always acquiring in that order. If both threads take a before b, nobody can hold b while waiting for a, so there is no cycle.
def worker():
with a:
with b:
... # both threads use the same order: a, then bRunning two threads of this form always finishes. For locks that are chosen dynamically, for example transferring money between two accounts, order by something stable such as account ID.
The other conditions can be attacked too, but with a cost. To avoid hold and wait, a thread must request all its resources at once, which wastes resources and can cause starvation. To allow preemption, the system takes resources back, which is only practical for things whose state can be saved, such as CPU registers or memory pages. Mutual exclusion usually cannot be removed, since some resources, like a printer, are inherently exclusive.
05Avoidance: the Banker's algorithm
Avoidance needs advance knowledge of each process's maximum demand. The OS grants a request only if there is still some order in which every process can finish. That is a safe state. An unsafe state does not mean deadlock has happened, but it means deadlock is possible.
The Banker's algorithm, by Dijkstra, checks this. Take a resource with 12 units. Three processes hold 5, 2 and 2 units, and could still need up to 5, 4 and 3 more. 3 units are free. The third process, which needs 3 more, can finish using those 3, and returns the 5 it then holds. That lets the first process (needs 5) finish and return 10, and then the second finishes too, so a safe order exists. Now suppose the 3 free units were instead handed to the first process. Zero units would be free and nobody could finish, so the algorithm refuses that grant.
It is a good teaching tool and a standard exam question. Real systems rarely use it, because processes seldom know their maximum needs in advance.
06Detection and recovery
If you do not prevent or avoid, you can detect. With one instance of each resource, build a wait-for graph: an arrow from each thread to the thread whose resource it is waiting for. A cycle means deadlock. Databases do exactly this, which is why one of two deadlocked transactions gets an error such as "deadlock detected" and is rolled back, and the application is expected to retry.
Recovery options are killing one or more processes in the cycle, rolling one back to an earlier checkpoint, or preempting a resource.
Many general-purpose operating systems take the "ostrich" approach for ordinary resources. They ignore the problem because deadlocks are rare and the cost of prevention is high, and leave it to application programmers to order their locks.
07Common interview questions
Q: What are the four conditions for deadlock?
A: Mutual exclusion, hold and wait, no preemption, circular wait. All must hold at the same time.
Q: Deadlock versus starvation?
A: In deadlock a group of threads are blocked on each other and none can proceed. In starvation a thread could proceed in principle but is repeatedly passed over.
Q: How do you prevent deadlock in code?
A: Acquire locks in a consistent global order, hold locks for as short a time as possible, and avoid calling unknown code while holding a lock. Use timeouts or try-lock where ordering is impossible.
Q: What is a safe state?
A: A state where there is at least one order in which all processes can run to completion with the resources available.
Q: How does a database handle deadlocks?
A: It detects cycles in the wait-for graph, picks a victim transaction, aborts it, and lets the others continue.