Deadlocks — Detection, Prevention & the Coffman Conditions

A deadlock is a cycle of waiting: a set of transactions where each holds a lock another needs and waits for a lock another holds, so none can ever proceed. It is the dark side of pessimistic locking — once transactions can block each other, they can block each other in a circle. The whole topic collapses into one master key: a deadlock needs all four Coffman conditions at once, so breaking any single one makes deadlock impossible.

Intermediate transactions deadlock coffman-conditions circular-wait wait-for-graph deadlock-detection deadlock-timeout 40P01 lock-ordering livelock Created 2026-06-15 · Updated 2026-06-15

Key Components

Deadlock: A situation in which no member of a group of transactions can proceed because each is waiting for a lock another member holds — a frozen cycle of waiting. It can arise even without explicit locking: two plain UPDATEs touching the same rows in opposite order are enough.
The four Coffman conditions: The four properties that must hold simultaneously for a deadlock (Coffman, 1971): mutual exclusion (a resource serves one holder at a time), hold and wait (a transaction holds one lock while requesting another), no preemption (a lock is released only voluntarily), and circular wait (a cycle of transactions each waiting on the next). Break any one and deadlock is impossible.
Wait-for graph: The detection structure: nodes are transactions, and an edge T1→T2 means "T1 waits for a lock T2 holds." A cycle in this graph is exactly a deadlock. (The resource-allocation graph is the fuller version with resource nodes too; databases use the transaction-only wait-for projection.)
deadlock_timeout: The interval (Postgres default 1s) a blocked transaction waits before the engine runs deadlock detection. Cycle-checking is expensive and most waits are ordinary contention that clears on its own, so the engine optimizes for the common case and only builds the graph if the wait persists.
Victim abort (SQLSTATE 40P01): The recovery action: on detecting a cycle, the engine picks one transaction, rolls it back to break the loop, and lets the others proceed. In Postgres this surfaces as ERROR: deadlock detected with SQLSTATE 40P01. The application must catch it and retry.
Livelock: The cousin of deadlock: transactions are not frozen but keep retrying-and-colliding forever, changing state yet making no progress. A naive no-delay retry loop turns a resolved deadlock into a livelock; the fix is randomized exponential backoff.

Concrete Example

The canonical database deadlock needs no explicit LOCK statement — just two transactions touching the same two rows in opposite order. Row-level locks taken by ordinary UPDATEs are enough:

-- T1                                          -- T2
UPDATE accounts SET ... WHERE acctnum = 11111; -- locks 11111
                                               UPDATE accounts SET ... WHERE acctnum = 22222; -- locks 22222
UPDATE accounts SET ... WHERE acctnum = 22222; -- BLOCKS (T2 holds it)
                                               UPDATE accounts SET ... WHERE acctnum = 11111; -- BLOCKS (T1 holds it)
-- T1 is blocked on T2, and T2 is blocked on T1: a deadlock condition.

Both transactions are now waiting for a lock the other holds, and neither will ever release first. After deadlock_timeout, Postgres detects the cycle and aborts one of them with 40P01 so the other can finish.

The deadlock exists only because the rows were locked in opposite order. Impose a single consistent global order — always lock the lower account number first — and the circular wait can never form:

-- Both transactions agree: always lock the LOWER acctnum first.
-- T1                                          -- T2
UPDATE accounts SET ... WHERE acctnum = 11111; -- locks 11111
                                               -- wants 11111 too → simply WAITS for T1
UPDATE accounts SET ... WHERE acctnum = 22222; -- locks 22222
COMMIT;                                        -- releases both
                                               UPDATE accounts SET ... WHERE acctnum = 11111; -- now proceeds
                                               UPDATE accounts SET ... WHERE acctnum = 22222;
                                               COMMIT;

With consistent ordering there is still contention — T2 waits for T1 — but no cycle: a cycle would require someone holding a higher lock while waiting for a lower one, which the ordering rule forbids. This is the single most practical takeaway, and the PostgreSQL docs state it directly: the best defense is being certain that all applications acquire locks on multiple objects in a consistent order.

Visual Model

Picture two people in a narrow one-person hallway, each standing in the doorway the other needs and refusing to back up. Nobody can pass, nobody will yield — that frozen standoff is a deadlock. The wait-for graph below draws the same standoff for transactions: each node is a transaction holding a row lock, and an arrow means "is waiting for." When the arrows form a closed loop, you have a cycle, and a cycle is a deadlock. Postgres plays the bouncer: it waits about a second, spots the loop, and drags one transaction out so the other can move.

