DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports
Events Video Library
Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
View Events Video Library
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Integrating PostgreSQL Databases with ANF: Join this workshop to learn how to create a PostgreSQL server using Instaclustr’s managed service

Mobile Database Essentials: Assess data needs, storage requirements, and more when leveraging databases for cloud and edge applications.

Monitoring and Observability for LLMs: Datadog and Google Cloud discuss how to achieve optimal AI model performance.

Automated Testing: The latest on architecture, TDD, and the benefits of AI and low-code tools.

Related

  • Java and Low Latency
  • Implementing WOPI Protocol For Office Integration
  • The Curious Case of Dead-End-Lock(Deadlock) | MySql
  • Dynamic Schedulers and Custom Cross-Server Schedule Lock

Trending

  • Spring Authentication With MetaMask
  • Five Free AI Tools for Programmers to 10X Their Productivity
  • Creating a Deep vs. Shallow Copy of an Object in Java
  • Automate Your Quarkus Deployment Using Ansible

ReentrantLock and the Dining Philosophers

Alex Miller user avatar by
Alex Miller
·
Feb. 12, 08 · News
Like (1)
Save
Tweet
Share
29.64K Views

Join the DZone community and get the full member experience.

Join For Free

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.

Lock (computer science)

Opinions expressed by DZone contributors are their own.

Related

  • Java and Low Latency
  • Implementing WOPI Protocol For Office Integration
  • The Curious Case of Dead-End-Lock(Deadlock) | MySql
  • Dynamic Schedulers and Custom Cross-Server Schedule Lock

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends: