# Deadlocks Explained > What a deadlock actually is, the four conditions that must all be true for one to happen, and how to prevent and detect them in real code. --- # Deadlocks Explained Your program hangs. Not crashed, not slow - frozen, forever, using zero CPU, doing absolutely nothing. Two threads are alive and technically "running," except each one is waiting for something the other thread is holding, and neither will ever let go first. That's a deadlock: not a bug that produces a wrong answer, but a bug that produces no answer at all. This guide builds the concept from one concrete example, gives you the checklist for recognizing a deadlock, and ends with what to put in your code so it doesn't happen - and what to do when it happens anyway. ## How to read this Read it in order. Phase 1 walks through one concrete two-lock example and the mental model behind it. Phase 2 is the checklist: four conditions that must *all* be true simultaneously for a deadlock to occur. Phase 3 is practical - lock ordering, timeouts, detection tools, and what to do when a production process is hung right now. Examples use plain pseudocode; the trap is identical whether you're writing Java, C++, Go, Python, or Rust. ## The phases 1. [What a deadlock actually is](01-what-a-deadlock-is.md) - two threads, two locks, each waiting on the other forever. 2. [The four conditions that must all be true](02-the-four-conditions.md) - mutual exclusion, hold-and-wait, no preemption, circular wait. 3. [Preventing and detecting them in real code](03-preventing-and-detecting.md) - lock ordering, timeouts, detection tools, and what to do about a live hang. --- # What a deadlock actually is A **deadlock** is two or more threads (or processes) each waiting forever for a resource that another one of them is holding - and none of them will ever release what they're holding, because they're all stuck waiting too. Nobody makes progress. Nobody crashes. The threads are technically alive, scheduled, and doing nothing, forever, unless something outside the situation intervenes. That last part is what makes deadlocks so unpleasant to debug: there's no exception, no stack trace pointing at a line of broken logic, no log message screaming that something went wrong. The program stops responding, silently. CPU usage often drops to near zero for the stuck threads, because they aren't spinning - they're parked, asleep, waiting on something that will never arrive. ## A concrete two-lock example Picture a banking application transferring money between two accounts. To keep the transfer safe from other threads touching the same accounts mid-transfer, you lock both accounts involved before moving money. ```text Thread A: transfer(account1 -> account2) lock(account1) ... do some work ... lock(account2) # waits here move money unlock(account2) unlock(account1) Thread B: transfer(account2 -> account1) lock(account2) ... do some work ... lock(account1) # waits here move money unlock(account1) unlock(account2) ``` *What just happened:* imagine both threads start at nearly the same moment. Thread A grabs `account1`'s lock. Thread B grabs `account2`'s lock. Now Thread A tries to lock `account2` - but Thread B already holds it, so Thread A waits. Meanwhile Thread B tries to lock `account1` - but Thread A already holds *that* one, so Thread B waits too. ```text Thread A holds account1, wants account2 (held by B) Thread B holds account2, wants account1 (held by A) ``` *What just happened:* each thread is waiting on the other to finish and release its lock. Neither will, because neither can move forward without the lock the other refuses to give up. This is the deadlock, captured completely in two lines: a cycle of waiting with no way out. > Notice what's missing from this picture: no bug in the arithmetic, no race condition corrupting a balance, nothing wrong with either function in isolation. Run `transfer(account1, account2)` alone all day and it works perfectly. The bug only exists in the *combination* - two correct-looking functions, called concurrently, in the wrong relative order. ## Why it's forever, not merely slow A slow lock wait resolves eventually - the other thread finishes and releases it. A deadlock never resolves on its own, because the "other thread" that would release the lock is itself waiting on you. It's not a long queue; it's a queue that loops back on itself. There's no front of the line to reach. This is also why deadlocks are timing-dependent and hard to reproduce on demand: the scenario only occurs if both threads reach their first lock at close to the same moment, then reach for the second lock in opposite order. Code that deadlocks under production load might run thousands of times in testing without ever triggering it, purely by scheduling luck. ## The mental model to keep Picture it as a graph: each thread points an arrow at the resource it's waiting for, and each held resource points back at the thread holding it. A deadlock exists exactly when that graph contains a **cycle** - a loop you can trace that comes back to where it started. Two threads is the simplest possible cycle; production deadlocks sometimes involve three, four, or more threads all waiting in a longer loop, but the shape is identical. That cycle is the entire disease. Phase 2 breaks down the four specific conditions that have to hold at once for such a cycle to form. ```quiz [ { "q": "In the two-account transfer example, what causes the deadlock?", "choices": [ "A bug in the money-transfer arithmetic", "Thread A locks account1 then wants account2, while Thread B locks account2 then wants account1", "One of the threads crashes mid-transfer", "The accounts have insufficient balance" ], "answer": 1, "explain": "Each thread holds one lock and waits for the other's lock - a cycle of waiting with no way to break out." }, { "q": "Why is a deadlock different from a thread that's merely waiting a long time?", "choices": [ "A deadlock uses more CPU than a normal wait", "A deadlock always involves exactly two threads", "A normal wait eventually ends when the holder finishes; a deadlock's \"holder\" is itself stuck waiting, so it never ends", "A deadlock only happens with database locks, never in-process locks" ], "answer": 2, "explain": "A deadlock forms a cycle - there's no thread outside the wait that will ever finish and release what's needed." }, { "q": "Why are deadlocks often hard to reproduce in testing?", "choices": [ "They only happen on multi-core CPUs", "They require a specific, timing-dependent interleaving of both threads reaching their locks in opposite order", "Test frameworks automatically prevent deadlocks", "They only occur with more than 100 threads" ], "answer": 1, "explain": "The deadlock depends on both threads acquiring their first lock before either reaches for the second - a narrow timing window that low-load testing may never hit." } ] ``` Watch it animated: [deadlocks](/explainers/Deadlocks.dc.html) --- # The four conditions that must all be true Computer scientists Edward Coffman and colleagues identified, back in 1971, that a deadlock can only occur when four specific conditions are true **at the same time**. This is useful, not academic trivia: it means you don't need to prevent deadlocks in general, an intimidating and vague goal. You only need to make sure at least one of these four conditions can never hold in your system. Break any single one, and the whole cycle becomes impossible. ## 1. Mutual exclusion A resource can be held by only one thread at a time - two threads can't both hold the same lock simultaneously. This is the entire *point* of a lock. In the transfer example, only one thread can hold `account1`'s lock at once. ```text lock(account1) # if another thread already holds it, this one waits ``` *What just happened:* mutual exclusion is why Thread B can't barge in and use `account1` while Thread A holds it - it has to wait. That waiting is necessary for correctness, but it's also the raw material a deadlock is built from. ## 2. Hold and wait A thread holds at least one resource while simultaneously waiting to acquire another. Thread A holds `account1`'s lock while it waits for `account2`'s lock - it doesn't release what it already has, even though it's stuck waiting for something more. ```text lock(account1) # holding this... lock(account2) # ...while waiting for this ``` *What just happened:* this is the condition that turns "waiting" into "waiting *while blocking someone else*." If Thread A gave up `account1` the instant it had to wait for `account2`, Thread B could proceed and the deadlock would never form. ## 3. No preemption A resource can't be forcibly taken away from the thread holding it - it can only be released voluntarily, by the thread that holds it, when that thread is good and ready. The operating system (or your locking library) won't reach in and yank a lock out of Thread A's hands to hand it to Thread B, even though Thread B is waiting. ```text # no mechanism does this automatically: force_unlock(account1, take_from=ThreadA, give_to=ThreadB) ``` *What just happened:* this line doesn't exist in real locking systems for good reason - forcibly revoking a lock mid-use would corrupt whatever the holding thread was in the middle of doing. But its absence is exactly why a stuck thread stays stuck: nothing can rescue it by force. ## 4. Circular wait There exists a cycle of threads where each one is waiting for a resource held by the next thread in the cycle. Thread A waits on Thread B; Thread B waits on Thread A. With more threads involved, the cycle can be longer - A waits on B, B waits on C, C waits on A - but it's still a closed loop. ```text A -> waiting for resource held by B B -> waiting for resource held by A ``` *What just happened:* this is the condition that completes the trap. The first three conditions describe *how* locks generally behave - sensibly, even necessarily. It's only when those normal behaviors form a closed loop of waiting that you get a deadlock. ## Why "all four" is the useful part ```text Mutual exclusion -> needed for correctness (can't safely remove this one) Hold and wait -> can be prevented (acquire everything up front, or release before waiting) No preemption -> can be worked around (use try-lock with a timeout instead) Circular wait -> can be prevented (always acquire locks in the same global order) ``` *What just happened:* mutual exclusion is almost never the one you attack - you generally need locks to exclude, or your program has a correctness bug instead of a deadlock. That leaves three practical angles of attack, and the most common one in real code is the last: preventing circular wait by imposing a **consistent lock ordering**. If every thread in your system always acquires `account1` before `account2` - never the reverse, no matter which direction the transfer runs - a cycle becomes structurally impossible. Thread B can't wait for `account1` while holding `account2`, because it would have had to acquire `account1` first under the ordering rule. > You don't have to eliminate all four conditions. You have to eliminate exactly one. That reframes "prevent deadlocks" from an abstract goal into a specific, checkable engineering decision. Phase 3 turns this into code: what lock ordering looks like in practice, how timeouts and try-lock sidestep "no preemption," and what tools exist to catch a deadlock that already happened. --- # Preventing and detecting them in real code Knowing the four conditions is half the battle; the other half is what you type into a real codebase. This phase covers the two prevention techniques you'll use constantly, one detection technique for when prevention wasn't enough, and - because production doesn't wait for you to have the right architecture - what to do when a process is hung right now. ## Technique 1: consistent lock ordering This is the fix for the transfer example from Phase 1, and it's the single most common deadlock fix in real systems: pick a global, deterministic order for acquiring locks, and never violate it, regardless of which "direction" the operation conceptually runs. ```text # before: order depends on transfer direction - deadlock possible transfer(account1, account2): lock(account1); lock(account2) transfer(account2, account1): lock(account2); lock(account1) # after: always lock in a fixed order, e.g. by account ID transfer(a, b): first, second = sorted_by_id(a, b) lock(first) lock(second) ... move money between a and b ... unlock(second) unlock(first) ``` *What just happened:* no matter which account initiates the transfer, both threads now agree on which lock to acquire first - say, whichever account has the lower ID. Thread A transferring 1-to-2 and Thread B transferring 2-to-1 will both try to lock account 1 first. One of them ends up waiting for a normal, resolving lock - not a circular one, because the second thread never holds a lock the first one needs before it can proceed. Circular wait, Phase 2's fourth condition, becomes structurally impossible. This generalizes beyond two locks: if your system ever needs three or more locks at once, sort them by some fixed key - an ID, a memory address, a hash - and always acquire in that order everywhere in the codebase. The rule is only as strong as its consistency; one code path that acquires locks in the wrong order breaks the guarantee for the entire system. ## Technique 2: timeouts and try-lock Sometimes a fixed global ordering isn't practical - maybe the locks come from a library you don't control, or the resource graph is too dynamic to sort cleanly. The fallback is to refuse to wait forever: use a **try-lock** that either succeeds immediately or fails after a timeout, instead of a plain `lock()` that blocks indefinitely. ```text if try_lock(account1, timeout=2s): if try_lock(account2, timeout=2s): ... move money ... unlock(account2) unlock(account1) else: # couldn't get the lock in time - back off and retry later retry_after_backoff() ``` *What just happened:* this attacks Phase 2's third condition, "no preemption," from the other side. You can't forcibly take a lock away from another thread, but you *can* refuse to sit there holding your own lock while waiting on someone else's forever. If the second lock doesn't show up in time, release what you're holding and try the whole operation again later. A deadlock that would have lasted forever instead resolves in a couple of seconds, at the cost of occasionally having to retry. The tradeoff: this trades a hang for a retry loop, and if retries aren't spaced out with backoff, two threads can end up fighting for the same locks repeatedly - a livelock, where both sides are actively working but neither makes progress. A small random delay before each retry usually breaks that pattern. ## Detecting deadlocks after the fact Some systems don't try to prevent deadlocks structurally - they let one happen, notice it, and recover. Databases are the classic example: most relational databases run a background **deadlock detector** that periodically checks the wait-for graph (the same cycle picture from Phase 1) among active transactions. When it finds a cycle, it doesn't wait for a human - it picks one transaction as the "victim," aborts it, and lets the others proceed. Your application code then sees a specific deadlock error and is expected to retry that transaction. ```text Transaction A: waiting on lock held by Transaction B Transaction B: waiting on lock held by Transaction A -> DB detector finds the cycle -> aborts one transaction (say, A) with a deadlock error -> B proceeds, A's caller retries ``` *What just happened:* this is prevention's opposite: instead of making the cycle impossible, the system tolerates that cycles will occasionally form and has a plan for breaking them automatically. It works well specifically because the cost of retrying one aborted transaction is small and well understood - the same approach is much riskier for arbitrary application-level threads doing non-transactional work, where "abort and retry" might not be safe or even meaningful. ## What to do when you see a hang in production A process that's frozen with no errors, no crash, and low CPU usage is the classic deadlock signature. The practical first move on most platforms is to get a **thread dump** - a snapshot of every thread's current stack trace and, critically, what lock (if any) it's currently blocked waiting on. ```text # examples of getting a thread dump, by platform: # Java: jstack # Linux (general): gdb -p then `thread apply all bt` # .NET: dotnet-dump collect, then dotnet-dump analyze ``` *What just happened:* a thread dump turns an invisible hang into readable text - you can see thread A is blocked on lock X, and cross-reference which other thread currently holds lock X. Do that for every blocked thread and you can usually reconstruct the exact wait-for cycle by hand, which tells you precisely which two (or more) code paths need a consistent lock order or a timeout. Some platforms make this even more direct: the JVM's thread dump explicitly flags detected deadlocks by name, no manual cycle-hunting required. > The fix for a live production deadlock is never "wait longer" - a true deadlock never resolves on its own. The fix is restart the stuck process to unblock users immediately, then use the thread dump you captured *before* restarting to find and fix the lock-ordering bug. Once you've found the offending pair of locks, the fix is almost always one of the two techniques from earlier in this phase: reorder the acquisition to match the rest of the codebase, or wrap the second acquisition in a timeout. Deadlocks are unusual among production bugs in that the fix is rarely complicated - the hard part is entirely in locating which two lock acquisitions formed the cycle.