Dining Philosophers problem solution with Java ReentrantLock

Question

I have implemented the Dining Philosopher problem using ReentrantLock in Java.

The goal of this program is:

• Every philosopher should follow the workflow of think, getchopsticks, eat, putchopsticks (no race conditions).
• No Philosopher should be starving for food (no deadlocks and no starvation).
• Every Philosopher should get a fair chance to eat food.

To measure these goals, I am printing the number of turns each philosopher got to eat. I would like to get some feedback about the concurrency quality of my implementation.

Philosopher

public class Philosopher implements Runnable {

    private ReentrantLock leftChopStick;
    private ReentrantLock rightChopStick;
    private int Id;

    public AtomicBoolean isTummyFull=new AtomicBoolean(false);

    //To randomize eat/Think time
    private Random randomGenerator = new Random();

    private int noOfTurnsToEat=0;

    public int getId(){
        return this.Id;
    }
    public int getNoOfTurnsToEat(){
        return noOfTurnsToEat;
    }

    /****
     * 
     * @param id Philosopher number
     * 
     * @param leftChopStick
     * @param rightChopStick
     */
    public Philosopher(int id, ReentrantLock leftChopStick, ReentrantLock rightChopStick) {
        this.Id = id;
        this.leftChopStick = leftChopStick;
        this.rightChopStick = rightChopStick;
    }

