The Dining Philosopher problem

The dining philosopher problem is a classic synchronization problem demonstrating a large class of concurrency control problems.

It was initially formulated in 1965 by Edsger Dijkstra as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals. Soon after, Tony Hoare gave the problem its present formulation.

The dining philosopher problem states that five philosophers are sitting at a circular table, and they eat and think alternatively. There is a bowl of rice for each philosopher and five chopsticks. A philosopher needs both their right and left chopstick to eat. A hungry philosopher may only eat if there are both chopsticks available. Otherwise, a philosopher puts down their chopstick and begins thinking again.

We are going to find a solution to this problem using Semaphores. So before that, we want to know about some keywords.

Semaphore:

A semaphore is a variable or abstract data type used to control access to a shared resource by multiple processes in a concurrent system such as a multitasking operating system.

Semaphores can be used to solve the critical section problem by using two atomic operations, wait and signal, used for process synchronization.

Wait:

The wait operation decrements the value of its argument s if it is positive. If s is negative or zero, then no operation is performed.

sem_wait(Semaphore s){
    while(s<=0);
    s--;
}

Signal:

The signal operation increments the value of its argument S.

sem_post(Semaphore s){
    s++;
}

To implement process synchronization both operations are used as below code.

Semaphore s=new Semaphore(1) // initialize the semaphore variable
to 1
sem_wait(s);
//Critical Section here
sem_post(s);

Initially, the value of the semaphore variable is 1. When a thread starts running first it runs the sem_wait and decrements the value of s if it is greater than 0 and runs the critical section. After running that section sem_post increment the s value to 1.

If a thread has already running variable s becomes 0. Therefore another thread can’t access the critical section unit the current thread ends. New thread sleep until the s variable becomes 1 after running the sem_post.

ok, now we move on to the solution for The Dining Philosophers problem.

Algorithm of solution:

repeat
 
  wait(chopstick[i]);wait(chopstick[(i+1) mod 5]);
  . . .
  eat
  . . .
  signal(chopstick[i]);
  signal(chopstick[(i+1) mod 5]);
  . . .
  think
  . . .
 
until false;

Code:

class Philosopher implements Runnable {
    private int id;
    private int amount=0;
    // The chopsticks this philosopher may use
    private Semaphore leftChopstick;
    private Semaphore rightChopstick;
    
    public Philosopher(int id, Semaphore leftChopstick, Semaphore 	rightChopstick) {
        this.id = id;
        this.leftChopstick = leftChopstick;
        this.rightChopstick = rightChopstick;
    }
    public void run() {
     	//...
     }
private void think() throws InterruptedException {
    System.out.println("Philosopher " + id + " is thinking.\n");
    System.out.flush();
    Thread.sleep(new Random().nextInt(10));
}
private void pickUpLeftChopstick() throws InterruptedException{
    if(leftChopstick.availablePermits() ==0){
        System.out.println("Philosopher " +id +" is waiting for left  chopstick");
    }
    leftChopstick.acquire();
    System.out.println("Philosopher " + id + " is holding  left  chopstick.\n");
    System.out.flush();
}
private void pickUpRightChopstick()  throws InterruptedException{
    if(rightChopstick.availablePermits() ==0){
        System.out.println("Philosopher " +id +" is waiting for right chopstick");
    }
    rightChopstick.acquire();
    System.out.println("Philosopher " + id + " is holding  right   chopstick.\n");
    System.out.flush();
}
Release the locks for chopsticks in the putDownChopstick method
private void putDownChopsticks() {
    leftChopstick.release();
    rightChopstick.release();
    System.out.println("Philosopher " + id +  " ate "+amount+"% and"+" released left and right sticks \n");
}
private void eat() throws InterruptedException {
    System.out.println("Philosopher " + id + " is eating.\n");
    System.out.flush();
    amount+=20;
    Thread.sleep(new Random().nextInt(10));
}
}

Initially, all the semaphore variable values are equal to 1. When the semaphore variable is 1 philosopher can take the chopstick. Then lock the chopstick by acquiring the method in semaphore class. That lock can be removed by calling the method release in Semaphore class

If the semaphore variable is 0 philosopher can not take the chopstick, so the process will wait for a stick.

public class DiningProblem {    
    private static final int n = 5;
    public static void main(String[] args) {
        
        Semaphore[] chopsticks = new Semaphore[n];
        for (int i = 0; i < n; i++) {
            chopsticks[i] = new Semaphore(1);
        }
       
        Philosopher[] philosophers = new Philosopher[n];
        for (int i = 0; i < n; i++) {
            philosophers[i] = new Philosopher(i, chopsticks[i], chopsticks[(i + 1) % n]);
            new Thread(philosophers[i]).start();
        }
    }
}

n is the number of philosophers. In the primary method make an array of semaphore variables for each thread and initialize all of them to 1. Then make an array of philosophers and initialize with the id, chopstick at the left, chopstick at the right. Start running each philosopher thread class.

The GIT link of the code is below here:

selvak7/The-Dining-Philosophers-problem