WalkthroughDifficulty: Advanced2 min

Preventing Deadlock With a Global Lock Order

Lock the accounts in id order and the transfer can no longer deadlock, whichever way it runs.

A global lock order is an agreed order in which every thread takes locks. It removes the circular-wait condition, so a deadlock cannot form. The transfer below is made deadlock-free by changing nothing about what it locks and everything about the order it locks in.

You start from the transfer that locks from then to, and you need something that puts any two accounts in a fixed order.

From a method that can deadlock to one that cannot

Find something to order the locks by

Any total order will do, as long as every thread agrees on it: an account number, a database id, a name. It must be fixed for the life of the object and never equal for two different objects.

java

record Account(long id, long pence) { }

Sort the two locks before taking either

java

void transfer(Account from, Account to, long pence) {
    Account first  = from.id() < to.id() ? from : to;
    Account second = from.id() < to.id() ? to : from;

    synchronized (first) {
        synchronized (second) {
            from.withdraw(pence);
            to.deposit(pence);
        }
    }
}

The locks are now taken in id order, whichever way the transfer goes. Both threads, one transferring from Alice to Bob and one from Bob to Alice, take Alice's lock first, so one waits briefly for the other and then proceeds.

Handle the case where both are the same object

java

if (from.id() == to.id()) {
    throw new IllegalArgumentException("cannot transfer to the same account");
}

Without this check, first and second are the same account and the inner lock is taken twice by the same thread, which reentrancy allows. That is harmless here, and a sign that the caller meant something else.

Check the cycle cannot form

What each thread now takes, in order
Thread	Takes first	Takes second
Alice to Bob	Alice, the lower id	Bob
Bob to Alice	Alice, the lower id	Bob

Both rows are identical, so no arrangement leaves one thread holding Bob's lock while waiting for Alice's. Circular wait is gone, and the other three conditions are untouched.

You know it worked when every place in the program that takes both locks takes them in the same order. The fix is not more locking or shorter locking; it is an agreement, applied everywhere.

← → move through sections and cards