# 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) {
}
}


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();
if(bothForksAvailable()){
System.out.println("both forks "+leftFork.getID() +" & "+rightFork.getID()+" are available for use for Philosopher "+id);
eat(TIME_REQUIRED_TO_EAT);
}

putDownBothForks();
}
private void putDownBothForks() {
if(null!=rightFork) {
rightFork.putDownFork();
}
if(null!=leftFork){
leftFork.putDownFork();
}
leftFork = null;
rightFork =null;
}
private void eat(long miliseconds) throws InterruptedException {
System.out.println(id+" has started eating");
eatFor(miliseconds);
System.out.println(id+" has finished eating");
}
private void eatFor(long miliseconds) throws InterruptedException {
waitFor(miliseconds);
}

private void waitTillHeFeelsHungry() throws InterruptedException {
waitFor(TIME_WHEN_PHILOSOPHER_FEELS_HUNGRY_AGAIN);
}

private void waitFor(long milliseconds) throws InterruptedException {
}

public boolean bothForksAvailable(){
return null!=leftFork && null!= rightFork;
}
@Override
public void run() {
System.out.println("Thread for philosopher "+id +" started");
while(true){
try {
eat();
waitTillHeFeelsHungry();
} catch (InterruptedException e) {
System.out.println("Interrupted Exception Occured, Reason "+e.getMessage());
}
}

}
}


Waiter

package com.study.fundamentals.util;
import java.util.HashMap;
import java.util.Map;

public class Waiter {
private static Map <Integer,Fork> map = new HashMap<Integer,Fork>(){{
put(1,new Fork(1));
put(2,new Fork(2));
put(3,new Fork(3));
put(4,new Fork(4));
put(5,new Fork(5));
}};

private boolean canUseFork(int forkId){
return !map.get(forkId).isBeingUsed();
}

public Fork getForkOnLeft(int philosopherId){
return getFork(philosopherId+1);
}

private Fork getFork(int forkId) {
if(canUseFork(forkId)){
map.get(forkId).useFork();
return map.get(forkId);
}
return null;
}

public Fork getForkOnRight(int philosopherId){
if(philosopherId==0){
return getFork(map.size());
}
else{
return getFork(philosopherId);
}
}
}


Fork

package com.study.fundamentals.util;
/**
* This is the resource which must be available for eating
*/
public class Fork {
int id;
boolean isBeingUsed ;
public Fork(int id){
this.id = id;
}

public boolean isBeingUsed(){
return isBeingUsed;
}

public void useFork(){
isBeingUsed = true;
}

public void putDownFork(){
isBeingUsed = false;
}

public int getID() {
return id;
}

}

-

## General Style

Coding Style

• Your spacing (for example this.id=noOfPhilosophers; vs leftFork = waiter.getForkOnLeft(id);, comparisons, etc.) as well as indentation (for example eat() and getFork()) is off quite often, which makes your code harder to read. Use any IDE to fix this easily.
• If you use this in the constructor, use it always (this.id=noOfPhilosophers; vs noOfPhilosophers++;)

Passing ids

I would prefer if you passed objects instead of ids in the Waiter methods, it seems cleaner to me than exposing ids.

private fields

Your Fork fields should be private.

Too many methods

In Philosopher, you have eat(), eat(long miliseconds), eatFor(long miliseconds), waitFor(long milliseconds). The eat() method makes a lot of sense, as does the waitFor method. But the other methods don't really do anything (except make the code harder to read).

use of static

