/** * 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 methodRemove 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)); } }