Dining Philosophers Problem Solution With Example

The Dining Philosopher problem is a synchronization problem. It is used to check situations where there is a need of allocating multiple resources to multiple resources.

Dining Philosophers Problem Statement

There is a dining room containing a circular table with K chairs. Corresponding to each chair, there is a plate. Between each plate, there is a single chopstick. In the middle of the table, there is a bowl of noodles. There are k philosophers sitting on each chair on a circular dining table. A chopstick can be used by one philosopher at a time. These philosophers spend their lives alternating between two activities – eating and thinking.
When it is time for a philosopher to eat, it must first acquire two chopsticks one from their left and one from their right. When a philosopher wants to think, he keeps down both chopstick at their original place.

Tutorialwing operating system Dining Philosophers Problem solution with example

Dining Philosophers Problem

In this example, we are assuming that there is only five chair. So, there is only five philosophers sitting on each chair. They can either think or eat.

Solution of the Dining Philosophers Problem

Since a philosopher can either think or eat, it is clear that a philosopher can think for indefinite amount of time. But, it can eat for only a limited amount of time. Also, Other philosophers must not starve. Thus, the philosopher is in an endless cycle of eating and thinking.

Thus, each philosopher is represented by the following pseudocode:

  wait(chopstick[(i+1)% 5]) ;

  signal(chopstick[(i+1)% 5]); 

Here, we have assumed that there is only five philosophers on the dining table. There is an array of five semaphores – chopstick[5] that represents each of the five chopsticks.

Philosopher may PICKUP and PUTDOWN their chopsticks in either order or nondeterministic ally, but these are atomic actions. Two philosophers can’t use single chopstick at the same time.

A case may arise when all the philosophers are hungry at the same time and each of them pick one chopstick. A deadlock will occur in this case because all the philosophers will wait for another chopstick forever.

This deadlock can be avoided using either of below solutions –

  • Allow only four philosophers to sit on the dining table. If the four philosophers pickup four chopstick, so one free chopstick will be always there. Thus, one philosopher can start eating because two chopsticks will be available. In this way, deadlock can be avoided.
  • A philosopher must be allowed to pick up the chopstick when both left and right chopsticks are available.

That’s end of tutorial on Dining Philosophers Problem Solution.

Leave a Reply