Dining Philosophers Concurrency Problem in Java


Dining Philosophers is a problem about concurrent programming and synchronization, first proposed in 1965 by Dijkstra.

Basically you have X philosophers sitting around a table, and there are X forks available (one between each philosopher). The philosophers do two things: think and eat (alternating between both). However, in order to eat the philosopher must grab both the fork on his left and on his right. As you can see not all philosophers can eat at the same thing, and figuring out an algorithm that will maximize the number of philosophers eating at any given time is not trivial.

Below you’ll find my Java implementation of this problem, which even has a small animation. Inside the code there are five different algorithms. Each has its pros and cons. You can read more about it on Github repository of the same problem (there you can find the images of the animation as well).

package DiningPhilosophers;

import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import java.io.*;
import javax.imageio.*;
import javax.swing.*;
import java.text.DecimalFormat;
import java.util.concurrent.Semaphore;

public class Philosophers{
  //Number of philosophers, max=14
  private static final int NUMBER = 9;
  //Min and Max Sleep Interval, used by eat() and think()
  private static final int MIN_SLEEP = 500;
  private static final int MAX_SLEEP = 3000;
  //Variables used by the animation
  private static JLabel[] forks = new JLabel[15];
  private static JLabel[] philosophers = new JLabel[14];
  private static JLabel table;
  private static JLabel[] averages = new JLabel[3];
  private static JFrame frame;
  private static JPanel compPanel;
  //Threads
  private static Thread[] threads = new Thread[NUMBER];
  private static Thread controller;
  //Data structures used for synchronization
  private static volatile int[] forksArray = new int[14];
  private static volatile int meals = 0;
  private static volatile int[] philosopherStatus = new int[NUMBER];
  private static float concurrent = 0;
  private static int samples = 0;
  private static float mealsPerSecond = 0;
  private static long startTime;
  private static long currentTime;
  private static Semaphore[] forksSem = new Semaphore[NUMBER];
  private static Semaphore placesSem;
  private static volatile int[] philosophersBlock = new int[NUMBER];

  private static void createAndShowFrame() {
        //Create and set up the window.
        frame = new JFrame("Dining Philosophers");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        
    //This will center the JFrame in the middle of the screen
        frame.setLocationRelativeTo(null);

    //Use this to find the path to files 
    //System.out.println(new File("table3.jpg").getAbsolutePath());

    //create GribBagLayout and the GridBagLayout Constraints
        GridBagLayout gridBag = new GridBagLayout();
        GridBagConstraints cons = new GridBagConstraints();
    cons.fill = GridBagConstraints.BOTH;

    //Create panel and set layout
    compPanel = new JPanel();
        compPanel.setLayout(gridBag);

    //Add first row of images
    cons.gridy = 0;
    cons.gridx = 0;
    for(int i = 0;i<NUMBER;i++){
      //Move grid if not first iteration
      if(i>0)
        cons.gridx = cons.gridx + 1;
      //Add Fork
      forks[i] = new JLabel();
      forks[i].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      gridBag.setConstraints(forks[i], cons);
      compPanel.add(forks[i]);

      cons.gridx = cons.gridx + 1;

      //Add Philosopher
      philosophers[i] = new JLabel();
      philosophers[i].setIcon(new ImageIcon("DiningPhilosophers/person1.jpg"));
      gridBag.setConstraints(philosophers[i], cons);
      compPanel.add(philosophers[i]);

      //Add last fork
      if(i==NUMBER-1){
        cons.gridx = cons.gridx + 1;
        forks[i+1] = new JLabel();
        forks[i+1].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
        gridBag.setConstraints(forks[i+1], cons);
        compPanel.add(forks[i+1]);
      }
    }  

    //Add table
    cons.gridx = 0;
    cons.gridy = 1;    
    cons.gridwidth = 3;  
    table = new JLabel();
    table.setIcon(new ImageIcon("DiningPhilosophers/table.jpg"));
    gridBag.setConstraints(table, cons);
    compPanel.add(table);
    cons.gridwidth = 2;  
    cons.gridx = cons.gridx + 3;
    for(int i=0;i<NUMBER-1;i++){      
      table = new JLabel();
      table.setIcon(new ImageIcon("DiningPhilosophers/table2.jpg"));
      gridBag.setConstraints(table, cons);
      compPanel.add(table);
      cons.gridx = cons.gridx + 2;
    }

    //Add averages section
    String[] titles = {"Total Meals = 0","Meals Per Second = 0","Eating Concurrently = 0"};
    cons.gridx = 0;
    cons.gridy = 2;
    cons.gridwidth = 4;  
    for(int i=0;i<3;i++){
      averages[i] = new JLabel();
      averages[i].setText(titles[i]);
      averages[i].setFont(new Font("Serif",Font.PLAIN, 20));
      gridBag.setConstraints(averages[i], cons);
      compPanel.add(averages[i]);
      cons.gridy = cons.gridy + 1;
    }

        //Display the window.
    frame.add(compPanel);
        frame.pack();
        frame.setVisible(true);
    } 

