Home / / Implementation of Dining Philosopher Problem using Semaphor in C Programming

Implementation of Dining Philosopher Problem using Semaphor in C Programming

June 29, 2019 , ,
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 philosophers 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 finishes 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:


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#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

Subscribe to: Post Comments ( Atom )