Dining Philosophers problem code review

Question

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();
        Thread t1 = new Thread(new Philosopher("First",this.chopsticks[4],this.chopsticks[0]));
        Thread t2 = new Thread(new Philosopher("Second",this.chopsticks[0],this.chopsticks[1]));
        Thread t3 = new Thread(new Philosopher("Third",this.chopsticks[1],this.chopsticks[2]));
        Thread t4 = new Thread(new Philosopher("Fourth",this.chopsticks[2],this.chopsticks[3]));
        Thread t5 = new Thread(new Philosopher("Fifth",this.chopsticks[3],this.chopsticks[4]));
        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 
    * information about the possible 
    * 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{
                    Thread.sleep(1);
                    _leftChopstick.setUsed(true);
                    _rightChopstick.setUsed(true);
                    this.setPhilosopherState(Philosopher.State.EATING);
                    Thread.sleep(randomise.nextInt(MAX_EATING_TIME));
                }
                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);
        Thread.sleep(randomise.nextInt(MAX_THINKING_TIME));
    }

    /*
    * 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;
    }
}

Answer 1

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.

Answer 2

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 {
                    Thread.sleep(randomise.nextInt(MAX_EATING_TIME));
                }
                finally {
                     _rightChopStick.unlock();
                }
            }
        }
        finally {
            _leftChopstick.unlock();
        }
    }
    think();
}      

Answer 3

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.