Facebook

Breaking News

Implementation of Dining Philosopher Problem using Semaphor in C Programming

In this problem, there are five philosophers who can think or eat. There is a circular table with five chairs, each chair belonging
to one philosopher. In the center of the table, there is a bowl of rice, and the table is laid with five single chopsticks.
Initially, all philosophers are thinking. From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to him (left and right). A philosopher may pick up only one chopstick at a time. Obviously, he cannot pick up a chopstick that is already in the hand of a neighbor and if he finds only one chopstick he has to drop it so that other philosopher can eat. When a hungry philosopher has both his chopsticks (left and right) at the same time, he eats without releasing the chopsticks. When he is finished eating, he puts down both chopsticks and starts thinking again and other philosophers get time to eat.
At once maximum, two philosophers can eat. For example, consider five philosophers are P0, P1, P2, P3, P4. Initially, all are thinking. Suppose P0 gets hungry and wants to eat he will pick chopsticks from his left and right consider the chopstick on the left was his own and chopstick which was on the right belongs to P1. Now P1 cannot eat until P0 finish eating. same if P2 picks up his own and the chopstick belonging to P3 then P3 cannot eat and has to wait for P2 to finish eating. In the end, P4 cannot eat as he has his own chopstick but not the second chopstick to pick which belongs to P0 as P0 is eating.

Code:

#include<stdio.h>
#include<unistd.h>
#include<semaphore.h>
#include<math.h>
#include<pthread.h>
#include<sys/sem.h>

sem_t mutex;

#define SEMKEY 222

union semun{
 int val;
 struct semid_ds *buf;
 unsigned short *array;
 struct seminfo *_buf;
};

int pickChopstick(int chop){
 struct sembuf sops[1];     
 union semun arg;
 unsigned short chopsticks[5];

 int sem_id = semget(SEMKEY, 5, 0666);

     if(sem_id < 0)
            perror("Cannot get semaphore\n");
     else{

      arg.array = chopsticks;

      if(semctl(sem_id,0,GETALL,arg)==-1){
    perror("semctl");
  }

  if(arg.array[chop]==0)
   return 0;
  
              sops[0].sem_num = chop;
  sops[0].sem_op = 0-1;
  sops[0].sem_flg = 0;

  if(semop(sem_id, sops, 1) < 0)
   perror("Semop error in think");
  else
   return 1;

  return 0;

 }
}

void dropChopstick(int chop){
 struct sembuf sops[1];

 int sem_id = semget(SEMKEY, 5, 0666);

     if(sem_id < 0)
        perror("Cannot get semaphore\n");
     else{

      sops[0].sem_num = chop;
 sops[0].sem_op = 1;
 sops[0].sem_flg = 0;

 if(semop(sem_id, sops, 1) < 0)
  perror("Semop error in think");
 }
}

void *eat(void *data){
 int ph = *((int *)data);
 int count1, count2;
 for(count1 = 0; count1<100; count1++){
  for(count2 = 0; count2<1000000; count2++){
   sin(count2*.0000005);
  }
 }
}

void *think(void *data){
 int ph = *((int *)data);
 int left=ph;
 int right = (ph+1)%5;

 while(1){
 
  printf("Philospher # %d wants to eat\n",ph);

  while(1){

   sem_wait(&mutex);

   if(pickChopstick(left))
    if(pickChopstick(right)){

     sem_post(&mutex);

     printf("Philospher # %d going to eat\n",ph);

     eat(data);

     dropChopstick(left);
     dropChopstick(right);

     printf("Philospher# %d done eating, Now going to think\n",ph);

     break;

    }else{
     dropChopstick(left);
    }
  
   sem_post(&mutex);
  }
 }
}

void createSemaphore(){
 int sem_id;
 union semun arg;
 unsigned short chopsticks[5]={1,1,1,1,1};
 
 sem_id = semget(SEMKEY,5,(IPC_CREAT | IPC_EXCL | 0666));

 if(sem_id < 0){
  perror("Cannot create semaphore\n");
 }else{
 
  arg.array = chopsticks;

  if(semctl(sem_id,0,SETALL,arg)==-1){
   perror("semctl");
  }
 }
}

int main(){
 
 pthread_t tid[5];
 int i,ph[5]={0,1,2,3,4};

 sem_init(&mutex,0,1);

 createSemaphore(); 

 for(i=0;i<5;i++){
  pthread_create((&tid[i]),NULL,think,&ph[i]);
 }

 for(i=0;i<5;i++){
  pthread_join(tid[i],NULL);
 }

 sem_destroy(&mutex);

 return 0;
}

OutPut:

itachay@ubuntu:~/Desktop$ gcc DiningPhiloshper.c -lpthread
itachay@ubuntu:~/Desktop$ ./a.out
Philospher # 4 wants to eat
Philospher # 4 going to eat
Philospher # 2 wants to eat
Philospher # 2 going to eat
Philospher # 0 wants to eat
Philospher # 3 wants to eat
Philospher # 1 wants to eat
Philospher# 2 done eating, Now going to think
Philospher # 2 wants to eat
Philospher # 1 going to eat
Philospher# 4 done eating, Now going to think
Philospher # 4 wants to eat
Philospher # 3 going to eat
Philospher# 1 done eating, Now going to think
Philospher # 0 going to eat
Philospher # 1 wants to eat
Philospher# 3 done eating, Now going to think
Philospher # 3 wants to eat
Philospher # 2 going to eat
Philospher# 0 done eating, Now going to think
Philospher # 0 wants to eat
Philospher # 4 going to eat
Philospher# 2 done eating, Now going to think
Philospher # 2 wants to eat
Philospher # 1 going to eat
Philospher# 4 done eating, Now going to think
Philospher # 3 going to eat
Philospher # 4 wants to eat
Philospher# 1 done eating, Now going to think
Philospher # 0 going to eat
Philospher # 1 wants to eat
Philospher# 3 done eating, Now going to think
Philospher # 3 wants to eat
Philospher # 2 going to eat
Philospher# 0 done eating, Now going to think
Philospher # 0 wants to eat
Philospher # 0 going to eat

No comments