Investigating Deadlocks – Part 5: Using Explicit Locking

The idea here of calling a locking mechanism explicit rather than implicit is that the explicit means that it is not part of the Java language and that classes have been written to fulfill the locking functionality. Implicit locking, on the other hand, can be defined as locking that is part of the language and is implemented in the background using the language keyword synchronchized.

You could argue as to whether or not explicit locking is a good idea. Shouldn’t the Java language be improved to include the features of explicit locking rather than adding yet another set of classes to the already enormous API? For example: trysynchronized().
Explicit locking is based around the Lock interface and its ReentrantLock implementation. Lock contains a bunch of methods that give you lots more control over locking than the traditional synchronized keyword. It’s got the methods that you'd expect it to have, such as lock(), which will create an entry point into a guarded section of code and unlock(), which creates the exit point. It also has tryLock(), which will only acquire a lock if it’s available and not already acquired by another thread and tryLock(long time,TimeUnit unit), which will try to acquire a lock and, if it's unavailable wait for the specified timer to expire before giving up.

In order to implement explicit locking I’ve first added the Lock interface to the Account class used in previous blogs in this series.

public class Account implements Lock {

  private final int number;

  private int balance;

  private final ReentrantLock lock;

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

  public void withDrawAmount(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;
  }

  // ------- Lock interface implementation

  @Override
  public void lock() {
    lock.lock();
  }

  @Override
  public void lockInterruptibly() throws InterruptedException {
    lock.lockInterruptibly();
  }

  @Override
  public Condition newCondition() {
    return lock.newCondition();
  }

  @Override
  public boolean tryLock() {
    return lock.tryLock();
  }

  @Override
  public boolean tryLock(long arg0, TimeUnit arg1) throws InterruptedException {
    return lock.tryLock(arg0, arg1);
  }

  @Override
  public void unlock() {
    if (lock.isHeldByCurrentThread()) {
      lock.unlock();
    }
  }

}

In the code above you can seen that I’m favouring aggregation by encapsulating a ReentrantLock object to which the Account class delegates locking functionality. The only small GOTCHA to be aware of is in the unlock() implementation:

 @Override
  public void unlock() {
    if (lock.isHeldByCurrentThread()) {
      lock.unlock();
    }
  }

This has an additional if() statement that checks whether or not the calling thread is the thread that currently holds the lock. If this line of code is missed out then you’ll get the following IllegalMonitorStateException:

Exception in thread "Thread-7" java.lang.IllegalMonitorStateException
 at java.util.concurrent.locks.ReentrantLock$Sync.tryRelease(ReentrantLock.java:155)
 at java.util.concurrent.locks.AbstractQueuedSynchronizer.release(AbstractQueuedSynchronizer.java:1260)
 at java.util.concurrent.locks.ReentrantLock.unlock(ReentrantLock.java:460)
 at threads.lock.Account.unlock(Account.java:76)
 at threads.lock.TrylockDemo$BadTransferOperation.transfer(TrylockDemo.java:98)
 at threads.lock.TrylockDemo$BadTransferOperation.run(TrylockDemo.java:67)

So, how is this implemented? Below is the listing of my TryLockDemo sample that’s based upon my original DeadLockDemo program.

public class TrylockDemo {

  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 LOCK_ATTEMPTS = 10000;

  static final Random rnd = new Random();

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

  public static void main(String args[]) {

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

  void setUp() {

    for (int i = 0; i < NUM_ACCOUNTS; i++) {
      Account account = new Account(i, 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() {

      int transactionCount = 0;

      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)) {

          boolean successfulTransfer = false;

          try {
            successfulTransfer = transfer(fromAccount, toAccount, amount);

          } catch (OverdrawnException e) {
            successfulTransfer = true;
          }

          if (successfulTransfer) {
            transactionCount++;
          }

        }
      }

      System.out.println("Thread Complete: " + threadNum + " Successfully made " + transactionCount + " out of "
          + NUM_ITERATIONS);
    }

    private boolean transfer(Account fromAccount, Account toAccount, int transferAmount) throws OverdrawnException {

      boolean success = false;
      for (int i = 0; i < LOCK_ATTEMPTS; i++) {

        try {
          if (fromAccount.tryLock()) {
            try {
              if (toAccount.tryLock()) {

                success = true;
                fromAccount.withDrawAmount(transferAmount);
                toAccount.deposit(transferAmount);
                break;
              }
            } finally {
              toAccount.unlock();
            }
          }
        } finally {
          fromAccount.unlock();
        }
      }

      return success;
    }

  }
}

The idea is the same, I have a list of bank accounts and I’m going to randomly choose two accounts and transfer a random amount from one to the other. The heart of the matter is my updated transfer(...) method as shown below.

private boolean transfer(Account fromAccount, Account toAccount, int transferAmount) throws OverdrawnException {

      boolean success = false;
      for (int i = 0; i < LOCK_ATTEMPTS; i++) {

        try {
          if (fromAccount.tryLock()) {
            try {
              if (toAccount.tryLock()) {

                success = true;
                fromAccount.withDrawAmount(transferAmount);
                toAccount.deposit(transferAmount);
                break;
              }
            } finally {
              toAccount.unlock();
            }
          }
        } finally {
          fromAccount.unlock();
        }
      }

      return success;
    }