Your use of the static keyword in the Waiter class (as well as the Philosopher class) is somewhat confusing (it's easy to overlook), and limiting. I would go with a different approach as @Loki Astari suggested.

## Implementation of Arbitrator solution

You are not actually implementing the Arbitrator solution as described by Wikipedia.

Another approach is to guarantee that a philosopher can only pick up both forks or none by introducing an arbitrator

What you are actually doing:

• pick up left fork
• pick up right fork
• eat if you can, otherwise don't
• put forks down

Nothing of this is synchronized, and you are not guaranteeing that a philosper can only pick up both forks.

if a philosopher is eating and one of his neighbors is requesting the forks, all other philosophers must wait until this request has been fulfilled even if forks for them are still available.

You are not doing this either. Whenever a philosopher asks for a fork (and it is available), the waiter will give him a fork.

Each fork can either be dirty or clean

You do not have this state.

And so on.

Basically, you do prevent deadlock, but your code is still open to livelock as well as starvation.

-
Thanks Tim for deep analysis.... I must admit that starvation could occure here... Will improve the code and repost it .. Just to bring to your notice that philosopher will try pickup left and right forks . but it will not start eating until both are available ... And if anyone is not available he will release the other one he is holding. – Shree Aug 31 '14 at 20:25
Isn't starvation part of the core problem, and a legitimately possible outcome? – RubberDuck Aug 31 '14 at 21:13
@RubberDuck well, yes, starvation is part of the problem. But it should not be a possible outcome. That's one of the main points. The Dining Philosophers Problem is meant to teach how to avoid deadlock, starvation and livelock. From the Wikipedia description of the solution which Shree tried to implement: It also solves the starvation problem – tim Aug 31 '14 at 21:17

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;
}

-
1. all waiters will refere to only one map which holds 5 forks , see that I have declared the map as static there private static Map <Integer,Fork> map 2. That is why logic added that if philosopher either philosopher will have both forks to be used or none – Shree Aug 31 '14 at 19:40
OK. I see that now. Would be easier to have a table with 5 forks. Then assign 5 philosophers to a table. Now you can have multiple tables in your restaurant. The current design only allows one group of 5 which is a bit limiting. – Loki Astari Aug 31 '14 at 19:42
yes whatever you said can be a new features which can be added. But the original problem talks about one Table only – Shree Aug 31 '14 at 19:53
@Shree: You asked for a code review. Not how to solve the problem. I am telling you why your design is bad. Hopefully you will take the advice and write a better solution. – Loki Astari Aug 31 '14 at 20:04
Thanks for alternate design approach/improvements you have suggested.. .Its nothing that I didn't wanted to consider these reviews.Rather these are valuable inputs to me. I was just trying to tell the intent of the code written – Shree Aug 31 '14 at 20:28

### Encapsulation

When you pass ids of objects around as method parameters, that's a sign that you're not using encapsulation correctly. Object ids are implementation details that should be hidden within a class. A Waiter class should not have knowledge about "fork ids" and "philosopher ids", which are internal implementation details of the Fork and Philosopher classes.

### Naming and logic

In the current implementation a Philospher does this in a loop:

1. eat
2. waitTillHeFeelsHungry

Technically, he doesn't eat just yet. He tries to eat, if the waiter lets him. So tryToEat would be a better name.

And since waitTillHeFeelsHungry is a method of a Philosopher, and not a NuttyPhilosopher, so he shouldn't refer to himself in the 3rd person, so waitUntilHungry would be a better name.

Then in eat, he calls pickUpLeftFork and then pickUpRightFork. Again that's not really how it works, he has to ask permission for the forks. So this kind of naming and design would be better:

if (waiter.provideLeftFork(this) && waiter.provideRightFork(this)) {
// ...
eat(TIME_REQUIRED_TO_EAT);  // this time, for real
waiter.thankYouItWasDelicious(this);  // signal that the forks are available
}


Which solves another issue: if the Philosopher couldn't get the left fork, he should not ask for the right, there's just no point, unless he wants to starve his fellow Philosopher at his right in a race condition.

Also, the Philosopher should not be bothered to manage the states of Forks. He can ask for them, use them, and return them, he shouldn't need to know what makes them tick.

### Hardcoding

The fact that there are 5 philosophers and 5 forks are hardcoded independently in two places: in DiningAlgorithm.main, and in the static initialization of Waiter. It can be forgivable to hardcode 5, but at least you should make sure somehow that if somebody changes the code to add one Philosopher, then a Fork should be automatically added too.

### Single responsibility principle

Counting unique IDs in the Philosopher class violates the single responsibility principle: in addition to eating, a Philosopher must also count. What an outrage ;-) You could use a PhilosopherFactory to be in charge of creating Philosophers with unique IDs.

### Repetition

Thread thread1= new Thread(new Philosopher());


This would be better:

for (int i = 0; i < 5; ++i) {

@janos but the Philosopher constructor doesn't need to be thread save, does it? (I agree though that philosophers should not count.) – tim Aug 31 '14 at 20:57