Dining philosophers problem
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.
The problem was designed to illustrate the challenges of avoiding deadlock, a system state in which no progress is possible.
To see that a proper solution to this problem is not obvious, consider a proposal in which each philosopher is instructed to behave as follows: With these instructions, the situation may arise where each philosopher holds the fork to their left; in that situation, they will all be stuck forever, waiting for the other fork to be available: it is a deadlock.
Resource starvation, mutual exclusion and livelock are other types of sequence and access problems.
In practice, negating mutual exclusion or non-preemption somehow can give a valid solution, but most theoretical treatments assume that those assumptions are non-negotiable, instead attacking resource holding or circular waiting (often both).
For GCC: compile with Another approach is to guarantee that a philosopher can only pick up both forks or none by introducing an arbitrator to replace circular waiting, e.g., a waiter.
A solution presented by William Stallings[7] is to allow a maximum of n-1 philosophers to sit down at any time.
The last philosopher would have to wait (for example, using a semaphore) for someone to finish dining before he "sits down" and requests access to any fork.
This negates circular wait, guaranteeing at least one philosopher may always acquire both forks, allowing the system to make progress.
In 1984, K. Mani Chandy and J. Misra[8] proposed a different solution to the dining philosophers problem to allow for arbitrary agents (numbered P1, ..., Pn) to contend for an arbitrary number of resources, unlike Dijkstra's solution.
However, if the system is initialized to a perfectly symmetric state, like all philosophers holding their left side forks, then the graph is cyclic at the outset, and their solution cannot prevent a deadlock.
