ThreadMentor: The Dining Philosophers Problem with Four Chairs

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 philosophers who always picks up his right chopstick first is introduced. We pointed out and showed that this lefty-righty version is deadlock-free. In this example, we shall present yet another deadlock-free solution.

Analysis

The deadlock of the simple solution is caused by all five philosophers picking up their left chopsticks at the same time. An obvious way to break this circular waiting is to only allow no more than four philosophers to sit down at the same time. As a result, even though all four of them pick up their left chopsticks, the last one of this four will have his right chopstick and eat as shown below. In fact, it is easy to see that if there are less than four philosophers sitting down simultaneously, no deadlock can occur.

This observation provides us with an easy way to overcome deadlock. We simply allow no more than four philosophers to sit down! In other word, we need a mechanism with which the fifth philosopher will be blocked after four have already sit down. This is exactly the countdown and lock technique. We need a semaphore initialized to four. Each philosopher must wait on this semaphore before he can pick up chopsticks. After eating, each philosopher must signal this semaphore to release his chair. Other than this additional effort, everything is identical to that of the original version.

Program

The class definition is identical to the previous version. Since each philosopher should be run as a thread, we define a Philosopher class as a derived class of class Thread.

#include "ThreadClass.h"

#define NUM_OF_PHILOSOPHERS   5

class Philosopher: public Thread 
{
     public:
          Philosopher(int Number, int iter);  // constructor
     private:
          int No;     // position of the philosopher
          int Iteration;
          void ThreadFunc();
};

The constructor takes two arguments, Number for the number assigned to this philosopher thread, and iter for specifying the number of thinking-eating cycles.

Each chopstick is protected by a mutex lock. To avoid initializing these locks in the main program as in the previous version, we declare them individually and store the pointer to each lock in an array. In addition, we have a semaphore FourChairs, with initial value 4, to count down and lock. These locks and semaphore are declared to be static so that they are not visible in other program files.

Function ThreadFunc() receives a very minor modification. That is, statements for picking up chopsticks, eating, and putting down chopsticks are unchanged and placed between acquiring and releasing a chair that is controlled by semaphore FourChairs. Since this semaphore has an initial value of 4, at most four threads can be executing between its Wait() and Signal() calls. Therefore, no deadlock will occur.

#include <iostream>

#include "Philosopher-4chairs.h"

static Semaphore FourChairs("FourChairs", NUM_OF_PHILOSOPHERS - 1);
static Mutex Chopstick1("Chopstick1");
static Mutex Chopstick2("Chopstick2");
static Mutex Chopstick3("Chopstick3");
static Mutex Chopstick4("Chopstick4");
static Mutex Chopstick5("Chopstick5");
static Mutex *Chopstick[NUM_OF_PHILOSOPHERS] = 
    { &Chopstick1, &Chopstick2, &Chopstick3, &Chopstick4, &Chopstick5 };

strstream *Filler(int n)
{
     int  i;
     strstream *Space;

     Space = new strstream;
     for (i = 0; i < n; i++)
          (*Space) << ' ';
     (*Space) << '\0';
     return Space;
}

Philosopher::Philosopher(int Number, int iter)
            :No(Number), Iteration(iter) 
{
     ThreadName.seekp(0, ios::beg);
     ThreadName << "Philosopher" << Number << '\0';
};

void Philosopher::ThreadFunc() 
{
     Thread::ThreadFunc();
     strstream *Space;
     int i;
     Space = Filler(No*2);

     for (i=0; i < Iteration; i++) {
          Delay();
          FourChairs.Wait();       // allows 4 to sit down
               Chopstick[No]->Lock();
               Chopstick[(No + 1) % NUM_OF_PHILOSOPHERS]->Lock();
               cout << Space->str() << ThreadName.str() 
                    << " begin eating." << endl;             
               Delay();
               cout << Space->str() << ThreadName.str()
                    << " finish eating." << endl;            
               Chopstick[No]->Unlock();      
               Chopstick[(No+1)%NUM_OF_PHILOSOPHERS]->Unlock();                         
          FourChairs.Signal();     // release the chair
     }
     Exit();
}

The main program is even easier than the previous one, because it does not have to initialize locks! The number of thinking-eating cycles a philosopher must perform is the only command line argument. The main thread continues to create philosopher threads and then joins with all of them. When all philosopher threads terminate, the main thread returns (i.e., terminates).

#include <iostream>
#include <stdlib.h>

#include "Philosopher-4chairs.h"

int main(int argc, char *argv[]) 
{
     Philosopher *Philosophers[NUM_OF_PHILOSOPHERS];
     int i, Iteration; 
     strstream name;

     if (argc != 2) {
          cout<<"Use " << argv[0] << " #-of-iterations." << endl;
          exit(0);          
     }      
     else
          Iteration = abs(atoi(argv[1]));

     // create all the philosopher threads and fire them up
     for (i = 0; i < NUM_OF_PHILOSOPHERS; i++) {       
          Philosophers[i]= new Philosopher(i, Iteration);
          Philosophers[i]->Begin();
     }
     for (i = 0; i < NUM_OF_PHILOSOPHERS; i++)   
          Philosophers[i]->Join();
     Exit();
     
     return 0;
}

Discussion

Note that starvation is also a problem! The example discussed previously still works for this version!