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 *
xmalloc(size_t n)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
shared_printf(char * format,...)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
shared_random()72 shared_random ()
73 {
74 int result;
75
76 pthread_mutex_lock (&random_mutex);
77 result = rand ();
78 pthread_mutex_unlock (&random_mutex);
79 return result;
80 }
81
82 void
my_usleep(long usecs)83 my_usleep (long usecs)
84 {
85 struct timeval timeout;
86
87 timeout.tv_sec = usecs / 1000000;
88 timeout.tv_usec = usecs % 1000000;
89
90 select (0, 0, 0, 0, &timeout);
91 }
92
93 void
random_delay()94 random_delay ()
95 {
96 my_usleep ((shared_random () % 2000) * 100);
97 }
98
99 void
print_philosopher(int n,char left,char right)100 print_philosopher (int n, char left, char right)
101 {
102 int i;
103
104 shared_printf ("%*s%c %d %c\n", (n * 4) + 2, "", left, n, right);
105 }
106
107 void *
philosopher(void * data)108 philosopher (void *data)
109 {
110 int n = * (int *) data;
111
112 print_philosopher (n, '_', '_');
113
114 #if 1
115 if (n == num_philosophers - 1)
116 for (;;)
117 {
118 /* The last philosopher is different. He goes for his right
119 fork first, so there is no cycle in the mutex graph. */
120
121 /* Grab the right fork. */
122 pthread_mutex_lock (&fork_mutex[(n + 1) % num_philosophers]);
123 print_philosopher (n, '_', '!');
124 random_delay ();
125
126 /* Then grab the left fork. */
127 pthread_mutex_lock (&fork_mutex[n]);
128 print_philosopher (n, '!', '!');
129 random_delay ();
130
131 print_philosopher (n, '_', '_');
132 pthread_mutex_unlock (&fork_mutex[n]);
133 pthread_mutex_unlock (&fork_mutex[(n + 1) % num_philosophers]);
134 random_delay ();
135 }
136 else
137 #endif
138 for (;;)
139 {
140 /* Grab the left fork. */
141 pthread_mutex_lock (&fork_mutex[n]);
142 print_philosopher (n, '!', '_');
143 random_delay ();
144
145 /* Then grab the right fork. */
146 pthread_mutex_lock (&fork_mutex[(n + 1) % num_philosophers]);
147 print_philosopher (n, '!', '!');
148 random_delay ();
149
150 print_philosopher (n, '_', '_');
151 pthread_mutex_unlock (&fork_mutex[n]);
152 pthread_mutex_unlock (&fork_mutex[(n + 1) % num_philosophers]);
153 random_delay ();
154 }
155
156 return (void *) 0;
157 }
158
159 int
main(int argc,char ** argv)160 main (int argc, char **argv)
161 {
162 num_philosophers = 5;
163
164 /* Set up the mutexes. */
165 {
166 pthread_mutexattr_t ma;
167 int i;
168
169 pthread_mutexattr_init (&ma);
170 pthread_mutex_init (&stdout_mutex, &ma);
171 pthread_mutex_init (&random_mutex, &ma);
172 fork_mutex = xmalloc (num_philosophers * sizeof (fork_mutex[0]));
173 for (i = 0; i < num_philosophers; i++)
174 pthread_mutex_init (&fork_mutex[i], &ma);
175 pthread_mutexattr_destroy (&ma);
176 }
177
178 /* Set off the threads. */
179 {
180 int i;
181 int *numbers = xmalloc (num_philosophers * sizeof (*numbers));
182 pthread_attr_t ta;
183
184 philosophers = xmalloc (num_philosophers * sizeof (*philosophers));
185
186 pthread_attr_init (&ta);
187
188 for (i = 0; i < num_philosophers; i++)
189 {
190 numbers[i] = i;
191 /* linuxthreads.exp: create philosopher */
192 pthread_create (&philosophers[i], &ta, philosopher, &numbers[i]);
193 }
194
195 pthread_attr_destroy (&ta);
196 }
197
198 /* linuxthreads.exp: info threads 2 */
199 sleep (1000000);
200
201 /* Drink yourself into oblivion. */
202 for (;;)
203 sleep (1000000);
204
205 return 0;
206 }
207