"Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.
Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when he has both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After he finishes eating, he needs to put down both forks so they become available to others. A philosopher can take the fork on his right or the one on his left as they become available, but cannot start eating before getting both of them.
Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply is assumed.
The problem is how to design a discipline of behavior (a concurrent algorithm) such that each philosopher will not starve; i.e., can forever continue to alternate between eating and thinking, assuming that any philosopher cannot know when others may want to eat or think. "
The problem was designed to illustrate the challenges of avoiding deadlock.
- think until the left fork is available; when it is, pick it up;
- think until the right fork is available; when it is, pick it up;
- when both forks are held, eat for a fixed amount of time;
- then, put the forks down;
- repeat from the beginning.
Solution:
import java.util.Random;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class DiningPhilosophers {
// The number of philosophers
private static final int numPhilosophers = 5;
public static void main(String[] args) {
// Model each fork with a lock
Lock[] forks = new ReentrantLock[numPhilosophers];
for(int i = 0; i < numPhilosophers; i++) {
forks[i] = new ReentrantLock();
}
// Create the philosophers and start each running in its own thread.
Philosopher[] philosophers = new Philosopher[numPhilosophers];
for(int i = 0; i < numPhilosophers; i++) {
philosophers[i] = new Philosopher(i, forks[i], forks[(i + 1) % numPhilosophers]);
new Thread(philosophers[i]).start();
}
}
}
//A philosopher alternates between thinking and eating. To eat, the philosopher needs to pick
//up the left fork and then the right fork sequentially. The philosopher shares
//forks with its neighbors, so it cannot eat at the same time as either neighbor
class Philosopher implements Runnable {
// Used to vary how long a philosopher thinks before eating and how long the
// philosopher eats
private Random numGenerator = new Random();
// The philosopher's unique id
private int pid;
// The forks this philosopher may use
private Lock leftFork;
private Lock rightFork;
//Constructs a new philosopher
public Philosopher(int pid, Lock leftFork, Lock rightFork) {
this.pid = pid;
this.leftFork = leftFork;
this.rightFork = rightFork;
}
//Repeatedly think, pick up forks, eat and put down forks
public void run() {
try {
while(true) {
think();
pickLeftFork();
pickRightFork();
eat();
putDownForks();
}
}catch (InterruptedException e) {
System.out.println("Philosopher " + pid + " was interrupted.\n");
}
}
//Let a random amount of time pass to model thinking. @throws InterruptedException
private void think() throws InterruptedException {
System.out.println("Philosopher " + pid + " is thinking.\n");
System.out.flush();
Thread.sleep (numGenerator.nextInt(10));
/**
* With "Thread.sleep(10)", this can eliminates the possibility of deadlock
* (the system can always advance to a different state) but still suffers from the problem of "livelock".
* If all five philosophers appear in the dining room at exactly the same time and
* each picks up the left fork at the same time the philosophers will wait ten milliseconds
* until they all put their forks down and then wait a further ten milliseconds
* before they all pick them up again.
*/
//Thread.sleep(10);
}
//Locks the left fork to signify that this philosopher is holding it
private void pickLeftFork() {
leftFork.lock();
System.out.println("Philosopher " + pid + " is holding left fork.\n");
System.out.flush();
}
//Locks the right fork to signify that this philosopher is holding it
private void pickRightFork() {
rightFork.lock();
System.out.println("Philosopher " + pid + " is holding right fork.\n");
System.out.flush();
}
//Let a random amount of time pass to model eating. @throws InterruptedException
private void eat() throws InterruptedException {
System.out.println("Philosopher " + pid + " is eating.\n");
System.out.flush();
Thread.sleep (numGenerator.nextInt(10));
//Thread.sleep(10);
}
//Releases the locks on both forks to model putting them down so the other philosophers can use them.
private void putDownForks() {
leftFork.unlock();
rightFork.unlock();
System.out.println("Philosopher " + pid + " puts down forks.\n");
}
}
Reference: http://everythingcomputerscience.com/projects/java_programs/DiningPhilosophers.txt
