Dining Philosopher’s Problem in Java Multithreading

Dining Philosopher’s Problem is one of the problem classic problems of multi threading and thread synchronization. 

Statement and Explanation

Here we have five philosophers sitting around a dining table which has five plates and five forks as shown in the image below. All they do is thinking and eating.

Here forks are the shared objects. Each fork is shared between two philosophers.

They will be thinking when they do not have access to both the forks. When they get both forks, they will eat. Our task is to synchronise this sharing of forks so that circular wait do not happens. In circular wait, every philosopher gets a fork and will be waiting for another fork which is acquired by another philosopher.

If this happens, no one gets to eat and will be waiting indefinitely.

Here we need to create five threads, one for each philosopher. Also, we need to create five fork objects.

 For each philosopher, we give two shared fork objects. Everyone gets the forks in the order of left first and right next except last philosopher. 

what’s the reason might be?

	public class DCControl {
	public static void main(String[] args) {
	Philosopher[] philosophers = new Philosopher[5];
	Object[] forks = new Object[philosophers.length];
	for (int i = 0; i < forks.length; i++) {
	forks[i] = new Object();
	}
	for (int i = 0; i < philosophers.length; i++) {
	Object leftFork = forks[i];
	Object rightFork = forks[(i + 1) % forks.length];
	if (i == philosophers.length - 1) {
	philosophers[i] = new Philosopher(rightFork, leftFork);
	} else {
	philosophers[i] = new Philosopher(leftFork, rightFork);
	}
	Thread thread = new Thread(philosophers[i], "Philosopher " + (i + 1));
	thread.start();
	}
	}
	}

view raw DCControl.java hosted with ❤ by GitHub

The reason is a circular wait condition might arise if forks given in Left first right next order. I recommend to experiment and try it out. 

The main logic is initially every philosopher will be thinking for a random amount of time. This will make someone to get a kick start instead of following the same order every time.

Here we are using synchronised block to get the access to monitor. In the previous examples we have used synchronised method.

 Here, the philosopher acquires left fork first and then right fork next and when he finishes eating, he will relieve the access in the reverse order.

	class Philosopher implements Runnable {
	private Object leftFork;
	private Object rightFork;
	public Philosopher(Object leftFork, Object rightFork) {
	this.leftFork = leftFork;
	this.rightFork = rightFork;
	}
	@Override
	public void run() {
	try {
	while (true) {
	doAction("Thinking");
	synchronized (leftFork) {
	doAction("Picked up left fork");
	synchronized (rightFork) {
	doAction("Picked up right fork-eating");
	doAction("Put down right fork");
	}
	doAction("Put down left fork");
	}
	}
	} catch (InterruptedException e) {
	e.printStackTrace();
	}
	}
	private void doAction(String action) throws InterruptedException {
	System.out.println(
	Thread.currentThread().getName() + " " + action);
	Thread.sleep(((int) (Math.random() * 3000)));
	}
	}

view raw Philosopher.java hosted with ❤ by GitHub

The same will go on indefinitely. Do experiment with the code and reason the random sleep time.

Output

The output looks something like this.

Resources

• Java Concurrency in Practice