ThreadMentor: The Dining Philosophers Problems: Revisited

Problem

The dining philosophers problem is invented by E. W. Dijkstra. Imagine that five philosophers who spend their lives just thinking and easting. In the middle of the dining room is a circular table with five chairs. The table has a big plate of spaghetti. However, there are only five chopsticks available, as shown in the following figure. Each philosopher thinks. When he gets hungry, he sits down and picks up the two chopsticks that are closest to him. If a philosopher can pick up both chopsticks, he eats for a while. After a philosopher finishes eating, he puts down the chopsticks and starts to think.

Previously, we discussed an example that uses five mutex locks. However, that solution may cause a deadlock. Then, the lefty-righty version in which there is at least one righty philosopher who always picks up his right chopstick first is introduced. Using semaphores, we have yet another version in which only four philosophers can sit down and eat. We pointed out and showed that these two versions are deadlock-free. In this example, we shall present yet another deadlock-free solution using a monitor.

Analysis

In all previous solutions, a philosopher picks his chopsticks one-by-one. This could cause a deadlock if the activity of picking up chopsticks is not coordinated properly. How about a philosopher picks up both chopsticks as a single unit? More precisely, a philosopher can eat only if he can pick up both chopsticks at the same time? Thus, if a philosopher sees both chopsticks are available, he takes them and easts. Otherwise, he waits until his chopsticks will become available. After eating, a philosopher releases his chopsticks.

How do we implement this strategy? To determine if both chopsticks are available to a particular philosopher, we may use an array ChopStick[5]. If ChopStick[i] is AVAILABLE, chopstick i is free. Therefore, philosopher i must check to see if ChopStick[i] and ChopStick[(i+1)%5] are both AVAILABLE. If they are, philosopher i can take them and eat. If they are not available, philosopher i must wait on his own condition variable until another philosopher wakes him up in the future. Note that because the monitor boundary provides a natural mutual exclusion, there is no need to protect various variables while they are being accessed.

When philosopher i finishes eating, he can set ChopStick[i] and ChopStick[(i+1)%5] to AVAILABLE to indicate that both chopsticks are free. Is this sufficient? No, because philosopher i's neighbors may be waiting for these chopsticks, he must inform his neighbors about this fact.

Program

The monitor interface is shown below. We have two methods, GetChopsticks() for requesting chopsticks and PutChopsticks() for returning chopsticks. Array ChopStick[PHILOSOPHERNUM], where PHILOSOPHERNUM is the number of philosophers, stores the status of each chopstick (i.e., AVAILABLE or NOT_AVAILABLE). We also have five condition variables, declared as five pointers, in array WaitChopStick[]. Philosopher i waits on condition variable *WaitChopStick[i] until he is signaled by another philosopher. Finally, private method CanEat() checks to see if a philosopher has his chopsticks and can eat.

#include "ThreadClass.h"

#define AVAILABLE        1
#define NOT_AVAILABLE    0

//------------------------------------------------------------------------
// PhilosopherMonitor class definition
//------------------------------------------------------------------------

class PhilosopherMonitor: public Monitor 
{
     public:
          PhilosopherMonitor(char* Name);

          void  GetChopsticks(int Number);
          void  PutChopsticks(int Number);

     private:
          Condition *WaitChopStick[PHILOSOPHERNUM];
          int ChopStick[PHILOSOPHERNUM];
          int CanEat(int Number);
};

The following is the implementation of the monitor methods. The constructor is easy. It creates all condition variables and initializes the status array ChopStick[].

Method CanEat() takes Number as its only argument and tests if the chopsticks that philosopher Number needs are available. The return value is 1, if both chopsticks for philosopher Number are available; otherwise, the return value is 0.

Method GetChopsticks() has one argument, the calling philosopher's number. This method calls CanEat() to determine if philosopher Number can eat. If one of his needed chopsticks is not available, this philosopher waits on condition variable *WaitChopStick[Number] until it is signaled by one of his neighboring philosophers who finishes eating. Then, this philosopher changes the status of ChopStick[Number] and ChopStick[(Number+1)%PHILOSOPHERNUM] to NOT_AVAILABLE, meaning these two chopsticks are taken. When this method returns, philosopher Number has the needed chopsticks and eats. But, the question is: why we use a while rather than a if. This will be clear soon.

