Задача с собеседования на Java программиста: Thread Safe перевод денег между двумя банковскими аккаунтами

Необходимо написать Thread Safe (потокобезопасную) функцию, которая списывает деньги с одного счета и зачисляет на другой. Иногда встречается в виде: дан код, которые делает такой трансфер и нужно найти в нем проблемы и починить. Это одна из классических задач на dead-lock.

Наивная реализация:

    public void transfer(Account from, Account to, int amount) {
      //Списываем деньги
      from.debit(amount);
      //Зачисляем деньги
      to.credit(amount);
    }

Какие проблемы с такой реализацией?

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

Или еще хуже, если нет синхронизации при выполнении методов credit и debit, то мы будет наблюдать эффекты пропажи денег из-за race-condition. Например, на счете 100 рублей. Два потока пытаются зачислить 20 и 30 рублей соответственно. В итоге мы ожидаем 150 рублей. Но может оказаться так, что мы получим только 120 рублей (30 рублей просто исчезнут). Например, оба потока одновременно считали 100 рублей как текущее состояние счета. Первый прибавил 20 и будет записывать 120 рублей как новое состояние счета. Второй будет пытаться записать 130 рублей. Если вначале запишет второй, а потом первый поток, то вначале состояние счета станет 130, а потом 120 рублей. Более того, запись может быть не атомарной и запись будет побайтово. Тогда можно вообще получить неадекватное значение баланса.

Поэтому нужно сделать эту реализацию потокобезопасной.

Может так?

    public void transfer(Account from, Account to, int amount) {
      synchronized(from) {
        synchronized(to) {
          //Списываем деньги
          from.debit(amount);
          //Зачисляем деньги
          to.credit(amount);
        }
      }
    }

Добавим еще проверку на отрицательный баланс:

    public void transfer(Account from, Account to, int amount) 
      throws InsufficientMoneyException {
      synchronized(from) {
        synchronized(to) {
          if (from.getBalance().compareTo(amount) < 0) {
            throw new InsufficientMoneyException();
          }
          //Списываем деньги
          from.debit(amount);
          //Зачисляем деньги
          to.credit(amount);
        }
      }
    }

Хорошо, это решает озвученные ранее проблемы. Мы всегда будем видеть консистентное состояние аккаунтов, никаких промежуточных состояний, это гарантирует synchronized.

Но, что будет, если мы одновременно сделаем перевод с первого счета на второй и со второго на первый?

    Поток 1: transfer(firstAccount, secondAccount, 10);
    Поток 2: transfer(secondAccount, firstAccount, 20);

Может возникнуть ситуация, когда первый поток получит лок на firstAccount, а второй поток на secondAccount. Первый поток будет ждать когда он может получить лок на secondAccount, а второй поток, пока он может получить лок на firstAccount. Имеем ситуацию классического dead-lock.

Как ее можно разрешить?

Есть несколько способов. Например, можно установить некий глобальный порядок получения локов. Чтобы не было такого, что кто-то хочет получить локи в порядке: firstAccount, secondAccount, а кто-то secondAccount, firstAccount.

Например, это можно сделать так:

    private static final Object lock = new Object();

    public void transfer(Account from, Account to, int amount)
      throws InsufficientMoneyException {
      //Берем hashCode аккаунтов для создания глобального порядка получения локов
      //Можно использовать другую информацию, например id аккаунта, 
      //если он уникален
      int fromHashCode = System.identityHashCode(from);
      int toHashCode = System.identityHashCode(to);
      if (fromHashCode > toHashCode) {
        synchronized(from) {
          synchronized(to) {
            helperTransfer(from, to, amount);
          }
        }
      } else if (fromHashCode < toHashCode) {
        synchronized(to) {
          synchronized(from) {
            helperTransfer(from, to, amount);
          }
        }
      } else {
        //Если hashCode равны, 
        //то будем использовать третий глобальный объект для лока
        //Для простоты, на собеседовании можно использовать id аккаунта и говорить,
        //что они уникальны. Тогда этот случай рассматривать не надо.
        //Для hashCode получить один и тот же hashCode возможно, 
        //это называется коллизией.
        synchronized(lock) {
          synchronized(to) {
            synchronized(from) {
              helperTransfer(from, to, amount);
            }
          }
        }
      }
    }

    private void helperTransfer(Account from, Account to, int amount) 
      throws InsufficientMoneyException {
      if (from.getBalance().compareTo(amount) < 0) {
        throw new InsufficientMoneyException();
      }
      //Списываем деньги
      from.debit(amount);
      //Зачисляем деньги
      to.credit(amount);
    }

В этом случае, мы локи получем в порядке значения их hashCode. Тогда оба потока будут пытаться получить локи в одном и том же порядке. Вместо hashCode можно использовать id счета, если он уникален.

Какие есть другие способы разрешить dead-lock?

Можно использовать ReentrantLock и tryLock(), если не получилось получить лок, то просто попытаемся еще раз через некоторое время.