Lock-Ordering Deadlock

The code snippet below shows an example of a lock-ordering deadlock.

/**
 * Swaps the balances of two accounts.
 * Deadlock-prone!
 *
 * @param a
 * @param b
 */
public void swap(Account a, Account b) {
 synchronized (a) {
  synchronized (b) {
   double aBal = a.getBalance();
   double bBal = b.getBalance();
   a.setBalance(bBal);
   b.setBalance(aBal);
  }
 }
}

It acquires locks on both Account objects and then swaps their balances. It may look harmless at first, but if you look closely you will see that a deadlock can occur if two threads call swap at the same time, for the same accounts, but in the opposite order:

Thread_1: swap(a,b)
Thread_2: swap(b,a)

It is possible that Thread_1 will acquire the lock on account a and wait for the lock on account b, while Thread_2 is holding the lock on b and waiting for the lock on a.

In order to fix this, we need to make sure that the locks are always acquired in the same order. Here are a few different approaches that can be taken to resolve this:

1. Synchronizing the method
Remove the nested lock acquisitions and synchronize the method instead.

/**
 * Swaps the balances of two accounts.
 *
 * @param a
 * @param b
 */
public synchronized void swap(Account a, Account b) {
 double aBal = a.getBalance();
 double bBal = b.getBalance();
 a.setBalance(bBal);
 b.setBalance(aBal);
}

2. Inducing a lock ordering
To induce a lock ordering, you can compare the two accounts based on a unique, immutable key such as an account number. If your accounts are not Comparable, you can use System.identityHashCode instead. In case, for some reason, the two accounts being passed in are the same, you need to aquire a tie-breaking lock before aquiring the account locks.

private static final Object tieBreaker = new Object();

public void swap(Account a, Account b) {
 final int c = a.compareTo(b);
 if (c > 0) {
  synchronized (a) {
   synchronized (b) {
    double aBal = a.getBalance();
    double bBal = b.getBalance();
    a.setBalance(bBal);
    b.setBalance(aBal);
   }
  }
 } else if (c < 0) {
  synchronized (b) {
   synchronized (a) {
    double aBal = a.getBalance();
    double bBal = b.getBalance();
    a.setBalance(bBal);
    b.setBalance(aBal);
   }
  }
 } else {
  synchronized (tieBreaker) {
   synchronized (a) {
    synchronized (b) {
     double aBal = a.getBalance();
     double bBal = b.getBalance();
     a.setBalance(bBal);
     b.setBalance(aBal);
    }
   }
  }
 }
}

3. Using tryLock
Use tryLock to acquire both locks, but backoff and retry if they cannot both be acquired.

public void swap(Account a, Account b)
                        throws InterruptedException {
 Random random = new Random();
 while(true){
  if(a.getLock().tryLock()){
   try{
    if(b.getLock().tryLock()){
     try{
      double aBal = a.getBalance();
      double bBal = b.getBalance();
      a.setBalance(bBal);
      b.setBalance(aBal);
      return;
     }
     finally{
      b.getLock().unlock();
     }
    }
   }
   finally{
    a.getLock().unlock();
   }
  }
  Thread.sleep(random.nextInt(1000));
 }
}