Chapter 3 The Deadlock Tutorial
This tutorial explains how to use the Thread Analyzer to detect potential, as well as actual, deadlocks in your multi-threaded program. The term 'deadlock' describes a condition in which two or more threads are blocked (hung) forever because they are waiting for each other. There are many causes of deadlocks such as erroneous program logic, inappropriate use of synchronizations and barriers. This tutorial focuses on deadlocks that are caused by the inappropriate use of mutual exclusion locks. This type of deadlock is commonly encountered in multi-threaded applications. A process with two or more threads can enter deadlock when the following three conditions hold:
-
Threads that are already holding locks request new locks
-
The requests for new locks are made concurrently
-
Two or more threads form a circular chain in which each thread waits for a lock which is held by the next thread in the chain
Here is a simple example of a deadlock condition:
|
Thread 1 holds lock A and requests lock B |
|
Thread 2 holds lock B and requests lock A |
A deadlock can be of two types: A potential deadlock or an actual deadlock and they are distinguished as follows:
-
A potential deadlock does not necessarily occur in a given run, but can occur in any execution of the program depending on the scheduling of threads and the timing of lock requests by the threads
-
An actual deadlock is one that occurs during the execution of a program. An actual deadlock causes the threads involved to hang, but may or may not cause the whole process to hang.
3.1 The Dining Philosophers Source File
The sample program which simulates the dining-philosophers problem is a C program that uses POSIX threads. The source file is called din_philo.c. The program can exhibit both potential and actual deadlocks. Here is the listing of the code which is followed by an explanation:
/* din_philo.c */
1 #include <pthread.h>
2 #include <stdio.h>
3 #include <unistd.h>
4 #include <stdlib.h>
5 #include <errno.h>
6 #include <assert.h>
7
8 #define PHILOS 5
9 #define DELAY 5000
10 #define FOOD 50
11
12 void *philosopher (void *id);
13 void grab_chopstick (int,
14 int,
15 char *);
16 void down_chopsticks (int,
17 int);
18 int food_on_table ();
19
20 pthread_mutex_t chopstick[PHILOS];
21 pthread_t philo[PHILOS];
22 pthread_mutex_t food_lock;
23 int sleep_seconds = 0;
24
25
26 int
27 main (int argn,
28 char **argv)
29 {
30 int i;
31
32 if (argn == 2)
33 sleep_seconds = atoi (argv[1]);
34
35 pthread_mutex_init (&food_lock, NULL);
36 for (i = 0; i < PHILOS; i++)
37 pthread_mutex_init (&chopstick[i], NULL);
38 for (i = 0; i < PHILOS; i++)
39 pthread_create (&philo[i], NULL, philosopher, (void *)i);
40 for (i = 0; i < PHILOS; i++)
41 pthread_join (philo[i], NULL);
42 return 0;
43 }
44
45 void *
46 philosopher (void *num)
47 {
48 int id;
49 int i, left_chopstick, right_chopstick, f;
50
51 id = (int)num;
52 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
53 right_chopstick = id;
54 left_chopstick = id + 1;
55
56 /* Wrap around the chopsticks. */
57 if (left_chopstick == PHILOS)
58 left_chopstick = 0;
59
60 while (f = food_on_table ()) {
61
62 /* Thanks to philosophers #1 who would like to take a nap
63 * before picking up the chopsticks, the other philosophers
64 * may be able to eat their dishes and not deadlock.
65 */
66 if (id == 1)
67 sleep (sleep_seconds);
68
69 grab_chopstick (id, right_chopstick, "right ");
70 grab_chopstick (id, left_chopstick, "left");
71
72 printf ("Philosopher %d: eating.\n", id);
73 usleep (DELAY * (FOOD - f + 1));
74 down_chopsticks (left_chopstick, right_chopstick);
75 }
76
77 printf ("Philosopher %d is done eating.\n", id);
78 return (NULL);
79 }
80
81 int
82 food_on_table ()
83 {
84 static int food = FOOD;
85 int myfood;
86
87 pthread_mutex_lock (&food_lock);
88 if (food > 0) {
89 food--;
90 }
91 myfood = food;
92 pthread_mutex_unlock (&food_lock);
93 return myfood;
94 }
95
96 void
97 grab_chopstick (int phil,
98 int c,
99 char *hand)
100 {
101 pthread_mutex_lock (&chopstick[c]);
102 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
103 }
104
105 void
106 down_chopsticks (int c1,
107 int c2)
108 {
109 pthread_mutex_unlock (&chopstick[c1]);
110 pthread_mutex_unlock (&chopstick[c2]);
111 }
3.2 The Dining Philosophers Scenario
The dining philosophers scenario is a classic which is structured as follows. Five philosophers, numbered zero to four, are sitting at a round table, thinking. As time passes, different individuals become hungry and decide to eat. There is a platter of noodles on the table but each philosopher only has one chopstick to use. In order to eat, they must share chopsticks. The chopstick to the left of each philosopher (as they sit facing the table) has the same number as that philosopher.
Each philosopher first reaches for his own chopstick which is the one with his number. When he has his assigned chopstick, he reaches for the chopstick assigned to his neighbor. After he has both chopsticks, he can eat. After eating, he returns the chopsticks to their original positions on the table, one on either side. The process is repeated until there are no more noodles.
3.2.1 How the Philosophers Can Deadlock
An actual deadlock occurs when every philosopher is holding his own chopstick and waiting for the one from his neighbor to become available:
|
Philosopher zero is holding chopstick zero, but is waiting for chopstick one |
|
Philosopher one is holding chopstick one, but is waiting for chopstick two |
|
Philosopher two is holding chopstick two, but is waiting for chopstick three |
|
Philosopher three is holding chopstick three, but is waiting for chopstick four |
|
Philosopher four is holding chopstick four, but is waiting for chopstick zero |
In this situation, nobody can eat and the philosophers are in a deadlock. Rerun the program a number of times and you will see that the program may sometimes hang, or run to completion at other times.
Run the dining philosophers program and see whether it completes or deadlocks. It may hang as shown in the following sample run:
prompt% cc din_phil.c -mt prompt% a.out Philosopher 0 is done thinking and now ready to eat. Philosopher 2 is done thinking and now ready to eat. Philosopher 2: got right chopstick 2 Philosopher 2: got left chopstick 3 Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 4 is done thinking and now ready to eat. Philosopher 4: got right chopstick 4 Philosopher 2: eating. Philosopher 3 is done thinking and now ready to eat. Philosopher 1 is done thinking and now ready to eat. Philosopher 0: got right chopstick 0 Philosopher 3: got right chopstick 3 Philosopher 2: got right chopstick 2 Philosopher 1: got right chopstick 1 (hang) Execution terminated by pressing CTRL-C
3.2.2 Introducing a Sleep Time for Philosopher One
One possible solution to the deadlock potential is for philosopher one to wait before reaching for his chopstick. In terms of the code, he can be put to sleep for a specified amount of time (sleep_seconds) before reaching for his chopstick. If he sleeps long enough, then the program may finish without any actual deadlock. You can specify the number of seconds he sleeps as an argument to the executable. If you do not specify an argument, the philosopher does not sleep.
The following pseudo-code shows the logic for each philosopher:
while (there is still food on the table)
{
if (sleep argument is specified and I am philosopher #1)
{
sleep specified amount of time
}
grab right fork
grab left fork
eat some food
put down left fork
put down right fork
}
The following listing shows one run of the program in which philosopher one waits 30 seconds before reaching for his chopstick. The program runs to completion and all five philosophers finish eating.
% a.out 30 Philosopher 0 is done thinking and now ready to eat. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 4 is done thinking and now ready to eat. Philosopher 4: got right chopstick 4 Philosopher 3 is done thinking and now ready to eat. Philosopher 3: got right chopstick 3 Philosopher 0: eating. Philosopher 2 is done thinking and now ready to eat. Philosopher 2: got right chopstick 2 Philosopher 1 is done thinking and now ready to eat. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. ... Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0 is done eating. Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 4 is done eating. Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 3 is done eating. Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 2 is done eating. Philosopher 1: got right chopstick 1 Philosopher 1: got left chopstick 2 Philosopher 1: eating. Philosopher 1 is done eating. % Execution terminated normally
Try running the program several times and specifying different sleep arguments. What happens when philosopher one waits only a short time before reaching for his chopstick? How about when he waits longer? Try specifying different sleep arguments to the executable a.out. Rerun the program with or without a sleep argument several times. Sometimes the program hangs, while it runs to completion at other times. Whether the program hangs or not depends on the scheduling of threads and the timings of requests for locks by the threads.
3.3 How to Use the Thread Analyzer to Find Deadlocks
You can use the thread Analyzer to check for potential and actual deadlocks in your program. The Thread Analyzer follows the same "collect-analyze" model that the Sun Studio Performance Analyzer uses. There are three steps involved in using the Thread Analyzer:
-
Compile the source code.
-
Create a deadlock-detection Experiment.
-
Examine the experiment results.
3.3.1 Compile the Source Code
Compile your code and be sure to specify -g. Do not specify a high-level of optimization because information such as line numbers and callstacks, may be reported incorrectly at a high optimization level. Compile an OpenMP program with -g -xopenmp=noopt, and compile a POSIX threads program with just -g -mt.
See cc.1, CC.1, or f95.1 for more information.
3.3.2 Create a Deadlock-Detection Experiment
Use the Thread Analyzer's collect command with the -r deadlock option. This option creates a deadlock-detection experiment during the execution of the program.
You can increase the likelihood of detecting deadlocks by creating several deadlock-detection experiments. Use a different number of threads and different input data for the various experiments.
See collect.1 and collector.1 for more information.
3.3.3 Examine the Experiment Results
You can examine the deadlock-detection experiment with either the tha command, the analyzer command, or the er_print utility. Both the Thread Analyzer and
the Analyzer present a GUI interface while er_print employes a command-line interface.
See tha.1, analyzer.1, and er_print.1 for more information.
3.3.3.1 The Thread Analyzer Interface
The Thread Analyzer includes a menu bar, a tool bar, and a split pane that contains tabs for the various displays. The following three tabs are shown by default in the left-hand pane:
-
The Deadlocks tab
This tab shows a list of potential and actual deadlocks that the Thread Analyzer detected in the program. This tab is selected by default. The threads involved for each deadlock are shown. These threads form a circular chain where each thread holds a lock and requests another lock that the next thread in the chain holds.
-
The Dual Source tab
Select a thread in the circular chain and then click on the Dual Source tab. The Dual Source tab shows the source location where the thread held a lock, and the source location where the same thread requested a lock. The source lines where the thread held and requested locks are highlighted.
-
The Experiments tab
This tab shows the load objects in the experiment, and lists any error and warning messages. The following two tabs are shown on the right-hand pane of the Thread Analyzer display:
-
The Summary tab which shows summary information about a deadlock selected from the Deadlocks tab.
-
The Deadlock Details tab which shows detailed information about a thread context selected from the Deadlocks tab.
-
3.3.3.2 The er_print Interface
In contrast to the left-hand pane, the right-hand pane contains the
Deadlock Details tab which shows detailed information for the selected thread
in the Deadlocks tab. The most useful subcommands for examining deadlocks
with er_print are the following:
-
-deadlocks
The option reports any potential and actual deadlocks detected in the experiment.
-
-ddetail deadlock_id
This option returns detailed information about the deadlock with the specified deadlock_id. If you specify the value all as the deadlock_id, then
er_printdisplays detailed information about all deadlocks. -
-header
This option displays descriptive information about the experiment and reports any errors or warnings.
See er_print.1 for more information.
3.4 Understanding the Experiment Results
This section explains how to use the Thread Analyzer to investigate the deadlocks in the dining philosopher program. We'll start by executing runs that result in actual deadlocks and then examine runs that terminate normally but have the potential for deadlocks.
3.4.1 Examining Runs That Deadlock
The following listing shows a run of the dining philosophers program that results in an actual deadlock.
prompt% cc din_philo.c -mt -g prompt% collect -r deadlock a.out Creating experiment database tha.1.er ... Philosopher 1 is done thinking and now ready to eat. Philosopher 2 is done thinking and now ready to eat. Philosopher 3 is done thinking and now ready to eat. Philosopher 0 is done thinking and now ready to eat. Philosopher 1: got right chopstick 1 Philosopher 3: got right chopstick 3 Philosopher 0: got right chopstick 0 Philosopher 1: got left chopstick 2 Philosopher 3: got left chopstick 4 Philosopher 4 is done thinking and now ready to eat. Philosopher 1: eating. Philosopher 3: eating. Philosopher 3: got right chopstick 3 Philosopher 4: got right chopstick 4 Philosopher 2: got right chopstick 2 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 1: got right chopstick 1 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 3: got right chopstick 3 Philosopher 1: got left chopstick 2 Philosopher 1: eating. Philosopher 2: got right chopstick 2 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 1: got right chopstick 1 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 3: got right chopstick 3 Philosopher 1: got left chopstick 2 Philosopher 1: eating. Philosopher 2: got right chopstick 2 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 1: got right chopstick 1 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 2: got right chopstick 2 Philosopher 3: got right chopstick 3 (hang) Execution terminated by pressing CTRL-C % er_print tha.1.er (er_print) deadlocks Deadlock #1, Potential deadlock Thread #2 Lock being held: 0x215a8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215c0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #3 Lock being held: 0x215c0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215d8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #4 Lock being held: 0x215d8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215f0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #5 Lock being held: 0x215f0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x21608, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #6 Lock being held: 0x21608, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215a8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Deadlock #2, Actual deadlock Thread #2 Lock being held: 0x215a8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215c0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #3 Lock being held: 0x215c0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215d8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #4 Lock being held: 0x215d8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215f0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #5 Lock being held: 0x215f0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x21608, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #6 Lock being held: 0x21608, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215a8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Deadlocks List Summary: Experiment: tha.1.er Total Deadlocks: 2 (er_print)
The following screen-shot shows the Thread Analyzer's presentation of the deadlock information:
The Thread Analyzer reports two deadlocks for din_philo.c, one potential and the other actual. On closer inspection, we find that the two deadlocks are identical. The circular chain involved in the deadlock is as follows:
|
Thread 2: holds lock at address |
|
Thread 3: holds lock at address |
|
Thread 4: holds lock at address |
|
Thread 5: holds lock at address |
|
Thread 6: holds lock at address |
Select the first thread in the chain (Thread #2) and then click on the
Dual Source tab to see where in the source code Thread #2 held the lock at
address 0x215a8, and where in the source code it
requested the lock at address 0x215c0. The following
screen-shot shows the Dual Source tab for thread number two. The default metric
(Exclusive Deadlocks metric) is shown to the left of each source line. This
metric gives a count of the number of times a lock-hold or lock-request operation,
which was involved in a deadlock, was reported on that line.
3.4.2 Examining Runs That Complete Despite Deadlock Potential
The dining philosophers program can avoid actual deadlock and terminate
normally if you supply a large enough sleep argument. Normal termination,
however, does not mean the program is safe from deadlocks. It simply means
that the locks held and requested did not form a deadlock chain during a given
run. If the timing changes in other runs, an actual deadlock can occur. The
following listing shows a run of the dining philosophers program that terminates
normally. However, the er_print utility and the
Thread Analyzer report potential deadlocks.
% cc din_philo.c -mt -g % collect -r deadlock a.out 40 Creating experiment database tha.2.er ... Philosopher 0 is done thinking and now ready to eat. Philosopher 2 is done thinking and now ready to eat. Philosopher 1 is done thinking and now ready to eat. Philosopher 3 is done thinking and now ready to eat. Philosopher 2: got right chopstick 2 Philosopher 3: got right chopstick 3 Philosopher 0: got right chopstick 0 Philosopher 4 is done thinking and now ready to eat. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 0: got right chopstick 0 Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 3: got right chopstick 3 Philosopher 2: got right chopstick 2 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 4: got right chopstick 4 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 3: got right chopstick 3 Philosopher 2: got right chopstick 2 Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 0: got right chopstick 0 Philosopher 2: got left chopstick 3 Philosopher 2: eating. ... Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 4: got right chopstick 4 Philosopher 3: got right chopstick 3 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 0: got right chopstick 0 Philosopher 3: got left chopstick 4 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 3: eating. Philosopher 0: got right chopstick 0 Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 4: got right chopstick 4 Philosopher 3: got right chopstick 3 Philosopher 2: got right chopstick 2 Philosopher 4: got left chopstick 0 Philosopher 4: eating. Philosopher 4 is done eating. Philosopher 3: got left chopstick 4 Philosopher 3: eating. Philosopher 0: got right chopstick 0 Philosopher 0: got left chopstick 1 Philosopher 0: eating. Philosopher 3 is done eating. Philosopher 2: got left chopstick 3 Philosopher 2: eating. Philosopher 0 is done eating. Philosopher 2 is done eating. Philosopher 1: got right chopstick 1 Philosopher 1: got left chopstick 2 Philosopher 1: eating. Philosopher 1 is done eating. % Execution terminated normally % er_print tha.2.er (er_print) deadlocks Deadlock #1, Potential deadlock Thread #2 Lock being held: 0x215a8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215c0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #3 Lock being held: 0x215c0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215d8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #4 Lock being held: 0x215d8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215f0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #5 Lock being held: 0x215f0, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x21608, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Thread #6 Lock being held: 0x21608, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Lock being requested: 0x215a8, at: grab_chopstick + 0x0000002C, line 101 in "din_philo.c" Deadlocks List Summary: Experiment: tha.2.er Total Deadlocks: 1 (er_print)
The following screen-shot shows the potential deadlock information in the Thread Analyzer interface:
3.5 Fixing the Deadlocks and Understanding False-Positives
In addition to the strategy of philosophers waiting before they start to eat, we can use a system of tokens in which 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.
3.5.1 Regulating the Philosophers With 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:
1 #include <pthread.h>
2 #include <stdio.h>
3 #include <unistd.h>
4 #include <stdlib.h>
5 #include <errno.h>
6 #include <assert.h>
7
8 #define PHILOS 5
9 #define DELAY 5000
10 #define FOOD 50
11
12 void *philosopher (void *id);
13 void grab_chopstick (int,
14 int,
15 char *);
16 void down_chopsticks (int,
17 int);
18 int food_on_table ();
19 int get_token ();
20 void return_token ();
21
22 pthread_mutex_t chopstick[PHILOS];
23 pthread_t philo[PHILOS];
24 pthread_mutex_t food_lock;
25 pthread_mutex_t num_can_eat_lock;
26 int sleep_seconds = 0;
27 uint32_t num_can_eat = PHILOS - 1;
28
29
30 int
31 main (int argn,
32 char **argv)
33 {
34 int i;
35
36 pthread_mutex_init (&food_lock, NULL);
37 pthread_mutex_init (&num_can_eat_lock, NULL);
38 for (i = 0; i < PHILOS; i++)
39 pthread_mutex_init (&chopstick[i], NULL);
40 for (i = 0; i < PHILOS; i++)
41 pthread_create (&philo[i], NULL, philosopher, (void *)i);
42 for (i = 0; i < PHILOS; i++)
43 pthread_join (philo[i], NULL);
44 return 0;
45 }
46
47 void *
48 philosopher (void *num)
49 {
50 int id;
51 int i, left_chopstick, right_chopstick, f;
52
53 id = (int)num;
54 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
55 right_chopstick = id;
56 left_chopstick = id + 1;
57
58 /* Wrap around the chopsticks. */
59 if (left_chopstick == PHILOS)
60 left_chopstick = 0;
61
62 while (f = food_on_table ()) {
63 get_token ();
64
65 grab_chopstick (id, right_chopstick, "right ");
66 grab_chopstick (id, left_chopstick, "left");
67
68 printf ("Philosopher %d: eating.\n", id);
69 usleep (DELAY * (FOOD - f + 1));
70 down_chopsticks (left_chopstick, right_chopstick);
71
72 return_token ();
73 }
74
75 printf ("Philosopher %d is done eating.\n", id);
76 return (NULL);
77 }
78
79 int
80 food_on_table ()
81 {
82 static int food = FOOD;
83 int myfood;
84
85 pthread_mutex_lock (&food_lock);
86 if (food > 0) {
87 food--;
88 }
89 myfood = food;
90 pthread_mutex_unlock (&food_lock);
91 return myfood;
92 }
93
94 void
95 grab_chopstick (int phil,
96 int c,
97 char *hand)
98 {
99 pthread_mutex_lock (&chopstick[c]);
100 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
101 }
102
103 void
104 down_chopsticks (int c1,
105 int c2)
106 {
107 pthread_mutex_unlock (&chopstick[c1]);
108 pthread_mutex_unlock (&chopstick[c2]);
109 }
110
111
112 int
113 get_token ()
114 {
115 int successful = 0;
116
117 while (!successful) {
118 pthread_mutex_lock (&num_can_eat_lock);
119 if (num_can_eat > 0) {
120 num_can_eat--;
121 successful = 1;
122 }
123 else {
124 successful = 0;
125 }
126 pthread_mutex_unlock (&num_can_eat_lock);
127 }
128 }
129
130 void
131 return_token ()
132 {
133 pthread_mutex_lock (&num_can_eat_lock);
134 num_can_eat++;
135 pthread_mutex_unlock (&num_can_eat_lock);
136 }
Try compiling and running 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.
3.5.1.1 A False-Positive Report
In spite of 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:
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 0x215a8, and where in the source
code it requested the lock at address 0x215c0. The
following screen-shot shows the Dual Source tab for Thread #2.
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.
3.5.2 An Alternative System of Tokens
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.
Note –
You must compiler din_philo_fix2.c with -lrt to link with the appropriate semaphore routines.
The following listing details din_philo_fix2.c:
1 #include <pthread.h>
2 #include <stdio.h>
3 #include <unistd.h>
4 #include <stdlib.h>
5 #include <errno.h>
6 #include <assert.h>
7 #include <semaphore.h>
8
9 #define PHILOS 5
10 #define DELAY 5000
11 #define FOOD 50
12
13 void *philosopher (void *id);
14 void grab_chopstick (int,
15 int,
16 char *);
17 void down_chopsticks (int,
18 int);
19 int food_on_table ();
20 int get_token ();
21 void return_token ();
22
23 pthread_mutex_t chopstick[PHILOS];
24 pthread_t philo[PHILOS];
25 pthread_mutex_t food_lock;
26 int sleep_seconds = 0;
27 sem_t num_can_eat_sem;
28
29
30 int
31 main (int argn,
32 char **argv)
33 {
34 int i;
35
36 pthread_mutex_init (&food_lock, NULL);
37 sem_init(&num_can_eat_sem, 0, PHILOS - 1);
38 for (i = 0; i < PHILOS; i++)
39 pthread_mutex_init (&chopstick[i], NULL);
40 for (i = 0; i < PHILOS; i++)
41 pthread_create (&philo[i], NULL, philosopher, (void *)i);
42 for (i = 0; i < PHILOS; i++)
43 pthread_join (philo[i], NULL);
44 return 0;
45 }
46
47 void *
48 philosopher (void *num)
49 {
50 int id;
51 int i, left_chopstick, right_chopstick, f;
52
53 id = (int)num;
54 printf ("Philosopher %d is done thinking and now ready to eat.\n", id);
55 right_chopstick = id;
56 left_chopstick = id + 1;
57
58 /* Wrap around the chopsticks. */
59 if (left_chopstick == PHILOS)
60 left_chopstick = 0;
61
62 while (f = food_on_table ()) {
63 get_token ();
64
65 grab_chopstick (id, right_chopstick, "right ");
66 grab_chopstick (id, left_chopstick, "left");
67
68 printf ("Philosopher %d: eating.\n", id);
69 usleep (DELAY * (FOOD - f + 1));
70 down_chopsticks (left_chopstick, right_chopstick);
71
72 return_token ();
73 }
74
75 printf ("Philosopher %d is done eating.\n", id);
76 return (NULL);
77 }
78
79 int
80 food_on_table ()
81 {
82 static int food = FOOD;
83 int myfood;
84
85 pthread_mutex_lock (&food_lock);
86 if (food > 0) {
87 food--;
88 }
89 myfood = food;
90 pthread_mutex_unlock (&food_lock);
91 return myfood;
92 }
93
94 void
95 grab_chopstick (int phil,
96 int c,
97 char *hand)
98 {
99 pthread_mutex_lock (&chopstick[c]);
100 printf ("Philosopher %d: got %s chopstick %d\n", phil, hand, c);
101 }
102
103 void
104 down_chopsticks (int c1,
105 int c2)
106 {
107 pthread_mutex_unlock (&chopstick[c1]);
108 pthread_mutex_unlock (&chopstick[c2]);
109 }
110
111
112 int
113 get_token ()
114 {
115 sem_wait(&num_can_eat_sem);
116 }
117
118 void
119 return_token ()
120 {
121 sem_post(&num_can_eat_sem);
122 }
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.
If you run this new implementation of the program several times, you will find that it terminates normally each time and does not hang. You will also find that the Thread Analyzer does not report any actual or potential deadlocks, as the following screen-shot shows:
See Appendix A, Thread Analyzer User API for a listing of the threading and memory allocation APIs that the Thread Analyzer recognizes.
- © 2010, Oracle Corporation and/or its affiliates