Avoid Deadlock example

Question

I am wondering what are the alternative ways to avoid deadlock in the following example. The following example is a typical bank account transferring deadlock problem. What are some of the better approaches to solve it in practice ?

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);                }           }      } }    

I am wondering if the deadlock issue will be solved if I separate the nested lock out in my transfer method like the following

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

Answer 1

Sort the accounts. The dead lock is from the ordering of the accounts (a,b vs b,a).

So try:

 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);            }       }  } 

Answer 2

In addition to the solution of lock ordered you can also avoid the deadlock by synchronizing on a private static final lock object before performing any account transfers.

 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);           }      } 

This solution has the problem that a private static lock restricts the system to performing transfers "sequentially".

Another one can be if each Account has a 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);         }   } 

Deadlock does not occur in this approach because those locks will never be held indefinitely. If the current object's lock is acquired but the second lock is unavailable, the first lock is released and the thread sleeps for some specified amount of time before attempting to reacquire the lock.