The Dining Philosopher’s Problem

Digital Anna
Oct 23, 2020 · 4 min read

The dining philosopher’s problem is a very well known resource sharing problem in the world of computers.

The problem says:

Dining philosopher problem
Dining philosopher problem

There are 5 philosophers sitting around a round table eating spaghetti and each of them has one chopstick between them. All 5 of them sit around the table and pick up the chopstick placed towards their right. But, here’s the problem. To eat the spaghetti they need both the chopsticks and since everyone picked up the chopstick to their right, nobody gets the left chopstick and hence, nobody can eat.

Logically thinking, this problem isn’t really a problem in real life scenario. The philosophers could have asked for a few extra pairs of chopsticks, or they could have eaten using their hands 😂 .

Jokes apart, but the dining philosophers problem is an excellent example to explain the concept of deadlock while resource sharing in OS.

Consider the philosophers to be processes and the chopsticks to be a shared resource. Every process needs two resources out of which one it has already acquired and the other is acquired by some other process. Till the other process does not free the resource, this process cannot proceed. Similarly, the other process is dependent on another process for its resource. Since every process is dependent on each other, it forms a circular-wait and the system goes into a deadlock condition.

Here, when each philosopher picks up the chopstick to their right, they also end up picking the left chopstick of the person sitting next to them which leaves every philosopher with just one chopstick and nobody can start eating.

To solve this problem, we can use this strategy:

Consider five philosophers: P0,P1,P2,P3,P4 &

five chopsticks: C0,C1,C2,C3,C4

Initially we let P0 enter into the dining room.

Since nobody else is present there all the chopsticks are free and P0 acquires chopsticks C0 and C1 and starts eating.

Now, P1 enters the room. Since P0 is already eating, chopstick C1 is not available for P1 and hence P1 cannot eat and is kept waiting.

PS : Since P1 does not get C1, it doesn’t claim C2.

Next, P2 enters the room. Since C2 and C3 both are available, P2 starts eating.

Next, P3 enters and is blocked and added to the waiting queue because C3 is not available.

Similarly P4 is blocked and is added to the waiting queue as C0 is not available

Now, consider P0 has finished eating and the resources claimed by it i.e. C0 and C1 are released. P1 cannot start eating since C2 is still not released and hence P4 starts eating since C4 and C0 both are released. Hence,

If now P2 releases the chopsticks C2 and C3, philosopher P1 can start eating

P3 has to stay in the waiting queue since chopstick C4 is not available.

Finally, consider that philosopher P4 has finished eating and has freed chopsticks C0 and C4, P3 can start eating.

This is the strategy using which we have ensured that all the philosophers have been served and avoided the circular wait situation.

This is the logic behind the solution of the dining philosophers problem.

Here is the C program designed to solve the problem:-

(I’ve used semaphores to solve this problem. For more information on semaphores, refer this website-)

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<semaphore.h>
#include<unistd.h>

sem_t room;
sem_t chopstick[5];

void * philosopher(void *);
void eat(int);
int main()
{
int i,a[5];
pthread_t tid[5];

sem_init(&room,0,4);

for(i=0;i<5;i++)
sem_init(&chopstick[i],0,1);

for(i=0;i<5;i++){
a[i]=i;
pthread_create(&tid[i],NULL,philosopher,(void *)&a[i]);
}
for(i=0;i<5;i++)
pthread_join(tid[i],NULL);
}

void * philosopher(void * num)
{
int phil=*(int *)num;

sem_wait(&room);
printf("\nPhilosopher %d has entered room",phil);
sem_wait(&chopstick[phil]);
sem_wait(&chopstick[(phil+1)%5]);

eat(phil);
sleep(2);
printf("\nPhilosopher %d has finished eating",phil);

sem_post(&chopstick[(phil+1)%5]);
sem_post(&chopstick[phil]);
sem_post(&room);
}

void eat(int phil)
{
printf("\nPhilosopher %d is eating",phil);
}
/* BY - ANUSHKA DESHPANDE */

To understand this program, refer my blog

Do let me know in the comments if this helps you.

Have a nice day!

The Startup

Get smarter at building your thing. Join The Startup’s +787K followers.

Sign up for Top 10 Stories

By The Startup

Get smarter at building your thing. Subscribe to receive The Startup's top 10 most read stories — delivered straight into your inbox, once a week. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +787K followers.

Digital Anna

Written by

Technology enthusiast, coder, designer

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +787K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store