Alex Miller lives in St. Louis. He writes code for a living and currently work for Terracotta Tech on the Terracotta open-source Java clustering product. Prior to Terracotta he worked at BEA Systems and was Chief Architect at MetaMatrix. His main language for the last decade has been Java, although Alex have been paid to program in several languages over the years (C++, Python, Pascal, etc). Alex has posted 43 posts at DZone. You can read more from them at their website. View Full User Profile

ReentrantLock and the Dining Philosophers

02.12.2008
| 19141 views |
  • submit to reddit

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.

Published at DZone with permission of its author, Alex Miller.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Alex Miller replied on Tue, 2008/02/12 - 3:29pm in response to: Artur Biesiadowski

Yep, this is an excellent point.  tryLock() and any retry strategy can avoid deadlock but does not alleviate the potential for livelock where all threads are constantly retrying and never succeeding.  In that case, you don't deadlock, but make no further progress.

I believe TCP uses an exponential backoff for stuff like this (although I haven't studied this in 10 years).  A fascinating topic in itself, but outside the scope of this article... :)

Guillermo Schwarz replied on Wed, 2008/02/13 - 10:39am

I think the Dining Philosophers is not such a great example of multithreading, because you can solve it simply by using one of the philosophers as an orchestrator directing other philosophers to eat.

 This is how we solve this situations in real life anyway, using an arbitrator when people can't agree on their own.

If you can't show a problem in real life that uses locks, why do you think locks are such a great idea? I don't see deadlocks in real life, why should computer programs have it? Are we using the wrong abstractions?

 A much better idea, IMHO, is to remove the use of locks by using lock free data structures and algorithms.

See: http://www.ibm.com/developerworks/java/library/j-jtp11234/

Alex Miller replied on Wed, 2008/02/13 - 11:41am

The point of this post is really about how ReentrantLock gives you options that don't exist with synchronized blocks and methods.  It's not an argument for or against the use of locks for protecting access to shared data. 

In general, having one entity tell others what to do sounds to me like a prescription for low concurrency because all of the entities then have to coordinate at the central point.  But it's hard to even talk about this without talking about real examples.  

I don't know about you, but I lock my house, my car, etc every day.  :)  Lock-based access to shared state is *one* style of concurrent programming and happens to be the most prevalent in Java (for better or worse and mean argue for worse).  Message-passing/actor-based or lock-free styles also exist and they all have their pros and cons. 

I've written about ConcurrentSkipListMap in the past, which is an incredibly cool high-concurrency sorted map in Java 6 written with lock-free code.  Lock-free data structures and algorithms rock.  They're also incredibly tricky to get right (if you actually read the code for something like ConcurrentSkipListMap/Set or LinkedBlockingQueue).  ReentrantLock itself is implemented with lock-free code actually. 

Javin Paul replied on Tue, 2011/05/10 - 7:12pm

great example. I have also read somewhere that by using Reentrant lock we can control Reader and Writer and can build cache which allows multiple concurrent read and block only write operation , something which is not possible with synchronized keyword in java which blocks both reader and writer mutual exclusively. I have also blogged some of my synchronization experience as How Synchronization works in Java , you may find useful.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.