In this post we are going to understand the C program implementing the solution to the Dining Philosopher Problem. The Dining Philosopher Problem states that there are five philosophers which do two thinks: think and eat. They share a table having a chair for each one of them. In the center of the table there is a bowl of rice and the table is laid with 5 single chopsticks (Refer Figure Below).
When a philosopher thinks, he does not interact with others. When he gets hungry, he tries to pick up the two chopsticks that are near to him. For example, philosopher 1 will try to pick chopsticks 1 and 2. But the philosopher can pickup only one chopstick at a time. He can not take a chopstick that is already in the hands of his neighbour. The philosopher stars to eat when he has both his chopsticks in his hand. After eating the philosopher puts down both the chopsticks and starts to think again.
Solution to Dining Philosopher Problem
Represent each chopstick with a semaphore. Each philosopher first picks up the left chopstick and then the right chopstick using the wait() operation each semaphore. After eating he puts down the chopsticks by using the signal() operation on each chopstick.
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<semaphore.h>
#include<unistd.h>
sem_t chopstick[5];
void * philos(void *);
void eat(int);
int main()
{
int i,n[5];
pthread_t T[5];
for(i=0;i<5;i++)
sem_init(&chopstick[i],0,1);
for(i=0;i<5;i++){
n[i]=i;
pthread_create(&T[i],NULL,philos,(void *)&n[i]);
}
for(i=0;i<5;i++)
pthread_join(T[i],NULL);
}
void * philos(void * n)
{
int ph=*(int *)n;
printf("Philosopher %d wants to eat\n",ph);
printf("Philosopher %d tries to pick left chopstick\n",ph);
sem_wait(&chopstick[ph]);
printf("Philosopher %d picks the left chopstick\n",ph);
printf("Philosopher %d tries to pick the right chopstick\n",ph);
sem_wait(&chopstick[(ph+1)%5]);
printf("Philosopher %d picks the right chopstick\n",ph);
eat(ph);
sleep(2);
printf("Philosopher %d has finished eating\n",ph);
sem_post(&chopstick[(ph+1)%5]);
printf("Philosopher %d leaves the right chopstick\n",ph);
sem_post(&chopstick[ph]);
printf("Philosopher %d leaves the left chopstick\n",ph);
}
void eat(int ph)
{
printf("Philosopher %d begins to eat\n",ph);
}
How it works?
Now let us understand how the code works
#include<stdio.h> #include<stdlib.h> #include<pthread.h> #include<semaphore.h> #include<unistd.h> sem_t chopstick[5]; void * philos(void *); void eat(int);
sem_t chopstick[5] is used to declare 5 semaphore variable, one for each of the five chopsticks. Next, two are the prototypes for functions defined below. In the main() function there are three for loops. The first loop is used to initialize each semaphore variable with initial value to 1. The second for loop is used to create five threads which will act as the five philosophers. The third for loop uses the pthread_join function which makes the parent program wait for each of the thread to finish.
Next is the philos function. The philos function when called by each thread receives the same value as the thread number. For example if thread one runs, the variable ph in the philos function is assigned the value n. This is done because each philosopher n before eating will pick two chopstick, n and (n+1)%5. Next, the sem_wait function is used on the left chopstick first
sem_wait(&chopstick[ph]);
If successful, the thread executes the sem_wait function on the right chopstick
sem_wait(&chopstick[(ph+1)%5]);
These two operations are equivalent to picking the left chopstick and then the right chopstick. If both these operations are successful this means that the philosopher is able to pick both the chopsticks and hence will start to eat by calling the eat() function. After eating both the chopsticks are release by using the sem_post() function.
Output
Here’s a sample output. Your output might differ each type you run the program. This is because the sequence of execution of threads will be different. Try to understand the output below and then relate it with what you get.
Here philosopher(thread) 0 tries to eat first. So, it tries to pick the left chopstick, which it does. Then the right one. Since it picks both the chopstick so philosopher 0 starts to eat. Now, refer to the image at the beginning of the post. If philosopher 0 starts to eat this means chopstick 0 and 1 are busy hence, philosopher 1 and 4 can not eat until philosopher 0 puts down the chopsticks. Read the output now, next philosopher wants to eat. It tries to pick the left chopstick (i.e. chopstick 1) but is not successful because chopstick 1 is already with philosopher 0. Similarly, you can understand the rest of the output.
Video Link
Viva Questions on Program on Dining Philosopher Problem
Q1. Which function is used to create the threads?
Q2. What is the use of sem_init() function?
Q3. Why is the sem_wait() function used twice in the philos function?