6
\$\begingroup\$

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();
            }
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I am sorry but could you explain to me why this code doesn't generate a deadlock if all the philosophers pick up the left chopstick? \$\endgroup\$ – user1544128 Jan 7 '14 at 9:49
6
\$\begingroup\$

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.
\$\endgroup\$

protected by Jamal Feb 10 '16 at 20:26

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.