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