Step through the formation and resolution below. Watch the two edges close into a cycle (the warning state), then watch the detector break it by aborting a victim — which is precisely how detect-and-recover violates the no-preemption condition.

Step 1 of N

Loading…

Deeper — Edge Cases & Gotchas

The four handling strategies

Every approach to deadlocks falls into one of four buckets, trading rigidity against wasted work:

Prevention — structurally deny one Coffman condition by design (e.g. resource-hierarchy lock ordering kills circular wait). Strong but rigid.
Avoidance — analyze each request at runtime and grant it only if the system stays in a "safe state" (the Banker's algorithm). Needs every transaction's maximum needs known in advance, so it is almost never used in real databases.
Detection + recovery — let deadlocks happen, maintain a wait-for graph, and on finding a cycle abort a victim (breaking no-preemption) so the others proceed. This is what Postgres and MySQL do.
Ignore (the Ostrich algorithm) — assume a deadlock will never occur. Some operating systems do this; databases do not.

Every strategy attacks exactly one Coffman condition

This table is the master key spelled out: each row removes one of the four conditions, and removing any one makes deadlock impossible. The shading tracks how practical each attack is for a real database under write workloads.

Condition attacked	How	Verdict for real DBs
Mutual exclusion	lock-free structures / MVCC reads (no read locks)	not possible for writes
Hold and wait	grab all locks atomically upfront = Conservative 2PL	kills concurrency; needs predeclared lock set
No preemption	abort + roll back a victim (steal its locks)	wasted work, but what real DBs actually do
Circular wait	global lock ordering (always lock 11111 before 22222)	the practical app-level fix

Note that pure reads cannot deadlock: shared (S) locks are compatible with each other, so mutual exclusion only bites on writes. And Conservative 2PL is deadlock-free precisely because it eliminates hold-and-wait — a transaction acquires its entire lock set atomically at the start and so never holds one lock while waiting for another.

How Postgres handles it, step by step

Postgres uses detection + recovery with a deliberate delay. A blocked transaction first waits deadlock_timeout (default 1s) before detection runs at all — because building and cycle-checking the wait-for graph is expensive, and the overwhelming majority of waits are ordinary contention that clears on its own. Only if the transaction is still blocked after the timeout does Postgres build the graph and look for a cycle. On finding one it picks a victim (exactly which is hard to predict), aborts it with SQLSTATE 40P01, and lets the rest complete. The application must catch 40P01 and retry — the same retry discipline as the 40001 serialization failures from isolation levels: different code, same contract.

Anti-pattern: retrying the aborted transaction in a tight, no-delay loop. This converts a cleanly-resolved deadlock into a livelock — the transactions are no longer frozen, but they keep retrying in lockstep and colliding again, changing state forever while making no progress.

# BROKEN: no-delay retry → livelock (both retry instantly, re-collide, repeat)
while True:
    try:
        run_transaction()      # T1 and T2 both abort, both retry at once…
        break
    except DeadlockDetected:   # SQLSTATE 40P01
        continue               # …and immediately deadlock again, forever

# FIX: randomized exponential backoff
delay = base
for attempt in range(max_retries):
    try:
        run_transaction()
        break
    except DeadlockDetected:
        time.sleep(random.uniform(0, delay))   # jitter breaks symmetry
        delay *= 2                              # backoff spreads load

Why it breaks: with zero delay both victims retry simultaneously and re-enter the same conflict, so they collide again and again. The fix is randomized exponential backoff: the random jitter breaks the lockstep symmetry so the two transactions stop colliding at the same instant, and the exponential backoff spreads retries out so load eases. The clean distinction to remember — a deadlock is frozen (no state change), a livelock is active but stuck (state changes, no progress).

Test Yourself

In the two-UPDATE opposite-order deadlock, which Coffman condition does enforcing "consistent lock ordering" eliminate?

A wait-for graph has nodes for transactions and an edge T1→T2 meaning "T1 waits for a lock T2 holds." What signals a deadlock, and which Coffman condition does detect-and-abort break?

Why does Postgres wait deadlock_timeout (default 1s) before running deadlock detection, instead of checking immediately on every block?

Conservative 2PL is deadlock-free. Which Coffman condition does it eliminate, and how?

Two transactions keep aborting on deadlock, retrying instantly, and re-colliding forever without ever committing. What is this called, and what is the fix?