    @Override
    public void run() {

        while ( !isTummyFull.get()) {
            try {
                think();
                if (pickupLeftChopStick() && pickupRightChopStick()) {
                    eat();
                }
                putDownChopSticks();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    private void think() throws InterruptedException {
        System.out
                .println(String.format("Philosopher %s is thinking", this.Id));
        System.out.flush();
        Thread.sleep(randomGenerator.nextInt(1000));
    }

    private void eat() throws InterruptedException {
        System.out.println(String.format("Philosopher %s is eating", this.Id));
        System.out.flush();
        noOfTurnsToEat++;
        Thread.sleep(randomGenerator.nextInt(1000));
    }

    private boolean pickupLeftChopStick() throws InterruptedException {
        if (leftChopStick.tryLock(10, TimeUnit.MILLISECONDS)) {
            System.out.println(String.format(
                    "Philosopher %s pickedup Left ChopStick", this.Id));
            System.out.flush();
            return true;
        }
        return false;
    }

    private boolean pickupRightChopStick() throws InterruptedException {
        if (rightChopStick.tryLock(10, TimeUnit.MILLISECONDS)) {
            System.out.println(String.format(
                    "Philosopher %s pickedup Right ChopStick", this.Id));
            System.out.flush();
            return true;
        }
        return false;
    }

    private void putDownChopSticks() {
        if (leftChopStick.isHeldByCurrentThread()) {
            leftChopStick.unlock();
            System.out.println(String.format(
                    "Philosopher %s putdown Left ChopStick", this.Id));
            System.out.flush();
        }
        if (rightChopStick.isHeldByCurrentThread()) {
            rightChopStick.unlock();
            System.out.println(String.format(
                    "Philosopher %s putdown Right ChopStick", this.Id));
            System.out.flush();
        }
    }
}

DiningPhilosopherProblem

public class DiningPhilosopherProblem {

    private static final int NO_OF_PHILOSOPHER = 50;
    private static final int SIMULATION_MILLIS = 1000*60*8;

    public static void main(String args[]) throws InterruptedException {
        ExecutorService executorService = null;

        Philosopher[] philosophers = null;
        try {

            philosophers = new Philosopher[NO_OF_PHILOSOPHER];

            //As many forks as Philosophers
            ReentrantLock[] forks = new ReentrantLock[NO_OF_PHILOSOPHER];
            Arrays.fill(forks, new ReentrantLock());

            executorService = Executors.newFixedThreadPool(NO_OF_PHILOSOPHER);

            for (int i = 0; i < NO_OF_PHILOSOPHER; i++) {
                philosophers[i] = new Philosopher(i, forks[i], forks[(i + 1)
                        % NO_OF_PHILOSOPHER]);
                executorService.execute(philosophers[i]);
            }
            //Main thread sleeps till time of simulation
            Thread.sleep(SIMULATION_MILLIS);
            for (Philosopher philosopher : philosophers) {
                philosopher.isTummyFull.set(true);
            }
            //all philosophers are done eating...

        } finally {
            executorService.shutdown();

            // Wait period for all thread to finish
            Thread.sleep(1000);

            //Time for check
            for (Philosopher philosopher : philosophers) {
                System.out.println("Philosopher (" + philosopher.getId()
                        + ") =>No of Turns to Eat ="
                        + philosopher.getNoOfTurnsToEat());
                System.out.flush();
            }
        }
    }
}

Answer 1

I post full code in the hope that you will learn. If this is homework please try to understand all the changes I have made instead of just copying it.

public class DiningPhilosopherProblem {
  // Makes the code more readable.
  public static class ChopStick {
    // Make sure only one philosopher can have me at any time.
    Lock up = new ReentrantLock();
    // Who I am.
    private final int id;

    public ChopStick(int id) {
      this.id = id;
    }

    public boolean pickUp(Philosopher who, String where) throws InterruptedException {
      if (up.tryLock(10, TimeUnit.MILLISECONDS)) {
        System.out.println(who + " picked up " + where + " " + this);
        return true;
      }
      return false;
    }

    public void putDown(Philosopher who, String name) {
      up.unlock();
      System.out.println(who + " put down " + name + " " + this);
    }

    @Override
    public String toString() {
      return "Chopstick-" + id;
    }
  }

  // One philosoper.
  public static class Philosopher implements Runnable {
    // Which one I am.
    private final int id;
    // The chopsticks on either side of me.
    private final ChopStick leftChopStick;
    private final ChopStick rightChopStick;
    // Am I full?
    volatile boolean isTummyFull = false;
    // To randomize eat/Think time
    private Random randomGenerator = new Random();
    // Number of times I was able to eat.
    private int noOfTurnsToEat = 0;

    /**
     * **
     *
     * @param id Philosopher number
     *
     * @param leftChopStick
     * @param rightChopStick
     */
    public Philosopher(int id, ChopStick leftChopStick, ChopStick rightChopStick) {
      this.id = id;
      this.leftChopStick = leftChopStick;
      this.rightChopStick = rightChopStick;
    }

    @Override
    public void run() {

      try {
        while (!isTummyFull) {
          // Think for a bit.
          think();
          // Make the mechanism obvious.
          if (leftChopStick.pickUp(this, "left")) {
            if (rightChopStick.pickUp(this, "right")) {
              // Eat some.
              eat();
              // Finished.
              rightChopStick.putDown(this, "right");
            }
            // Finished.
            leftChopStick.putDown(this, "left");
          }
        }
      } catch (Exception e) {
        // Catch the exception outside the loop.
        e.printStackTrace();
      }
    }

    private void think() throws InterruptedException {
      System.out.println(this + " is thinking");
      Thread.sleep(randomGenerator.nextInt(1000));
    }

    private void eat() throws InterruptedException {
      System.out.println(this + " is eating");
      noOfTurnsToEat++;
      Thread.sleep(randomGenerator.nextInt(1000));
    }

    // Accessors at the end.
    public int getNoOfTurnsToEat() {
      return noOfTurnsToEat;
    }

    @Override
    public String toString() {
      return "Philosopher-" + id;
    }
  }
  // How many to test with.
  private static final int NO_OF_PHILOSOPHER = 50;
  //private static final int SIMULATION_MILLIS = 1000 * 60 * 8;
  private static final int SIMULATION_MILLIS = 1000 * 10;

  public static void main(String args[]) throws InterruptedException {
    ExecutorService executorService = null;

    Philosopher[] philosophers = null;
    try {

      philosophers = new Philosopher[NO_OF_PHILOSOPHER];

      //As many forks as Philosophers
      ChopStick[] chopSticks = new ChopStick[NO_OF_PHILOSOPHER];
      // Cannot do this as it will fill the whole array with the SAME chopstick.
      //Arrays.fill(chopSticks, new ReentrantLock());
      for (int i = 0; i < NO_OF_PHILOSOPHER; i++) {
        chopSticks[i] = new ChopStick(i);
      }

      executorService = Executors.newFixedThreadPool(NO_OF_PHILOSOPHER);

      for (int i = 0; i < NO_OF_PHILOSOPHER; i++) {
        philosophers[i] = new Philosopher(i, chopSticks[i], chopSticks[(i + 1) % NO_OF_PHILOSOPHER]);
        executorService.execute(philosophers[i]);
      }
      // Main thread sleeps till time of simulation
      Thread.sleep(SIMULATION_MILLIS);
      // Stop all philosophers.
      for (Philosopher philosopher : philosophers) {
        philosopher.isTummyFull = true;
      }

    } finally {
      // Close everything down.
      executorService.shutdown();

      // Wait for all thread to finish
      while (!executorService.isTerminated()) {
        Thread.sleep(1000);
      }

      // Time for check
      for (Philosopher philosopher : philosophers) {
        System.out.println(philosopher + " => No of Turns to Eat ="
                + philosopher.getNoOfTurnsToEat());
      }
    }
  }
}

Please note at least the following changes:

• Creation of a ChopStick class to make the code more readable and easier to print from.
• Surrounding the whole while loop in the try/catch block instead of one iteration. This will ensure that if you are interrupted you will exit immediately which is more polite instead of carrying on.
• Use of volatile boolean instead of AtomicBoolean. They are similar but different and AtomicBoolean is not necessary in this case.
• Adding and using toString methods.
• Parameterise pickUp and putDown to reduce unnecessary code.
• Correct flow to pickup right and, if that succeeds, pickup left - along with safe putDown calls if one succeeds and not the other.
• Correct construction of the locks (now ChopStick objects). You had them all being the same object.
• Safe waiting for the executor shutdown rather than just waiting 1 second.
• Move the lock mechanism into the ChopStick object.