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