Избегать примера взаимоблокировки

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

class Account {
     double balance;
     int id;
     public Account(int id, double balance){
          this.balance = balance;
          this.id = id;
     }
     void withdraw(double amount){
          balance -= amount;
     } 
     void deposit(double amount){
          balance += amount;
     }
}
class Main{
     public static void main(String [] args){
           final Account a = new Account(1,1000);
           final Account b = new Account(2,300);
           Thread a = new Thread(){
                 public void run(){
                     transfer(a,b,200);
                 }
           };
           Thread b = new Thread(){
                 public void run(){
                     transfer(b,a,300);
                 }
           };
           a.start();
           b.start();
     }
     public static void transfer(Account from, Account to, double amount){
          synchronized(from){
               synchronized(to){
                    from.withdraw(amount);
                    to.deposit(amount);
               }
          }
     }
}

Мне интересно, решит ли он проблему тупика, если я отделяю вложенную блокировку от моего метода переноса, например, следующего

 synchronized(from){
      from.withdraw(amount);
 }
 synchronized(to){
      to.deposit(amount);
 }

Ответы

Ответ 1

Сортировка учетных записей. Мертвая блокировка - это упорядочение счетов (a, b vb, a).

Итак, попробуйте:

 public static void transfer(Account from, Account to, double amount){
      Account first = from;
      Account second = to;
      if (first.compareTo(second) < 0) {
          // Swap them
          first = to;
          second = from;
      }
      synchronized(first){
           synchronized(second){
                from.withdraw(amount);
                to.deposit(amount);
           }
      }
 }

Ответ 2

Это классический вопрос. Я вижу два возможных решения:

Чтобы сортировать учетные записи и синхронизировать их с учетной записью, которая имеет идентификатор ниже другого. Этот метод упоминается в библии concurrency Java concurrency на практике в главе 10. В этой книге авторы используют системный хеш-код для различения учетных записей. См. java.lang.System # identityHashCode.
Второе решение упомянуто вами - да, вы можете избежать вложенных синхронизированных блоков, и ваш код не приведет к взаимоблокировке. Но в этом случае обработка может иметь некоторые проблемы, потому что если вы снимаете деньги с первой учетной записи, вторая учетная запись может быть заблокирована на какое-либо значительное время, и, вероятно, вам нужно будет вернуть деньги на первую учетную запись. Это не очень хорошо и потому, что вложенная синхронизация и блокировка двух учетных записей лучше и чаще используются для решения.

Ответ 3

