Example of deadlock

Question

I have checked many websites and the only example of deadlock is something like this. There is always a synchronized block inside a synchronized block.

(method withdraw is locked by a and method deposit is locked by b.)

class Account
{
    int balance;
    Account(int amount)
    {balance = amount;}

    void withdraw(int amount)
    {balance-=amount;}

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

class Threaddemo extends Thread
{
    Account a,b;
    int amount;

    Threaddemo(Account a,Account b,int amount)
    {
        this.a=a;this.b=b;this.amount=amount;
        start();
    }

    public void run()
    {
        transfer(a,b,amount);
    }

    public void transfer(Account a,Account b,int amount)
    {
        synchronized(a)
        {
            a.withdraw(amount);
            System.out.print(amount+" is withdrawn from account a\n");

            try{Thread.sleep(500);}
            catch(Exception e){System.out.println(e);}

            synchronized(b)
            {
                b.deposit(amount);
                System.out.print(amount+" is deposited into account b\n");
            }
        }
    }
}
class U3
{
    public static void main(String[] args) 
    {
        Account a = new Account(1000);
        Account b = new Account(2000);

        new Threaddemo(a,b,100);
        new Threaddemo(b,a,200);

    }
}

but if we use a synchronized block after a synchronized block there will be no deadlock.

class Account
{
    int balance;
    Account(int amount)
    {balance = amount;}

    void withdraw(int amount)
    {balance-=amount;}

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

class Threaddemo extends Thread
{
    Account a,b;
    int amount;

    Threaddemo(Account a,Account b,int amount)
    {
        this.a=a;this.b=b;this.amount=amount;
        start();
    }

    public void run()
    {
        transfer(a,b,amount);
    }

    public void transfer(Account a,Account b,int amount)
    {
        synchronized(a)
        {
            a.withdraw(amount);
            System.out.print(amount+" is withdrawn from account a\n");

            try{Thread.sleep(500);}
            catch(Exception e){System.out.println(e);}
        }
        synchronized(b)
        {
            b.deposit(amount);
            System.out.print(amount+" is deposited into account b\n");
        }
    }
}
class U3
{
    public static void main(String[] args) 
    {
        Account a = new Account(1000);
        Account b = new Account(2000);

        new Threaddemo(a,b,100);
        new Threaddemo(b,a,200);

    }
}

If this is the only way to get deadlock then why don't we use two separate synchronized block? If there are other ways to get deadlock please give example.

Answer 1

Consider a bank with thousands of bank accounts of type Account. Now let's look at why this code causes a deadlock:

public void transfer(Account a,Account b,int amount)
    {
        synchronized(a)
        {
            a.withdraw(amount);
            System.out.print(amount+" is withdrawn from account a\n");

            try{Thread.sleep(500);}
            catch(Exception e){System.out.println(e);}

            synchronized(b)
            {
                b.deposit(amount);
                System.out.print(amount+" is deposited into account b\n");
            }
        }
    }

Let there be a thread tA and thread tB. If thread tA runs the following code transfer(accountA, AccountB) while thread tB runs transfer(accountB, accountA) simultaneously, there could be a chance of deadlock, because if we look at the following order:

1. tA: synchronized(accountA)

2. tB: synchronized(accountB)

3. tA: tries to lock object AccountB, but lock is held by tB => deadlock

we see that there is a cyclic dependency between the two, not allowing one of the threads to progress any further.

If we look at your updated code:

public void transfer(Account a,Account b,int amount)
    {
        synchronized(a)
        {
            a.withdraw(amount);
            System.out.print(amount+" is withdrawn from account a\n");

            try{Thread.sleep(500);}
            catch(Exception e){System.out.println(e);}
        }
        synchronized(b)
        {
            b.deposit(amount);
            System.out.print(amount+" is deposited into account b\n");
        }
    }

we must take the following assumptions:

• Account a has unlimited funds, as it could be that a.balance < amount, which means a.balance < 0, which breaks our invariant of always having a balance>=0.

  • We allow inconsistencies, e.g. if we want to sum up all the current cash, we will sum up less than the actual amount, because your current code allows us to do so.

If we try to fix the code, we would have to make sure that a.balance >= amount before we update our balance. Now let's look at the following scenario:

1. Account a has balance < amount

2. We must wait until a.balance >= amount to withdraw money from Account a

3. As we are keeping the lock of Account a in this thread, no other thread can ever update a.balance => We suffer from starvation

To fix these problems, you would either have to use a monitor or condition that checks whether a.balance>=amount to progress and to put the thread in a blocked state, such that the thread can progress or update your code such that the locks are always acquired in the same order.

Solution #1: Unique order of acquiring object's locks

If we use an unique order for acquiring locks of the objects, we can ensure that no deadlock can occur as we are acquiring the locks in a specified order, not allowing any cyclic dependencies otherwise known as deadlock.

public void transfer(Account a,Account b,int amount)
    {
       //define a specific order, in which locks are acquired
       //the id's of all accounts are unique!
       if(a.id<b.id){
          synchronized(a){
            synchronized(b){
               //do operations here
            }
          }
       }else{
          synchronized(b){
            synchronized(a){
               //do operations here
            }
          }
       }
    }

Solution #2: Use a producer-consumer pattern to check a.balance>=amount.

public void transfer(Account a,Account b,int amount)
{
    while(true){
      synchronized(a){
          if(a.balance>=amount){
              //do operations here
          }
      }

        try{Thread.sleep(500);} //Use this as a backoff, as otherwise you'd likely get high congestion
        catch(Exception e){System.out.println(e);}
    }
    synchronized(b)
    {
       //do operations here
    }
}