What is the Dining Philosophers Problem?

Introduction to the problem

The Dining Philosophers Problem was first given by Edsger Dijkstra in 1965. This problem is faced by 5 philosophers sitting around a circular table. These philosophers can only eat if they have both left and right chopsticks; otherwise, they will sit and think (without eating) until they starve.

Below, is the figure that describes how the problem looks:

Dining Philosophers Problem

Let’s understand by thinking of an example.

Suppose that there is a bowl of noodles kept on a circular table and there are 5 people sitting around it. This means that there will be a total of 5 plates and 5 chopsticks. If any person wants to eat noodles they can only eat them by using both left and right chopsticks. So, while one person is eating, the neighbors to their immediate left and right will have to wait, think, and starve as well.

The Dining Philosophers Problem is used to design a scheduling technique such that no philosopher will starve.

Solution to the problem

One way to solve the problem is by using Semaphores.

A Semaphore is a tool used for concurrent processes that works by assigning an integer value. The two functions that are operated using semaphore are wait() and signal().

Take a look at the solution:

void Philosopher  
{
  while(1)  
  {  
    wait(take_chopstick[x]);  
    wait(take_chopstick[(x + 1) % 5]) ;  
    
    //  EATING THE NOODLE  
 
    signal(put_chopstick[x]);  
    signal(put_chopstick[(x + 1) % 5]) ;  
 
    // THINKING
  }  
}
Solution using Semaphore

Explanation:

  • The above code suggests that the wait() operation is first performed where take_chopstick[x] and take_chopstick[(x+1) % 5] are executed. This corresponds to the philosopher picking up both the left and the right chopsticks and then starting to eat while the others wait and think until their turn comes.
  • After eating, the signal() operation is performed where put_chopstick[x] and put_chopstick[(x+1) % 5] are executed. This means that the philosopher has eaten, after which the philosopher puts down the chopstick and starts to think again.

This is the solution to the problem, but it has some drawbacks as it will create a deadlock. For example, when all the philosophers pick up the left chopstick and then have to wait for the right one – this will create a deadlock situation.

To avoid this deadlock, some measures that could have been taken are:

  • There could be, at most, 4 people at the table.
  • The philosophers can alternatively eat and think. For example, if the first philosopher is eating, then the second should wait and think while the third eats, and so on.
Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
YouTubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)