ThreadMentor: The Dining Philosophers Problems: version 5

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 four versions. The first version that uses five mutex locks in a naive way could cause a deadlock. The lefty-righty version has at least one righty philosopher who always picks up his right chopstick first. The third version uses a semaphore that only allows four philosophers to sit down and eat. Using a monitor, the fourth version forces a philosopher to wait until both chopsticks are available. However, this version has a repeated wait which might not be very efficient. In this fifth version, we shall develop a more efficient solution based on the same idea.

Analysis

The key to this new version is the way of handling who can have two chopsticks and eat. Again, if philosopher i cannot eat, he is put to wait on condition variable self[i]. Moreover, a philosopher has three states: THINKING, HUNGRY and EATING. A philosopher is in state HUNGRY if he wants to eat but is not able to get any chopstick. More precisely, state HUNGRY means a philosopher is waiting to have his chopsticks.

When a philosopher tries to eat, his state becomes HUNGRY. Then, we test to see if this philosopher can eat. If the chopsticks are available, he can eat and his state becomes EATING. Otherwise, this philosopher simply blocks himself. On the other hand, when a philosopher finishes eating, he changes his state to THINKING, and informs his neighbors so that they have a chance to eat. The remaining question is that how do we design a testing procedure that is different from the previous solution.

This test procedure is very similar to CanEat() in the previous solution. Philosopher i can eat only if his left and right neighbors are not EATING and philosopher i himself is HUNGRY. If this condition is met, the state of philosopher i is changed to EATING and a signal is sent to self[i] to wake up philosopher i so that he can start to eat.

What is the difference between this version and method CanEat() in the previous solution? The main difference is that the states of a philosopher are used to determine if a philosopher can eat. In the previous solution, the test is based on if the chopsticks that a philosopher needs are available rather than based on the state of a philosopher. As a result, philosophers are forced to repeatedly examine if the chopsticks becomes available.

Program

The structure of this program is very similar to the previous one. The following is the monitor definition. We still have two methods, GetChopsticks() for requesting chopsticks and PutChopsticks() for releasing chopsticks. Private method Test() determines if a particular philosopher can eat.

#include "ThreadClass.h"

enum State { THINKING, HUNGRY, EATING };  // philosopher states

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

class PhilosopherMonitor: public Monitor 
{
     public:
          PhilosopherMonitor(char* Name);
          void  GetChopsticks(int PhilospherNumber);      //  pick up the chopstick
          void  PutChopsticks(int PhilospherNumber);      //  put down the chopstick

     private:
          void      Test(int Number);
          Condition *self[PHILOSOPHERNUM];
          State     state[PHILOSOPHERNUM];
};

The constructor sets every philosopher to THINKING, and creates condition variable self[]. Note that the constructor also makes this a Hoare monitor. The argument of method Test() is the number of a philosopher, Number. If philosopher Number is hungry and his two neighbors are not EATING, philosopher Number can eat. Therefore, the state of philosopher Number is set to EATING and condition variable self[Number] on which philosopher Number is waiting is signaled. Note that if philosopher Number is not waiting on condition variable self[Number] this signal is lost.

The GetChopsticks() method is simple. First, the calling philosopher Number is set to HUNGRY and calls method Test() to see if he can eat. If State[Number] is set to EATING by Test(), philosopher Number can eat. Otherwise, philosopher Number waits on condition variable self[Number] until is will be signaled in the future.

The PutChopsticks() method is called when a philosopher finishes eating. Therefore, in this method, the state of the calling philosopher is changed to THINKING. Because philosopher Number releases chopsticks Number and (Number+1)%PHILOSOPHERNUM, philosopher (Number+1)%PHILOSOPHERNUM and philosopher (Number+PHILOSOPHERNUM-1)%PHILOSOPHERNUM may have a chance to eat, where PHILOSOPHERNUM is the number of philosophers. To make sure this will happen, this philosopher uses Test((Number+PHILOSOPHERNUM-1)%PHILOSOPHERNUM) and Test((Number+1)%PHILOSOPHERNUM) to release his neighbors.

Why is a if used in GetChopsticks() rather than a while as we did in the previous solution. Recall that this is a Hoare monitor. When self[Number]->Signal() in method Test(Number) is executed, the caller is suspended, and philosopher Number is released and resumes its execution. As a result, no other philosopher can take philosopher Number's chopsticks away, and, a simple if is sufficient. What if this is a Mesa type monitor? Should we make any change? This is an important question for you to think about.

#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++) {
          state[i] = THINKING;    // initially, all philosophers are thinking
          strstream *ConditionName;
          ConditionName = new strstream;
          ConditionName->seekp(0, ios::beg);
          (*ConditionName) << "Self" << i << '\0';
          self[i] = new Condition(ConditionName->str());         
     }
}

void PhilosopherMonitor::Test(int Number)
{
     if (state[(Number+PHILOSOPHERNUM-1)%PHILOSOPHERNUM] != EATING &&  // left is not eating
         state[Number] == HUNGRY                                   &&  // I am hungry, and
         state[(Number+1)%PHILOSOPHERNUM] != EATING ) {                // right is not eating 
          state[Number] = EATING;       // philosopher Number can eat
          self[Number]->Signal();       // wake him up
     }
}

void PhilosopherMonitor::GetChopsticks(int Number)
{
     MonitorBegin();
     state[Number] = HUNGRY;       // I am hungry
     Test(Number);                 // Test if I can eat
     if (state[Number] != EATING)  // if the test result says no, 
          self[Number]->Wait();    // then wait
     MonitorEnd();                 // finally, I can eat
}

void  PhilosopherMonitor::PutChopsticks(int Number)
{
     MonitorBegin();
     state[Number] = THINKING;          // go back to thinking
     Test((Number+PHILOSOPHERNUM-1) % PHILOSOPHERNUM); // let my left neighbor eat
     Test((Number+1)%PHILOSOPHERNUM);   // let my right neighbor eat
     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 his neighbors are not eating, the situation in which a philosopher holds a chopstick and waits for the second can never occur. 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: