The dining philosophers problem

                                                  

There are some Philosophers whose work is just thinking and eating. Let there are 5 (for example) philosophers. They sat at a round table for dinner. To complete dinner each must need two Forks (spoons). But there are only 5 Forks available (Forks always equal to no. of Philosophers) on table. They take in such a manner that, first take left Fork and next right Fork. But problem is they try to take at same time. Since they are trying at same time, Fork 1, 2, 3, 4, 5 taken by Philosopher 1, 2, 3, 4, 5 respectively (since they are left side of each). And each one tries to ta ke right side Fork. But no one found available Fork. And also that each one thinks that someone will release the Fork and then I can eat. This continuous waiting leads to Dead Lock situation

Solution: To solve this Dead Lock situation, Last philosopher (any one can do this) first try to take right side fork and then left side fork. i.e in our example 5th person tries to take 4th Fork instead of 5th one. Since 4th Fork already taken by 4th the person, he gets nothing. But he left 5th Fork. Now the first person will take this 5th Fork and complete dinner and make 1st and 5th available for remaining people. Next 2nd person takes 1st fork and completes and releases 1st and 2nd. This continuous until all finishes dinner.

#include <pthread.h> 

#include <semaphore.h> 

#include <stdio.h> 

#define N 5 

#define THINKING 2 

#define HUNGRY 1 

#define EATING 0 

#define LEFT (phnum + 4) % N 

#define RIGHT (phnum + 1) % N 

int state[N]; 

int phil[N] = { 0, 1, 2, 3, 4 }; 

sem_t mutex; 

sem_t S[N]; 

void test(int phnum) 

{ 

if (state[phnum] == HUNGRY 

&& state[LEFT] != EATING 

&& state[RIGHT] != EATING) { 

// state that eating 

state[phnum] = EATING; 

sleep(2); 

printf("Philosopher %d takes fork %d and %d\n", 

phnum + 1, LEFT + 1, phnum + 1); 

printf("Philosopher %d is Eating\n", phnum + 1); 

// sem_post(&S[phnum]) has no effect 

// during takefork 

// used to wake up hungry philosophers 

// during putfork 

sem_post(&S[phnum]); 

} 

} 

// take up chopsticks 

void take_fork(int phnum) 

{ 

sem_wait(&mutex); 

// state that hungry 

state[phnum] = HUNGRY; 

printf("Philosopher %d is Hungry\n", phnum + 1); 

// eat if neighbours are not eating 

test(phnum); 

sem_post(&mutex); 

// if unable to eat wait to be signalled 

sem_wait(&S[phnum]); 

sleep(1); 

} 

// put down chopsticks 

void put_fork(int phnum) 

{ 

sem_wait(&mutex); 

// state that thinking 

state[phnum] = THINKING; 

printf("Philosopher %d putting fork %d and %d down\n", 

phnum + 1, LEFT + 1, phnum + 1); 

printf("Philosopher %d is thinking\n", phnum + 1); 

test(LEFT); 

test(RIGHT); 

sem_post(&mutex); 

} 

void* philospher(void* num) 

{ 

while (1) { 

int* i = num; 

sleep(1); 

take_fork(*i); 

sleep(0); 

put_fork(*i); 

} 

} 

int main() 

{ 

int i; 

pthread_t thread_id[N]; 

// initialize the semaphores 

sem_init(&mutex, 0, 1); 

for (i = 0; i < N; i++) 

sem_init(&S[i], 0, 0); 

for (i = 0; i < N; i++) { 

// create philosopher processes 

pthread_create(&thread_id[i], NULL, 

philospher, &phil[i]); 

printf("Philosopher %d is thinking\n", i + 1); 

} 

for (i = 0; i < N; i++) 

pthread_join(thread_id[i], NULL); 

}