Sun Studio 12: Thread Analyzer User's Guide

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:

A screen-shot of the Thread Analyzer window which shows
a deadlock in thread number two.

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.

A screen shot of the Thread Analyzer's Dual-Source tab
which shows a potential deadlock.

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:

A screen shot of the Thread Analyzer window which shows
no deadlocks.

See Appendix A, Thread Analyzer User API for a listing of the threading and memory allocation APIs that the Thread Analyzer recognizes.