Задача с собеседования на Java программиста: Thread Safe перевод денег между двумя банковскими аккаунтами
Published: 2023-11-25 23:25:04


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

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

```java
    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 рублей. Более того, запись может быть не атомарной и запись будет побайтово. Тогда можно вообще получить неадекватное значение баланса.

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

Может так?

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

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

```java
    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.

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

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

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

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

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

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

```java
    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(), если не получилось получить лок, то просто попытаемся еще раз через некоторое время.**