Let us examine method PutChopsticks(). The caller (i.e., philosopher Number) sends in its number. The first thing to do is setting his two chopsticks, ChopStick[Number] and ChopStick[(Number+1)%PHILOSOPHERNUM], to AVAILABLE. After this, this philosopher signals his left neighbor (i.e., WaitChopStick[(Number+PHILOSOPHERNUM-1)%PHILOSOPHERNUM]->Signal()) and his right neighbor (i.e., WaitChopStick[(Number+1)%PHILOSOPHERNUM]->Signal()) for them to use the released chopsticks. Once this is done, the left and right neighbors of philosopher Number are released from their condition variables.

Now we can explain why a while rather than a if is used in method GetChopsticks(). Suppose philosopher 3 calls method GetChopsticks(). Suppose further that method CanEat finds out the chopsticks that philosopher 3 needs (i.e., 3 and 4) are not available (i.e., philosophers 2 and 4 are eating). As a result, philosopher 3 waits on condition variable WaitChopStick[3]. Sometime later, philosopher 2 calls method PutChopsticks(), sets chopsticks 2 and 3 to available, and signals WaitChopStick[1] and WaitChopStick[3]. As a result, philosopher 3 is released. If we use a if, philosopher 3 will set chopsticks 3 and 4 to not available. However, it is possible that philosopher 4 is still eating, and chopstick 4 is being used by both philosophers 3 and 4 at the same time, which is incorrect. This is the reason we use a while to force philosopher 3 to go back and make sure both chopsticks he needs are available. Thus, even though we declare this monitor to be a Hoare monitor, its inner working actually follows the Mesa type.

In the above, philosopher 2 also signals his left neighbor, philosopher 1. What if philosopher 1 is not even in the monitor (i.e. has finished eating and left the monitor)? No problem. With a monitor, the signal to a condition variable on which no thread is waiting is ignored as if this signal never occurs. Check here for a review of the differences between semaphores and monitor.

#include <iostream.h>
#include <stdlib.h>
#include "ThreadClass.h"
#include "Philosopher-Thrd.h"
#include "Philosopher-mon.h"

PhilosopherMonitor::PhilosopherMonitor(char* Name)
                    : Monitor(Name, HOARE) 
{
     for (int i = 0; i < PHILOSOPHERNUM; i++) {
          strstream *ConditionName;
          ConditionName = new strstream;
          ConditionName->seekp(0, ios::beg);
          (*ConditionName) << "WaitChopStick" << i << '\0';
          WaitChopStick[i] = new Condition(ConditionName->str());
          ChopStick[i] = AVAILABLE;
     }
}

int PhilosopherMonitor::CanEat(int Number)
{
     if ((ChopStick[Number] == AVAILABLE) && 
         (ChopStick[(Number+1)%PHILOSOPHERNUM] == AVAILABLE))
          return 1;      // if both chopsticks are available, return 1
     else
          return 0;      // otherwise, return 0
}

void PhilosopherMonitor::GetChopsticks(int Number)
{
     MonitorBegin();
     while (!CanEat(Number))                 // wait if both chops 
          WaitChopStick[Number]->Wait();     // are not available
     ChopStick[Number] = NOT_AVAILABLE;      // got them, set to unavailable
     ChopStick[(Number+1)%PHILOSOPHERNUM] = NOT_AVAILABLE;
     MonitorEnd();
}

void  PhilosopherMonitor::PutChopsticks(int Number)
{
     MonitorBegin();
     ChopStick[Number]=AVAILABLE;       // put back two chopsticks
     ChopStick[(Number+1)%PHILOSOPHERNUM]=AVAILABLE;
     WaitChopStick[(Number+1)%PHILOSOPHERNUM]->Signal();  // right neighbor
     WaitChopStick[(Number+PHILOSOPHERNUM-1)%PHILOSOPHERNUM]->Signal(); // left
     MonitorEnd();
}

Will deadlock occur? To have a deadlock, the involved philosophers must have a pattern of circular waiting (i.e., philosopher a has a chopstick that philosopher b needs, philosopher b has a chopstick that philosopher c needs, and philosopher c has a chopstick that philosopher a needs). Since a philosopher can eat only if he has both chopsticks, the situation in which a philosopher holds a chopstick and waits for the other can never occur, and two neighboring philosophers never eat at the same time. Consequently, deadlock cannot happen.

The declaration and creation of threads and the main program are similar to the other versions and their discussions are omitted. Click the following file names to retrieve a copy of the thread component and the main program: