1 /*
2 August 1st, 11:00 am, 2009
3 The Dinning Philosophers Problem, Linux C
4 Allowing 4 philosophers at most to take their left chopsticks, otherwise death lock will happen.
5 */
6
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10 #include <unistd.h>
11 #include <sys/types.h>
12 #include <sys/wait.h>
13 #include <linux/sem.h>
14
15 #define SEM_KEY 1025
16 #define CHOP_NUM 5
17 #define MOD 500000000L
18
19 void think(int id)
20 {
21 int tm = rand() % MOD;
22 printf("Philosopher #%d starts thinking.\n", id);
23 while (tm--);
24 }
25
26 /*
27 P operation, is to ask for resourse of some kind.
28 If fialed, it will be blocked and wait until the resourses is available.
29 */
30 int p(int sem_id, int idx)
31 {
32 struct sembuf sem_op;
33 sem_op.sem_num = idx;
34 sem_op.sem_op = -1;
35 sem_op.sem_flg = 0;
36 semop(sem_id, &sem_op, 1);
37 }
38
39 /*
40 V operation, is to release resourse asked before.
41 */
42 int v(int sem_id, int idx)
43 {
44 struct sembuf sem_op;
45 sem_op.sem_num = idx;
46 sem_op.sem_op = 1;
47 sem_op.sem_flg = 0;
48 semop(sem_id, &sem_op, 1);
49 }
50
51 void eat(int sem_id, int id) {
52 int tm;
53 int i;
54 printf("Philosopher #%d is hungery.\n", id);
55 p(sem_id, CHOP_NUM);
56 p(sem_id, id);
57 printf("Philosopher #%d starts taking left chopstick.\n", id);
58 tm = rand() % MOD;
59 while (tm--);
60 printf("Philosopher #%d has got left chopstick.\n", id);
61 p(sem_id, (id + 1) % CHOP_NUM);
62 printf("Philosopher #%d has got left and right chopsticks, and starts eating.\n", id);
63 tm = rand() % MOD;
64 while (tm--);
65 v(sem_id, id);
66 v(sem_id, CHOP_NUM);
67 v(sem_id, (id + 1) % CHOP_NUM);
68 printf("Philosopher #%d has finished eating.\n", id);
69 }
70
71 int main(int argc, char **argv)
72 {
73 int sem_id;
74 int i, id, pid;
75 int rv; /*return value*/
76 int count = 0;
77 union semun sem_val;
78 sem_id = semget(SEM_KEY, CHOP_NUM + 1, IPC_CREAT | 0666);
79 if (sem_id == -1) {
80 perror("semget");
81 exit(-1);
82 }
83 /*
84 Set CHOP_NUM + 1 semaphores, the first CHOP_NUM represent the available resource of chopsticks,
85 the last represents the available four left chopsticks at most will be used at the same time.
86 */
87 for (i = 0; i < CHOP_NUM; i++) {
88 sem_val.val = 1;
89 rv = semctl(sem_id, i, SETVAL, sem_val);
90 if (rv == -1) {
91 perror("semctl + SETVAL");
92 exit(-1);
93 }
94 }
95 sem_val.val = 4;
96 rv = semctl(sem_id, CHOP_NUM, SETVAL, sem_val);
97 if (rv == -1) {
98 perror("semctl + SETVAL");
99 exit(-1);
100 }
101 for (i = 0; i < CHOP_NUM; i++) {
102 pid = fork();
103 id = count++;
104 if (pid == 0) break;
105 }
106 if (pid == 0) {
107 printf("%d created.\n", id);
108 while (1) {
109 think(id);
110 eat(sem_id, id);
111 }
112 } else {
113 /*
114 Main process wait the end signal form all its child process,
115 then release the semaphores.
116 */
117 int chld_stat;
118 wait(&chld_stat);
119 for (i = 0; i <= CHOP_NUM; i++) {
120 rv = semctl(sem_id, i, IPC_RMID, NULL);
121 if (rv == -1) {
122 perror("semctl + IPC_RMID");
123 exit(-1);
124 }
125 }
126 printf("Finish.\n");
127 }
128 return 0;
129 }