Why five dining philosophers?

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.