The idea here is that I try to lock the fromAccount and then the toAccount. If that works then I make the transfer before remembering to unlock both accounts. If then accounts are already locked, then my tryLock() method fails and the whole thing loops around and tries again. After 10000 lock attempts, the thread gives up and ignores the transfer. I guess that in a real world application you’d want to put this failure onto some sort of queue so that it can be investigated later.

In using explicit locking, you have to consider how well it works, so take a look at the results below...

Thread Complete: 17 Successfully made 58142 out of 100000
Thread Complete: 12 Successfully made 57627 out of 100000
Thread Complete: 9 Successfully made 57901 out of 100000
Thread Complete: 16 Successfully made 56754 out of 100000
Thread Complete: 3 Successfully made 56914 out of 100000
Thread Complete: 14 Successfully made 57048 out of 100000
Thread Complete: 8 Successfully made 56817 out of 100000
Thread Complete: 4 Successfully made 57134 out of 100000
Thread Complete: 15 Successfully made 56636 out of 100000
Thread Complete: 19 Successfully made 56399 out of 100000
Thread Complete: 2 Successfully made 56603 out of 100000
Thread Complete: 13 Successfully made 56889 out of 100000
Thread Complete: 0 Successfully made 56904 out of 100000
Thread Complete: 5 Successfully made 57119 out of 100000
Thread Complete: 7 Successfully made 56776 out of 100000
Thread Complete: 6 Successfully made 57076 out of 100000
Thread Complete: 10 Successfully made 56871 out of 100000
Thread Complete: 11 Successfully made 56863 out of 100000
Thread Complete: 18 Successfully made 56916 out of 100000
Thread Complete: 1 Successfully made 57304 out of 100000

These show that although the program didn’t deadlock and hang indefinitely, it only managed to make the balance transfer in only slightly more than half the transfer requests. This means that it’s burning lots of processing power looping and looping and looping - which is altogether not very efficient. Also, I said a moment ago that that the program “didn’t deadlock and hang indefinitely”, which is not quite true. If you think about what’s happening then you’ll realize that your program is deadlocking and then backing out of that situation.

The second version of my explicit locking demo code uses the tryLock(long time,TimeUnit unit) mentioned above.

private boolean transfer(Account fromAccount, Account toAccount, int transferAmount) throws OverdrawnException {

      boolean success = false;

      try {
        if (fromAccount.tryLock(LOCK_TIMEOUT, TimeUnit.MILLISECONDS)) {
          try {
            if (toAccount.tryLock(LOCK_TIMEOUT, TimeUnit.MILLISECONDS)) {

              success = true;
              fromAccount.withDrawAmount(transferAmount);
              toAccount.deposit(transferAmount);
            }
          } finally {
            toAccount.unlock();
          }
        }
      } catch (InterruptedException e) {
        e.printStackTrace();
      } finally {
        fromAccount.unlock();
      }

      return success;
    }

In this code I’ve replaced the for loop with a tryLock(...) timeout of 1 millisecond. This means that when the tryLock(...) is called and cannot acquire the lock, it’ll wait 1 mS before rolling back and giving up.

Thread Complete: 0 Successfully made 26637 out of 100000
Thread Complete: 14 Successfully made 26516 out of 100000
Thread Complete: 3 Successfully made 26552 out of 100000
Thread Complete: 11 Successfully made 26653 out of 100000
Thread Complete: 7 Successfully made 26399 out of 100000
Thread Complete: 1 Successfully made 26602 out of 100000
Thread Complete: 18 Successfully made 26606 out of 100000
Thread Complete: 17 Successfully made 26358 out of 100000
Thread Complete: 19 Successfully made 26407 out of 100000
Thread Complete: 16 Successfully made 26312 out of 100000
Thread Complete: 15 Successfully made 26449 out of 100000
Thread Complete: 5 Successfully made 26388 out of 100000
Thread Complete: 8 Successfully made 26613 out of 100000
Thread Complete: 2 Successfully made 26504 out of 100000
Thread Complete: 6 Successfully made 26420 out of 100000
Thread Complete: 4 Successfully made 26452 out of 100000
Thread Complete: 9 Successfully made 26287 out of 100000
Thread Complete: 12 Successfully made 26507 out of 100000
Thread Complete: 10 Successfully made 26660 out of 100000
Thread Complete: 13 Successfully made 26523 out of 100000

The result above show that when using a timer the balance transfer success rate falls even more to slightly more than 25%. Although it’s not now burning stack of processor time, it is still highly inefficient.

I could mess around with both of these code samples for quite some time choosing variables that tune the app and improve performance, but at the end of the day, there’s no real substitute for getting your lock ordering right. I’d personally prefer to use the old fashioned synchronized key word implicit locking where ever possible and reserve explicit locking for those few situations where the deadlocking code is old, gnarly, indecipherable, I’ve tried everything else, the app needs to go live, it’s late and it’s time to go home...

---

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