1 /*
2 ** GNU Pth - The GNU Portable Threads
3 ** Copyright (c) 1999-2006 Ralf S. Engelschall <rse@engelschall.com>
4 **
5 ** This file is part of GNU Pth, a non-preemptive thread scheduling
6 ** library which can be found at http://www.gnu.org/software/pth/.
7 **
8 ** This library is free software; you can redistribute it and/or
9 ** modify it under the terms of the GNU Lesser General Public
10 ** License as published by the Free Software Foundation; either
11 ** version 2.1 of the License, or (at your option) any later version.
12 **
13 ** This library is distributed in the hope that it will be useful,
14 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
15 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 ** Lesser General Public License for more details.
17 **
18 ** You should have received a copy of the GNU Lesser General Public
19 ** License along with this library; if not, write to the Free Software
20 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
21 ** USA, or contact Ralf S. Engelschall <rse@engelschall.com>.
22 **
23 ** test_philo.c: Pth test application showing the 5 philosopher problem
24 */
25 /* ``It's not enough to be a great programmer;
26 you have to find a great problem.''
27 -- Charles Simonyi */
28
29 /*
30 * Reference: E.W. Dijkstra,
31 * ``Hierarchical Ordering of Sequential Processes'',
32 * Acta Informatica 1, 1971, 115-138.
33 */
34
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <signal.h>
39 #include <sys/types.h>
40
41 #include "pth.h"
42
43 #include "test_common.h"
44
45 #define PHILNUM 5
46
47 typedef enum {
48 thinking,
49 hungry,
50 eating
51 } philstat;
52
53 static const char *philstatstr[3] = {
54 "thinking",
55 "hungry ",
56 "EATING "
57 };
58
59 typedef struct tablestruct {
60 pth_t tid[PHILNUM];
61 int self[PHILNUM];
62 pth_mutex_t mutex;
63 pth_cond_t condition[PHILNUM];
64 philstat status[PHILNUM];
65 } table;
66
67 static table *tab;
68
printstate(void)69 static void printstate(void)
70 {
71 int i;
72
73 for (i = 0; i < PHILNUM; i++)
74 printf("| %s ", philstatstr[(int)(tab->status)[i]]);
75 printf("|\n");
76 return;
77 }
78
test(unsigned int i)79 static int test(unsigned int i)
80 {
81 if ( ((tab->status)[i] == hungry)
82 && ((tab->status)[(i + 1) % PHILNUM] != eating)
83 && ((tab->status)[(i - 1 + PHILNUM) % PHILNUM] != eating)) {
84 (tab->status)[i] = eating;
85 pth_cond_notify(&((tab->condition)[i]), FALSE);
86 return TRUE;
87 }
88 return FALSE;
89 }
90
pickup(unsigned int k)91 static void pickup(unsigned int k)
92 {
93 pth_mutex_acquire(&(tab->mutex), FALSE, NULL);
94 (tab->status)[k] = hungry;
95 printstate();
96 if (!test(k))
97 pth_cond_await(&((tab->condition)[k]), &(tab->mutex), NULL);
98 printstate();
99 pth_mutex_release(&(tab->mutex));
100 return;
101 }
102
putdown(unsigned int k)103 static void putdown(unsigned int k)
104 {
105 pth_mutex_acquire(&(tab->mutex), FALSE, NULL);
106 (tab->status)[k] = thinking;
107 printstate();
108 test((k + 1) % PHILNUM);
109 test((k - 1 + PHILNUM) % PHILNUM);
110 pth_mutex_release(&(tab->mutex));
111 return;
112 }
113
philosopher(void * _who)114 static void *philosopher(void *_who)
115 {
116 unsigned int *who = (unsigned int *)_who;
117
118 /* For simplicity, all philosophers eat for the same amount of time
119 and think for a time that is simply related to their position at
120 the table. The parameter who identifies the philosopher: 0,1,2,.. */
121 for (;;) {
122 pth_sleep((*who) + 1);
123 pickup((*who));
124 pth_sleep(1);
125 putdown((*who));
126 }
127 return NULL;
128 }
129
main(int argc,char * argv[])130 int main(int argc, char *argv[])
131 {
132 int i;
133 sigset_t ss;
134 int sig;
135 pth_event_t ev;
136
137 /* initialize Pth library */
138 pth_init();
139
140 /* display test program header */
141 printf("This is TEST_PHILO, a Pth test showing the Five Dining Philosophers\n");
142 printf("\n");
143 printf("This is a demonstration showing the famous concurrency problem of the\n");
144 printf("Five Dining Philosophers as analysed 1965 by E.W.Dijkstra:\n");
145 printf("\n");
146 printf("Five philosophers are sitting around a round table, each with a bowl of\n");
147 printf("Chinese food in front of him. Between periods of talking they may start\n");
148 printf("eating whenever they want to, with their bowls being filled frequently.\n");
149 printf("But there are only five chopsticks available, one each to the left of\n");
150 printf("each bowl - and for eating Chinese food one needs two chopsticks. When\n");
151 printf("a philosopher wants to start eating, he must pick up the chopstick to\n");
152 printf("the left of his bowl and the chopstick to the right of his bowl. He\n");
153 printf("may find, however, that either one (or even both) of the chopsticks is\n");
154 printf("unavailable as it is being used by another philosopher sitting on his\n");
155 printf("right or left, so he has to wait.\n");
156 printf("\n");
157 printf("This situation shows classical contention under concurrency (the\n");
158 printf("philosophers want to grab the chopsticks) and the possibility of a\n");
159 printf("deadlock (all philosophers wait that the chopstick to their left becomes\n");
160 printf("available).\n");
161 printf("\n");
162 printf("The demonstration runs max. 60 seconds. To stop before, press CTRL-C.\n");
163 printf("\n");
164 printf("+----P1----+----P2----+----P3----+----P4----+----P5----+\n");
165
166 /* initialize the control table */
167 tab = (table *)malloc(sizeof(table));
168 if (!pth_mutex_init(&(tab->mutex))) {
169 perror("pth_mutex_init");
170 exit(1);
171 }
172 for (i = 0; i < PHILNUM; i++) {
173 (tab->self)[i] = i;
174 (tab->status)[i] = thinking;
175 if (!pth_cond_init(&((tab->condition)[i]))) {
176 perror("pth_cond_init");
177 exit(1);
178 }
179 }
180
181 /* spawn the philosopher threads */
182 for (i = 0; i < PHILNUM; i++) {
183 if (((tab->tid)[i] =
184 pth_spawn(PTH_ATTR_DEFAULT, philosopher,
185 &((tab->self)[i]))) == NULL) {
186 perror("pth_spawn");
187 exit(1);
188 }
189 }
190
191 /* wait until 60 seconds have elapsed or CTRL-C was pressed */
192 sigemptyset(&ss);
193 sigaddset(&ss, SIGINT);
194 ev = pth_event(PTH_EVENT_TIME, pth_timeout(60,0));
195 pth_sigwait_ev(&ss, &sig, ev);
196 pth_event_free(ev, PTH_FREE_ALL);
197
198 /* cancel and join the philosopher threads */
199 for (i = 0; i < PHILNUM; i++)
200 pth_cancel((tab->tid)[i]);
201 while (pth_join(NULL, NULL));
202
203 /* finish display */
204 printf("+----------+----------+----------+----------+----------+\n");
205
206 /* free the control table */
207 free(tab);
208
209 /* shutdown Pth library */
210 pth_kill();
211
212 return 0;
213 }
214
215