Dining Philosophers Problem C [Semaphore,Threads] [System Programming]

This is the implementation of classic dining philosophers problem in java using semaphores and threads

Problem statement

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers. (An alternative problem formulation uses rice and chopsticks instead of spaghetti and forks.)

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when he has both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After he finishes eating, he needs to put down both forks so they become available to others. A philosopher can take the fork on his right or the one on his left as they become available, but cannot start eating before getting both of them.

Eating is not limited by the amount of spaghetti left; an infinite supply is assumed.

The problem is how to design a discipline of behavior (a concurrent algorithm) such that each philosopher will not starve; i.e., can forever continue to alternate between eating and thinking, assuming that any philosopher cannot know when others may want to eat or think.

Problems
The problem was designed to illustrate the challenges of avoiding deadlock, a system state in which no progress is possible. To see that a proper solution to this problem is not obvious, consider a proposal in which each philosopher is instructed to behave as follows:

think until the left fork is available; when it is, pick it up;
think until the right fork is available; when it is, pick it up;
when both forks are held, eat for a fixed amount of time;
then, put the right fork down;
then, put the left fork down;
repeat from the beginning.
This attempted solution fails because it allows the system to reach a deadlock state, in which no progress is possible. This is the state in which each philosopher has picked up the fork to the left, and is waiting for the fork to the right to become available. With the given instructions, this state can be reached, and when it is reached, the philosophers will eternally wait for each other to release a fork.

Resource starvation might also occur independently of deadlock if a particular philosopher is unable to acquire both forks because of a timing problem. For example there might be a rule that the philosophers put down a fork after waiting ten minutes for the other fork to become available and wait a further ten minutes before making their next attempt. This scheme eliminates the possibility of deadlock (the system can always advance to a different state) but still suffers from the problem of livelock. If all five philosophers appear in the dining room at exactly the same time and each picks up the left fork at the same time the philosophers will wait ten minutes until they all put their forks down and then wait a further ten minutes before they all pick them up again.

Mutual exclusion is the core idea of the problem; the dining philosophers create a generic and abstract scenario useful for explaining issues of this type. The failures these philosophers may experience are analogous to the difficulties that arise in real computer programming when multiple programs need exclusive access to shared resources. These issues are studied in the branch of Concurrent Programming. The original problems of Dijkstra were related to external devices like tape drives. However, the difficulties exemplified by the dining philosophers problem arise far more often when multiple processes access sets of data that are being updated. Systems such as operating system kernels use thousands of locks and synchronizations that require strict adherence to methods and protocols if such problems as deadlock, starvation, or data corruption are to be avoided.

#include<stdio.h>
#include<pthread.h>
#include<semaphore.h>
#define N 5
#define LEFT i>0?(i-1)%N:N-1
#define RITE (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2


int state[N];
int philosopher_num[N];

sem_t mutex;
sem_t sem_phil[N];

void * philosopher(void *);
void takechops(int);
void putchops(int);
void test(int);

main(int argc,char **argv)
{
int k;
pthread_t tid[N];
printf("Dining Phiosophern");
for(k=0;k<N;k++)
{
philosopher_num[k]=k;
}
sem_init(&mutex,0,1);
for(k=0;k<N;k++) sem_init(&sem_phil[k],0,0);
for(k=0;k<N;k++) pthread_create(&tid[k],NULL,philosopher,&philosopher_num[k]);
for(k=0;k<N;k++) pthread_join(tid[k],NULL);
}

void * philosopher(void *param)
{
int i=*((int *)param);
int tt=1;
int et=2;
while(1)
{
sleep(tt);
takechops(i);
sleep(et);
putchops(i);
}
}

void takechops(int i)
{
sem_wait(&mutex);
state[i]=HUNGRY;
printf("Philosopher %d is hungryn",i);
test(i);
sem_post(&mutex);
sem_wait(&sem_phil[i]);
}

void putchops(int i)
{
sem_wait(&mutex);
state[i]=THINKING;
printf("Philosopher %d is thinkingn",i);
test(LEFT);
test(RITE);
sem_post(&mutex);
}

void test(int i)
{
if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RITE]!=EATING){
state[i]=2;
printf("Philosopher %d is eatingn",i);
sem_post(&sem_phil[i]);
}
}