  private static void startAnimation(){  
    //Initialize variables
    for(int i=0;i<NUMBER;i++){
      forksArray[i] = 1;
      philosopherStatus[i] = 0;
      forksSem[i] = new Semaphore(1,true);
      philosophersBlock[i] = 0;
    }

    startTime = System.nanoTime();
    placesSem = new Semaphore(NUMBER-1,true);

    //Start controller thread
    controller = new Thread(new Controller());
    controller.start();

    //Create and start individual threads
    for(int i=0;i<NUMBER;i++){
      threads[i] = new Thread(new Philosopher(i));
      threads[i].start();
    }
  }

  /***********     MAIN   *****************/
  public static void main(String[] args){
    javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowFrame();
        startAnimation();
            }
        });
  }

  /*Class that represents a single philosopher*/
  private static class Philosopher implements Runnable{
    private int id;
    private int leftFork;
    private int rightFork;
    private int leftNeighbor;
    private int rightNeighbor;

    /* Choose the algorithm to run: getForks1(), getForks2(), etc. */
    public void run(){
      while(true){
        think();
        try{
          getForks3();
        }
        catch(Exception e){

        }
        eat();
        putForks3();
      }
    }

    /*Constructor*/
    public Philosopher(int id){
      this.id = id;
      this.rightFork = id;
      if(id==NUMBER - 1)
        this.leftFork = 0;
      else
        this.leftFork = id + 1;
      this.rightNeighbor = id - 1;
      if(id==0)
        this.rightNeighbor = NUMBER -1;
      this.leftNeighbor = (id + 1) % NUMBER;
    }

    public void think(){
      try{
        int sleepInterval = MIN_SLEEP + (int)(Math.random() * ((MAX_SLEEP - MIN_SLEEP) + 1));
        Thread.sleep(sleepInterval);
      }
      catch(Exception e){
        System.out.println(e);
      }
    }

    public void getForks1(){
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person2.jpg"));
      //Grab fork on the right
      while(forksArray[rightFork]==0);
      forksArray[rightFork] = 0;
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person3.jpg"));
      forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
      if(rightFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));      

      //Grab fork on the left
      while(forksArray[leftFork]==0);
      forksArray[leftFork] = 0;
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person5.jpg"));
      forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
      if(leftFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
    }/*end of getForks1()*/

    public void getForks2(){      
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person2.jpg"));
      if(id%2==0){
        //Grab fork on the right
        while(forksArray[rightFork]==0);          
        forksArray[rightFork] = 0;
        philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person3.jpg"));
        forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        if(rightFork==0)
          forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));      

        //Grab fork on the left
        while(forksArray[leftFork]==0);          
        forksArray[leftFork] = 0;
        philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person5.jpg"));
        forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        if(leftFork==0)
          forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
      }/*end of if*/

      else{
        //Grab fork on the left
        while(forksArray[leftFork]==0);
        forksArray[leftFork] = 0;
        philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person4.jpg"));
        forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        if(leftFork==0)
          forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));

        //Grab fork on the right
        while(forksArray[rightFork]==0);
        forksArray[rightFork] = 0;
        philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person5.jpg"));
        forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        if(rightFork==0)
          forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));            
      }/*end of else*/
    }/*end of getForks2()*/

    public void getForks3() throws InterruptedException{      
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person2.jpg"));
      if(id%2==0){
        //Grab fork on the right
        forksSem[rightFork].acquire();  
        forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        if(rightFork==0)
          forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));      
        philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person3.jpg"));              

        //Grab fork on the left
        forksSem[leftFork].acquire();
        forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        if(leftFork==0)
          forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person5.jpg"));

      }/*end of if*/

      else{
        //Grab fork on the left
        forksSem[leftFork].acquire();  
        forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        if(leftFork==0)
          forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person4.jpg"));

        //Grab fork on the right
        forksSem[rightFork].acquire();
        forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        if(rightFork==0)
          forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
        philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person5.jpg"));

      }/*end of else*/
    }/*end of getForks3()*/

    public void getForks4() throws InterruptedException{      
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person2.jpg"));

      placesSem.acquire();
      //Grab fork on the left
      forksSem[leftFork].acquire();
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person4.jpg"));
      forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
      if(leftFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));

      //Grab fork on the right
      forksSem[rightFork].acquire();
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person5.jpg"));
      forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
      if(rightFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));            

    }/*end of getForks4()*/

    public void getForks5() throws InterruptedException{      
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person2.jpg"));

      while(philosophersBlock[id]!=0){
        ;
      }

      //Block neighbors
      philosophersBlock[leftNeighbor]++;
      philosophersBlock[rightNeighbor]++;

      //Ready to go, grab both forks
      forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
      if(leftFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person5.jpg"));
      forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));
      if(rightFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/nofork.jpg"));  

    }/*end of getForks5()*/

    public void eat(){
      meals++;
      philosopherStatus[id] = 1;
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person6.jpg"));
      int eatInterval = MIN_SLEEP + (int)(Math.random() * ((MAX_SLEEP - MIN_SLEEP) + 1));
      try{
        Thread.sleep(eatInterval);
      }
      catch(Exception e){
        System.out.println(e);
      }
    }

    /*works with getForks() 1 and 2*/
    public void putForks1(){
      philosopherStatus[id] = 0;
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person1.jpg"));
      forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      if(rightFork==0||leftFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      forksArray[leftFork] = 0;
      forksArray[rightFork] = 0;
    }

    public void putForks3(){
      philosopherStatus[id] = 0;
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person1.jpg"));      
      forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      if(rightFork==0||leftFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      forksSem[rightFork].release();  
      forksSem[leftFork].release();  
    }

    public void putForks4(){
      philosopherStatus[id] = 0;
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person1.jpg"));      
      forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      if(rightFork==0||leftFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      forksSem[rightFork].release();
      forksSem[leftFork].release();
      placesSem.release();
    }

    public void putForks5(){
      philosopherStatus[id] = 0;
      philosophers[id].setIcon(new ImageIcon("DiningPhilosophers/person1.jpg"));      

      forks[rightFork].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      forks[leftFork].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));
      if(rightFork==0||leftFork==0)
        forks[NUMBER].setIcon(new ImageIcon("DiningPhilosophers/fork.jpg"));

      //Unblock neighbors
      philosophersBlock[leftNeighbor]--;
      philosophersBlock[rightNeighbor]--;
    }

  }

  /*Thread that tracks the number of meals, time elapsed and concurrency level*/
  private static class Controller implements Runnable{
    public void run(){
      while(true){
        DecimalFormat df = new DecimalFormat("#.##");

        //Update total meals
        averages[0].setText("Total meals = "+meals);

        //Update meals per second
        long diff;
        currentTime = System.nanoTime();
        diff = currentTime - startTime;
        diff = diff / 1000000000;
        float mealSecond = (float)meals/diff;
        averages[1].setText("Meals Per Second = "+df.format(mealSecond));

        //Update concurrent meals
        int count = 0;
        for(int i=0;i<NUMBER;i++){
          if(philosopherStatus[i]==1)
            count++;
        }  
        samples++;      
        concurrent = concurrent + count;
        float avg = concurrent / samples;

        averages[2].setText("Eating Concurrently = "+df.format(avg));

        if(meals>1000){
          System.out.println("meals/second="+mealSecond+" concurrency="+avg);
        }

        try{
          Thread.sleep(1000);
        }
        catch(Exception e){

        }
      }
    }
  }
}

Leave a Reply

Your email address will not be published. Required fields are marked *