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

score 36 · Accepted Answer · answered Nov 10 '12 at 23:06

36

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

answered Nov 10 '12 at 23:06

Will Hartung

115,893
19
128
203

3

This will work when dealing with more than two Accounts, correct ? – peter Nov 11 '12 at 02:12
I might not understand the concept well, but what about situation in which both accounts have the same balance? As far as I understand, they won't be swapped, therefore deadlock will still exist. – Piotr Chojnacki Mar 28 '14 at 14:16
3

@Piotr: No, in this case you sort the accounts on something unique to them (such as an account number, or their primary key in the DB, etc.). The actual ordering doesn't matter as long as it is a stable ordering across all participants (i.e. no duplicates, as you suggested). – Will Hartung Mar 28 '14 at 15:08
@WillHartung Thank you Will, this sounds convincing! – Piotr Chojnacki Mar 29 '14 at 20:50
@WillHartung I disagree with you. Imagine situation when we have accounts A,B,C and when we transfer data from A to B lock is acquired on A account but I the same time T2 wants to transfer from B to C account, acquired lock on B but T1 can acquired lock on B. So we have deathlock – Matrix12 Jan 07 '23 at 09:28
@Matrix12 No, all you have there is a race condition on B. T1 will lock A, and try to lock B. T2 will try to lock B as well. One of those will "lose the race" and have to wait for the other to complete. If T1 wins, it finishes, B is released and T2 proceeds normally. If T2 wins, T1 will have the lock on A, and will wait for T2 to finish, releasing the lock in B. Since T1 has nothing to do with C, there's no deadlock. If T1 needed A, B, and C, and locked C first, then there could be a DL. But that's why you lock the elements in order to prevent that from happening. – Will Hartung Jan 07 '23 at 19:07
Okay make sense but synchronized is bad for that case because it’s easy to make deathlock – Matrix12 Jan 08 '23 at 20:23
Still I disagree because event in book Concurrency in Practice is that example and author indicates that Deathlock still is possible. To avoid that we have to introduce another lock object and first of all, make lock on him and after that do two locks on account objects… – Matrix12 Jan 26 '23 at 14:19

dreamcrash · Answer 2 · 2018-09-25T18:54:27.980

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.

score 9 · Answer 3 · answered Nov 11 '12 at 00:10

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

To sort accounts and synchronize at account which has an id lower than another one. This method mentioned in the bible of concurrency Java Concurrency in Practice in chapter 10. In this book authors use system hash code to distinguish the accounts. See java.lang.System#identityHashCode.
The second solution is mentioned by you - yes you can avoid nested synchronized blocks and your code will not lead to deadlock. But in that case the processing might have some problems because if you withdraw money from the first account the second account may be locked for any significant time and probably you will need to put money back to the first account. That's not good and because that nested synchronization and the lock of two accounts is better and more commonly used solution.

score 5 · Answer 4 · answered Oct 07 '14 at 17:26

You can also create separate lock for each Account (in Account class) and then before doing transaction acquire both locks. 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 get two locks you can do transfer without worrying about safe.

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

score 0 · Answer 5 · answered Jan 16 '18 at 17:04

Here is the solution for the problem stated.

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

}

OldCurmudgeon · Answer 6 · 2012-11-11T00:40:53.147

There are three requirements you must satisfy:

Consistently reduce the contents of one account by the specified amount.
Consistently increase the contents of the other account by the specified amount.
If one of the above is successful, the other must also be successful.

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

So you're left with your third requirement - if one succeeds the other must succeed. There is a simple technique that works superbly with atomics and that is using the 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);
}

Correct! But I bet `Account.credit/debit` will throw something when OP gets around to that. — OldCurmudgeon, Nov 11 '12 at 17:42

Avoid Deadlock example

6 Answers6

Linked