Dining philosophers in java using semaphores

Question

I want to solve dining philosophers problem using java semaphores but I'm stuck. Highest id chopstick should be available but it seems to be always taken and i don't know why. Can anyone tell me where I made mistake?

Fork class:

class Fork {
public static Semaphore fork = new Semaphore(1);
public int id;

Fork(int id) {
    this.id = id;
}

public int getId() {
    return id;
}

public boolean take() {
    return fork.tryAcquire();
}

public void putDown() {
    fork.release();
}}

Philosopher class:

class Philosopher extends Thread {

private Fork fork_low;
private Fork fork_high;
private String name;

Philosopher(Fork fork_low, Fork fork_high, String name) {
    this.fork_low = fork_low;
    this.fork_high = fork_high;
    this.name = name;
}

public void run() {

    try {
        sleep(1000);
    } catch (InterruptedException ex) {
    }

    while (true) {
        eat();
    }
}

private void eat(){
    if(fork_low.take()){
        if(fork_high.take()){
            try {
                sleep(2000); // eating;
            } catch (InterruptedException ex) { }

            fork_high.putDown();
            fork_low.putDown();  

        }
        else{
            fork_low.putDown();
        }
    }
}}

Main:

public static void main(String[] args) {
    String[] names = {"Plato", "Aristotle", "Cicero", "Confucius", "Eratosthenes"};
    Fork[] fork = new Fork[5];
    Philosopher[] philosopher = new Philosopher[5];

    for (int i = 0; i < fork.length; i++) {
        fork[i] = new Fork(i);
    }

    for (int i = 0; i < philosopher.length; i++) {

        if (i != philosopher.length - 1) {
            philosopher[i] = new Philosopher(fork[i], fork[i+1], names[i]);
            philosopher[i].start();
        } else {
            philosopher[i] = new Philosopher(fork[0], fork[i], names[i]);
            philosopher[i].start();
        }
    }
}

Answer 1

Here is the same problem solved in C language with explaination

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>  
//if not used then gives warning for sleep used

//semaphore are basically designed to share the resources
// here the sem_t is the data type for the semaphore
sem_t room;//counting semaphore bcoz here only one instance of room butchair has 4
sem_t spoon[5]; //this is binary semaphore since every spoon has its own instance


void * philosopher(void *);
void eat(int);
int main()
{
int i;
int a[5];
pthread_t tid[5];// threads here are refrence to philosophers or diners bcoz we will have multiple users dining
                  
sem_init(&room,0,4);  
//1.pointer to declared semaphore
//2.pshared which has 0,1 value that is if 0 ->shared between threads                        
//                                      if 1 ->shared between process
//3.value with whch u initalise the semaphore
for(i=0;i<5;i++){
    //5 binary semaphore each for individual spoon
    sem_init(&spoon[i],0,1);
}

for(i=0;i<5;i++){
    a[i]=i;//allow 5 to enter at a time and deadlock occurs so let 4 of them in
    pthread_create(&tid[i],NULL,philosopher,(void*)&a[i]);
  //1.thread id 2.NULL 3.function 4.what you want to pass to the new thread   
  //here we pass the address of philosophers number to function
}

for(i=0;i<5;i++){
    pthread_join(tid[i],NULL);
}
}

void * philosopher(void * num){
int phil=*(int *)num; //cast the number passed as void to integer
//put sem_wait on both semaphore room and spoon
sem_wait(&room);//checks if resource is available,if then allocates and blocks semaphore
// room is counting semaphore so any is alocated then it decrements the count of total semaphore and 
// if all are allocated then it blocks thread and places it on queue untill resource is freed
printf("\nPhilospher number %d has sat on dining table\n",phil);
  
  sem_wait(&spoon[phil]);
  sem_wait(&spoon[(phil+1)%5]);
  //spoon is binary so if value of semaphore is 1 it is changed to 0 which means semaphore is allocated and cannot be used
  
  eat(phil);
  sleep(2);
  printf("\nPhilosopher %d has finished eating\n",phil);
  //free the semaphores so others in thread can use resources
  //returns +ve value on freeing semaphore
  //for binary semaphore if queue is empty then change semaphore value to 1 if not empty then remove process from queue and 
  // get it ready for allocation
  sem_post(&spoon[(phil+1)%5]);
  sem_post(&spoon[phil]);
  sem_post(&room);
}   

void eat(int phil){
  printf("\nPhilosopher %d is eating now\n",phil);
}

Answer 2

You have a deadlock, because the Semaphore is static in the Fork class, which is equivalent to only have one fork available. It works perfectly when you make the Semaphore not static (2 random philosophers running on the same time).

You can observe your threads working in JDK's build in tool jvisualvm.