Синхронизация с Java: атомарное перемещение денег через пары пар?

Ответ 1

Простое решение может заключаться в использовании блокировки для каждой учетной записи, но чтобы избежать тупиковой ситуации, вы должны всегда получать блокировки в том же порядке. Таким образом, вы можете иметь окончательный идентификатор учетной записи и сначала получить блокировку учетной записи с меньшим идентификатором:

public void transfer(Account acc1, Account acc2, BigDecimal value) {
    Object lock1 = acc1.ID < acc2.ID ? acc1.LOCK : acc2.LOCK;
    Object lock2 = acc1.ID < acc2.ID ? acc2.LOCK : acc1.LOCK;
    synchronized (lock1) {
       synchronized (lock2) {
          acc1.widrawal(value);
          acc2.send(value);
       }
    }
}

Ответ 2

Один из способов сделать это - иметь журнал транзакций. Прежде чем переводить деньги, вам нужно будет записать в журнал транзакций каждую учетную запись, что вы намерены делать. Журнал должен содержать: сумму денег, полученную в/из учетной записи, и блокировку, которая разделяется между лог-парой.

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

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

Этот подход может быть немного тяжелым, но он также будет работать в распределенном сценарии, где учетные записи фактически находятся на разных машинах, и фактические данные должны быть сохранены, чтобы гарантировать, что деньги никогда не будут потеряны, если какая-либо машина Авария/неожиданно отключается. Его общий метод называется двухфазной блокировкой.

Ответ 3

Я бы предложил создать метод Account.withdraw(amount), который выдает исключение, если у него недостаточно средств. Этот метод необходимо синхронизировать с самой учетной записью.

Edit:

Также должен быть метод Account.deposit(amount), который синхронизируется в экземпляре принимающей учетной записи.

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

Пример кода: Предполагает, что вывод/депозит синхронизируются и возвращают логический статус успеха, а не генерируют исключение.

public boolean transfer(Account from, Account to, BigDecimal amount) {
    boolean success = false;
    boolean withdrawn = false;
    try {
        if (from.withdraw(amount)) {
            withdrawn = true;
            if (to.deposit(amount)) {
                success = true;
            }
        }
    } finally {
        if (withdrawn && !success) {
            from.deposit(amount);
        }
    }

    return success;
}

Ответ 4

Вы можете создать дополнительный Account T, который существует исключительно для перевода денег. Поэтому, если вы хотите перейти от A в B, вы фактически переходите от A до T, а затем от T до B. Для каждой из этих передач вы блокируете только A или B в зависимости от того, какая учетная запись участвует в передаче. Поскольку вы используете один и тот же тип для переноса, вы получаете небольшой дополнительный код и, следовательно, низкие затраты на обслуживание.

Чтобы уменьшить количество дополнительных учетных записей, вы можете удерживать их в пуле. Если у вас есть пул потоков, который обрабатывает переводы, вы можете назначить каждому потоку собственную учетную запись. Поэтому вам не нужно слишком часто запрашивать и освобождать эти дополнительные учетные записи из/в пул.

Ответ 5

Один из подходов - использовать "полосатый замок" с методами блокировки/разблокировки, работающими на нескольких замках. Учетные записи сопоставляются с блокировкой с помощью hashCode, чем больше блокировок вы выделяете, тем больше parallelism вы получаете.

Здесь пример кода:

public class StripedLock {

    private final NumberedLock[] locks;

    private static class NumberedLock {
        private final int id;
        private final ReentrantLock lock;

        public NumberedLock(int id) {
            this.id = id;
            this.lock = new ReentrantLock();
        }
    }


    /**
     * Default ctor, creates 16 locks
     */
    public StripedLock() {
        this(4);
    }

    /**
     * Creates array of locks, size of array may be any from set {2, 4, 8, 16, 32, 64}
     * @param storagePower size of array will be equal to <code>Math.pow(2, storagePower)</code>
     */
    public StripedLock(int storagePower) {
        if (!(storagePower >= 1 && storagePower <= 6)) { throw new IllegalArgumentException("storage power must be in [1..6]"); }

        int lockSize = (int) Math.pow(2, storagePower);
        locks = new NumberedLock[lockSize];
        for (int i = 0; i < locks.length; i++)
            locks[i] = new NumberedLock(i);
    }

    /**
     * Map function between integer and lock from locks array
     * @param id argument
     * @return lock which is result of function
     */
    private NumberedLock getLock(int id) {
        return locks[id & (locks.length - 1)];
    }

    private static final Comparator<? super NumberedLock> CONSISTENT_COMPARATOR = new Comparator<NumberedLock>() {
        @Override
        public int compare(NumberedLock o1, NumberedLock o2) {
            return o1.id - o2.id;
        }
    };


