# Why five dining philosophers?

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?

• The original problem was described by Dijkstra in 1965 and called the Dining Quintuple (found in notes at the top of page 3).
– user40980
Commented Feb 21, 2013 at 17:06
• I seem to remember learning aobut four dining philosophers... Commented Feb 21, 2013 at 17:13
• 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. Commented Feb 21, 2013 at 17:58
• @Jimmy Hoffa -+1. And why is that not answer? Commented Feb 21, 2013 at 19:16

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

• 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. Commented Feb 24, 2013 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

• 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.
– user40980
Commented Feb 21, 2013 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.

• This point is crucial. With four philosophers, two pairs of them could take turns eating. Commented Nov 10, 2016 at 17:12