This is an example of the Dining Philosophers’ problem. A short description of the problem shows that there are N philosphers sitting around a circular table eating and discussing philosphy. The problem is that each philosopher needs 2 forks to eat, and there are only N forks, one between each 2 philosophers. An algorithm is needed for the philosophers to follow that will ensure that none starves as long as each philosopher eventually stops eating, and such that the maximum number of philosophers can eat at once. The example consists of the following classes:
- The class
Spoonrepresents the spoons that a Philosopher needs in order to eat. - The class Philosopher extends the Thread, and overrides its
run()method and itstoString()method. It consists of two methods,think()andeat(). In thethink()method, the thread sleeps for a random number of milliseconds. In itseat()method the thread holds in asynchronizedstatement the left Spoon first and then the second Spoon that represent the left and the right spoon of thePhilosopher. In its constructor the thread gets the two Spoon objects that represent the left and the right spoon and calls itsstart()method to begin execution. In its overridenrun()method the thread keeps callingthink()andeat()methods forever. - The
Timeoutclass extends the Timer class and overrides itsrun()method. It sets its superTimer(boolean isDaemon)true, so that the associated thread should run as a daemon. It calls itsschedule(TimerTask task, long delay)method with a new TimerTask and a specified delay. Is is used in the example in order to stop the running Java Virtual Machine after a specified time. - In order to run the example, we create a
Philosopherarray. We create the two Spoon objects, that are the left and right spoon. For each one of the philosopher array positions we create a new Philosopher to put into the array and we give the Philosopher a left and a right spoon. Then the right spoon is set to the left and a new rightSpoonis created for the nextPhilosopher. In order to avoid the deadlock we use the static booleangotoDeadLock. When set to true a newPhilosopheris created and gets the left and first spoon, that have values set above and in the while statement.
Let’s take a look at the code snippet that follows:
package com.javacodegeeks.snippets.core;
import java.util.Random;
import java.util.Timer;
import java.util.TimerTask;
class Spoon {
private static int cnt = 0;
private int num = cnt++;
@Override
public String toString() {
return "Spoon " + num;
}
}
class Philosopher extends Thread {
private static Random rnd = new Random();
private static int cnt = 0;
private int num = cnt++;
private Spoon leftSpoon;
private Spoon rightSpoon;
static int waiting = 0;
public Philosopher(Spoon left, Spoon right) {
leftSpoon = left;
rightSpoon = right;
start();
}
public void think() {
System.out.println(this + " is thinking");
if (waiting > 0) {
try {
sleep(rnd.nextInt(waiting));
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
public void eat() {
synchronized (leftSpoon) {
System.out.println(this + " has " + this.leftSpoon + " Waiting for " + this.rightSpoon);
synchronized (rightSpoon) {
System.out.println(this + " eating");
}
}
}
@Override
public String toString() {
return "Philosopher " + num;
}
@Override
public void run() {
while (true) {
think();
eat();
}
}
}
public class DiningPhilosophers {
private static boolean gotoDeadLock =true;
public static void main(String[] args) {
Philosopher[] phil = new Philosopher[10];
Philosopher.waiting = 8;
Spoon left = new Spoon(), right = new Spoon(), first = left;
int i = 0;
while (i < phil.length - 1) {
phil[i++] = new Philosopher(left, right);
left = right;
right = new Spoon();
}
if (gotoDeadLock) {
phil[i] = new Philosopher(left, first);
} else
{
phil[i] = new Philosopher(first, left);
}
if (args.length >= 4) {
int delay = 3;
if (delay != 0) {
Timeout timeout = new Timeout(delay * 1000, "Timed out");
}
}
}
}
class Timeout extends Timer {
public Timeout(int delay, final String msg) {
super(true);
schedule(new TimerTask() {
@Override
public void run() {
System.out.println(msg);
System.exit(0);
}
}, delay);
}
}
This was an example of the Dining Philosophers’ problem in Java.
