The question this answers
A deadlock needs four things to be true at once — which one is cheapest for me to make false in this particular system?
A worker that must hold both a connection from a pool and a per-tenant mutex before it can write a batch, in a service where both resources are contended.
A bounded connection pool (a counting resource) and a per-tenant mutex (an exclusive resource). Both are acquired by every writer; neither knows the other exists.
No set of threads may ever reach a state where each one holds a resource another one in the set is waiting for. Stated as a graph property: the wait-for graph stays acyclic. The four conditions are the four independent preconditions for that property to fail, and destroying any single one preserves it.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Four conditions, four techniques, four bills
The classical framing — mutual exclusion, hold-and-wait, no preemption, circular wait — is often taught as trivia. It is not trivia; it is a decision table. Deadlock requires the *conjunction* of all four, so prevention is the question "which conjunct can I afford to make false here?" and the answer is different for a request handler, a batch pipeline and a UI thread.
The mechanism side of these conditions belongs to Operating Systems — Deadlocks states them. What matters here is the right-hand column: every technique that breaks a condition trades the deadlock away for a different, specific problem. Break mutual exclusion and you need a data structure whose correctness argument is much harder. Break no-preemption with try-lock and you have invented a retry loop that can Livelock. Break hold-and-wait with all-at-once acquisition and you have made every acquisition as contended as the most contended resource.
In practice the fourth row wins almost every time, and the rest of this module explains why: imposing a global acquisition order is the only technique whose cost is entirely at development time. It buys deadlock freedom with a convention rather than with runtime machinery.
| Condition | What it means here | Technique that breaks it | What it costs |
|---|---|---|---|
| Mutual exclusion | Only one thread may hold the tenant mutex at a time. | Remove the exclusive resource: immutable data, per-thread copies, an atomic or a lock-free structure. | Only available when the invariant fits in one word or the data can be copied. Lock-free correctness is far harder to establish — see Lock-Free Is a Progress Guarantee. |
| Hold and wait | The worker holds a pool connection while it queues for the tenant mutex. | Acquire everything at once, or acquire nothing: a single all-or-nothing step that releases and retries on partial failure. | Every request now contends for the union of resources, so throughput drops to the most contended one. Also requires knowing the full resource set up front, which recursive code does not. |
| No preemption | A lock cannot be taken away from its holder; only the holder releases it. | Timed or try-lock acquisition: fail the second acquire, release the first, back off, retry. | Turns a hang into an error path you must now handle, and introduces a livelock risk if every thread backs off identically. Needs randomised backoff to be safe. |
| Circular wait | Worker 1 holds the pool and wants the mutex; worker 2 holds the mutex and wants the pool. | A total order over all lockable resources, acquired strictly ascending. See Lock Ordering. | A convention nothing enforces at runtime, which decays as the codebase grows. Cost is entirely in discipline and review — which is why it is usually the right answer. |
Why all four, and not any three
The conjunction is the point, and it is easy to prove to yourself on the graph. A cycle in the wait-for graph requires every node on it to be *waiting* (that is hold-and-wait plus mutual exclusion — nothing to wait for otherwise), requires those waits to be permanent (no preemption), and requires the edges to close on themselves (circular wait). Delete any one of those four properties and no cycle can exist, regardless of the schedule.
The graph below is the mixed case that catches teams out: the two resources are of *different kinds*. pool is a counting semaphore with three permits and L-t42 is an exclusive mutex, and people reason about them in separate mental compartments. The wait-for graph does not have compartments. A thread blocked because the pool is exhausted is waiting on a resource held by other threads exactly like a thread blocked on a mutex, and the cycle closes just the same.
Concretely: worker 1 has a connection and wants tenant 42's mutex; worker 2 holds tenant 42's mutex and is blocked because all three connections are out. That is a cycle even though only one of the two resources is a lock. The rule generalises — anything a thread can hold while waiting for something else belongs in the graph, including queue capacity, pool permits, and a thread-pool slot.
Hold-and-wait is the condition you break by accident
Of the four, hold-and-wait is the one most often broken *unintentionally and for free*, simply by moving code. Most two-lock functions do not need both locks at the same time — they need lock A for a read, then lock B for a write, and someone nested them because the braces were already there.
The pair below is the change: the same function, restructured so the two critical sections are sequential rather than nested. No new machinery, no ordering convention, no retry loop. The cycle becomes unconstructable because there is never a moment where this thread holds one resource and wants the other.
The correctness question you must answer before doing this is the important one, and it is a Finding the Critical Section question, not a deadlock question: is it acceptable for the state to change between the two regions? If the invariant genuinely spans both — a transfer must see both balances atomically — then you cannot split, and you fall back to ordering. If it does not, splitting is strictly better than every other technique on the table.
1def write_batch(tenant_id, rows):2 with pool.acquire() as conn: # holds a scarce permit ...3 with tenant_lock(tenant_id): # ... while queueing here4 merged = merge(load_state(tenant_id), rows)5 conn.execute(UPSERT, merged) # only this line needs conn6 7# hold-and-wait: a permit is held while waiting for the mutex,8# and elsewhere a mutex is held while waiting for a permit.1def write_batch(tenant_id, rows):2 with tenant_lock(tenant_id): # region 1: compute3 merged = merge(load_state(tenant_id), rows)4 with pool.acquire() as conn: # region 2: write5 conn.execute(UPSERT, merged)6 7# no thread ever holds one of the two while waiting for the other,8# so no cycle can be constructed and the pool permit is held for9# microseconds instead of for the length of the lock queue.Splitting destroys hold-and-wait and shortens the pool hold time at the same time, which reduces ordinary contention as a side effect. It is only valid if the tenant state may legally change between the two regions — if it may not, the invariant spans both resources and you must order them instead. Read the two versions as a question about the invariant, not about the locks.
Key points
- Deadlock requires all four conditions simultaneously; prevention means choosing one to make false, permanently.
- The list is a decision table, not trivia — each row has a different, concrete price.
- Breaking circular wait via a global lock order is usually cheapest because its entire cost is at development time.
- The wait-for graph does not distinguish resource kinds: pool permits, queue capacity and thread-pool slots form cycles with mutexes.
- Hold-and-wait is frequently breakable for free by making two nested critical sections sequential — if the invariant does not span both.
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.
- • Enumerate the resources a thread can hold while blocked: mutexes, semaphore permits, pool connections, bounded-queue slots, thread-pool workers.
- • For each pair, ask whether both acquisition orders exist anywhere in the codebase. If yes, a latent cycle exists.
- • Pick the condition to break, per resource pair rather than globally — mutual exclusion may be removable for a counter but not for a tenant lock.
- • Apply the technique and write down what it cost: a convention, a retry loop, a throughput cap, or a harder correctness argument.
- • Re-check after every new lock is introduced, because the property is global and each addition is a new proof obligation.
- • W1 takes a permit; W1 takes the tenant lock; W1 writes and releases both; W2 proceeds. Fine — the common schedule.
- • W1 takes a permit; W2 takes the tenant lock; W1 blocks on the tenant lock; W2 blocks because the pool is empty — cycle across two resource kinds, and no mutex-pair audit would have found it.
- • With hold-and-wait broken: W1 takes the tenant lock, computes, releases, takes a permit; W2 does the same in either order. No thread holds one while waiting for the other, so no schedule produces a cycle.
- • With no-preemption broken via try-lock and *identical* backoff: W1 and W2 both fail, both release, both sleep 10 ms, both retry, both fail again — safety preserved, progress lost. See Livelock.
- • With circular wait broken by rank: pool has rank 1, tenant locks rank 2. W2 attempting the tenant lock before a permit is now a bug the review catches, not a schedule the scheduler picks.
- • Breaking one condition guarantees no deadlock among the resources it covers. It guarantees nothing about resources outside that scope — a lock introduced by a library you call is not in your order.
- • A global lock order guarantees acyclicity only if every acquisition path obeys it, including the ones inside callbacks and inside third-party code you invoke while holding a lock.
- • Try-lock guarantees you will not block forever. It does not guarantee you will ever succeed — that is the livelock gap, and only randomised backoff narrows it.
- • All-at-once acquisition guarantees no hold-and-wait, but only if the resource set is known before the first acquire. Recursive or data-dependent acquisition cannot use it.
- • Removing mutual exclusion with atomics guarantees no lock-based deadlock and guarantees nothing about the multi-step invariant — see Atomics Are Not Magic.
- • All-at-once acquisition makes contention equal to the most contended resource in the set, because a thread cannot start until every one of them is free.
- • Try-lock with backoff converts blocking into CPU: threads that fail and retry are runnable, so a contended lock now burns cores instead of parking them.
- • A global order costs nothing at runtime — no extra waiting, no extra state. Its cost is entirely human.
- • Coarsening (one lock instead of two, which removes the pair) removes the cycle and removes parallelism in the same stroke. Measure before assuming that trade is bad; two fine-grained locks that are always taken together were never buying parallelism.
- • Circular wait across resource kinds — the pool/mutex cycle above, missed because the audit only looked at mutexes.
- • Livelock from breaking no-preemption with deterministic backoff.
- • Starvation from all-at-once acquisition: a thread needing four scarce resources may never find all four free while threads needing one keep succeeding. See Starvation.
- • Order violation inside a callback: your code obeys the order, then calls a listener that takes a lock out of rank. The condition is broken by code you did not write.
- • Silent decay: the order was documented in a comment in 2021, three new locks have been added since, and nothing enforces the ranking.
- • The framework earns its keep during design review of a new subsystem, when the resource set is small enough to enumerate and the cost of each technique can be argued concretely.
- • It helps most when the answer is *not* the default: a lock-free counter or an immutable snapshot genuinely removes mutual exclusion for some hot structures, and you only find that by walking the table.
- • It helps in incident review: naming which of the four was violated turns "we deadlocked" into a specific, testable fix.
- • As a runtime strategy it is useless — you cannot check four conditions from inside the program. It is a design-time tool only.
- • Applied dogmatically it produces all-at-once acquisition in systems whose resource set is data-dependent, which turns a rare deadlock into a permanent throughput ceiling.
- • Treating "we broke a condition" as a proof is dangerous when a third-party library or a framework callback acquires locks you never see.
- • Static: an inventory of every lock, permit and bounded queue, plus the acquisition order at each site. A lock-order checker (ThreadSanitizer's deadlock detector,
-fsanitize=thread, or Java's-XX:+PrintConcurrentLocksplus tooling) automates most of this. - • Dynamic: instrument acquisitions with a rank and assert monotonicity in debug builds. A single assertion failure in CI finds a latent inversion long before it deadlocks in production.
- • Watch for a permit-holding thread blocked on a mutex in dumps — grep for stacks that contain both a pool checkout frame and a lock-wait frame.
- • Track try-lock failure rate if you broke no-preemption: a rising failure rate with flat throughput is livelock, not contention.
- • The framework itself adds no runtime complexity; the techniques do, and unevenly. Ordering adds a convention, try-lock adds an error path, all-at-once adds a resource-set computation, lock-free adds a correctness argument few reviewers can check.
- • Every technique except ordering introduces code that only executes under contention — which means it is the code your tests never run.
- • Per-pair decisions mean a codebase can end up with three different strategies in three subsystems, and the interaction between them is a fifth thing to reason about.
- • Have one lock, not two. The conditions cannot be satisfied with a single resource, and a coarse lock is often fast enough — measure before defending fine-grained locking you have not benchmarked.
- • Move the work to a single-owner queue so no shared resource is contended at all. See Producer / Consumer and Channels.
- • Push the coordination into a database transaction and inherit its detector and its retryable error. See Locks and Deadlocks.
- • Use an immutable snapshot plus a compare-and-swap publish, which removes mutual exclusion for readers entirely. See Immutability as a Concurrency Strategy and Copy-on-Write as a Concurrency Strategy.
What people believe, and what is true
Breaking one condition is a partial fix.
It is a complete fix for the resources it covers. Deadlock needs all four; falsifying one makes the cycle unconstructable, not merely less likely.
The conditions only apply to mutexes.
They apply to anything a thread holds while blocked. Connection-pool permits, bounded-queue capacity and thread-pool slots all form cycles, and those cycles are the ones that survive a mutex-only audit.
Try-lock everywhere is a general solution.
It converts deadlock into livelock and an error path. Without randomised backoff and a bounded retry budget it is a different permanent stall with a busier CPU graph.
Go deeper
Overview
Four things must all be true for a deadlock: exclusive resources, holding while waiting, no taking things away, and a cycle. Break one and deadlock is impossible.
Practical
Walk your resource pairs and pick a technique per pair. In application code the answer is nearly always "impose an order" — its cost is a convention rather than runtime machinery. Check whether the two critical sections need to be nested at all first; often they do not.
Advanced
The subtle failure is scope. "We broke circular wait" is true of your code and false of the process, because a framework callback, a destructor, a logging hook or a garbage-collection finalizer can acquire a lock outside your ranking while you hold one. The only robust version of the rule is: never call code you do not own while holding a lock.
Internals
Operating systems historically offered a fifth option — the Banker's algorithm, which *avoids* deadlock by refusing allocations that could lead to an unsafe state. It requires each process to declare its maximum resource claim up front, which no general-purpose system can supply, and it is why real kernels prevent or ignore rather than avoid. See Deadlocks.