Dining Philosophers Problem

Dining philosophers problem is a classic multiprocess synchronisation problem. Problem is summarised as 5 philosophers sitting at a round table doing 2 things, eating and thinking. While eating they are not thinking and while thinking they are not eating. Each philosophers have plates, that is 5 plates. And there is fork places between each pair of adjacent philosophers, that is total of 5 forks. Each philosopher need 2 forks to eat. Each philosopher can only use the forks on his immediate left and immediate right.
Here is the solution for the Dining philosophers problem.

/* 
Name        :   Dining Philosophers Problem
Author      :   jishnu7
Web         :   http://thecodecracker.com
Date        :   26-Sep-2010
Description :   C Program to solve Dining philosophers problem
License     :   GNU GPL License
*/

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

#define N 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2
#define LEFT (ph_num+4)%N
#define RIGHT (ph_num+1)%N

sem_t mutex;
sem_t S[N];

void * philospher(void *num);
void take_fork(int);
void put_fork(int);
void test(int);

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

int main()
{
    int i;
    pthread_t thread_id[N];
    sem_init(&mutex,0,1);
    for(i=0;i<N;i++)
        sem_init(&S[i],0,0);
    for(i=0;i<N;i++)
    {
        pthread_create(&thread_id[i],NULL,philospher,&phil_num[i]);
        printf("Philosopher %d is thinking\n",i+1);
    }
    for(i=0;i<N;i++)
        pthread_join(thread_id[i],NULL);
}

void *philospher(void *num)
{
    while(1)
    {
        int *i = num;
        sleep(1);
        take_fork(*i);
        sleep(0);
        put_fork(*i);
    }
}

void take_fork(int ph_num)
{
    sem_wait(&mutex);
    state[ph_num] = HUNGRY;
    printf("Philosopher %d is Hungry\n",ph_num+1);
    test(ph_num);
    sem_post(&mutex);
    sem_wait(&S[ph_num]);
    sleep(1);
}

void test(int ph_num)
{
    if (state[ph_num] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)
    {
        state[ph_num] = EATING;
        sleep(2);
        printf("Philosopher %d takes fork %d and %d\n",ph_num+1,LEFT+1,ph_num+1);
        printf("Philosopher %d is Eating\n",ph_num+1);
        sem_post(&S[ph_num]);
    }
}

void put_fork(int ph_num)
{
    sem_wait(&mutex);
    state[ph_num] = THINKING;
    printf("Philosopher %d putting fork %d and %d down\n",ph_num+1,LEFT+1,ph_num+1);
    printf("Philosopher %d is thinking\n",ph_num+1);
    test(LEFT);
    test(RIGHT);
    sem_post(&mutex);
}
1

Note : Don’t forgot to link pthread when compiling. It can be done by compiling with -lpthread option. eg: gcc -lpthread philospher.c

OUTPUT
——-

Philosopher 1 is thinking
Philosopher 2 is thinking
Philosopher 3 is thinking
Philosopher 4 is thinking
Philosopher 5 is thinking
Philosopher 1 is Hungry
Philosopher 1 takes fork 5 and 1
Philosopher 1 is Eating
Philosopher 2 is Hungry
Philosopher 3 is Hungry
Philosopher 3 takes fork 2 and 3
Philosopher 3 is Eating
Philosopher 4 is Hungry
Philosopher 5 is Hungry
Philosopher 1 putting fork 5 and 1 down
Philosopher 1 is thinking
Philosopher 5 takes fork 4 and 5
Philosopher 5 is Eating
Philosopher 3 putting fork 2 and 3 down
Philosopher 3 is thinking

VN:F [1.9.22_1171]
Rating: 8.8/10 (82 votes cast)
VN:F [1.9.22_1171]
Rating: +38 (from 56 votes)
Dining Philosophers Problem, 8.8 out of 10 based on 82 ratings

29. September 2010 by Jishnu
Categories: C Programming, System Programming | Tags: , | 19 comments

Comments (19)

  1. minta dong file semaphore.h dan pthread.h
    kirim ke email ya
    thnks

  2. quite understandable
    Now how can you write this same code in parallel using threads ?? like the dining philosopher problem
    Thanks in advance
    Would be grateful to receive the code via my email

  3. hi Jishnu,

    Thanks a lot for the code…

    It will be of great help for me if you could get me the c code for Producer consumer problem

  4. thanks boss…..can u get me the code for reader-writer and producer-consumer problem…….

  5. thanks

  6. Where can i get the Algorithm for this programs

  7. Thanks a lot, great code!

  8. Thanks…………

  9. wow……..beautifull

  10. greattttttt

  11. You made my work easy

  12. what is ph_num in the above program…please do reply…….

  13. i couldnt compile, please help

  14. thanks alot man

  15. semaphore.h cant run plz help

  16. Ese código es épico!! gracias Jishnu :D Lo traduje al español, y lo comenté… espero que le sirva a alguien…

    that code is awesome!! thanks jishnu :D i translated it to spanish, and commented it, if anyone is interested

Leave a Reply