Deadlock Explained: The Four Conditions and How to Break Them

A deadlocked service does not crash. There is no stack trace and no error in the log. Requests simply stop coming back while the CPU sits idle, because every thread that could make progress is waiting for another thread that is also waiting. The good news is that deadlock is not random bad luck. It needs four specific conditions to hold at the same time, and every standard fix works by removing one of them.

The problem it solves

Two bank transfers run at once. Transfer one moves money from Alice to Bob: it locks Alice's account, then Bob's. Transfer two moves money from Bob to Alice: it locks Bob's account, then Alice's. If each takes its first lock before the other takes its second, both wait forever. Nothing is wrong with either function on its own; the bug lives only in the interleaving, which is why it survives testing and shows up under load.

Knowing the conditions turns "add a timeout and hope" into a design decision: pick the condition that is cheapest to break in your system and break it on purpose.

The intuition

The four conditions were set out in 1971 by Coffman, Elphick and Shoshani. A deadlock is possible only when all of these hold:

1. Mutual exclusion. A resource can be held by only one thread at a time. A lock is exactly this.
2. Hold and wait. A thread keeps the resources it already has while it waits for more.
3. No preemption. A resource cannot be taken away from its holder; it is released only voluntarily.
4. Circular wait. There is a cycle of threads, each waiting for a resource the next one holds.

The first three describe ordinary locking and are true in most programs. The fourth is the one that actually closes the trap, and it is the one most fixes target. You can see it as a graph: draw an arrow from each waiting thread to the thread holding what it wants. A deadlock is a cycle in that wait-for graph.

Each condition suggests its own fix:

• Break circular wait: take locks in one global order, for example sorted by account id. A cycle needs someone to take a "later" lock before an "earlier" one, which the rule forbids.
• Break hold and wait: acquire everything you need at once, or hold nothing while waiting.
• Break no preemption: use a timed or non-blocking acquire; if the second lock is not available, release the first, back off and retry.
• Break mutual exclusion: avoid the shared lock altogether, with immutable data, per-thread copies or a single owner thread that receives messages.

Watch it run

The animation plays the lesson's standoff. Thread 1 takes lock A, thread 2 takes lock B, and then each asks for the other's lock. The two "wants" arrows cross in the middle of the stage: that X is the circular wait. Nothing crashes; both threads just park. The last frames apply the cheapest fix, a global order: both threads must take A first, so thread 2 waits for A instead of holding B, and thread 1 finishes.

The code

The deadlock itself, made safe to run. A barrier forces the bad interleaving, and a timeout on the second acquire lets the program report the deadlock instead of hanging:

import threading

a, b = threading.Lock(), threading.Lock()
both_hold_one = threading.Barrier(2)
both_gave_up = threading.Barrier(2)
results = {}

def worker(name, first, second):
    with first:
        both_hold_one.wait()                     # each thread now holds one lock
        got = second.acquire(timeout=0.5)        # ...and wants the other
        results[name] = "finished" if got else "stuck"
        if got:
            second.release()
        both_gave_up.wait()                      # keep holding until both tried

t1 = threading.Thread(target=worker, args=("t1", a, b))
t2 = threading.Thread(target=worker, args=("t2", b, a))
t1.start(); t2.start(); t1.join(); t2.join()
print(sorted(results.items()))                   # [('t1', 'stuck'), ('t2', 'stuck')]

Break circular wait. Both transfers sort their locks by a fixed key, so both try Alice's lock first. Whoever loses that race holds nothing while it waits:

locks = {"alice": threading.Lock(), "bob": threading.Lock()}
done = []

def transfer(src, dst):
    first, second = sorted([src, dst])           # one global order
    with locks[first], locks[second]:
        done.append(src + "->" + dst)

threads = [threading.Thread(target=transfer, args=p) for p in [("alice", "bob"), ("bob", "alice")] * 50]
for t in threads: t.start()
for t in threads: t.join()
print(len(done))                                 # 100

Break no preemption. If the second lock is busy, give up the first and try again. This avoids deadlock without a global order, at the price of retries:

def transfer_backoff(first, second):
    while True:
        with first:
            if second.acquire(blocking=False):   # never wait while holding
                second.release()
                return "ok"
        # first is released here; loop and retry

print(transfer_backoff(a, b))                    # ok

The claim that ordering removes deadlock, tested rather than trusted. A toy scheduler runs random threads that each acquire a random list of locks and then release them all, picking a random runnable thread at every step. A run is deadlocked when threads remain but none can move; the wait-for graph is then checked for a cycle:

import random

def has_cycle(waits_for):
    for start in waits_for:
        seen, at = set(), start
        while at in waits_for:
            if at in seen:
                return True
            seen.add(at)
            at = waits_for[at]
    return False

def simulate(plans, rng):
    owner, step = {}, [0] * len(plans)
    alive = set(range(len(plans)))
    while alive:
        runnable = [t for t in alive if owner.get(plans[t][step[t]]) in (None, t)]
        if not runnable:                         # nobody can move
            waits = {t: owner[plans[t][step[t]]] for t in alive}
            return "deadlock", has_cycle(waits)
        t = rng.choice(runnable)
        owner[plans[t][step[t]]] = t
        step[t] += 1
        if step[t] == len(plans[t]):             # done: release everything
            owner = {k: v for k, v in owner.items() if v != t}
            alive.discard(t)
    return "finished", False

rng = random.Random(4)
ok, deadlocks = True, 0
for _ in range(3000):
    plans = [rng.sample(range(4), rng.randint(1, 3)) for _ in range(rng.randint(2, 4))]
    outcome, cycle = simulate(plans, rng)
    if outcome == "deadlock":
        deadlocks += 1
        ok &= cycle                              # every deadlock is a cycle
    ordered = [sorted(p) for p in plans]
    ok &= simulate(ordered, rng)[0] == "finished"   # ordering never deadlocks
print(ok, deadlocks > 0)                         # True True

The complexity

Lock ordering costs nothing at runtime: a sort of two or three keys. Its cost is organisational, because every code path must agree on the order, including ones written next year. Backoff costs wasted work and, under heavy contention, livelock: threads that keep releasing and retrying in step without anyone finishing. Randomised backoff delays break the symmetry. Detection, building the wait-for graph and searching it for a cycle, is linear in the number of threads and edges, but it only tells you a deadlock happened; something must then be aborted and retried. PostgreSQL, for example, detects deadlocks between transactions and aborts one of them.

Where it goes wrong

• Orders that are only mostly global. One helper that locks "B then A" is enough to reintroduce the cycle. Enforce the order in one function, not by convention.
• Hidden locks. Calling out to unknown code, a callback or a logger, while holding a lock can acquire locks you never see. Release before calling out.
• Re-acquiring a non-reentrant lock. A thread that takes the same threading.Lock twice deadlocks with itself. Use RLock only when re-entry is really intended.
• Timeouts as the fix. A timeout turns a permanent hang into a retry, which is friendlier but is still the same bug, and it can turn into livelock.

How to say it in an interview

"Deadlock needs four conditions at once: mutual exclusion, hold and wait, no preemption and circular wait. Locks give you the first three for free, so the practical fix is usually to break circular wait with a global lock order, for example always locking accounts by id. Alternatives are to acquire everything at once, or to try-lock the second lock and release the first on failure, which risks livelock without random backoff. Detection is also possible: a cycle in the wait-for graph is a deadlock, and you abort one member."

The detection side has its own lesson, detecting deadlock, and the locks themselves are introduced in locks and mutexes.