| Skip Navigation Links | |
| Exit Print View | |
|
Oracle Solaris Studio 12.3: Thread Analyzer User's Guide Oracle Solaris Studio 12.3 Information Library |
| Skip Navigation Links | |
| Exit Print View | |
|
|
Oracle Solaris Studio 12.3: Thread Analyzer User's Guide Oracle Solaris Studio 12.3 Information Library |
1. What is the Thread Analyzer and What Does It Do?
3.2 Getting the Deadlock Tutorial Source Files
3.2.1 Source Code Listing for din_philo.c
3.3 The Dining Philosophers Scenario
3.3.1 How the Philosophers Can Deadlock
3.3.2 Introducing a Sleep Time for Philosopher 1
3.4 How to Use the Thread Analyzer to Find Deadlocks
3.4.2 Create a Deadlock Detection Experiment
3.4.3 Examine the Deadlock Detection Experiment
3.4.3.1 Using Thread Analyzer to View the Deadlock Detection Experiment
3.4.3.2 Using er_print to View the Deadlock Detection Experiment
3.5 Understanding the Deadlock Experiment Results
3.5.1 Examining Runs That Deadlock
3.5.2 Examining Runs That Complete Despite Deadlock Potential
3.6 Fixing the Deadlocks and Understanding False Positives
3.6.1 Regulating the Philosophers With Tokens
One way to remove potential and actual deadlocks is to use a system of tokens so that a philosopher must receive a token before attempting to eat. The number of available tokens must be less than the number of philosophers at the table. After a philosopher receives a token, he can attempt to eat in accordance with the rules of the table. After eating, each philosopher returns the token and repeats the process. The following pseudo-code shows the logic for each philosopher when using the token system.
while (there is still food on the table)
{
get token
grab right fork
grab left fork
eat some food
put down left fork
put down right fork
return token
}
The following sections detail two different implementations for the system of tokens.
The following listing shows the fixed version of the dining philosophers program that uses the token system. This solution incorporates four tokens, one less than the number of diners, so no more than four philosophers can attempt to eat at the same time. This version of the program is called din_philo_fix1.c:
Tip - If you downloaded the sample applications, you can copy the din_philo_fix1.c file from the SolarisStudioSampleApplications/ThreadAnalyzer/din_philo directory.
1 /*
2 * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All Rights Reserved.
3 * @(#)din_philo_fix1.c 1.3 (Oracle) 10/03/26
4 */
5
6 #include <pthread.h>
7 #include <stdio.h>
8 #include <unistd.h>
9 #include <stdlib.h>
10 #include <errno.h>
11 #include <assert.h>
12
13 #define PHILOS 5
14 #define DELAY 5000
15 #define FOOD 100
16
17 void *philosopher (void *id);
18 void grab_chopstick (int,
19 int,
20 char *);
21 void down_chopsticks (int,
22 int);
23 int food_on_table ();
24 void get_token ();
25 void return_token ();
26
27 pthread_mutex_t chopstick[PHILOS];
28 pthread_t philo[PHILOS];
29 pthread_mutex_t food_lock;
30 pthread_mutex_t num_can_eat_lock;
31 int sleep_seconds = 0;
32 uint32_t num_can_eat = PHILOS - 1;
33
34
35 int
36 main (int argn,
37 char **argv)
38 {
39 int i;
40
41 pthread_mutex_init (&food_lock, NULL);
42 pthread_mutex_init (&num_can_eat_lock, NULL);
43 for (i = 0; i < PHILOS; i++)
44 pthread_mutex_init (&chopstick[i], NULL);
45 for (i = 0; i < PHILOS; i++)
46 pthread_create (&philo[i], NULL, philosopher, (void *)i);
47 for (i = 0; i < PHILOS; i++)
48 pthread_join (philo[i], NULL);
49 return 0;
50 }
51
52 void *
53 philosopher (void *num)
54 {
55 int id;
56 int i, left_chopstick, right_chopstick, f;
57
58 id = (int)num;
59 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
60 right_chopstick = id;
61 left_chopstick = id + 1;
62
63 /* Wrap around the chopsticks. */
64 if (left_chopstick == PHILOS)
65 left_chopstick = 0;
66
67 while (f = food_on_table ()) {
68 get_token ();
69
70 grab_chopstick (id, right_chopstick, "right ");
71 grab_chopstick (id, left_chopstick, "left");
72
73 printf ("Philosopher %d: eating.\n", id);
74 usleep (DELAY * (FOOD - f + 1));
75 down_chopsticks (left_chopstick, right_chopstick);
76
77 return_token ();
78 }
79
80 printf ("Philosopher %d is done eating.\n", id);
81 return (NULL);
82 }
83
84 int
85 food_on_table ()
86 {
87 static int food = FOOD;
88 int myfood;
89
90 pthread_mutex_lock (&food_lock);
91 if (food > 0) {
92 food--;
93 }
94 myfood = food;
95 pthread_mutex_unlock (&food_lock);
96 return myfood;
97 }
98
99 void
100 grab_chopstick (int phil,
101 int c,
102 char *hand)
103 {
104 pthread_mutex_lock (&chopstick[c]);
105 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
106 }
107
108
109
110 void
111 down_chopsticks (int c1,
112 int c2)
113 {
114 pthread_mutex_unlock (&chopstick[c1]);
115 pthread_mutex_unlock (&chopstick[c2]);
116 }
117
118
119 void
120 get_token ()
121 {
122 int successful = 0;
123
124 while (!successful) {
125 pthread_mutex_lock (&num_can_eat_lock);
126 if (num_can_eat > 0) {
127 num_can_eat--;
128 successful = 1;
129 }
130 else {
131 successful = 0;
132 }
133 pthread_mutex_unlock (&num_can_eat_lock);
134 }
135 }
136
137 void
138 return_token ()
139 {
140 pthread_mutex_lock (&num_can_eat_lock);
141 num_can_eat++;
142 pthread_mutex_unlock (&num_can_eat_lock);
143 }
Try compiling this fixed version of the dining philosophers program and running it several times. The system of tokens limits the number of diners attempting to use the chopsticks and thus avoids actual and potential deadlocks.
To compile, use the following command:
cc -g -o din_philo_fix1 din_philo_fix1.c
To collect an experiment:
collect -r deadlock din_philo_fix1 -o din_philo_fix1.1.er
Even when using the system of tokens, the Thread Analyzer reports a potential deadlock for this implementation even though none exists. This is a false positive. Consider the following screen shot which details the potential deadlock.
Figure 3-5 False Positive Report of a Potential Deadlock
Select the first thread in the chain (Thread #2) and then click on the Dual Source tab to see the source code location in which Thread #2 held the lock at address 0x216a8, and where in the source code it requested the lock at address 0x216c0. The following figure shows the Dual Source tab for Thread #2.
Figure 3-6 False Positive Potential Deadlock's Source
The get_token() function in din_philo_fix1.c uses a while loop to synchronize the threads. A thread will not leave the while loop until it successfully gets a token (this occurs when num_can_eat is greater than zero). The while loop limits the number of simultaneous diners to four. However, the synchronization implemented by the while loop is not recognized by the Thread Analyzer. It assumes that all five philosophers attempt to grab the chopsticks and eat concurrently, so it reports a potential deadlock. The following section details how to limit the number of simultaneous diners by using synchronizations which the Thread Analyzer recognizes.
The following listing shows an alternative implementation of the system of tokens. This implementation still uses four tokens, so no more than four diners attempt to eat at the same time. However, this implementation uses the sem_wait() and sem_post() semaphore routines to limit the number of eating philosophers. This version of the source file is called din_philo_fix2.c.
Tip - If you downloaded the sample applications, you can copy the din_philo_fix2.c file from the SolarisStudioSampleApplications/ThreadAnalyzer/din_philo directory.
The following listing details din_philo_fix2.c:
1 /*
2 * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All Rights Reserved.
3 * @(#)din_philo_fix2.c 1.3 (Oracle) 10/03/26
4 */
5
6 #include <pthread.h>
7 #include <stdio.h>
8 #include <unistd.h>
9 #include <stdlib.h>
10 #include <errno.h>
11 #include <assert.h>
12 #include <semaphore.h>
13
14 #define PHILOS 5
15 #define DELAY 5000
16 #define FOOD 100
17
18 void *philosopher (void *id);
19 void grab_chopstick (int,
20 int,
21 char *);
22 void down_chopsticks (int,
23 int);
24 int food_on_table ();
25 void get_token ();
26 void return_token ();
27
28 pthread_mutex_t chopstick[PHILOS];
29 pthread_t philo[PHILOS];
30 pthread_mutex_t food_lock;
31 int sleep_seconds = 0;
32 sem_t num_can_eat_sem;
33
34
35 int
36 main (int argn,
37 char **argv)
38 {
39 int i;
40
41 pthread_mutex_init (&food_lock, NULL);
42 sem_init(&num_can_eat_sem, 0, PHILOS - 1);
43 for (i = 0; i < PHILOS; i++)
44 pthread_mutex_init (&chopstick[i], NULL);
45 for (i = 0; i < PHILOS; i++)
46 pthread_create (&philo[i], NULL, philosopher, (void *)i);
47 for (i = 0; i < PHILOS; i++)
48 pthread_join (philo[i], NULL);
49 return 0;
50 }
51
52 void *
53 philosopher (void *num)
54 {
55 int id;
56 int i, left_chopstick, right_chopstick, f;
57
58 id = (int)num;
59 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
60 right_chopstick = id;
61 left_chopstick = id + 1;
62
63 /* Wrap around the chopsticks. */
64 if (left_chopstick == PHILOS)
65 left_chopstick = 0;
66
67 while (f = food_on_table ()) {
68 get_token ();
69
70 grab_chopstick (id, right_chopstick, "right ");
71 grab_chopstick (id, left_chopstick, "left");
72
73 printf ("Philosopher %d: eating.\n", id);
74 usleep (DELAY * (FOOD - f + 1));
75 down_chopsticks (left_chopstick, right_chopstick);
76
77 return_token ();
78 }
79
80 printf ("Philosopher %d is done eating.\n", id);
81 return (NULL);
82 }
83
84 int
85 food_on_table ()
86 {
87 static int food = FOOD;
88 int myfood;
89
90 pthread_mutex_lock (&food_lock);
91 if (food > 0) {
92 food--;
93 }
94 myfood = food;
95 pthread_mutex_unlock (&food_lock);
96 return myfood;
97 }
98
99 void
100 grab_chopstick (int phil,
101 int c,
102 char *hand)
103 {
104 pthread_mutex_lock (&chopstick[c]);
105 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
106 }
107
108 void
109 down_chopsticks (int c1,
110 int c2)
111 {
112 pthread_mutex_unlock (&chopstick[c1]);
113 pthread_mutex_unlock (&chopstick[c2]);
114 }
115
116
117 void
118 get_token ()
119 {
120 sem_wait(&num_can_eat_sem);
121 }
122
123 void
124 return_token ()
125 {
126 sem_post(&num_can_eat_sem);
127 }
This new implementation uses the semaphore num_can_eat_sem to limit the number of philosophers who can eat at the same time. The semaphore num_can_eat_sem is initialized to four, one less than the number of philosophers. Before attempting to eat, a philosopher calls get_token() which in turn calls sem_wait(&num_can_eat_sem). The call to sem_wait() causes the calling philosopher to wait until the semaphore's value is positive, then changes the semaphore's value by subtracting one from the value. When a philosopher is done eating, he calls return_token() which in turn calls sem_post(&num_can_eat_sem). The call to sem_post() changes the semaphore's value by adding one. The Thread Analyzer recognizes the calls to sem_wait() and sem_post(), and determines that not all philosophers attempt to eat concurrently.
Note - You must compile din_philo_fix2.c with -lrt to link with the appropriate semaphore routines.
To compile din_philo_fix2.c, use the following command:
cc -g -lrt -o din_philo_fix2 din_philo_fix2.c
If you run this new implementation of the program din_philo_fix2 several times, you will find that it terminates normally each time and does not hang.
To create an experiment on this new binary:
collect -r deadlock -o din_philo_fix2.1.er din_philo_fix2
You will find that the Thread Analyzer does not report any actual or potential deadlocks in the din_philo_fix2.1.er experiment, as the following figure shows.
Figure 3-7 Deadlocks Not Reported in din_philo_fix2.c
See Appendix A, APIs Recognized by the Thread Analyzer for a listing of the threading and memory allocation APIs that the Thread Analyzer recognizes.
|