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 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.
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