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  /*
     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 -o din_philo_fix1.1.er din_philo_fix1 

A False Positive Report

Even when using the system of tokens, Thread Analyzer reports a potential deadlock for this implementation when 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 the Dual Source view 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 view 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 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 that Thread Analyzer recognizes.