The Dining philosophers

• Download sourcecode - 539Kb 

The problem

Five philosophers spend their time eating and thinking. The college where they live has a dining table with a large bowl of spaghetti in the center of the table. There are five plates at the table and five forks set between the plates.

Eating the spaghetti requires the use of two forks (often, the problem is explained with chopsticks instead of forks, because it is easier to understand requiring two chopsticks to eat spaghetti than two forks) which the philosophers pick up one at a time. The philosophers never speak to each other which creates a dangerous possibility of deadlock in which every philosopher holds a left fork and waits perpetually for a right fork (or vice versa).

The problem is stated verbatim from en.wikipedia.org site. In this article I present a simple multithreaded solution to how to schedule all of them without a race for spoons. And as usual I do a lot of explaining.

Solution

Let the philosophers be numbered philosopher 1, philosopher 2, philosopher 3, philosopher 4, philosopher 5.

Let

1. Philosopher 1 uses Spoon 1 and Spoon 5.
2. Philosopher 2 uses Spoon 1 and Spoon 2.
3. Philosopher 3 uses Spoon 2 and Spoon 3.
4. Philosopher 4 uses Spoon 3 and Spoon 4.
5. Philosopher 5 uses Spoon 4 and Spoon 5.

Philosophers who have finished eating can release other philosophers who are waiting to eat. So we have the following:

1. Philosopher 1 can release only Philosopher 2 or Philosopher 5.
2. Philosopher 2 can release only Philosopher 3 or Philosopher 1.
3. Philosopher 3 can release only Philosopher 4 or Philosopher 2.
4. Philosopher 4 can release only Philosopher 5 or Philosopher 3.
5. Philosopher 5 can release only Philosopher 1 or Philosopher 4.

The code is very much simple. There are 5 threads, one for each philosopher that simulates eating and thinking. The code is essentially the same for each of the philosopher, but I have repeated the code to just improve readability.

Here is a multi- threaded architecture I have, which attempts to solve a class of such problems. Some of them are listed below.

1. Dinning philosophers problem
2. Readers and writers problems.

Every thread that runs under a condition has to have an entry criteria and an exit criteria. It is in between these criterion  that thread safe conditional code can execute. I will use this architecture to dig deep into the readers and writers problem in my forth coming articles. For the present let me use it to explain the solution to the “Dinning Philosophers” problems.

There is a CRITICAL_SECTION variable that synchronizes the entry and exit criteria that all the threads have to perform. There are five event handles, one for each thread, on which wait have to performed as and when required and there is a five element integer array depicting the spoons. Each of these elements is either 1 or 0 ( Boolean) 0 to simulate that the spoons is not used by any philosopher and 1 to simulate that the spoon is being used by some philosopher. Apart form this there are other data members that I use, but they are only for animation so I will not dwell into those.

Every Philosopher thread will  continuously spin in a while(1) loop. At the beginning of the loop there is a local variable nSHouldWait, a bool value to whether put the thread state to wait or execute.

The following steps illustrate the entry criteria.

1. Here the critical section is entered,  EnterCriticalSection(&cs); . Read the above below.
2. Check if I  have my spoons ready to eat  <FONT color=#000000>if(!sp[1] && !sp[5])</FONT>
3. if my spoons are ready for eating, set the spoon variables to occupied,  sp[1]=sp[5]=1;
4. So I need not wait, nSHouldWait=0;
5. else  From (2) my spoons are not free, some other philosopher is using them , so I cannot eat Therefore I will wait, nSHouldWait=1;
6. LeaveCriticalSection(&cs);
7. if(nSHouldWait)
8. wait on my even till I am signalled to run,  WaitForSingleObject(hndEvents[1],INFINITE);

This is where the entry criteria ends.

Note: All entry criteria have to guarded by a common critical section, lest the state of the globals would not be consistent. Similarly all of the exit criteria  have to be guarded so I use the same critical section for both the purposes.

When the code completes the entry criteria, it means it either has full legal authority to run or wait. Let us take the case, where it is going to run (simulated by the philosopher eating) and finally after some time it would have finished eating. So it is time to dig into exit criteria.

The exit criteria is illustrated in the following steps.

1. Define a local handle and initialize it to NULL, HANDLE hndTmp = NULL;
2. First surrender my spoons since I have finished eating, sp[1]=sp[5]=0;
3. Since Philosopher 1 can release only to Philosopher 2 or Philosopher 5. Check if I can release Philosopher 2 first, if(!sp[1] && !sp[2]) if true.
4. If so put his spoonstooccupiedstate,sp[1]=sp[2]=1;
5. And set his event handle, he is waiting to eat, hndTmp = hndEvents[2];
6. If not check if I can free Philosopher 5 and repeat the above steps for Philosopher 5.
7. Finally leave the critical section, LeaveCriticalSection(&cs);
8. Allow either Philosopher 2 or Philosopher 5 to eat, if(hndTmp != NULL) SetEvent(hndTmp);

This is where the exit criteria ends and the Philosopher 1 can loop back and start to execute the entry criteria all over again.

The code is essentially same for all the others but for the spoons usage number and the event handles the set. To test the code one can vary the eat intervals and observe that none of them starve when run over a period of time