Thread Deadlock

Thread deadlock is a hot topic in multi-threading, which makes multi-threading a complex area for beginners. Thread deadlock is a situation, where more than one threads with a shared resource are waiting for other thread(s) to release the lock on that shared resource without doing anything usefully.

This article explains the dead lock using a simple Java application, which simulates a bank transaction.

Create an Account class:
public class Account {
    private final String name;
    private double balance;

    public Account(String name) {
        this.name = name;
    }

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

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

    public double getBalance() {
        return this.balance;
    }

    @Override
    public String toString() {
        return name;
    }
}

Create a Transaction class which is a sub class of java.lang.Thread:
public class Transaction extends Thread {
    private final String id;
    private final Account from;
    private final Account to;
    private final double amount;

    public Transaction(String id, Account from, Account to, double amount) {
        this.id = id;
        this.from = from;
        this.to = to;
        this.amount = amount;
    }

    @Override
    public void run() {
        // Acquire the lock of Account 'from'
        synchronized (from) {
            from.withdraw(amount);
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) { }

            // Acquire the lock of Account 'to'
            synchronized (to) {
                to.deposit(amount);
            }
            // Release the lock of Account 'to'
        }
        // Release the lock of Account 'from'
        System.out.println(amount + "is transfered from " + from + " to " + to);
    }
}
Inside the run method, this class synchronizes the 'from' account first and without releasing the lock, it acquires (at least tries to acquire) the lock of 'to' account. Synchronization is the technique of avoiding data corruption or unexpected results in a shared resource environment. For more details about synchronization, visit to this article: Thread Synchronization in Java.

Create a Main class to execute the application:
public class Main {
    public static void main(String[] args) {
        final Account accA = new Account("Acc 1");
        final Account accB = new Account("Acc 2");
        accA.deposit(1000.00);
        accB.deposit(1000.00);

        Transaction t1 = new Transaction("T01", accA, accB, 100.00);
        Transaction t2 = new Transaction("T02", accB, accA, 500.00);

        t1.start();
        t2.start();
    }
}

Suppose there are two customers want to transfer some amount of money to each other from their account at the same time, there is a possibility of getting thread deadlock during this transaction. If you run this program multiple times, sometimes you will not get any outputs in the terminal. Let's analyze the execution of this code into two cases.

Case 1:
Step 1: Transaction 1 starts first, receives the lock of account A and withdraws the money.

Step 2: Transaction 1 received the lock of account B and deposits the money.

Step 3: Transaction 1 releases the lock of B and A respectively.

Step 4: Now transaction 2 starts, gets the lock of account B and withdraws the money.

Step 5: Transaction 2 receives the lock of account A and deposits the money.

Step 6: Transaction 2 releases the lock of A and B respectively.

You will get the expected output as shown below.
100.0is transfered from Acc 1 to Acc 2
500.0is transfered from Acc 2 to Acc 1


Case 2:
Step 1: Transaction 1 starts first, receives the lock of account A and withdraws the money.

Step 2:
Due to some reasons operating system declares a timeout for this thread and let the Transaction 2 to execute. (The Thread.sleep method is added in the code to increase the possibility of getting timeout) Remember that even if a thread is in the waiting pool, it still keeps the lock of the synchronized object. Now it is the time for Transaction 2. It receives the lock of account B and withdraws the money.

Transaction 2 may experience a timeout or not, however it cannot lock the "account A" because Transaction 1 is in the waiting pool which already received the lock of "account A". Therefore transaction 2 has to wait until the "account A" becomes available. Suppose transaction 1 gets the chance to execute again, it needs to get the lock of "account B" to deposit the money. However, the transaction 2 already holds the lock of "account B" so the transaction 1 has to wait.

Now transaction 1 is waiting for transaction 2 to release the account B, at the same time transaction 2 is waiting for transaction 1 to release the account A. No one is going to release their lock so the ultimate result is THREAD DEADLOCK. No outputs and no termination; just waiting... just waiting forever.


This problem can be avoided easily by using proper synchronization. Look at the following code where the lock of "Account from" is released once the withdrawal is completed.
public class Transaction extends Thread {
    private final String id;
    private final Account from;
    private final Account to;
    private final double amount;

    public Transaction(String id, Account from, Account to, double amount) {
        this.id = id;
        this.from = from;
        this.to = to;
        this.amount = amount;
    }

    @Override
    public void run() {
        // Acquire the lock of Account 'from'
        synchronized (from) {
            from.withdraw(amount);
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) { }
        }
        // Release the lock of Account 'from'
        // Acquire the lock of Account 'to'
        synchronized (to) {
            to.deposit(amount);
        }
        // Release the lock of Account 'to'
        System.out.println(amount + "is transfered from " + from + " to " + to);
    }
}
In this case a thread (or transaction) holds only one lock at a time so there is no way of getting deadlock.

Find the source code at Git Hub.
Previous
Next Post »

Contact Form

Name

Email *

Message *