    public void lockIds(@Nonnull int[] ids) {
        Preconditions.checkNotNull(ids);
        NumberedLock[] neededLocks = getOrderedLocks(ids);
        for (NumberedLock nl : neededLocks)
            nl.lock.lock();
    }

    public void unlockIds(@Nonnull int[] ids) {
        Preconditions.checkNotNull(ids);
        NumberedLock[] neededLocks = getOrderedLocks(ids);
        for (NumberedLock nl : neededLocks)
            nl.lock.unlock();
    }

    private NumberedLock[] getOrderedLocks(int[] ids) {
        NumberedLock[] neededLocks = new NumberedLock[ids.length];
        for (int i = 0; i < ids.length; i++) {
            neededLocks[i] = getLock(i);
        }
        Arrays.sort(neededLocks, CONSISTENT_COMPARATOR);
        return neededLocks;
    }
}

    // ...
    public void transfer(StripedLock lock, Account from, Account to) {
        int[] accountIds = new int[]{from.getId(), to.getId()};
        lock.lockIds(accountIds);
        try {
            // profit!
        } finally {
            lock.unlockIds(accountIds);
        }
    }

Ответ 6

Не используйте встроенную синхронизацию, используйте объект Lock. Используйте tryLock(), чтобы получить эксклюзивную блокировку на обеих учетных записях одновременно. Если один из них терпит неудачу, отпустите обе блокировки и подождите некоторое время и повторите попытку.

Ответ 7

Как вы уже упоминали, будет одновременная транзакция 1000-10000, которую вы ожидаете за один раз, чем вы можете хранить учетные записи, на которых происходит какая-то транзакция, и обрабатывать concurrency

Одно решение состоит в том, чтобы позволить системе создавать только один объект идентификатора счета в виде частиц, означает, что если вы хотите сделать транзакцию между учетной записью "123" и "456", чем ваш поток, создайте объект учетной записи и в этом конструкторе учетной записи класс, мы проверим, существует ли какой-либо другой объект учетной записи с идентификатором счета в виде частиц, если другой объект учетной записи существует с таким же идентификатором учетной записи, означает, что происходит какая-то транзакция с идентификатором счета частиц, поэтому вам нужно подождать, чтобы получить объект учетной записи.

Таким образом, мы можем совершать транзакции между "123" и "456", и в то же время мы можем совершать транзакции между "abc" и "xyz", но если в то же время какой-то другой поток попытается создать объект учетной записи "123" , чем система скажет пожалуйста, подождите

для справки вы можете увидеть ниже код

Обратите внимание:

• Не пропустите удаление идентификатора вашей учетной записи из карты блокировок путем вызова freeAccount (BigDecimal accId) из класса LockHolder

• Я использовал список HasMap списка, потому что список не будет хорошим выбором, когда вы произвольно удаляете из него элемент (или когда вы его часто обновляете)

  package test;
  
  import java.math.BigDecimal;
  import java.util.HashMap;
  import java.util.Map;
  
  public class T {
  
  public static void main(String[] args) {
      Account ac, ac2;
  
      try {
          ac = new Account(new BigDecimal("123"));
      } catch (Exception e) {
          e.printStackTrace();
      }
      try {
          ac2 = new Account(new BigDecimal("123"));
      } catch (Exception e) {
          System.out.println("Please Wait");
      }
  
  }
  }
  
  class Account {
   public Account(BigDecimal accId) throws Exception {
      if (LockHolder.isLocked(accId)) {
          throw new Exception();
      } else {
          LockHolder.setLock(accId);
      }
   }
  }
  
  class LockHolder {
   public static  Map<BigDecimal, Integer> locks = new HashMap<BigDecimal, Integer>();
  
   public synchronized static boolean isLocked(BigDecimal accId) {
      return LockHolder.locks.containsKey(accId);
   }
  
   public synchronized static void setLock(BigDecimal accId) {
      LockHolder.locks.put(accId , 1);
   }
   public synchronized static void freeAccount(BigDecimal accId) {
      LockHolder.locks.remove(accId);
   }
  }
  

Ответ 8

Как указано ранее, вы должны блокировать обе учетные записи, всегда в том же порядке. Ключевая часть, однако, обеспечивает как высокую детализацию, так и сингулярность в экземпляре виртуальной машины. Это можно сделать, используя String.intern():

public boolean transfer(Account from, Account to, BigDecimal amount) {
    String fromAccountId = from.id.toString().intern();
    String toAccountId = to.id.toString().intern();
    String lock1, lock2;

    if (from.id < to.id) {
       lock1 = fromAccountId;
       lock2 = toAccountId;
    } else {
       lock1 = toAccountId;
       lock2 = fromAccountId;
    }

    // synchronizing from this point, since balances are checked
    synchronized(lock1) {
        synchronized(lock2) {
            BigDecimal fromValue = from.getAmount();
            if (amount.compareTo(fromValue) < 0)
                 return false;
            BigDecimal toValue = to.getAmount();
            from.setAmount(fromValue.add(amount.negate()));
            to.setAmount(toValue.add(amount));
            return true;
        }
    }
}

