Two threads transfer money between accounts, each locking the source account and then the destination. Explain why this can hang forever, how a global lock ordering fixes it, and what you do when the objects being locked have no natural order.
answer
- opposite orders on the same pair = cycle
- one total order, always ascending
- sort by stable unique id; tie-break lock on collision
- lock levels + debug assertion
- no alien calls while holding a lock
basics
~20 sTransfer(A,B) and transfer(B,A) take the two locks in opposite orders and can each hold one while waiting for the other. Fix: define one total order over all lockable objects, such as a unique id, and always acquire in that order.
solid answer
~60 sTwo concurrent transfers in opposite directions acquire the same pair of locks in opposite orders. If each takes its first lock before either takes its second, they wait on each other forever - a circular wait. The fix is a **global lock ordering**: define one total order over every lockable object, and require all code to acquire in increasing order. Then no cycle can form, because a cycle needs at least one thread that acquired out of order. This attacks the circular-wait condition directly, and it is a static guarantee, not a probability reduction. When objects have no natural order, derive one from a stable unique key - an account id, a primary key, a monotonically assigned lock id. If the only candidate is an identity value that can collide (a hash), add a **tie-breaker lock**: acquire one designated global lock first, then take the two colliding locks in any order, then release the tie-breaker. The ordering must be total, stable, and computable without holding either lock - and every code path must obey it, including library callbacks.
code
text · 10 linestransfer(from, to, amount):
if from.id < to.id:
lock(from); lock(to)
else if from.id > to.id:
lock(to); lock(from)
else: # same object or colliding key
lock(TIE_BREAKER)
lock(from); lock(to) # order irrelevant: only one thread here
...move money...
release all in reverse ordergo deeper
Explain the two-thread opposite-order scenario and that acquiring in a fixed global order, such as ascending account id, removes it.
State the requirements on the order - total, stable, computable without the locks - and handle the collision case with a tie-breaker lock.
Talk about enforcement: lock levels, runtime assertions in debug builds, open calls, and hidden locks inside libraries that fall outside your order.
Treat the order as an architectural invariant with a documented level table and a mechanical check, and discuss designs that need fewer co-held locks so the ordering surface stays small.
## Why the transfer example deadlocks `transfer(from, to)` locks `from`, then locks `to`, then moves the money. Two threads run `transfer(A, B)` and `transfer(B, A)` at the same instant. Thread 1 takes A's lock; thread 2 takes B's lock; thread 1 then asks for B and blocks; thread 2 asks for A and blocks. The wait-for graph is T1 -> T2 -> T1, and neither will release, because release happens only after acquisition succeeds. Notice what the code looks like locally: perfectly reasonable, and correct in isolation. The defect is **global**: it is a property of the set of acquisition orders that exist across the whole program, which no single function's review will reveal. That is what makes lock ordering an architectural rule rather than a local coding trick. ## The ordering rule Define a total order over all lockable objects and require that any thread holding lock L may only acquire locks that come strictly after L in that order. Then the wait-for graph is a strict order relation and cannot contain a cycle: any cycle would need a thread waiting for something *earlier* than what it holds, which the rule forbids. This eliminates the circular-wait condition entirely, so deadlock among ordered locks becomes impossible rather than unlikely. The order must be: - **Total** over everything that can be co-held (no incomparable pairs), - **Stable** for the lifetime of the objects (it cannot change between acquisitions), - **Computable without holding the locks** (otherwise you need a lock to decide lock order), - **Universally obeyed** - one violating path anywhere reinstates the possibility. ## Ordering with no natural order Domain objects usually carry a stable unique identifier: an account number, a primary key, a resource path, an allocation index assigned when the lock is created. Sort by that and acquire in ascending order. When no such key exists and you must fall back on an identity value that can collide, the collision case is the whole problem: two distinct objects that compare equal give no defined order, so two threads can still disagree. The standard remedy is a **tie-breaker lock**: a single, process-wide lock acquired first, only on the rare collision path. While holding it, take the two object locks in either order, do the work, then release. Because at most one thread is ever in the collision path, no cycle can form there. The cost - a global serialization point - is acceptable precisely because collisions are rare. ## Lock hierarchies (lock levels) A practical form of the same idea assigns each *class* of lock a level number: for example, cache = 1, account = 2, ledger = 3. The rule is that a thread may acquire only strictly higher levels than the highest it currently holds. This scales to systems where you cannot enumerate individual objects, is documentable in one table that reviewers can check, and can be asserted at runtime in debug builds by tracking each thread's held levels and failing loudly on a violation. Making the rule mechanically checkable is what keeps it alive as the codebase grows. ## Where the discipline breaks - **Callbacks and alien code.** If you call a listener, plugin, virtual method or framework hook while holding a lock, that code may take locks you cannot see, inserting an edge that ignores your order. Prefer *open calls*: gather state under the lock, release, then call out. - **Re-entrancy across layers.** A higher-level lock taken while holding a lower-level one is the classic inversion; layered systems must fix a direction (always outer-to-inner) and never call upward under a lock. - **Hidden locks.** Libraries, loggers, connection pools and even memory allocation may lock internally, so the order you designed is incomplete. - **Dynamic sets.** When the number of locks depends on input (locking every account in a batch), sort the whole set first and then acquire in order; do not acquire as you iterate an unsorted input. ## Why this is the default answer Of all deadlock defences, a global order is the one that gives a **static** guarantee for a fixed cost of discipline: no runtime checks, no aborts, no retries, no lost work, and no throughput penalty beyond what the locks already impose. Its weakness is entirely social - it depends on every path obeying, including code you did not write - which is why the strongest teams encode it as levels with assertions rather than as a comment.
- A third-party library takes its own locks inside a callback you invoke while holding yours. How do you keep the ordering guarantee?You cannot order locks you cannot see, so stop co-holding them: make it an open call by copying whatever state you need under your lock, releasing it, and only then invoking the library. If the callback must run atomically with your state change, publish an event to a queue and let a separate consumer do the work outside your lock. Failing both, wrap the interaction in a documented level that sits above all your own locks so at least the direction is fixed.
- Does a lock ordering rule prevent all deadlocks in the system?It prevents deadlocks among the locks that participate in the order. It does nothing for waits on resources outside it - pool permits, queue slots, worker slots in a bounded executor, remote leases, or a blocking call to another service - all of which can still form a circular wait. It also breaks the moment a path acquires out of order, which is why the order should be asserted at runtime rather than merely documented.
saying these in an interview costs you the question
- Ordering locks by memory address or a hash without handling the collision case, leaving a rare but real cycle.
- Claiming a shorter critical section or a sleep before retry 'fixes' the transfer deadlock; that changes probability, not possibility.
- Deriving the ordering key by reading state that is itself protected by one of the locks being ordered.
- Applying the order only in the function under review, while other paths still acquire in their own order.
- Assuming a reentrant lock removes the problem - reentrancy helps a thread re-enter its own lock, not two threads crossing.