The question this answers
Two threads are alive, each holding a lock it acquired correctly, and neither will ever make progress again — how do I find the cycle that did it?
Two concurrent transfers between the same pair of accounts: transfer(7, 12, 50) on one request thread and transfer(12, 7, 30) on another, each locking both account rows before touching a balance.
Two account records, each guarded by its own mutex. Nothing else is shared — which is precisely why this surprises people, because each lock is used correctly when you read either thread on its own.
Every thread that acquires a lock eventually releases it, so every thread waiting on a lock eventually acquires it. Deadlock breaks *that* invariant — the liveness one. The safety invariant the locks were protecting (the sum of the two balances never changes) still holds perfectly while the process hangs, which is why no assertion fires and no data looks wrong.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The schedule where nobody moves
Deadlock is not a rare cosmic event. It is one specific interleaving of two schedules that are individually fine, and you can write it down in six steps. Both threads follow the same code path — lock the source account, lock the destination account, move the money, unlock both — and both are correct in isolation. The only thing that differs is the argument order.
Read the trace below one step at a time and watch the point of no return arrive. It is step 4. After step 4 there is no schedule, no scheduler decision and no amount of waiting that recovers: A is blocked until B releases L12, B releases L12 only after acquiring L7, and A holds L7 until it returns. Every thread is doing exactly what it was told.
Notice what is *not* happening. Nobody is spinning, no CPU is burning, no memory is corrupt. Both threads are in the OS blocked state — see Process States — which is why a CPU graph during a deadlock looks like an idle system rather than a broken one.
| # | Thread A — transfer(7 → 12, 50) | Thread B — transfer(12 → 7, 30) | State |
|---|---|---|---|
| 1 | lock(L7) — acquired | · | L7=held by A L12=free |
| 2 | · | lock(L12) — acquired | L7=held by A L12=held by B |
| 3 | lock(L12) — blocks | · | L7=held by A L12=held by B A state=blocked on L12 |
| 4 | · | lock(L7) — blocks | L7=held by A L12=held by B A state=blocked on L12 B state=blocked on L7 ✕ Liveness: A releases L7 only after it gets L12, and B releases L12 only after it gets L7. The wait-for edges now form a cycle and neither lock will ever be released. |
| 5 | (no further steps possible — thread is off the run queue) | · | |
| 6 | · | (no further steps possible) |
Draw the wait-for graph and look for a cycle
The diagnostic tool for deadlock is a graph, not a debugger. Make one node per thread and one node per lock. Draw an edge from a thread to a lock it is *waiting for*, and an edge from a lock to the thread that *holds* it. A deadlock exists exactly when that graph contains a directed cycle — this is the same cycle-detection problem the DSA domain teaches on a Directed Graph, and a database lock manager runs it on a timer for precisely this reason.
This is why the graph is worth drawing rather than reasoned about in prose. Two threads and two locks make a cycle you can see in your head; four threads and five locks make a cycle you cannot. The graph scales, the intuition does not.
The graph also tells you what to break. A cycle can be destroyed by removing any single edge, and each edge corresponds to a different prevention technique: remove the wait edge with a try-lock, remove the hold edge by not holding across the second acquisition, or make the cycle unconstructable by imposing a global order. That last one is the practical answer — see Lock Ordering — and the full menu is Preventing Deadlock.
What it actually looks like at 03:00
Deadlock does not announce itself. There is no exception, no log line, no error rate. What you see is a service that stops answering while its CPU sits near zero, its memory is flat, and its health check — if the health check does not take the same locks — keeps returning 200. Requests pile up in the accept queue and the load balancer eventually marks the instance unhealthy for timing out, which is three symptoms downstream of the cause.
The evidence lives in a thread dump. Every runtime has one, and the dumps are the reason the wait-for graph is worth knowing: modern JVM and .NET dumps will find and print the cycle for you, while a gdb backtrace of every thread or a Python faulthandler dump makes you assemble it by hand. See Reading a Thread Dump for reading them, and take two dumps thirty seconds apart — identical stacks in both is the confirmation that the threads are stuck and not merely slow.
The database version of this is worth knowing because it behaves completely differently. Postgres and InnoDB run deadlock *detection*, find the cycle, and abort one transaction with a retryable error. Your application deadlock has no detector: nothing aborts, nothing retries, and the process hangs until someone restarts it.
"http-nio-8080-exec-4" #34 prio=5 BLOCKED waiting to lock <0x00000000d7f1a2b8> (Account@12) locked <0x00000000d7f0e140> (Account@7) at TransferService.transfer(TransferService.java:41) "http-nio-8080-exec-9" #39 prio=5 BLOCKED waiting to lock <0x00000000d7f0e140> (Account@7) locked <0x00000000d7f1a2b8> (Account@12) at TransferService.transfer(TransferService.java:41) Found one Java-level deadlock: exec-4 -> exec-9 -> exec-4 host metrics during the same window: cpu.user 1.2% <- not a hot loop runnable.threads 0 <- not a scheduling problem http.inflight 200 <- the pool is full of corpses http.error_rate 0% <- nothing failed; things stopped
Key points
- Deadlock is a liveness failure, not a safety failure — the data stays consistent, and that is why nothing alerts.
- It is one specific interleaving of two individually correct threads, which is why it survives code review and unit tests.
- The diagnostic is a wait-for graph: threads and resources as nodes, "waits for" and "held by" as edges, deadlock as a directed cycle.
- The signature is a service that stops with near-zero CPU and a 0% error rate — a hang, not a crash.
- Application deadlock has no detector. Databases abort a victim transaction; your process just stops.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Thread A acquires lock L7 and enters a region where it holds L7 while asking for more.
- • Thread B acquires L12 and enters the mirror-image region.
- • A requests L12, finds it held, and the OS moves A off the run queue into a blocked state on L12's wait queue.
- • B requests L7, finds it held by a thread that is itself blocked, and joins L7's wait queue.
- • The wait-for graph now contains the cycle A → L12 → B → L7 → A; no scheduler decision can break it because neither thread is runnable.
- • Every subsequent request that needs either account joins one of the two wait queues, so the deadlock spreads through the thread pool until nothing is left to serve.
- • A locks L7; A locks L12; A transfers and unlocks both; B locks L12; B locks L7; B transfers. Serialised, correct, and the schedule you get 99.9% of the time.
- • A locks L7; B locks L12; A waits on L12; B waits on L7 — the cycle closes on the fourth step and the process never recovers.
- • A locks L7; B locks L12; A waits on L12; B *finishes without needing L7* — no deadlock, because the cycle requires both wait edges to exist simultaneously. Deadlock needs the pairing, not just the interleaving.
- • Three threads, three locks: A holds L1 wants L2, B holds L2 wants L3, C holds L3 wants L1. Same cycle, invisible in any pairwise code review, which is the argument for the graph.
- • A locks L7; A calls a slow HTTP client while still holding L7; B locks L12 then waits on L7 for the length of the network call. Not yet a deadlock — but the window in which one can form just grew from microseconds to seconds. See Lock Scope: What You Hold It Across.
- • A mutex guarantees mutual exclusion of its critical section. It guarantees nothing about the *order* in which locks are acquired across your codebase, and it has no idea another mutex exists.
- • It guarantees that a waiter will acquire the lock once the holder releases it. It does not guarantee the holder ever will.
- • Blocking on a mutex does not time out on its own in most APIs.
lock()waits forever by design; onlytry_lockand timed variants give you an escape. - • Nothing in a mutex API detects cycles. The detection you may have seen belongs to database lock managers and to some runtime dump tools — see Deadlock Detection: The Waits-For Graph — not to the primitive itself.
- • Deadlock freedom is a property of the *whole program's* lock-acquisition order, not of any individual function. No amount of local reasoning proves it.
- • Before the cycle closes, this looks exactly like ordinary contention: threads waiting briefly on a busy lock. That is why lock-wait dashboards do not distinguish "hot lock" from "about to deadlock".
- • After the cycle closes, contention becomes unbounded: every arriving request that needs either lock parks forever, and the wait queue length grows with arrival rate.
- • The cost is the whole thread pool. Two dead threads become two hundred as soon as traffic touches the same accounts, because each new request is a fresh thread joining a queue that never drains.
- • The deeper the lock nesting, the wider the window between the first acquire and the last, and the window is where the interleaving has to land. Holding a lock across a blocking call widens it by six orders of magnitude.
- • Deadlock (circular wait): the canonical case above — permanent, silent, and unrecoverable without a restart.
- • Self-deadlock: one thread re-acquires a non-reentrant mutex it already holds, typically through a callback or a recursive helper. A cycle of length one. See Reentrancy.
- • Lock-order inversion that has not deadlocked yet: the code contains both orderings but the interleaving has not occurred. A latent deadlock, and the one a static analyser or a race detector can actually find for you.
- • Deadlock between a lock and a queue: a thread holds a mutex while blocking on a full bounded queue whose consumer needs the same mutex. Same cycle, different resource types — the graph does not care.
- • Thread pool exhaustion masquerading as deadlock: a pool task blocks waiting for another task that can never be scheduled because the pool is full. See Pool Saturation.
- • Taking two locks at once is genuinely correct when an invariant spans two objects — a transfer must see both balances under one consistent view, or the "total money is conserved" invariant is observable as broken.
- • It helps when the alternative is a single coarse global lock that serialises every account in the system; two fine-grained locks let unrelated transfers run in parallel.
- • It is the right shape when the lock hold time is short, bounded, and contains no I/O — the window for an inversion is then measured in microseconds.
- • Any time the second lock is acquired while an unbounded operation is in flight — an HTTP call, a database query, a disk write — the deadlock window becomes large enough to hit in production.
- • When the set of locks is open-ended (a lock per user, per row, per cache key), no developer can hold the acquisition order in their head, and the discipline degrades silently as the codebase grows.
- • When the invariant does not actually span both objects. Plenty of two-lock code exists because someone was cautious, not because anything required it — and that code is pure deadlock risk with no correctness benefit.
- • Two thread dumps thirty seconds apart with identical stacks in a
BLOCKED/Lock waitstate — the confirmation, not just the suspicion. - • The characteristic metric triple: request in-flight count pinned at the pool ceiling, CPU near idle, error rate zero. Together these mean "stopped", and only deadlock and full-pool blocking produce them.
- • JVM
ThreadMXBean.findDeadlockedThreads(), .NET dump analysis,pstack/gdb thread apply all bt, Pythonfaulthandler.dump_traceback_later()— a periodic self-dump that fires when a watchdog stops being fed. - • Lock-wait time p99 climbing toward infinity for one specific lock pair while p50 stays flat is the pre-deadlock signature. See
lock-contentionin Observability & Performance and Hold Time, Wait Time, and the Ratio Between Them. - • Deliberate stress testing that randomises the interleaving is the only way to find it before production — see Stress Testing: A Test That Passed Once Proves Nothing.
- • Deadlock freedom is a global property, so every new lock added anywhere in the codebase is a proof obligation on every existing lock. That cost grows quadratically with the number of locks, not linearly.
- • It cannot be unit tested in any meaningful sense: the schedule that deadlocks is one of thousands and the test scheduler will not choose it.
- • Recovering at runtime means either timed acquisition everywhere (which turns a hang into an error path you must then handle) or a watchdog that restarts the process (which turns it into an availability event).
- • Every prevention technique costs something concrete — ordering costs a global convention nobody enforces automatically, try-lock costs a retry loop and a livelock risk, coarser locking costs parallelism.
- • One lock instead of two. If the two objects are almost always used together, a single lock covering both removes the cycle by removing the second edge — and costs you the parallelism you probably were not getting anyway.
- • Hand the work to a single owner. A queue with one consumer that performs all transfers serially has no locks at all and no possible cycle. See Message Passing and The Actor Model.
- • Let the database do it. A transaction taking row locks in a real lock manager gets deadlock detection and a retryable error for free — see Locks and Deadlocks and The Database Solves Concurrency For Its Data, Not For Your Memory.
- • Optimistic concurrency: read both balances, compute, then compare-and-swap on a version. No lock is held while thinking, so no cycle can form. It costs a retry loop under contention — see Optimistic Concurrency Control.
Build a deadlock yourself
The lost update, step by step
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=— |
| 2 | · | rB ← counter | counter=0 rA=0 rB=0 |
| 3 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 4 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=1 |
| 6 | · | counter ← rB | counter=1 rA=1 rB=1 ✕ 2 increments completed, counter = 1 |
What people believe, and what is true
Deadlock means something is corrupted.
The opposite. Every lock did its job and every invariant the locks protected still holds. That is what makes it silent — there is nothing wrong to detect except the absence of progress.
A deadlocked thread will eventually time out.
A plain lock()/acquire() has no timeout. It waits forever, by design. The timeout you are thinking of is on the HTTP request that gave up on the thread, several layers away.
Deadlocks need at least two locks.
They need a cycle. One non-reentrant mutex re-acquired by the same thread is a cycle of length one. A thread holding a lock while waiting on a bounded queue whose consumer wants that lock is a two-node cycle with no second mutex in it.
Go deeper
Overview
Deadlock is a cycle of "I am waiting for something you are holding". Two threads, opposite lock order, permanent stop. The data is fine; the progress is gone.
Practical
When a service hangs with idle CPU and a zero error rate, take two thread dumps thirty seconds apart. Identical BLOCKED stacks means deadlock. Then read the "waiting to lock"/"locked" pairs and draw the graph — the cycle falls out in a minute.
Advanced
Deadlock freedom is not compositional: two deadlock-free modules combine into a deadlocking program the moment one calls into the other while holding a lock. This is the real argument against holding locks across any call you do not own — you cannot know what it locks. A documented, enforced global lock order is the only technique that composes.
Internals
Database lock managers make the opposite trade: they *allow* cycles and detect them, running a periodic wait-for-graph search and aborting the cheapest victim with a retryable error. That is affordable because a transaction has a defined rollback; your in-memory state has none, which is why application code prevents rather than detects. See Deadlock Detection: The Waits-For Graph and The Lock Manager.