Semaphore problems in Java with the Dining Philosophers

Question

Hello, I'm trying to learn the basic jist of a Semaphore in the Dining Philosopher problem. Right now, I have an array of class Chopstick, and each Chopstick has a semaphore with 1 available permit:

public class Chopstick
{
    Thread holder = null;
    private Semaphore lock = new Semaphore(1);

    public synchronized void take() throws InterruptedException
    {
     this.lock.acquire();
     holder = Thread.currentThread();

    }

    public synchronized void release()
    { 
     this.lock.release();
     holder = null;
    }
}

The holder variable is used for a function that I am not sure I need:

public synchronized void conditionalRelease()
{
 if (holder == Thread.currentThread())
 {
  holder = null;
  this.lock.release();
 }
}

The program compiles and runs, but seems to have some trouble releasing the chopsticks. Sometimes, the chopsticks get released, sometimes they don't. When they don't release, the program eventually hangs up when all of the chopsticks are taken and one philosopher is hungry.

Here is the code within the Philosopher class to release the chopstick after a random amount of time:

System.out.println(this.name + " is eating");
Thread.sleep(this.getRandTime());
System.out.println(this.name + " has finished eating");

rightChopstick.release();
System.out.println(this.name + " has released the right chopstick");
leftChopstick.release();
System.out.println(this.name + " has released the left chopstick");

My program does output "Philosopher 0 has finished eating", for example, and continues execution. The other two lines never output, so obviously something is wrong with the way I am releasing.

Any help is appreciated.

Answer 1

I would take the 'synchronized' keyword out of your method signatures. You're using an external locking mechanism (the semaphore, in this case). The 'synchronized' keyword is trying to get locks using the object's own mutex. You are now locking on 2 resources which I suspect might be causing a deadlock.

Answer 2

The problem is that when thread1 has a specific chopstick and another tries to get the same one it will wait in the take()-method on line this.lock.acquire(); but it will NOT release the monitor on the object itself.

If now thread1 tries to release the chopstick it can not enter the release()-method since it's still locked by the other thread waiting in take(). That's a deadlock

Answer 3

It seems a little confusing that you are both locking on the chopstick and having it hold a semaphore of size 1. Generally a semaphore provides tickets to a resource and if you have only one ticket, that's effectively mutual exclusion which is identical to a lock (either a synchronized block or a Lock object). You might consider actually making the Chopstick the lock object itself.

I did a blog post on the dining philosophers in Java a while back if you're interested, although it's really about how to avoid deadlock by using other strategies.

• http://tech.puredanger.com/2008/02/12/reentrantlock-and-the-dining-philosophers/