The question this answers
How do I make circular wait unconstructable rather than merely unlikely?
Concurrent transfer(from, to, amount) calls between arbitrary pairs of accounts, where any thread may be asked for any pair in either direction.
One mutex per account, keyed by account id. The set of locks is unbounded and chosen at runtime by the request — which is exactly the case people assume ordering cannot handle.
The sum of the two balances is unchanged by a transfer, and no balance goes negative — which requires both accounts to be locked across the read-modify-write. On top of that, a second, structural invariant: at any instant, every thread holding two account locks holds them in ascending id order. The first invariant is the reason for the locks; the second is the reason there is no deadlock.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
transfer(7, 12) against transfer(12, 7)
Here is the whole bug and the whole fix in one example. The natural way to write a transfer is "lock the source, lock the destination" — it reads well and it mirrors the domain. It is also the one formulation guaranteed to deadlock, because the source and destination swap when the transfer runs the other way, and two threads moving money in opposite directions between the same pair take the locks in opposite orders.
The trace below is the failure. Watch the state column: after step 2 the two locks are held by different threads, and after step 4 the wait edges close. Nothing is wrong with either thread; the pair is wrong. This is the schedule that never appears in a test suite, because a test that transfers 7 → 12 twice cannot produce it and a test that transfers in both directions almost always serialises.
Now change one line — sort the two ids before locking — and re-run every possible schedule in your head. Both threads want L7 first. One gets it, one blocks on it. The thread that got L7 proceeds to L12 unimpeded, because a thread that does not hold L7 cannot be holding L12. There is no interleaving left that produces a cycle: the ordering does not make deadlock rare, it makes it non-existent.
| # | Thread A — transfer(7 → 12, 50) | Thread B — transfer(12 → 7, 30) | State |
|---|---|---|---|
| 1 | lock(L7) [source] | · | L7=A L12=free A holds=7 |
| 2 | · | lock(L12) [source] | L7=A L12=B A holds=7 B holds=12 ✕ Ordering invariant: B now holds a higher-ranked lock (12) without holding the lower one (7). A descending acquisition is in progress, and a cycle is now possible. |
| 3 | lock(L12) [dest] — blocks | · | L7=A L12=B A state=blocked on L12 |
| 4 | · | lock(L7) [dest] — blocks | L7=A L12=B A state=blocked on L12 B state=blocked on L7 |
| 5 | --- with ordering: lock(min(7,12)) = lock(L7) | · | L7=A L12=free |
| 6 | · | lock(min(12,7)) = lock(L7) — blocks | L7=A L12=free B state=blocked on L7 |
| 7 | lock(L12) — acquired, no contention | · | L7=A L12=A |
| 8 | move 50, unlock L12, unlock L7 | · | L7=free L12=free acct 7=50 acct 12=150 |
| 9 | · | wakes with L7, locks L12, moves 30, unlocks both | acct 7=80 acct 12=120 |
The rank removes the edge that closes the cycle
It is worth seeing why ordering works in graph terms, because that is what makes it generalise beyond two locks. Give every lock an integer rank. A thread that obeys the rule only ever has wait edges pointing from a lower-ranked held lock to a higher-ranked requested one. Every edge in the wait-for graph therefore points "up", and a cycle requires at least one edge pointing down. No down edges, no cycles — for any number of threads and any number of locks.
That argument is why the rule scales. Deadlock reasoning normally does not compose, but ranking does: a new lock is safe if you can place it in the existing hierarchy and every acquisition respects it. Whole subsystems can be given rank bands — "all cache locks are rank 100–199, all persistence locks are 200–299, never take a cache lock while holding a persistence lock" — and the property holds across teams that never talk to each other.
The graph below shows both states. On the left the descending edge exists and the cycle is live. On the right, B is waiting on L7 while holding nothing, so its only edge points up, and the cycle has nowhere to close. Note that ordering does not reduce *waiting* at all — B still waits, and lock-wait metrics look identical. It converts an unbounded wait into a bounded one, which is the entire difference between a hang and some contention.
Deriving a rank when the locks are dynamic
The objection to ordering is always the same: "our locks are created at runtime, we cannot rank them." Account locks are the canonical case — millions of them, chosen per request. The answer is that you almost never need a *registry* of ranks; you need a total order over lock identities, and identities always have one.
Sort by the natural key when there is one — account id, user id, partition number, file path. Sort by object address when there is not; std::lock and most hierarchy checkers do exactly this, and it is a legitimate total order as long as the objects outlive the acquisition. Where an object is relocatable, give each one a monotonically increasing sequence number at construction and sort on that.
Two details make or break the implementation. First, the *self-transfer* case: transfer(7, 7) with a non-reentrant mutex self-deadlocks instantly, and this is a real production bug, not a hypothetical. Second, the rule must apply at the acquisition site, not the domain site — the code must lock in id order and then apply the debit and credit in business order, which is a small and slightly awkward decoupling that reviewers try to "clean up" back into a bug.
1void transfer(Account& from, Account& to, Money amount) {2 if (&from == &to) return; // self-transfer: non-reentrant mutex3 // would deadlock on the second lock4 5 // Acquire in rank order, never in business order.6 Account& first = (from.id < to.id) ? from : to;7 Account& second = (from.id < to.id) ? to : from;8 std::scoped_lock guard(first.mtx, second.mtx);9 10 // Apply in business order. This asymmetry is the point: the lock order11 // is a global structural property, the debit/credit order is domain logic.12 if (from.balance < amount) throw InsufficientFunds{};13 from.balance -= amount;14 to.balance += amount;15}16 17// std::scoped_lock over two mutexes is itself deadlock-free (it uses a18// try-and-back-off protocol), so this example is belt and braces. The19// explicit ordering still matters: it is the rule the rest of the20// codebase must follow when the two acquisitions are not adjacent.Key points
- "Lock the source, then the destination" is not an order — it depends on the arguments, so opposite calls take opposite orders.
- A rank makes every wait edge ascending; a cycle needs a descending edge, so no cycle can exist for any thread or lock count.
- The rule composes across teams and subsystems in a way no other deadlock technique does — assign rank bands and the property holds globally.
- Dynamic locks are rankable: sort by natural key, by stable object address, or by a construction sequence number.
- Ordering does not reduce waiting. It converts an unbounded wait into a bounded one, which is the whole difference between a hang and contention.
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.
- • Assign every lockable resource a rank that is independent of the operation being performed — an id, an address, a band per subsystem.
- • At every site that acquires more than one lock, sort the set by rank and acquire strictly ascending.
- • Handle the degenerate case where two "different" resources are the same object, which self-deadlocks a non-reentrant mutex.
- • Apply the business operation in business order after all locks are held; the two orders are deliberately decoupled.
- • Enforce with a debug-build hierarchy checker that records the highest rank each thread holds and asserts monotonicity on acquire.
- • Unordered, opposite directions: A locks L7, B locks L12, A waits L12, B waits L7 — deadlock on the fourth step.
- • Unordered, same direction: A locks L7, B blocks on L7, A locks L12, A completes, B proceeds. Correct — which is why same-direction load tests pass.
- • Ordered, opposite directions: both threads request L7 first; the loser holds nothing while waiting, so it contributes no edge that could close a cycle.
- • Ordered, three-way: A wants {7,12}, B wants {12,19}, C wants {19,7}. Under ranking, A and C both queue on L7 and B on L12; no descending edge exists, so the classic three-cycle also cannot form.
- • Ordered but violated once: a new
applyFee(account, feeAccount)path locks the fee account first because it is "always the same account". That single descending acquisition restores the full deadlock risk — the property is all-or-nothing.
- • Guarantees that no cycle can exist among ranked locks, in every schedule — a stronger guarantee than anything detection or timeouts can offer.
- • Guarantees nothing about locks outside the ranking: a mutex inside a logging library or a framework callback invoked while you hold an account lock is unranked and can still close a cycle.
- • Does not guarantee fairness. The thread that loses the race on
L7may lose repeatedly; see Fairness and Starvation. - • Does not guarantee bounded latency. A slow holder still blocks every waiter, and if enough threads queue on one popular account you get a convoy — see Lock Convoys.
- • Does not guarantee correctness of the operation. Locking in id order and then applying a debit to the wrong account is a bug the ordering cannot see.
- • Ordering does not change contention at all: the same threads wait on the same locks for the same durations. It changes only whether the wait ever ends.
- • A hot account (a house account, a fee account, a settlement account) becomes a global serialisation point regardless of ordering, because every transfer touching it queues on the same mutex.
- • The rank itself can create a hot spot if you rank by something correlated with traffic — ranking by "always take the ledger lock first" means the ledger lock is acquired earliest and held longest by every thread.
- • Sorting two ids costs a comparison. That is the entire runtime overhead of the technique.
- • Self-deadlock on
transfer(x, x)with a non-reentrant mutex — a cycle of length one, and one of the most common real bugs in this pattern. - • A single unordered acquisition path anywhere reintroduces the full risk; there is no partial credit.
- • An unranked lock acquired inside a callback or a destructor while ranked locks are held.
- • Order inverted by refactoring: someone extracts a helper that acquires internally, and the acquisition order becomes invisible at the call site.
- • Starvation of a thread that repeatedly loses the race for the first lock, which ordering does nothing to prevent.
- • Whenever two or more locks must be held simultaneously to preserve an invariant that spans them — the transfer case, and anything shaped like it.
- • In large codebases, because it is the only prevention technique whose correctness argument survives being split across teams and files.
- • When the lock set is dynamic and unbounded, where registries and all-at-once acquisition are impractical but a natural key ordering is trivial.
- • When the natural rank forces an awkward hold pattern — sorting by id may mean acquiring the lock you need last, first, and holding it longer than necessary.
- • When it is used to justify keeping multi-lock code that should have been restructured into two sequential critical sections. Ordering makes bad locking safe, not good.
- • When third-party code participates in the acquisition, because the rank space is not closed and the guarantee silently becomes a hope.
- • A debug-build lock hierarchy checker: store the maximum rank held per thread in thread-local storage and assert on every acquire that the new rank is strictly greater. One CI failure finds every inversion.
- • ThreadSanitizer's deadlock detector (
--detect_deadlocks) and Boost'slock_errorstyle hierarchy mutexes find inversions from a single non-deadlocking execution — you do not need the bad schedule to occur. - • Grep-level audit: every call site that acquires two locks should have a visible sort. A site that does not is either wrong or has the sort hidden in a helper, and both are worth a comment.
- • Lock-wait p99 per account id, to find the hot account that ordering will not help with.
- • Zero deadlock incidents is not evidence. Absence of a deadlock proves nothing about whether the ordering holds — only the checker does.
- • The runtime complexity added is a comparison. The human complexity is a convention that must be documented, taught, and re-checked on every review of multi-lock code.
- • Decoupling acquisition order from business order makes the code slightly harder to read, and that awkwardness is a recurring target for "simplifying" refactors that reintroduce the bug.
- • Rank bands across subsystems require a written hierarchy that someone owns, or it becomes folklore.
- • The checker itself is real code — small, but it must run in CI to be worth anything, and it changes lock acquisition on the hot path in debug builds only.
- • Restructure to hold one lock at a time. If the invariant does not truly span both accounts, two sequential critical sections beat any ordering scheme. See Finding the Critical Section.
- • A single lock over the account table when contention allows it — no order needed because there is no pair.
- • A database transaction with row locks, which handles ordering and detection for you and gives a retryable error on conflict. See Locks and Deadlocks.
- •
std::scoped_lockwith multiple mutexes, which is deadlock-free within one acquisition without you specifying an order — useful, but it does not help when the two acquisitions are in different functions. - • Route all transfers for an account through a single owner keyed by id (an actor or a partitioned queue), removing simultaneous acquisition entirely. See The Actor Model.
A global lock order is a proof, not a habit
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
Our locks are created dynamically, so we cannot order them.
You need a total order over identities, not a static registry. Account id, user id, partition number, stable address or a construction counter all supply one, and sorting two of them costs a comparison.
Locking the source first is a consistent order.
It is consistent within one call and inverted between calls, which is the definition of an inconsistent order. Any rule that depends on the operation's arguments is not an order.
Ordering makes the lock contention go away.
It changes nothing about how long threads wait. A hot account still serialises every transfer that touches it; ordering only guarantees the wait terminates.
Go deeper
Overview
Always take the lower account id first. Two transfers in opposite directions then both queue on the same lock instead of each holding what the other wants.
Practical
Sort the lock set at the acquisition site, apply the business operation afterwards, and guard the self-transfer case. Then add a debug-build hierarchy checker, because the convention is only as good as the enforcement.
Advanced
Ranking is the only deadlock technique that composes. Assign rank bands per subsystem — cache below persistence below external — and independent teams preserve global acyclicity without coordination. The rule's weakness is closure: an unranked lock inside a callback breaks it, which is why "no unknown calls under a lock" is its necessary companion.
Internals
Kernels and database lock managers use the same idea under different names — lock hierarchies, latch ordering, intent locks arranged by level. Postgres additionally detects rather than only prevents, because a transaction can be rolled back; see The Lock Manager. The choice between preventing and detecting is really a choice about whether your state has an undo.