Investigating Deadlocks – Part 1: Creating a Deadlock

I’m sure we’ve all been there: it’s late, you’re hungry, your server has hung or your application’s running at snail’s pace, and there’s someone breathing down your neck wanting you to fix the problem before you go. One of the possible causes of your application hanging unexpectedly is a threading issue known as a Deadlock.

Without going into too much detail, threads can be in one of a number of states as shown by the UML state diagram below...

...and an deadlock is all to do with the BLOCKED state, which the API documentation defines as a “a thread that is blocked waiting for a monitor lock”.

So, what is a deadlock? Simply put, given two threads A and B then a deadlock occurs when thread A blocks because it’s waiting for thread B to release a monitor lock, and thread B blocks because it’s waiting for thread A to release the same monitor lock.

However, things can be more complex than this in that the deadlock can contain a whole bunch of threads. For example, thread A blocks because it’s waiting for thread B, thread B blocks because it’s waiting for thread C, thread C blocks because it’s waiting for thread D, D blocks because it’s waiting for E, E blocks because it’s waiting for F and F blocks because it’s waiting for A.

The trick is finding out which threads are blocked and why, and that’s done by taking a thread dump from your application. A thread dump is simply a snapshot report showing the status of all your application’s threads at a given point in time. There are several tools and techniques available to help you get hold of a thread dump and these include jVisualVM, jstack and the unix kill command; however, before obtaining and interpreting a thread dump, I’ll need some code that will create a deadlock

The scenario I’ve chosen for this is one of a simple bank account transfer. The idea is that there is a balance transfer program running that's randomly transferring various amounts between different accounts using a bunch of threads. In this program, a bank account is represented using the following, very simplistic, Account class:

public class Account {

  private final int number;

  private int balance;

  public Account(int number, int openingBalance) {
    this.number = number;
    this.balance = openingBalance;
  }

  public void withdraw(int amount) throws OverdrawnException {

    if (amount > balance) {
      throw new OverdrawnException();
    }

    balance -= amount;
  }

  public void deposit(int amount) {

    balance += amount;
  }

  public int getNumber() {
    return number;
  }

  public int getBalance() {
    return balance;
  }
}

The above class models a bank account with attributes of account number and balance, and operations such as deposit(...) and withdraw(...). withdraw(...) will throw a simple checked exception, OverdrawnException, if the amount to withdraw is greater than the available balance.

The remaining classes in the example code are DeadlockDemo and its nested class BadTransferOperation.

public class DeadlockDemo {

  private static final int NUM_ACCOUNTS = 10;
  private static final int NUM_THREADS = 20;
  private static final int NUM_ITERATIONS = 100000;
  private static final int MAX_COLUMNS = 60;

  static final Random rnd = new Random();

  List<Account> accounts = new ArrayList<Account>();

  public static void main(String args[]) {

    DeadlockDemo demo = new DeadlockDemo();
    demo.setUp();
    demo.run();
  }

  void setUp() {

    for (int i = 0; i < NUM_ACCOUNTS; i++) {
      Account account = new Account(i, rnd.nextInt(1000));
      accounts.add(account);
    }
  }

  void run() {

    for (int i = 0; i < NUM_THREADS; i++) {
      new BadTransferOperation(i).start();
    }
  }

  class BadTransferOperation extends Thread {

    int threadNum;

    BadTransferOperation(int threadNum) {
      this.threadNum = threadNum;
    }

    @Override
    public void run() {

      for (int i = 0; i < NUM_ITERATIONS; i++) {

        Account toAccount = accounts.get(rnd.nextInt(NUM_ACCOUNTS));
        Account fromAccount = accounts.get(rnd.nextInt(NUM_ACCOUNTS));
        int amount = rnd.nextInt(1000);

        if (!toAccount.equals(fromAccount)) {
          try {
            transfer(fromAccount, toAccount, amount);
            System.out.print(".");
          } catch (OverdrawnException e) {
            System.out.print("-");
          }

          printNewLine(i);
        }
      }
      // This will never get to here...
      System.out.println("Thread Complete: " + threadNum);
    }

    private void printNewLine(int columnNumber) {

      if (columnNumber % MAX_COLUMNS == 0) {
        System.out.print("\n");
      }
    }

    /**
     * The clue to spotting deadlocks is in the nested locking - synchronized keywords. Note that the locks DON'T
     * have to be next to each other to be nested.
     */
    private void transfer(Account fromAccount, Account toAccount, int transferAmount) throws OverdrawnException {

      synchronized (fromAccount) {
        synchronized (toAccount) {
          fromAccount.withdraw(transferAmount);
          toAccount.deposit(transferAmount);
        }
      }
    }
  }
}

DeadlockDemo provides the application framework that creates a deadlock. It has two simple tasks: setup() and run(). setup() creates 10 accounts initializing them with an account number and a random opening balance. run() creates 20 instances of the nested class BadTransferOperation, which simply extends Thread, and starts them running. Note that the values used for the number of threads and accounts are totally arbitrary.

BadTransferOperation is where all the action takes place. Its run() method loops 10000 times randomly choosing two accounts from the accounts list and transferring a random amount of between 0 and 1000 from one to the other. If the fromAccount contains insufficient funds then an exception is thrown and a ‘-’ printed on the screen. If all goes well and the transfer succeeds then a ‘.’ is printed on the screen.

The heart of the matter is the method transfer(Account fromAccount, Account toAccount, int transferAmount) containing the FAULTY synchronization code:

      synchronized (fromAccount) {
        synchronized (toAccount) {
          fromAccount.withdraw(transferAmount);
          toAccount.deposit(transferAmount);
        }
      }

This code first locks the fromAccount, and then the toAccount before transferring the cash and subsequently releasing both locks.

Given two threads A and B and accounts 1 and 2, then problems will arise when thread A locks its fromAccount, number 1, and tries to lock its toAccount, which is account number 2. Simultaneously thread B locks its fromAccount, number 2, and tries to lock its toAccount, which is account number 1. Hence thread A is BLOCKED on thread B and thread B is BLOCKED on thread A – a deadlock.

If you run this application, then you’ll get some output that looks something like this:

…as the program comes to an abrupt halt.

Now I have a deadlocked application, my next blog will actually get hold of a thread dump and take a look at what it all means.

---

For more information see the other blogs in this series.

All source code for this an other blogs in the series are available on Github at git://github.com/roghughe/captaindebug.git