Avoid deadlock example

Question

I am wondering what alternative ways to avoid a deadlock in the following example. The following example is a typical bank account translating a deadlock problem. What are some more effective approaches to solving 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 it will solve the deadlock problem if I separate the nested lock from my transfer method, like the following

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

Answer 1

Sort accounts. Deadlock is the ordering of accounts (a, b vb, 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

This is a classic question. I see two possible solutions:

• To sort accounts and synchronize them with an account that has an identifier lower than another. This method is mentioned in the concurrency Java concurrency bible in practice in Chapter 10. In this book, authors use a system hash code to distinguish between accounts. See java.lang.System # identityHashCode .
• The second solution you mentioned is yes, you can avoid nested synchronized blocks, and your code will not lead to deadlock. But in this case, processing may have some problems, because if you withdraw money from the first account, the second account may be blocked for some considerable time, and you will probably need to return the money to the first account. This is not very good either because the nested synchronization and locking of two accounts are better and more often used for solving.

Answer 3

In addition to resolving the lock, you can also avoid deadlocks by synchronizing on a locked static lock target before performing any transfer to your account.

  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 execution of the system "sequentially".

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

There is no deadlock in this approach, since locks are never held indefinitely. If the current lock of the object is obtained, but the second lock is not available, the first lock is released, and the thread falls asleep for a certain time before trying to restore the lock.

Answer 4

You can also create a separate lock for each account (in the Account class), and then get both locks before making a transaction. Take a look:

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

After receiving the two locks, you can make the transfer without worrying about security.

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

Answer 5

Here is the solution to the problem.

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

Answer 6

There are three requirements that you must fulfill:

• Constantly reduce the contents of one account by the specified amount.
• Continuously increase the contents of another account by the indicated amount.
• If one of the above is successful, the other should be successful.

You can achieve 1. and 2. using Atomics , but you have to use something else that double , since there is no AtomicDouble . AtomicLong will probably be your best bet.

So, you have left the third requirement - if you succeed in fulfilling another must . There is a simple method that works great with atomatics and uses getAndAdd methods.

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