Ответ 9

Подход, который будет оставаться надежным, даже если потоки могут быть произвольно запущены, заключается в том, чтобы каждая учетная запись поддерживала список транзакций, запрошенных или размещенных против него. Чтобы запросить перевод из одной учетной записи в другую, создайте объект транзакции, определяющий запрос, и добавьте его в очередь запросов для исходной учетной записи. Если эта учетная запись может выполнить транзакцию, она должна переместить ее в список опубликованных транзакций и добавить ее в очередь запросов для получателя. Используя AtomicReference, можно гарантировать, что с момента, когда транзакция будет помещена в очередь для первой учетной записи, состояние системы всегда будет иметь либо ожидающую транзакции, либо завершенную, либо прерванную, и даже если некоторые или все потоки должны были быть замечены, изучение списков транзакций позволило бы определить, какие деньги принадлежали где.

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

Ответ 10

Спасибо всем за интерес к вопросу.

Я нашел несколько решений в https://www.securecoding.cert.org/confluence/display/java/LCK07-J.+Avoid+deadlock+by+requesting+and+releasing+locks+in+the+same+order

Как только один ответ на связь был удален здесь, необходим фрагмент кода, который помогает кому угодно, когда cert.org падает. Пьесы длинны, поэтому я не включал никаких плюсов и минусов.

Частный статический конечный объект блокировки:

final class BankAccount {
  private double balanceAmount;  // Total amount in bank account
  private static final Object lock = new Object();

  BankAccount(double balance) {
    this.balanceAmount = balance;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba
  private void depositAmount(BankAccount ba, double amount) {
    synchronized (lock) {
      if (amount > balanceAmount) {
        throw new IllegalArgumentException(
            "Transfer cannot be completed");
      }
      ba.balanceAmount += amount;
      this.balanceAmount -= amount;
    }
  }

  public static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {

    Thread transfer = new Thread(new Runnable() {
        @Override public void run() {
          first.depositAmount(second, amount);
        }
    });
    transfer.start();
  }
}

Упорядоченные блокировки:

final class BankAccount implements Comparable<BankAccount> {
  private double balanceAmount;  // Total amount in bank account
  private final Object lock;

  private final long id; // Unique for each BankAccount
  private static long NextID = 0; // Next unused ID

  BankAccount(double balance) {
    this.balanceAmount = balance;
    this.lock = new Object();
    this.id = this.NextID++;
  }

  @Override public int compareTo(BankAccount ba) {
     return (this.id > ba.id) ? 1 : (this.id < ba.id) ? -1 : 0;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba
  public void depositAmount(BankAccount ba, double amount) {
    BankAccount former, latter;
    if (compareTo(ba) < 0) {
      former = this;
      latter = ba;
    } else {
      former = ba;
      latter = this;
    }
    synchronized (former) {
      synchronized (latter) {
        if (amount > balanceAmount) {
          throw new IllegalArgumentException(
              "Transfer cannot be completed");
        }
        ba.balanceAmount += amount;
        this.balanceAmount -= amount;
      }
    }
  }

  public static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {

    Thread transfer = new Thread(new Runnable() {
        @Override public void run() {
          first.depositAmount(second, amount);
        }
    });
    transfer.start();
  }
}

Соответствующее решение (ReentrantLock):

final class BankAccount {
  private double balanceAmount;  // Total amount in bank account
  private final Lock lock = new ReentrantLock();
  private final Random number = new Random(123L);

  BankAccount(double balance) {
    this.balanceAmount = balance;
  }

  // Deposits amount from this object instance
  // to BankAccount instance argument ba
  private void depositAmount(BankAccount ba, double amount)
                             throws InterruptedException {
    while (true) {
      if (this.lock.tryLock()) {
        try {
          if (ba.lock.tryLock()) {
            try {
              if (amount > balanceAmount) {
                throw new IllegalArgumentException(
                    "Transfer cannot be completed");
              }
              ba.balanceAmount += amount;
              this.balanceAmount -= amount;
              break;
            } finally {
              ba.lock.unlock();
            }
          }
        } finally {
          this.lock.unlock();
        }
      }
      int n = number.nextInt(1000);
      int TIME = 1000 + n; // 1 second + random delay to prevent livelock
      Thread.sleep(TIME);
    }
  }

  public static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {

    Thread transfer = new Thread(new Runnable() {
        public void run() {
          try {
            first.depositAmount(second, amount);
          } catch (InterruptedException e) {
            Thread.currentThread().interrupt(); // Reset interrupted status
          }
        }
    });
    transfer.start();
  }
}