# Dining Philosophers

I've just finished my solution to the Dining Philosopher's Problem, but I am not confident with my code because I am still newbie to the concurrency world. I would appreciate it if you could leave me some feedback.

Here is my main class:

public class DiningPhilosophersTable {

//An array holding all the chopsticks
private final Chopstick[] chopsticks = new Chopstick[5];

/*Constructor for the main class
* Creates all the chopsticks
* Creates and starts all the threads*/
public DiningPhilosophersTable(){
putChopsticksOnTheTable();
t1.start();
t2.start();
t3.start();
t4.start();
t5.start();
}

/*Initialise the chopsticks in the array*/
private void putChopsticksOnTheTable(){
for(int i = 0;i < chopsticks.length;i++)
chopsticks[i]= new Chopstick();
}

public static void main(String[] args){
new DiningPhilosophersTable();
}
}


Here is the Philosopher class:

public class Philosopher extends Thread{

private static final int MAX_EATING_TIME = 1000;
private static final int MAX_THINKING_TIME = 800;
private final Random randomise = new Random();
private final Chopstick _leftChopstick;
private final Chopstick _rightChopstick;
private final String _name;
private State _state;

/* Enumeration class that holds
* Philosopher's states
*/
public enum State {
EATING, THINKING, WAITING
}

/*
* Main constructor for the Philosopher class
* @param name   the name of the Philosopher
* @param leftChopstick  the chopstick that is currently on the left of the Philosopher
* @param rightChopstick the chopstick currently on the right of the Philosopher
*
*/
public Philosopher(String name, Chopstick leftChopstick, Chopstick rightChopstick) {
System.out.println(name +"Started");
this._leftChopstick = leftChopstick;
this._rightChopstick = rightChopstick;
this._name = name;
}

/*
* The method eat that uses two chopsticks. It blockes the two Chopstick
* objects so they could not be changed then it changes their state
* as well as the state of the philosopher
* At the end of the method, the chopsticks' state is reverted and
* the Philosopher goes into the Thinking state
*/
private void eat() throws InterruptedException {

synchronized(_leftChopstick){
while(_leftChopstick.isUsed() || _rightChopstick.isUsed())
try{
this.setPhilosopherState(Philosopher.State.WAITING);
_leftChopstick.wait();
}catch (InterruptedException e){}
synchronized(_rightChopstick) {
try{
_leftChopstick.setUsed(true);
_rightChopstick.setUsed(true);
this.setPhilosopherState(Philosopher.State.EATING);
}
finally {
_leftChopstick.setUsed(false);
_rightChopstick.setUsed(false);
_leftChopstick.notify();
_rightChopstick.notify();
}
}
}

think();
}

/*
* This method only changes the state
* of the Philosopher to Thinking
*/
private void think() throws InterruptedException{
this.setPhilosopherState(Philosopher.State.THINKING);
}

/*
* Set the current state of the Philosopher
*/
private void setPhilosopherState(State state){
this._state = state;
System.out.println(System.currentTimeMillis() +":"+ _state +", "+ _name+";");
}

/*
* Get the current state of the Philosopher
*/
public State getPhilosopherState(){
return _state;
}

/*
* The method is invoked with the start of the thread
* and runs the eat function for 10 times
*/
public void run(){
for(int i =0; i< 10;i++){
try {
eat();
} catch (InterruptedException e) {
e.printStackTrace();
}
}

System.out.println("Succesfully finished: " +_name);
}
}


And the last class:

public class Chopstick {

private boolean _isUsed;

/*
* @return the current state of the chopstick
*/
public boolean isUsed(){
return _isUsed;
}

/*
* @param usedFlag the new state of the chopstick
*/
public void setUsed(boolean usedFlag){
_isUsed = usedFlag;
}
}

-
Why does Philosopher extend Thread? –  Peter Taylor Nov 28 '11 at 13:04
Since I need 5 Philosophers on the table I thought It might be a good idea to make them concurrent. –  Zee Nov 28 '11 at 14:47
But you could change Philosopher to simply implement Runnable and it would still work - this is good practice. Alternatively you could change new Thread(new Philosopher(...)) to new Philosopher(...) but this is not considered good practice. As it is you create Thread instances which you never call start() on, which is at best pointless and at worst wasteful of a limited OS resource. –  Peter Taylor Nov 28 '11 at 15:04
The formatting of the indentation of eat() does NOT match how the statements are actually (not) nested, which gives the impression of a completely different outcome. And yes, implement Runnable instead of extending thread. –  Clockwork-Muse Nov 28 '11 at 18:16
Do you want to demonstrate the possible deadlock with this code? Or is it supposed to be a deadlock-free implementation? –  palacsint Dec 2 '11 at 22:13

Just a quick note:

synchronized(_leftChopstick){
while(_leftChopstick.isUsed() || _rightChopstick.isUsed())


Here you should synchronize on _rightChopstick too since isUsed could be called from other threads concurrently.

[...] synchronization has no effect unless both read and write operations are synchronized.

From Effective Java, 2nd Edition, Item 66: Synchronize access to shared mutable data.

Locking is not just about mutual exclusion; it is also about memory visibility. To ensure that all threads see the most up-to-date values of shared mutable variables, the reading and writing threads must synchronize on a common lock.

From Java Concurrency in Practice, 3.1.3. Locking and Visibility.

Another (and better) solution is using AtomicBooleans.

-
Hmm.. I am synchronizing on it a few lines further down. I cannot w8 on _rightChopstick outside the synchronizing block for it. I'm sorry I might be missunderstanding your idea. –  Zee Nov 28 '11 at 14:49
When you read a variable which is written by multiple threads you should synchronize the access. I mean before you access it, not later. Java Concurrency in Practice is a really good book on this topic, if you have time read it, it's worth the time. –  palacsint Nov 29 '11 at 9:29
Do you suggest I use only _rightChopstick.isUsed() in my while loop? –  Zee Nov 30 '11 at 18:05
@palacsint there is no need to lock on _rightChopstick before testing its availability as write access always occures in synchronized region –  maks Dec 16 '12 at 0:46
@Zee: I'm just saying that you should synchronize on that variable too. Sorry for the late answer. –  palacsint Dec 21 '12 at 7:44

Instead of Chopstick class you could use java.util.concurrent.locks.Lock directly. Possible implementation (not starvation free)

private void eat() {
if (_leftChopstick.tryLock()) {
try {
if (_rightChopStick.tryLock()) {
try {
}
finally {
_rightChopStick.unlock();
}
}
}
finally {
_leftChopstick.unlock();
}
}
think();
}

-

Theoretically deadlock can occur in your code(There is a small probability, especially this probability rises when you run your code on a single core system).

Suppose such situation in which philosophers are enumerated clockwise. 1st philosophers acquire a lock on left chopstick, then test if left and right chopstics are free(at start they can be free) and right after that 2nd philosopher(which sits right to first) also acquire a lock on his left chopstick. So the 1st philosopher will be blocked on his right chopstick's monitor.

3rd and 4th philosophers repeat described process after 1st and 2nd philosopher.

And the lst 5th philosophers will acquire a lock on his left chopstick's monitor and will be blocked on his right chopsticks monitor while testing its availability.

This probability is rather small but it can occur. And if it can occur then I think it is not a valid code. Deadlock's propability has to be equal to 0, then it will be a valid code.

-