Investigating Deadlocks – Part 1

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.

Reference: Investigating Deadlocks – Part 1 from our JCG partner Roger Hughes at the Captain Debug’s Blog blog.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

Leave a Reply


five × 3 =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close