Dining Philosophers Algorithm

I have written this program to solve this problem by Arbitrator solution algorithm, mentioned here, to solve this. It states that each philosopher should ask permission from Waiter to get the Fork. Philosopher cannot start eating until he has both the forks. I have implemented logic that he should either hold both forks or put down if holds only one fork.

I need this code to be reviewed by you all about any suggestions regarding coding practice, improvements, possible bugs or alternate solutions.

DiningAlgorithm

package com.study.fundamentals.util;
    /**
     * This is starting point for the dining algorithm
     */
    public class DiningAlgorithm {

    public static void main(String[] args) {
        Thread thread1= new Thread(new Philosopher());
        Thread thread2= new Thread(new Philosopher());
        Thread thread3= new Thread(new Philosopher());
        Thread thread4= new Thread(new Philosopher());
        Thread thread5= new Thread(new Philosopher());
        thread1.start(); 
        thread2.start();
        thread3.start();
        thread4.start();
        thread5.start();
     }
    }

Philosopher

```
package com.study.fundamentals.util;
public class Philosopher implements Runnable{
private static final int TIME_WHEN_PHILOSOPHER_FEELS_HUNGRY_AGAIN = 10;
private static final int TIME_REQUIRED_TO_EAT = 5;
private static int noOfPhilosophers =0;
private int id;
private Waiter waiter = new Waiter();
private Fork leftFork;
private Fork rightFork;
public Philosopher() {
this.id=noOfPhilosophers;
noOfPhilosophers++;
}
private void pickUpLeftFork(){
if(null==leftFork){
leftFork = waiter.getForkOnLeft(id);
}
}
private void pickUpRightFork(){
if(null==rightFork){
rightFork = waiter.getForkOnRight(id);
}
}

private void eat() throws InterruptedException{

pickUpLeftFork();
pickUpRightFork();

In the end your code does not solve the problem because of thread contention and synchronization (see below) and thus ultimately fails.

But you also do not address the real issue at the heart of this problem. How do you design a method to make resource resolution better?

At the moment all 5 philosophers will grab the fork on their left when they go to get the fork on the right it is now already held by another philosopher. So immediately you have 5 contentions. The idea is to design a system were you minimize the number of contentions.

Also why do you pick up the right fork when you don't have the left. To be bloody minded and say if I can't have both forks I may as well have at least one and try and prevent the others from eating. The whole point is not to be greedy. It should be designed so that the philosophers as a group get as much pasta as they can eat combined (without any particular philosopher starving).

I would prefer it to look like this:

private void eat() throws InterruptedException
{
    // Only bother to try the right fork if the left succeeds.
    if (pickUpLeftFork() && pickUpRightFork())
    {
        System.out.println("both forks "+leftFork.getID() +
                           " & "+rightFork.getID()+
                           " are available for use for Philosopher "+id);
        eat(TIME_REQUIRED_TO_EAT);
    }

    putDownBothForks();
}

Code Review

If each Philosopher has his/her own waiter then there will never be any contention (as each waiter independently has 5 forks).

private Waiter waiter = new  Waiter();

What you really need is a shared waiter (or I would call it a table). The controls the shared resources. So Philosopher N can use fork N and ((N+1)%MaxForks).

Also there is no syncronization on the Waiter so between the test and the get another thread can easily steel the fork.

private Fork getFork(int forkId) {

    if(canUseFork(forkId)){           // Philosopher 1 tests and sees a fork.
       map.get(forkId).useFork();     // But before 1 can get the fork.
                                      // his thread is de-sheduled and Philosopher 2
                                      // tests and gets the fork.
                                      // Thus leaving them both using the fork.
       return map.get(forkId);
    }
    return null;
}

StackExchange Code Review Q#61644, answer score: 11