A deadlock is a set of threads (or processes, or transactions) where each one is waiting for something another one in the set holds, so none of them can ever proceed. CPU use drops to zero, requests time out, and nothing in the logs says why. It’s one of the most-asked concurrency topics because the classic version is easy to write by accident, and the standard fix is simple enough to explain on a whiteboard in two minutes.
Two transfers in opposite directions
Here’s the textbook case. Each bank account has its own lock, and a transfer locks the source, then the destination. Thread one moves money from A to B while thread two moves money from B to A. A barrier makes sure each thread holds its first lock before trying for the second, so the bad interleaving happens every time instead of once a month:
import threading
class Account:
def __init__(self, id, balance):
self.id, self.balance, self.lock = id, balance, threading.Lock()
def transfer_naive(src, dst, amount, barrier=None):
with src.lock:
if barrier: barrier.wait() # make sure both threads hold their first lock
with dst.lock:
src.balance -= amount; dst.balance += amount
a, b = Account(1, 100), Account(2, 100)
barrier = threading.Barrier(2)
t1 = threading.Thread(target=transfer_naive, args=(a, b, 10, barrier), name="a-to-b", daemon=True)
t2 = threading.Thread(target=transfer_naive, args=(b, a, 20, barrier), name="b-to-a", daemon=True)
t1.start(); t2.start(); t1.join(1); t2.join(1)After a second, the script prints which threads are still alive and where each is stuck, using sys._current_frames(), which is a do-it-yourself thread dump:
after 1 s, alive: ['a-to-b', 'b-to-a']
a-to-b waiting at line 10 in transfer_naive(): with dst.lock:
b-to-a waiting at line 10 in transfer_naive(): with dst.lock:Both threads are on the same line, each waiting for the lock the other holds. Draw it as a wait-for graph and the problem is visible at once:
a-to-b --holds--> lock A b-to-a --holds--> lock B
a-to-b --waits--> lock B b-to-a --waits--> lock A
a-to-b -> (waits for holder of B) b-to-a -> (waits for holder of A) a-to-bA cycle in the wait-for graph is a deadlock. Without the daemon flag and the timeout on join, this script would hang forever.
The four conditions
In 1971 Coffman, Elphick and Shoshani described four conditions that must all hold for a deadlock to occur. Interviewers often ask you to name them, and the useful part is mapping each one onto the example, because breaking any single one prevents the deadlock:
- Mutual exclusion. A resource can be held by only one thread at a time. Each account lock admits one holder.
- Hold and wait. A thread holds one resource while waiting for another. Each transfer keeps its first lock while asking for the second.
- No preemption. Resources can’t be taken away; the holder must release them. Nothing forces a thread to give up lock A.
- Circular wait. There’s a cycle of threads, each waiting for a resource held by the next. A-to-B waits for B-to-A, which waits for A-to-B.
Breaking circular wait with a global order
The most practical fix is to make every thread acquire locks in the same global order. If everyone locks the lower account ID first, a cycle is impossible: a thread holding lock 2 never waits for lock 1, so no thread can be waiting “backwards” around a loop.
def transfer_ordered(src, dst, amount):
first, second = (src, dst) if src.id < dst.id else (dst, src)
with first.lock:
with second.lock:
src.balance -= amount; dst.balance += amountFour threads doing 100,000 random-direction transfers each between the same two accounts:
ordered: 400000 transfers in 0.15s, total balance 2000No hang, and the total is conserved. The order can be anything stable and total: a database ID, an account number, even the memory address of the lock object for in-process locks. The hard part in real code is that lock acquisitions hide inside other functions, callbacks and libraries, so two code paths can disagree about order without either looking wrong. Large codebases enforce ordering with tooling: the Linux kernel’s lockdep records the order in which lock classes are taken at run time and warns the first time it sees an ordering that could form a cycle, even if no deadlock actually happened.
Other ways out
You can attack the other three conditions too, each with a trade-off.
Hold and wait. Acquire everything you need at once, or none of it. One version is try-lock with back-off: take the first lock, try the second, and if it’s busy, release the first and retry after a random delay. This works, but without the randomness two threads can back off and retry in lockstep forever. That’s livelock: both threads busy, neither making progress.
No preemption. Allow a waiter to give up. lock.acquire(timeout=0.5) in Python, or tryLock(timeout) in Java, turns an infinite wait into an error you can handle, usually by releasing everything and retrying the whole operation. Databases do the forceful version: PostgreSQL waits deadlock_timeout (one second by default), then checks the wait-for graph and aborts one transaction with ERROR: deadlock detected. Your application must be ready to retry it.
Mutual exclusion. Don’t share the resource. Give each account to a single owner thread and send it messages, use immutable data, or use a lock-free structure. This removes the risk entirely but usually means redesigning, not patching.
There’s also avoidance: the banker’s algorithm grants a request only if the system stays in a state where every thread can still finish. It needs every thread’s maximum demand in advance, which real programs rarely know, so it’s mostly a textbook topic.
Deadlocks without explicit locks
The conditions are about resources in general, and some of the nastiest deadlocks involve no mutex at all.
A thread pool is a fixed set of resources. If tasks submit subtasks to the same pool and block waiting for them, the pool can fill with parents waiting for children that are queued behind them:
from concurrent.futures import ThreadPoolExecutor, TimeoutError
pool = ThreadPoolExecutor(max_workers=4)
def child(i):
return i * i
def parent(i):
f = pool.submit(child, i) # queued behind the other parents
return f.result() # this worker now waits for a free worker
futures = [pool.submit(parent, i) for i in range(4)]no parent finished within 2 s; work queue holds 4 child tasksWith five workers instead of four, the same code printed [0, 1, 4, 9], because one free worker could run the children. That’s what makes this bug load-dependent: it appears only when enough parents arrive together.
Pipes do it too. A parent that writes a large input to a child’s stdin before reading the child’s stdout can block when the pipe buffer fills, while the child blocks writing output nobody is reading. That’s why Python’s subprocess documentation tells you to use communicate() instead of writing and reading the pipes by hand. And a single thread can deadlock with itself: acquiring a non-reentrant lock it already holds blocks forever (an error-checking pthread mutex returns EDEADLK instead).
Interview practice: a thread pool that stops dead
A Java service handles each request on a fixed pool of 16 threads. Each request handler submits two lookups to the same pool and calls future.get() on both. Under a traffic spike the service stops responding entirely, CPU is near zero, and a thread dump shows all 16 threads parked in FutureTask.get. Explain what happened in terms of the four conditions and fix it.
Answer
The resources are the 16 pool threads. During the spike, 16 request handlers occupied all of them, each submitted its lookups to the pool’s queue, and each blocked waiting for results. The lookups can only run on a pool thread, and every pool thread is a handler waiting for a lookup. Mapping it: mutual exclusion, a worker runs one task at a time; hold and wait, each handler keeps its thread while waiting; no preemption, a blocked task can’t be suspended to free its thread; circular wait, handlers wait for lookups, which wait for a thread held by a handler.
Fixes, in rough order of preference: don’t block inside the pool. Compose the futures asynchronously (CompletableFuture.thenCombine and return the combined future), so a handler releases its thread while it waits. Or run the lookups on a separate executor, which removes the cycle because handlers and lookups no longer compete for the same resource. A ForkJoinPool with join() also avoids it, because a joining worker runs queued tasks itself instead of just waiting. Simply making the pool bigger only raises the traffic level at which it happens again. I’d also add a timeout on get() so a future recurrence shows up as errors rather than a silent hang.
Further reading
- Operating Systems interview questions
- Operating Systems MCQs
- Mutexes Versus Semaphores and Resource Ownership
- Operating Systems: Thread Pools
- OSTEP, Common Concurrency Problems, covering the deadlock conditions and how real systems prevent each one