В дополнение к решению блокировки вы также можете избежать взаимоблокировки путем синхронизации на закрытом статическом конечном объекте блокировки перед выполнением любой передачи учетной записи.

 class Account{
 double balance;
 int id;
 private static final Object lock = new Object();
  ....




 public static void transfer(Account from, Account to, double amount){
          synchronized(lock)
          {
                    from.withdraw(amount);
                    to.deposit(amount);
          }
     }

Это решение имеет проблему, заключающуюся в том, что частный статический замок ограничивает выполнение системы "последовательно".

Другой может быть, если у каждой учетной записи есть ReentrantLock:

private final Lock lock = new ReentrantLock();




public static void transfer(Account from, Account to, double amount)
{
       while(true)
        {
          if(from.lock.tryLock()){
            try { 
                if (to.lock.tryLock()){
                   try{
                       from.withdraw(amount);
                       to.deposit(amount);
                       break;
                   } 
                   finally {
                       to.lock.unlock();
                   }
                }
           }
           finally {
                from.lock.unlock();
           }

           int n = number.nextInt(1000);
           int TIME = 1000 + n; // 1 second + random delay to prevent livelock
           Thread.sleep(TIME);
        }

 }

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

Ответ 4

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

private boolean acquireLocks(Account anotherAccount) {
        boolean fromAccountLock = false;
        boolean toAccountLock = false;
        try {
            fromAccountLock = getLock().tryLock();
            toAccountLock = anotherAccount.getLock().tryLock();
        } finally {
            if (!(fromAccountLock && toAccountLock)) {
                if (fromAccountLock) {
                    getLock().unlock();
                }
                if (toAccountLock) {
                    anotherAccount.getLock().unlock();
                }
            }
        }
        return fromAccountLock && toAccountLock;
    }

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

    public static void transfer(Acc from, Acc to, double amount) {
        if (from.acquireLocks(to)) {
            try {
                from.withdraw(amount);
                to.deposit(amount);
            } finally {
                from.getLock().unlock();
                to.getLock().unlock();
            }
        } else {
            System.out.println(threadName + " cant get Lock, try again!");
            // sleep here for random amount of time and try do it again
            transfer(from, to, amount);
        }
    }

Ответ 5

Вот решение проблемы.

import java.util.Random;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class FixDeadLock1 {

    private class Account {

        private final Lock lock = new ReentrantLock();

        @SuppressWarnings("unused")
        double balance;
        @SuppressWarnings("unused")
        int id;

        public Account(int id, double balance) {
            this.balance = balance;
            this.id = id;
        }

        void withdraw(double amount) {
            this.balance -= amount;
        }

        void deposit(double amount) {
            balance += amount;
        }
    }

    private class Transfer {

        void transfer(Account fromAccount, Account toAccount, double amount) {
            /*
             * synchronized (fromAccount) { synchronized (toAccount) {
             * fromAccount.withdraw(amount); toAccount.deposit(amount); } }
             */

            if (impendingTransaction(fromAccount, toAccount)) {
                try {
                    System.out.format("Transaction Begins from:%d to:%d\n",
                            fromAccount.id, toAccount.id);
                    fromAccount.withdraw(amount);
                    toAccount.deposit(amount);
                } finally {
                    fromAccount.lock.unlock();
                    toAccount.lock.unlock();
                }

            } else {
                 System.out.println("Unable to begin transaction");
            }

        }

        boolean impendingTransaction(Account fromAccount, Account toAccount) {

            Boolean fromAccountLock = false;
            Boolean toAccountLock = false;

            try {
                fromAccountLock = fromAccount.lock.tryLock();
                toAccountLock = toAccount.lock.tryLock();
            } finally {
                if (!(fromAccountLock && toAccountLock)) {
                    if (fromAccountLock) {
                        fromAccount.lock.unlock();
                    }
                    if (toAccountLock) {
                        toAccount.lock.unlock();
                    }
                }
            }

            return fromAccountLock && toAccountLock;
        }

    }

    private class WrapperTransfer implements Runnable {
        private Account fromAccount;
        private Account toAccount;
        private double amount;

        public WrapperTransfer(Account fromAccount,Account toAccount,double amount){
            this.fromAccount = fromAccount;
            this.toAccount = toAccount; 
            this.amount = amount;
        }

        public void run(){
            Random random = new Random();
            try {
                int n = random.nextInt(1000);
                int TIME = 1000 + n; // 1 second + random delay to prevent livelock
                Thread.sleep(TIME);
            } catch (InterruptedException e) {}
            new Transfer().transfer(fromAccount, toAccount, amount);
        }

    }

    public void initiateDeadLockTransfer() {
        Account from = new Account(1, 1000);
        Account to = new Account(2, 300);       
        new Thread(new WrapperTransfer(from,to,200)).start();
        new Thread(new WrapperTransfer(to,from,300)).start();
    }

    public static void main(String[] args) {
        new FixDeadLock1().initiateDeadLockTransfer();
    }

}

Ответ 6

Существует три требования, которые вы должны выполнить:

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

Вы можете достичь 1. и 2. с помощью Atomics, но вам придется использовать что-то другое, что double, поскольку нет AtomicDouble. AtomicLong, вероятно, будет вашим лучшим выбором.

Итак, у вас оставлено третье требование - если вам удастся выполнить другой должен. Существует простой метод, который отлично работает с атоматикой и использует методы getAndAdd.

class Account {
  AtomicLong balance = new AtomicLong ();
}

...
Long oldDebtor = null;
Long oldCreditor = null;
try {
  // Increase one.
  oldDebtor = debtor.balance.getAndAdd(value);
  // Decrease the other.
  oldCreditor = creditor.balance.gtAndAdd(-value);
} catch (Exception e) {
  // Most likely (but still incredibly unlikely) InterruptedException but theoretically anything.
  // Roll back
  if ( oldDebtor != null ) {
    debtor.getAndAdd(-value);
  }
  if ( oldCreditor != null ) {
    creditor.getAndAdd(value);
  }
  // Re-throw after cleanup.
  throw (e);
}