[NetBehaviour] The Dining Philosophers Problem

[James Morris]

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

The dining philosophers problem is summarized as five philosophers sitting
at a table doing one of two things: eating or thinking. While eating, they
are not thinking, and while thinking, they are not eating. The five
philosophers sit at a circular table with a large bowl of rice in the
center. A chopstick is placed in between each pair of adjacent
philosophers, and as such, each philosopher has one chopstick to his left
and one chopstick to his right. As rice is difficult to serve and eat with
a single chopstick, it is assumed that a philosopher must eat with two
chopsticks. Each philosopher can only use the chopsticks on his immediate
left and immediate right.

The philosophers never speak to each other, which creates a dangerous
possibility of deadlock when every philosopher holds a left chopstick and
waits perpetually for a right chopstick (or vice versa).

Originally used as a means of illustrating the problem of deadlock, this
system reaches deadlock when there is a 'cycle of unwarranted requests'.
In this case philosopher P1 waits for the chopstick grabbed by philosopher
P2 who is waiting for the chopstick of philosopher P3 and so forth, making
a circular chain.

Starvation (and the pun was intended in the original problem description)
might also occur independently of deadlock if a philosopher is unable to
acquire both chopsticks because of a timing problem. For example there
might be a rule that the philosophers put down a chopstick after waiting
five minutes for the other chopstick to become available and wait a
further five minutes before making their next attempt. This scheme
eliminates the possibility of deadlock (the system can always advance to a
different state) but still suffers from the problem of livelock. If all
five philosophers appear in the dining room at exactly the same time and
each picks up their left chopstick at the same time the philosophers will
wait five minutes until they all put their chopsticks down and then wait a
further five minutes before they all pick them up again.

In general the dining philosophers problem is a generic and abstract
problem used for explaining various issues which arise in problems which
hold mutual exclusion as a core idea. The various kinds of failures these
philosophers may experience are analogous to the difficulties that arise
in real computer programming when multiple programs need exclusive access
to shared resources. These issues are studied in the branch of Concurrent
Programming. The original problems of Dijkstra were related to external
devices like tape drives. However, the difficulties studied in the Dining
Philosophers problem arise far more often when multiple processes access
sets of data that are being updated. Systems that must deal with a large
number of parallel processes, such as operating system kernels, use
thousands of locks and synchronizations that require strict adherence to
methods and protocols if such problems as deadlock, starvation, or data
corruption are to be avoided.