Click here to Skip to main content
11,803,019 members (67,479 online)
Click here to Skip to main content

The Dining philosophers

, 1 Aug 2006 64.8K 3.4K 34
Rate this:
Please Sign up or sign in to vote.
A multi-threaded GDI simulation of the famous problem

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 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.


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


  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  if(!sp[1] && !sp[5])
  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


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

GeneralMy vote of 4 Pin
Vijay_vijay12-Jul-14 21:52
memberVijay_vijay12-Jul-14 21:52 
Questionphilosepher problem Pin
maryam ghezelji10-Aug-11 2:01
membermaryam ghezelji10-Aug-11 2:01 
GeneralGood Pin
Ehsan Golkar12-Apr-07 8:18
memberEhsan Golkar12-Apr-07 8:18 
QuestionA link problem? Pin
Jun Du5-Sep-06 10:19
memberJun Du5-Sep-06 10:19 
AnswerRe: A link problem? Pin
toxcct19-Sep-06 3:52
membertoxcct19-Sep-06 3:52 
GeneralRe: A link problem? Pin
Dr. Sai2-Oct-06 22:10
memberDr. Sai2-Oct-06 22:10 
GeneralRe: A link problem? Pin
toxcct2-Oct-06 22:11
membertoxcct2-Oct-06 22:11 
GeneralExcellent Re: A link problem? Pin
Vishaaal_VC15-Oct-06 21:19
memberVishaaal_VC15-Oct-06 21:19 
Generalfantastic Pin
Bharath_NS10-Aug-06 23:47
memberBharath_NS10-Aug-06 23:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.151002.1 | Last Updated 1 Aug 2006
Article Copyright 2006 by Dr.Sai
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid