Dinning Philosopher Problem

The dinning philosopher problem,invented by Edster Dijkster is the classic demonstration of deadlock. The Dinning Philosopher problem used to describe synchronization issues in a multi-threaded environment and illustrate techniques for solving them.

The basic description specifies five philosophers(or any number) sitting around around a circle table ,spending time eating and thinking. There are only five forks for them(for five philosophers) on the table between plates. A philosopher needs to have forks in both his hands to be able to eat. After eating he puts both of them down think for a while and forks can be picked by another who repeats the same procedure.

NOTE

Imagine that all the philosophers pick their right side(same side) fork at the same time, then all of them will have only one fork on their hands . They will not be able to eat anymore. This is what we call as a Dead Lock. Our goal is to come up with a solution that helps the philosophers achieve their goal of eating and thinking without getting starved to death.

We are going to find solution to this problem using Semaphore

Semaphore:

Semaphore is an abstract data type or a variable used to control access to a common resources by multiple processes in a concurrent system such as a multitasking operating system. This concept is used to solve critical section problem by using two atomic operations.

Wait and Signal that are used for process synchronization.

Solution:

In this solution, each of the philosophers follow the following protocol:

While(the conditions is true) {

• Think…
• pick up left fork()(Think until the right one is available)
• pick up right fork ()
• eat() for a fixed amount of time
• put down right fork()
• put down left fork()
• back to the thinking…

}

Implementation

we model each of our philosophers as classes that implement the Runnable interface so that we can run them as separate threads. All of them have the access to both forks on his left and right.

Also, there is another method that instructs a philosopher to perform his preferred action:

• Eat, think , getting forks to eat

The execution order is not enforced by time alone.

To simulate acquiring a fork, we need to lock it so that no two philosopher threads acquire it at the same time.We use the synchronized keyword to acquire the internal monitor of the fork object and prevent other threads from doing the same to achieve this.

This is done in run() method in Philosopher class.

• A philosopher think for a while and then decides to eat. timestamps were added to each action, in order to understand the order in which event occur.

To operate the whole process, we write a Main method that creates 5 philosophers (or any number of philosophers) as threads and start all of them:

The output of this program :

Running this code results in an output similar to the following. Your output will most likely differ because of the sleep() method invoked for a different interval

Resolving the Deadlock

A deadlock is a situation where the progress of a system is halted as each process is waiting to acquire a resource held by some other process.

if(j == philosophers.length - 1){
    //The last philosopher picks up the right fork first
    philosophers[j] = new Philosopher(rightFrk, leftFork);
}else{
    philosophers[j] = new Philosopher(leftFork, rightFrk);
}

Above code is used in the Main Method to avoid the deadlock. We have mentioned what deadlock is in a previous paragraph in this article.

It can be verified by running the code several times, that the system is free from the deadlock situation that occurred before.

philosopher reach for his right fork first, instead of the left. This breaks the circular wait condition and we can avert the deadlock.

You all can clone and download my code:

https://github.com/mihinduranasinghe/DinningPhilosopherProblem

Hope you all enjoyed and learned something on this. Please let me know your comments suggestions and any questions you have about this blog.

👉 Visit me - https://mihinduranasinghe.com/