Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I was wondering why the Dining philosophers problem is based on a five philosophers case. Why not four?

I guess that we can observe all unpleasant issues that can occur when discussing five philosophers example also when we are given four thinkers. Is it only for a historical reason then?

share|improve this question
1  
The original problem was described by Dijkstra in 1965 and called the Dining Quintuple (found in notes at the top of page 3). –  MichaelT Feb 21 '13 at 17:06
    
I seem to remember learning aobut four dining philosophers... –  Michael Borgwardt Feb 21 '13 at 17:13
15  
It's 5 philosophers because he was trying to see if anybody would ever notice the obvious out; 5 philosophers together will talk until the restaurant kicks them out, they'll never even pick up their silverware. 4 might have a break in conversation long enough for them to start eating. With 5 as soon as any two stop talking for a moment there is already one in queue waiting to interject to ensure continuity. –  Jimmy Hoffa Feb 21 '13 at 17:58
    
@Jimmy Hoffa -+1. And why is that not answer? –  SChepurin Feb 21 '13 at 19:16

3 Answers 3

up vote 16 down vote accepted

Per what is written in EWD310 "Hierarchical Ordering of Sequential Processes", it looks like number 5 has been chosen for educational purposes, in order to make it easier for students to understand algorithm designed to demonstrate solution of the problem.

This very paper further supports the idea that 5 is not really relevant to general problem, first by explicitly stating that "the problem could have been posed for 9 or 25 philosophers..." and next, by representing it in terms of two concurrently operating entities, "class A and class B, sharing the same resource..."

Solution used by Dijkstra introduces three "states of philosopher": thinking, eating, hungry. Code presented to solve the problem, operates these three states, along with an unrelated to it number of philosophers.

Would author has chosen number of philosophers 2, 3 or 4, this could cause confusion of the students reading the code, whether chosen number is related to the amount of states or something else. This can easily be tested by trying mentioned numbers in description quoted from EWD310 below: note for example how this would change [0:4] to [0:3], [0:2], [0:1] and statements involving mod.

As opposed to this, number 5 looks fairly innocent and doesn't invoke unneeded associations. One can say that it has been chosen to better illustrate that amount of philosophers is, well, arbitrary.


Mentioned algorithm is presented in EWD310 as follows:

...we associate with each philosopher a state variable, "C" say, where

C[i] = 0 means: philosopher i is thinking

C[i] = 2 means: philosopher i is eating.

...

we introduce for the last transition an intermediate state

C[i] = 1 means: philosopher i is hungry

Now each philosopher will go cyclically through the states 0, 1, 2, 0 ...... The next question to ask is: when has the (dangerous) transition from 1 to 2 to take place for philosopher K?

...

In the universe we assume declared

1) the semaphore mutex, initially = 1

2) the integer array C[0:4], with initially all element = 0

3) the semaphore array prisem[0:4] with initially all elements = 0

4) procedure test (integer value K);

if C[(K-1) mod 5] ≠ 2 and C[K]= 1
    and C[(K+1) mod 5] ≠ 2 do
      begin C[K]:= 2; V(prisem[K]) end;

(This procedure, which resolves unstability for K when present, will only be called from within a critical section).

In this universe the life of philosopher w can now be coded

cycle begin think;
            P (mutex);
               C[w]:= 1; test (w);
            V(mutex);
            P(prisem[w]); eat
            P(mutex);
               C[w]:= 0; test [(w+l) mod 5];
               test [(w-1) mod 5];
            V(mutex)
      end

And this concludes the solution I was aiming at...

share|improve this answer
2  
I might not be a philosopher then, because I can think at the same time when eating or being hungry. And more: none of them is drinking or even talking. –  ott-- Feb 24 '13 at 19:46

Only Dijkstra can answer for sure but I would be confident enough that it's arbitrary.

"It was originally formulated in 1965 by Edsger Dijkstra as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals. Soon after, Tony Hoare gave the problem its present formulation."

http://en.wikipedia.org/wiki/Dining_philosophers_problem

share|improve this answer
2  
Consider the problem of four diners compared to five. How does the problem change? Is it easier or harder? This was an exam question - the harder one is likely the one that is desired to ask. –  MichaelT Feb 21 '13 at 17:49

Because it's odd, not even. So that you don't try to devise an algorythm that relies on symmetry or forming pairs, and only much later realize it doesn't work for the general case.

This is an opinion; I have no historical knowledge of what crossed the author's mind.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.