The question this answers
Given a system that could deadlock, which fix gives the most safety for the least ongoing cost?
An order-fulfilment handler that touches an inventory record, a customer record and an outbound HTTP call to a payment provider, currently under two mutexes.
An inventory map guarded by L_inv, a customer map guarded by L_cust, and a shared HTTP client with its own internal connection pool that the handler is unaware of.
Reserved inventory equals the sum of unfulfilled order lines, and no order is ever charged without a reservation. That invariant spans two structures, which is the only legitimate reason to hold two locks — and every technique below is judged by whether it 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.
Ordered by leverage, not by novelty
Deadlock prevention has a clear ranking, and most teams reach for the bottom of it first because timeouts feel like engineering and deleting a lock feels like giving up. The ranking is by leverage: how much deadlock risk the technique removes divided by how much ongoing cost it adds. By that measure the top of the list is *having fewer things to order*.
Techniques one through three are structural. They change the shape of the code so that the cycle cannot be constructed, and they add zero runtime machinery — no retries, no error paths, no extra state. Techniques four and five are defensive. They accept that a cycle might form and give you a way out, which means new code that only runs under contention and therefore is never exercised by your tests.
The single highest-value rule on the list is the third: never hold a lock across a call that can block. Not because blocking calls deadlock on their own, but because they stretch the hold window from microseconds to seconds, and every deadlock probability in the system is proportional to that window. It is also the rule that composes — you cannot know what locks a library takes, so the only safe assumption is that it takes some.
| # | Technique | What it removes | Runtime cost | When it is the wrong choice |
|---|---|---|---|---|
| 1 | Delete a lock — one coarser lock, or none | The pair. No second resource, no cycle. | None. Possibly less parallelism. | When the two regions genuinely run in parallel under load and you have measured that they do. |
| 2 | Impose a global acquisition order | Circular wait, permanently and for every schedule. | None. The cost is a convention and a review habit. | When lock identity is data-dependent in a way that has no natural rank — rare; object addresses or ids always give one. |
| 3 | Never hold a lock across a blocking call | The window. Shrinks the hold time by orders of magnitude and removes unknown nested locks. | None. Usually improves throughput as a side effect. | When the invariant must hold across the call — in which case the design is wrong and needs a state machine, not a longer lock. |
| 4 | Timed acquisition (try-lock with timeout) | Permanent blocking — turns a hang into a failure you can observe. | A retry loop, a backoff policy, and an error path on every call site. | As a primary strategy. It is a safety net under 1–3, not a substitute; on its own it converts deadlock into Livelock. |
| 5 | Hand coordination to a higher-level primitive | Your locks entirely — a queue, an actor, a transaction or a semaphore owns the ordering. | A new component, its backpressure behaviour, and its own failure modes. | When the primitive introduces a bounded queue you then block on while holding a lock — you have moved the cycle, not removed it. |
Rule three, in code
The payment call is the whole problem. Holding L_inv across an HTTP request means the lock is held for the p99 latency of somebody else's service, plus their retries, plus your client's connection-pool wait. A 2-second tail on the payment provider is a 2-second lock hold, and during those two seconds every other order thread queues behind it — which is a convoy (Lock Convoys) even before it is a deadlock.
It is also where the invisible lock lives. The HTTP client has its own pool and its own internal synchronisation. You do not know its acquisition order, so holding your lock while calling into it means your program's lock order now includes locks you have never seen and cannot rank. That is the composability argument from The Four Conditions in its most concrete form.
The restructure is the standard one and it is worth naming as a pattern: take the lock, decide, release, act, take the lock, record. Two short critical sections around a long unlocked middle. It costs you a reconciliation step, because the world may have changed while you were unlocked — and that reconciliation is the real work, not the locking.
1def fulfil(order):2 # region 1: decide and reserve. Short, no I/O, both invariants visible.3 with L_inv:4 if inventory[order.sku] < order.qty:5 return Rejected('insufficient stock')6 inventory[order.sku] -= order.qty7 reservation = reserve(order) # invariant restored before unlock8 9 # no lock held here. The payment provider may take 2s or time out;10 # nobody is queued behind us and no unknown library lock is nested11 # inside one of ours.12 try:13 receipt = payments.charge(order, idempotency_key=reservation.id)14 except PaymentError:15 with L_inv: # compensate, do not "unwind"16 inventory[order.sku] += order.qty17 release(reservation)18 raise19 20 # region 2: record. The world changed while we were unlocked, so this21 # must be written as a reconciliation, not as a continuation.22 with L_cust: # rank(L_cust) > rank(L_inv): never nested the other way23 customers[order.user].orders.append(Fulfilled(order, receipt))24 return Fulfilled(order, receipt)What a timeout actually buys, and what it does not
Timed acquisition is the technique people trust most and understand least. try_lock_for(50ms) does not prevent the deadlock — the cycle still forms, exactly as before. What it does is guarantee that you leave the cycle, which converts an unrecoverable hang into a bounded failure you can count, alert on and retry.
That is genuinely valuable, and it is not free. Look at the timeline: thread A spends its 50 ms parked, wakes with a failure, releases L_inv, sleeps a randomised backoff, and tries again. During that whole period A did no work. If the contention is real rather than a cycle, you have replaced blocking (which costs nothing but latency) with polling (which costs latency *and* CPU *and* a wakeup storm). And if both threads back off by the same fixed amount, you have built Livelock — the failure the randomisation exists to prevent.
The correct role for a timeout is as instrumentation and as a last line of defence: keep techniques 1–3 as the actual strategy, add timed acquisition so that a bug in the strategy surfaces as a metric rather than as a 3 a.m. page about a hung service. A lock_acquire_timeout_total counter that is normally zero is one of the highest-signal metrics a concurrent service can have.
Key points
- Rank techniques by leverage: fewer locks, a global order, and no locks across blocking calls are structural and cost nothing at runtime.
- Never hold a lock across a call you do not own — you cannot know which locks it takes, so your acquisition order is no longer knowable.
- A timeout does not prevent the cycle; it guarantees you leave it. That is worth having, as a net under a real strategy.
- Timed acquisition without randomised backoff converts deadlock into livelock, which is harder to diagnose because the CPU looks busy.
- Splitting one long critical section into two short ones forces you to write a reconciliation step — that step is the actual design work.
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.
- • Inventory the locks and ask, per pair, whether both are ever needed simultaneously; delete the pairing where the answer is no.
- • Assign every remaining lock a rank and acquire strictly ascending — see Lock Ordering for how to derive a rank when the locks are dynamic.
- • Move every blocking call — I/O, queue put, another service — outside every critical section, adding compensation for the failure path this creates.
- • Add timed acquisition with randomised backoff and a bounded retry budget as a net, and export a counter for every timeout.
- • Where the coordination is complex enough that the above is hard to hold in your head, replace it with a single-owner queue or a transaction and let that primitive own the ordering.
- • Baseline: A holds L_inv wants L_cust; B holds L_cust wants L_inv — permanent stop.
- • With ordering: B cannot acquire L_cust first because rank(L_inv) < rank(L_cust), so the second wait edge never exists; the cycle is unconstructable in every schedule.
- • With the blocking call moved out: A holds L_inv for ~5 µs instead of ~2 s. The cycle is still constructable in principle but the window shrank by five orders of magnitude — which is mitigation, not prevention, and is why this rule sits alongside ordering rather than replacing it.
- • With timeouts and identical fixed backoff: A and B both time out at t=50 ms, both sleep 50 ms, both retry at t=100 ms, both time out again — livelock, with 100% CPU on two cores and zero throughput.
- • With timeouts and randomised backoff: A retries at +30 ms, B at +90 ms; A completes; B completes. Progress restored by asymmetry, at the cost of one wasted round trip.
- • A global lock order guarantees deadlock freedom over the locks it covers, in every schedule, forever. It guarantees nothing about locks inside code you call.
- • Moving I/O out of the critical section guarantees nothing about cycles; it only shrinks the window. Do not treat it as a proof.
- • A timed acquisition guarantees bounded blocking. It does not guarantee eventual success, does not guarantee fairness, and does not guarantee that the retry will not fail identically.
- •
std::scoped_lockwith multiple mutexes guarantees deadlock-free acquisition of *those* mutexes via an internal back-off protocol — a real guarantee, but only for locks acquired in that one call. - • A queue or actor guarantees no lock cycle among the state it owns. It introduces its own liveness question: what happens when the queue is full and the producer blocks. See Bounded vs Unbounded Queues.
- • Coarsening (technique 1) increases contention on the surviving lock. That is the honest cost, and it is often smaller than expected because the two locks were usually taken together anyway.
- • Ordering adds zero contention — it changes which order threads queue in, not how long they queue.
- • Removing I/O from the critical section usually *reduces* contention dramatically; a 2-second hold under 200 rps builds a queue of 400 threads, and a 5-microsecond hold builds none.
- • Timed acquisition increases CPU under contention because failed waiters become runnable and retry rather than parking. Under heavy contention this can be worse than the blocking it replaced.
- • Livelock from symmetric backoff after timed acquisition.
- • Lost compensation: the payment succeeded but the process died before region 2 recorded it, so the reconciliation the split forced now has a durability requirement you did not plan for.
- • A partial order — most call sites ordered, one legacy path not — which is indistinguishable from no order at all, because deadlock needs only one violating path.
- • Moving the cycle rather than removing it: replacing two mutexes with a bounded queue that a lock-holder then blocks on.
- • Timeout tuned to hide a real problem: a 5-second acquisition timeout makes deadlocks invisible while leaving a 5-second latency spike in the p99.
- • Techniques 1–3 help unconditionally. There is no system where fewer locks, a consistent order and shorter holds make things worse.
- • Timed acquisition helps most in systems you cannot fully audit — a large codebase with third-party callbacks — where you want a bounded failure instead of a hang while the audit happens.
- • Handing coordination to a queue helps when the work is naturally serialisable and the throughput of a single consumer is sufficient; it removes the entire class of problem rather than managing it.
- • Coarsening hurts when the two locks genuinely protect independent hot paths — merging them serialises work that was running in parallel, and the fix for a rare deadlock becomes a permanent throughput cut.
- • Timeouts hurt when they are the only strategy: the service now fails intermittently under contention with an error nobody can reproduce, which is worse to debug than a clean hang.
- • A queue hurts when it hides unbounded growth: the deadlock is gone and replaced by a memory leak and a queue age that climbs all afternoon. See Backpressure.
- • A
lock_acquire_timeout_totalcounter that is normally exactly zero — any non-zero value is a design violation, not a capacity signal. - • Lock hold-time histogram per lock. A hold time whose p99 tracks an external service's p99 is the signature of rule three being violated.
- • A debug-build assertion on rank monotonicity that fails CI on the first inversion, which is how ordering stays true as the codebase grows.
- • Retry counts and backoff distribution after timed acquisition: rising retries with flat throughput is livelock.
- • Before and after throughput when coarsening. If merging two locks does not change p99, the fine-grained pair was never buying parallelism.
- • Splitting a critical section around I/O introduces a compensation path — the hardest code in the function and the least tested.
- • Timed acquisition adds a failure mode to every call site that previously had none, and the caller must decide between retry, degrade and reject.
- • A rank convention requires documentation and enforcement; without a checker it decays into folklore within a year.
- • Handing coordination to a queue moves complexity rather than deleting it: you now own queue sizing, backpressure, shutdown draining and consumer failure.
- • Single-threaded ownership of the mutable state, with concurrency only in the I/O around it — the model an event loop gives you for free. See Event Loops as a Concurrency Model and UI Concurrency: One Thread Owns the Screen.
- • A database transaction that takes the locks in a real lock manager with detection and a retryable error, when the state is already in a database.
- • Optimistic concurrency with a version check, when contention is low: no lock is held during the think time, so no cycle can form. See Optimistic vs Pessimistic.
- • Immutable snapshots published by a single atomic store, when readers vastly outnumber writers. See Copy-on-Write as a Concurrency Strategy.
What people believe, and what is true
Adding a timeout to every lock makes the system deadlock-proof.
It makes the system hang-proof. The cycle still forms every time; you now leave it, having done no work, and may re-enter it immediately unless the backoff is randomised.
Fine-grained locking is always faster than one coarse lock.
Only if the fine-grained regions actually run concurrently. Two locks that are always acquired together give you all the deadlock risk of fine-grained locking and none of the parallelism.
Holding a lock across an HTTP call is fine if the call is usually fast.
Lock hold time follows the *tail* of that call, not its median. One provider incident turns a microsecond lock into a multi-second one and the whole thread pool queues behind it.
Go deeper
Overview
In order: use fewer locks, always take them in the same order, and never hold one while waiting on I/O. Add timeouts as a safety net, not as the plan.
Practical
The refactor that fixes most real cases is "decide under the lock, act outside it, record under the lock again". The work it creates is the compensation path for when the outside action fails — write that path first, because it is where the bugs live.
Advanced
Prevention is a property of the whole program, so the only rule that survives a growing codebase is the one that needs no global knowledge: do not call unknown code while holding a lock. Ordering is second because it needs global knowledge but is checkable; timeouts are last because they need no knowledge and prove nothing.
Internals
Deadlock-free multi-lock acquisition (as in std::lock) works by trying the first lock blocking and the rest with try-lock, releasing everything and restarting from a different mutex if any fails. It is livelock-safe in practice because the restart point rotates, which is the same asymmetry argument as randomised backoff, implemented deterministically.