1*b725ae77Skettenis /* linux-dp.c --- dining philosophers, on LinuxThreads
2*b725ae77Skettenis Jim Blandy <jimb@cygnus.com> --- March 1999 */
3*b725ae77Skettenis
4*b725ae77Skettenis /* It's okay to edit this file and shift line numbers around. The
5*b725ae77Skettenis tests use gdb_get_line_number to find source locations, so they
6*b725ae77Skettenis don't depend on having certain line numbers in certain places. */
7*b725ae77Skettenis
8*b725ae77Skettenis #include <stdarg.h>
9*b725ae77Skettenis #include <stdlib.h>
10*b725ae77Skettenis #include <stdio.h>
11*b725ae77Skettenis #include <pthread.h>
12*b725ae77Skettenis #include <sys/time.h>
13*b725ae77Skettenis #include <sys/types.h>
14*b725ae77Skettenis
15*b725ae77Skettenis /* The number of philosophers at the table. */
16*b725ae77Skettenis int num_philosophers;
17*b725ae77Skettenis
18*b725ae77Skettenis /* Mutex ordering -
19*b725ae77Skettenis If you want to lock a mutex M, all the mutexes you have locked
20*b725ae77Skettenis already must appear before M on this list.
21*b725ae77Skettenis
22*b725ae77Skettenis fork_mutex[0]
23*b725ae77Skettenis fork_mutex[1]
24*b725ae77Skettenis ...
25*b725ae77Skettenis fork_mutex[num_philosophers - 1]
26*b725ae77Skettenis stdout_mutex
27*b725ae77Skettenis random_mutex
28*b725ae77Skettenis */
29*b725ae77Skettenis
30*b725ae77Skettenis /* You must hold this mutex while writing to stdout. */
31*b725ae77Skettenis pthread_mutex_t stdout_mutex;
32*b725ae77Skettenis
33*b725ae77Skettenis /* You must hold this mutex while calling any of the random number
34*b725ae77Skettenis generation routines. */
35*b725ae77Skettenis pthread_mutex_t random_mutex;
36*b725ae77Skettenis
37*b725ae77Skettenis /* array of mutexes, one for each fork; fork_mutex[i] is to the left
38*b725ae77Skettenis of philosopher i. A philosopher is holding fork i iff his/her
39*b725ae77Skettenis thread has locked fork_mutex[i]. */
40*b725ae77Skettenis pthread_mutex_t *fork_mutex;
41*b725ae77Skettenis
42*b725ae77Skettenis /* array of threads, one representing each philosopher. */
43*b725ae77Skettenis pthread_t *philosophers;
44*b725ae77Skettenis
45*b725ae77Skettenis void *
xmalloc(size_t n)46*b725ae77Skettenis xmalloc (size_t n)
47*b725ae77Skettenis {
48*b725ae77Skettenis void *p = malloc (n);
49*b725ae77Skettenis
50*b725ae77Skettenis if (! p)
51*b725ae77Skettenis {
52*b725ae77Skettenis fprintf (stderr, "out of memory\n");
53*b725ae77Skettenis exit (2);
54*b725ae77Skettenis }
55*b725ae77Skettenis
56*b725ae77Skettenis return p;
57*b725ae77Skettenis }
58*b725ae77Skettenis
59*b725ae77Skettenis void
shared_printf(char * format,...)60*b725ae77Skettenis shared_printf (char *format, ...)
61*b725ae77Skettenis {
62*b725ae77Skettenis va_list ap;
63*b725ae77Skettenis
64*b725ae77Skettenis va_start (ap, format);
65*b725ae77Skettenis pthread_mutex_lock (&stdout_mutex);
66*b725ae77Skettenis vprintf (format, ap);
67*b725ae77Skettenis pthread_mutex_unlock (&stdout_mutex);
68*b725ae77Skettenis va_end (ap);
69*b725ae77Skettenis }
70*b725ae77Skettenis
71*b725ae77Skettenis int
shared_random()72*b725ae77Skettenis shared_random ()
73*b725ae77Skettenis {
74*b725ae77Skettenis static unsigned int seed;
75*b725ae77Skettenis int result;
76*b725ae77Skettenis
77*b725ae77Skettenis pthread_mutex_lock (&random_mutex);
78*b725ae77Skettenis result = rand_r (&seed);
79*b725ae77Skettenis pthread_mutex_unlock (&random_mutex);
80*b725ae77Skettenis return result;
81*b725ae77Skettenis }
82*b725ae77Skettenis
83*b725ae77Skettenis void
my_usleep(long usecs)84*b725ae77Skettenis my_usleep (long usecs)
85*b725ae77Skettenis {
86*b725ae77Skettenis struct timeval timeout;
87*b725ae77Skettenis
88*b725ae77Skettenis timeout.tv_sec = usecs / 1000000;
89*b725ae77Skettenis timeout.tv_usec = usecs % 1000000;
90*b725ae77Skettenis
91*b725ae77Skettenis select (0, 0, 0, 0, &timeout);
92*b725ae77Skettenis }
93*b725ae77Skettenis
94*b725ae77Skettenis void
random_delay()95*b725ae77Skettenis random_delay ()
96*b725ae77Skettenis {
97*b725ae77Skettenis my_usleep ((shared_random () % 2000) * 100);
98*b725ae77Skettenis }
99*b725ae77Skettenis
100*b725ae77Skettenis void
print_philosopher(int n,char left,char right)101*b725ae77Skettenis print_philosopher (int n, char left, char right)
102*b725ae77Skettenis {
103*b725ae77Skettenis int i;
104*b725ae77Skettenis
105*b725ae77Skettenis shared_printf ("%*s%c %d %c\n", (n * 4) + 2, "", left, n, right);
106*b725ae77Skettenis }
107*b725ae77Skettenis
108*b725ae77Skettenis void *
philosopher(void * data)109*b725ae77Skettenis philosopher (void *data)
110*b725ae77Skettenis {
111*b725ae77Skettenis int n = * (int *) data;
112*b725ae77Skettenis
113*b725ae77Skettenis print_philosopher (n, '_', '_');
114*b725ae77Skettenis
115*b725ae77Skettenis #if 1
116*b725ae77Skettenis if (n == num_philosophers - 1)
117*b725ae77Skettenis for (;;)
118*b725ae77Skettenis {
119*b725ae77Skettenis /* The last philosopher is different. He goes for his right
120*b725ae77Skettenis fork first, so there is no cycle in the mutex graph. */
121*b725ae77Skettenis
122*b725ae77Skettenis /* Grab the right fork. */
123*b725ae77Skettenis pthread_mutex_lock (&fork_mutex[(n + 1) % num_philosophers]);
124*b725ae77Skettenis print_philosopher (n, '_', '!');
125*b725ae77Skettenis random_delay ();
126*b725ae77Skettenis
127*b725ae77Skettenis /* Then grab the left fork. */
128*b725ae77Skettenis pthread_mutex_lock (&fork_mutex[n]);
129*b725ae77Skettenis print_philosopher (n, '!', '!');
130*b725ae77Skettenis random_delay ();
131*b725ae77Skettenis
132*b725ae77Skettenis print_philosopher (n, '_', '_');
133*b725ae77Skettenis pthread_mutex_unlock (&fork_mutex[n]);
134*b725ae77Skettenis pthread_mutex_unlock (&fork_mutex[(n + 1) % num_philosophers]);
135*b725ae77Skettenis random_delay ();
136*b725ae77Skettenis }
137*b725ae77Skettenis else
138*b725ae77Skettenis #endif
139*b725ae77Skettenis for (;;)
140*b725ae77Skettenis {
141*b725ae77Skettenis /* Grab the left fork. */
142*b725ae77Skettenis pthread_mutex_lock (&fork_mutex[n]);
143*b725ae77Skettenis print_philosopher (n, '!', '_');
144*b725ae77Skettenis random_delay ();
145*b725ae77Skettenis
146*b725ae77Skettenis /* Then grab the right fork. */
147*b725ae77Skettenis pthread_mutex_lock (&fork_mutex[(n + 1) % num_philosophers]);
148*b725ae77Skettenis print_philosopher (n, '!', '!');
149*b725ae77Skettenis random_delay ();
150*b725ae77Skettenis
151*b725ae77Skettenis print_philosopher (n, '_', '_');
152*b725ae77Skettenis pthread_mutex_unlock (&fork_mutex[n]);
153*b725ae77Skettenis pthread_mutex_unlock (&fork_mutex[(n + 1) % num_philosophers]);
154*b725ae77Skettenis random_delay ();
155*b725ae77Skettenis }
156*b725ae77Skettenis
157*b725ae77Skettenis return (void *) 0;
158*b725ae77Skettenis }
159*b725ae77Skettenis
160*b725ae77Skettenis int
main(int argc,char ** argv)161*b725ae77Skettenis main (int argc, char **argv)
162*b725ae77Skettenis {
163*b725ae77Skettenis num_philosophers = 5;
164*b725ae77Skettenis
165*b725ae77Skettenis /* Set up the mutexes. */
166*b725ae77Skettenis {
167*b725ae77Skettenis pthread_mutexattr_t ma;
168*b725ae77Skettenis int i;
169*b725ae77Skettenis
170*b725ae77Skettenis pthread_mutexattr_init (&ma);
171*b725ae77Skettenis pthread_mutex_init (&stdout_mutex, &ma);
172*b725ae77Skettenis pthread_mutex_init (&random_mutex, &ma);
173*b725ae77Skettenis fork_mutex = xmalloc (num_philosophers * sizeof (fork_mutex[0]));
174*b725ae77Skettenis for (i = 0; i < num_philosophers; i++)
175*b725ae77Skettenis pthread_mutex_init (&fork_mutex[i], &ma);
176*b725ae77Skettenis pthread_mutexattr_destroy (&ma);
177*b725ae77Skettenis }
178*b725ae77Skettenis
179*b725ae77Skettenis /* Set off the threads. */
180*b725ae77Skettenis {
181*b725ae77Skettenis int i;
182*b725ae77Skettenis int *numbers = xmalloc (num_philosophers * sizeof (*numbers));
183*b725ae77Skettenis pthread_attr_t ta;
184*b725ae77Skettenis
185*b725ae77Skettenis philosophers = xmalloc (num_philosophers * sizeof (*philosophers));
186*b725ae77Skettenis
187*b725ae77Skettenis pthread_attr_init (&ta);
188*b725ae77Skettenis
189*b725ae77Skettenis for (i = 0; i < num_philosophers; i++)
190*b725ae77Skettenis {
191*b725ae77Skettenis numbers[i] = i;
192*b725ae77Skettenis /* linuxthreads.exp: create philosopher */
193*b725ae77Skettenis pthread_create (&philosophers[i], &ta, philosopher, &numbers[i]);
194*b725ae77Skettenis }
195*b725ae77Skettenis
196*b725ae77Skettenis pthread_attr_destroy (&ta);
197*b725ae77Skettenis }
198*b725ae77Skettenis
199*b725ae77Skettenis /* linuxthreads.exp: info threads 2 */
200*b725ae77Skettenis sleep (1000000);
201*b725ae77Skettenis
202*b725ae77Skettenis /* Drink yourself into oblivion. */
203*b725ae77Skettenis for (;;)
204*b725ae77Skettenis sleep (1000000);
205*b725ae77Skettenis
206*b725ae77Skettenis return 0;
207*b725ae77Skettenis }
208