Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

communitycreator
operating system

What is the Dining Philosophers Problem?

Harsh Jain

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code

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 deadlockwhen a process stops. 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.

RELATED TAGS

communitycreator
operating system

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code
Keep Exploring