skip to content

How does a consistent global lock-ordering prevent deadlock, and how do you order locks that have no natural ordering (e.g. two account objects)?

level: seniorimportance: must knowfreq 55%

answer

  1. Total lock order -> acyclic wait-for graph -> no deadlock
  2. Lock min(a,b) before max(a,b)
  3. System.identityHashCode as the order when no natural key
  4. Tie-breaker lock for equal hashes
  5. Ordering is a convention — one bad call site breaks it

basics

~20 s

If every thread always acquires locks in the same order, no cycle of waiting can form, so no deadlock. When objects have no natural order, derive one from a stable key like System.identityHashCode, and use a tie-breaker lock for rare hash collisions.

solid answer

~50 s

Deadlock needs a circular wait — a cycle in the wait-for graph. If you define a single global total order over all locks and require every thread to acquire them in that order, the graph can never contain a cycle, so deadlock is structurally impossible. The challenge is when locks are on dynamically created objects with no inherent order, like transferring between two Account objects. The standard trick is to induce an order from a stable, unique key: a business id if one exists, otherwise System.identityHashCode(obj). You compare the two objects' hashes and lock the lower one first. Because identityHashCode can (rarely) collide, you add a third 'tie-breaker' lock acquired before the pair whenever the hashes are equal, guaranteeing a strict order in every case. This keeps acquisition order consistent across all threads regardless of the argument order they were called with, eliminating circular wait without any timeouts or rollback.

code

java · 15 lines
java
private static final Object TIE_BREAKER = new Object();

void transfer(Account from, Account to, long amt) {
    int hf = System.identityHashCode(from);
    int ht = System.identityHashCode(to);
    if (hf < ht) {
        synchronized (from.lock) { synchronized (to.lock) { doTransfer(from, to, amt); } }
    } else if (hf > ht) {
        synchronized (to.lock) { synchronized (from.lock) { doTransfer(from, to, amt); } }
    } else { // rare hash collision
        synchronized (TIE_BREAKER) {
            synchronized (from.lock) { synchronized (to.lock) { doTransfer(from, to, amt); } }
        }
    }
}

go deeper

for a junior

Knows the rule 'always lock in the same order' prevents deadlock for fixed locks.

for a middle

Can apply min/max ordering to the two-account transfer and explain why it removes the cycle.

for a senior

Handles the no-natural-order case with identityHashCode plus a tie-breaker lock and explains the acyclicity argument.

for a principal

Weighs ordering (convention, zero runtime cost, unenforced) vs. tryLock/rollback at scale, and proposes enforcement (lint, lock hierarchies).

## The principle A deadlock requires **circular wait**: a cycle in the **wait-for graph** (nodes are threads, an edge A→B means 'A waits for a lock held by B'). If you can guarantee the graph is always **acyclic**, deadlock is impossible. The cleanest way to guarantee acyclicity is to put **all locks in one global total order** and require every thread to acquire locks **only in increasing order**. Why this works: suppose a cycle existed. Following the cycle, each thread holds a lock and waits for a 'higher' lock (since it acquires in increasing order). Going all the way around the cycle, you'd return to a lock that is simultaneously higher and lower than itself — a contradiction. So no cycle can exist. ## The easy case: a natural order exists If locks correspond to things with an obvious order — say lock IDs 1..N, or a fixed hierarchy (outer before inner) — you simply always acquire low-to-high. The bank-transfer deadlock vanishes if both `transfer(a,b)` and `transfer(b,a)` first lock `min(a,b)` then `max(a,b)`. ## The hard case: no natural order Dynamically allocated objects (two `Account` instances) have no inherent ordering. You must *induce* a consistent order from something **stable and comparable**: 1. **Best:** a unique business key (account number, primary key). Lock the account with the smaller id first. 2. **Fallback:** `System.identityHashCode(obj)` — an identity-based int that's stable for an object's lifetime. Lock the object with the smaller hash first. Crucially this order is the *same* no matter which order the two accounts were passed in, so two threads calling `transfer(a,b)` and `transfer(b,a)` acquire in the *same* sequence and cannot deadlock. ## Handling hash collisions (the tie-breaker) `identityHashCode` is not guaranteed unique — two different objects can share a value. If `hash(a) == hash(b)` you can't decide who's first, reopening the deadlock window. The fix is a single static **tie-breaker lock**: when (and only when) the hashes are equal, acquire that one extra lock *before* locking the pair. Since all threads use the same tie-breaker, only one can be in the ambiguous region at a time, so order is restored. ## Costs and alternatives - Global ordering needs **no runtime machinery** (no timeouts, no rollback) — it's a pure discipline, which is why it's preferred. Its weakness is that it's a *convention*: nothing enforces it, so a single mis-ordered call site reintroduces the bug. Lock-hierarchy tooling or annotations can help enforce it. - When you genuinely can't impose an order (e.g. locks discovered incrementally), fall back to `tryLock` with a timeout and back-off retry. ## Deriving the answer Remember: ordering kills circular wait; for orderless objects, manufacture a stable order from a unique key or `identityHashCode`, with a tie-breaker lock for collisions.

  • Why use System.identityHashCode rather than obj.hashCode()?
    obj.hashCode() can be overridden to a value derived from mutable fields, which may change or collide unpredictably and isn't identity-stable. System.identityHashCode returns the original identity hash regardless of overrides, giving a stable per-object ordering key.
  • Global ordering needs no timeouts, so what's its main weakness compared to tryLock?
    It's only a convention — nothing enforces it, so one call site that acquires out of order silently reintroduces deadlock. tryLock-with-timeout is self-correcting (it recovers at runtime) but pays in retries, wasted work, and added complexity.

saying these in an interview costs you the question

  • Ordering by the *argument* order instead of a stable per-object key (still deadlocks)
  • Forgetting the tie-breaker, leaving a window when identityHashCode collides
  • Using Object.hashCode() that may be overridden — identity ordering needs System.identityHashCode
  • Assuming ordering is enforced by the compiler — it's only a discipline

context

resolving links…