Java: Классический dead lock

Классический dead lock (Java Concurrency In Practice, p.10.1):

When a thread holds a lock forever, other threads attempting to acquire that lock will block forever waiting. When thread A holds lock L and tries to acquire lock M, but at the same time thread B holds M and tries to acquire L, both threads will wait forever. This situation is the simplest case of deadlock (or deadly embrace), where multiple threads wait forever due to a cyclic locking dependency. (Think of the threads as the nodes of a directed graph whose edges represent the relation "Thread A is waiting for a resource held by thread B". If this graph is cyclical, there is a deadlock.)

Пример иллюстрирующий пробему:

Есть сущность типа счёт, необходимо реализовать сервис типа переводчика денег с одного счёта на другой.

Для определённости стоит уточнить, что счетов с системе очень много (скажем, несколько миллионов) и порядка несколько тысяч операций в секунду (всё многопоточно).

// ради простоты сущность счёт это такая простая структура:
public class Account {
    public int id;
    public int sum;
}

необходимо реализовать

public class MoneyTransfer {
  /**
   * 
   * @param sourceAccount счёт с которого надо снять сумму
   * @param targetAccount счёт на который надо зачислить сумму
   * @param sum сумма, которую необходимо перевести
   */
  public void doTransfer(final Account sourceAccount, 
        final Account targetAccount, final int sum){
  // TODO: реализовать
  }
}

Ошибка №1. DeadLock:

synchronized(sourceAccount){
  if (sourceAccount.sum > sum) {
    synchronized(targetAccount) {
      sourceAccount.sum -= sum;
      targetAccount.sum += sum;
    }
  }
}

Если в момент, когда деньги переводятся со счёта1 на счёт2 будет произведён обратный перевод (т.е со счёта2 на счёт1) получим ситуацию т.н. dead lock'а :

Классическая схема dead lock

• Первая нить (T1) блокирует счёт1 (используя монитор lock a) и в этот же самый момент вторая нить (Т2) блокирует счёт2 (используя соответствующий монитор lock b)
• Т1 пытается получить блокировку счёта2 - но не может получить, т.к Т2 его держит и не может отпустить, т.к. он (Т2) пытается получить блокировку счёта1, который держит Т1 и так же не может отдать

Ошибка №2. BottleNeck:

synchronized(this) {
  if (sourceAccount.sum > sum) {
      sourceAccount.sum -= sum;
      targetAccount.sum += sum;
  }
}

В данном случае все запросы выстроятся в очередь - т.к. блокировка происходит по экземпляру MoneyTransfer - т.е пока каждый последующий трансфер независимо от счетов и потоков из которого происходит трансфер, вынужден дождаться окончания предыдущего трансфера.

Ошибка №3. Не атомарность:

boolean transfered = false;
synchronized(sourceAccount) {
  if (sourceAccount.sum > sum) {
      transfered = true; 
      sourceAccount.sum -= sum;
  }
}
if (transfered) {
  synchronized(targetAccount) {
      targetAccount.sum += sum;
  }
}

Правильное решение (респект Павлу Куракину): выстраивание строго определённой последовательности блокировок:

final Object lock1 = sourceAccount.id < targetAccount.id ? sourceAccount : targetAccount;
final Object lock2 = sourceAccount.id < targetAccount.id ? targetAccount : sourceAccount;
synchronized(lock1){
  if (sourceAccount.sum > sum) {
    synchronized(lock2) {
      sourceAccount.sum -= sum;
      targetAccount.sum += sum;
    }
  }
}

В данном случае не будет dead lock при "встречных" переводах - т.к. блокировка всегда будет происходить в одной и той же последовательности, в то же время нет bottle neck'а и операция трансфера атомарна с точки зрения обоих счетов.

P.S. Стоит так же посмотреть, хотя бы по диагонали статью
IBM developerWorks : Writing multithreaded Java applications.