ReentrantLock and the Dining Philosophers

A classic problem in concurrency is that of the Dining Philosophers, which examines the issue of deadlock and solutions involving lock ordering and lock management. I'd like to use this problem as a way to investigate some new capabilities offered by the addition of ReentrantLock in Java 5.

The problem involves five philosophers seated at a round table and five chopsticks, one between each pair of philosophers. The philosophers repeatedly alternate between eating and thinking. To eat, they must first pick up one, then the other of the chopsticks.

If they grab the chopsticks arbitrarily, over time a deadlock will inevitably occur such that all philosophers hold the left chopstick and wait for the right one (or vice-versa). The simplest example of this is two philosophers and two chopsticks. If both philosophers pick up their own left chopstick, they will both wait forever for the right one.

Let's start with a Chopstick:

public class Chopstick {
  private final int id;
  public Chopstick(int id) {
    this.id = id;
  }
  
  // equals, hashcode, and toString() omitted
}

We're going to want to abstract out how the chopsticks are obtained so I'm going to also create a ChopstickOrder:

public interface ChopstickOrder {
  Chopstick[] getOrder(Chopstick left, Chopstick right);
}

To start there will be two implementations, RandomOrder (which randomly picks the left or right to start with) and LeftRightOrder (which always picks left, then right).

Then we need a Philosopher:

class Philosopher implements Runnable {
  public final int id;
  private final Chopstick[] chopsticks;
  protected final ChopstickOrder order;
  
  public Philosopher(int id, Chopstick[] chopsticks, ChopstickOrder order) {
    this.id = id;
    this.chopsticks = chopsticks;
    this.order = order;
  }
  
  public void run() {
    while(true) {
      eat();
    }
  }

  protected void eat() {
    Chopstick[] chopstickOrder = order.getOrder(getLeft(), getRight());
    synchronized(chopstickOrder[0]) {      
      synchronized(chopstickOrder[1]) {
        Util.sleep(1000);
      }
    }
  }

  Chopstick getLeft() {  return chopsticks[id]; }
  Chopstick getRight() { return chopsticks[(id+1) % chopsticks.length]; }
  }
}

Here the philosopher can be run and just eats forever, where eating involves choosing which chopstick to pick up first, picking it up, then picking the other one up, then eating.

To test we spin up N chopsticks and N philosophers and set them all to eating using a LeftRightOrder or even a Random order. This will eventually deadlock.

The classic fix is to specify an ordering on how we obtain the resources. If the chopsticks are numbered and every philosopher first tries the lower numbered chopstick, we are guaranteed to avoid deadlock. For example, if N=2, every philosopher grabs chopstick 0 before chopstick 1, so they can never be holding 1 without also holding 0.

So that was all setup. If you look at the Philosopher code above in the eat() method, you'll see that we "grab" a chopstick by synchronizing on it, locking the chopstick's monitor. In Java 5, we have a new way to lock critical sections - the Lock interface and ReentrantLock implementation.

(You may be wondering what "reentrant" means here. It just means that once a thread holds a lock, if it tries to reacquire the lock (reenters the locking code), it will proceed. In other words, it behaves exactly like Java monitors and the familiar behavior of synchronized methods and blocks in Java.)

ReentrantLock gives you all of the functionality of synchronized, plus a lot more options. First let's rewrite eat() with ReentrantLock:

public class GraciousPhilosopher extends Philosopher {

  private static Map chopstickLocks = new ConcurrentHashMap();

  public GraciousPhilosopher(int id, Chopstick[] chopsticks, ChopstickOrder order) {
    super(id, chopsticks, order);
  
    // Every philosopher creates a lock for their left chopstick
    chopstickLocks.put(getLeft(), new ReentrantLock());
  }

  protected void eat() {
    Chopstick[] chopstickOrder = order.getOrder(getLeft(), getRight());
    Lock firstLock = chopstickLocks.get(chopstickOrder[0]);

    Lock secondLock = chopstickLocks.get(chopstickOrder[1]);
    firstLock.lock();
    try { 
        secondLock.lock();
        try { 
          Util.sleep(1000);
        } finally {
          secondLock.unlock();
		}
    } finally { 
        firstLock.unlock();
	}
  }
}

Here we just replace synchronized with lock() and the end of the synchronized block with a try { } finally { unlock() }. So far, no difference in runtime behavior, however.

But we can leverage the additional capabilities of ReentrantLock to do some other nifty stuff. First, we don't have to block forever on the lock call. Instead we can do a timed wait using tryLock(). One form of this method returns immediately if the lock is already held and the other can wait for some period of time for the lock to become available before giving up. In both cases, we could effectively loop and retry the tryLock() until it succeeds.

Another nice option is to lockInterruptibly(). Calling this method makes it possible to wait indefinitely but respond to the thread being interrupted. It is possible to write an external monitor that either watches for deadlock or allows a user to forcibly interrupt one of the working threads. Something like this could be provided via JMX to allow a user to recover from a deadlock. (Of course, I'd recommend fixing the deadlock situation in the first place!)

There is of course some performance cost to using ReentrantLock over synchronized. The implementation is very efficient however and still provides acceptable performance for many common use cases.