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.

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. Thread Analyzer recognizes the calls to sem_wait() and sem_post(), and determines that not all philosophers attempt to eat concurrently.

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 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 Thread Analyzer for a listing of the threading and memory allocation APIs that Thread Analyzer recognizes.