In a famous 1971 paper titled "Hierarchical Ordering of Sequential Processes," Edsger Dijkstra proposed a problem that has become a canonical example of difficulties in concurrency, multithreading, multi-process synchronization, and mutual exclusion. Dijkstra's formulation is as follows. Five philosophers sit at a circular dining table. Each has before him a plate with spaghetti on it. The table is set with one fork beside each plate, five forks in all. The philosophers spend their time alternating between thinking and eating, and two forks are needed for any philosopher to eat.

When a philosopher wishes to eat, it is necessary for him to obtain both forks, one on each side, which can only happen if both are available. If a philosopher is unable to obtain both forks, he will be unable to eat, and will eventually die of starvation. The resulting competition for forks is a representation of the competition for resources that occurs in operating systems. Specifically, if there are multiple threads of execution and threads need to access their critical sections without getting deadlocked, the problem is equivalent to that of the dining philosophers.

The trivial single-threaded solution is to traverse the table allowing one philosopher to eat at a time. This solution does not maximize concurrency. A common multi-threaded solution is to have a separate thread per philosopher executing code:

• while (true)
• {
• Think();
• Lock_Left_Fork();
• Lock_Right_Fork();
• Eat();
• Release_Right_Fork();
• Release_Left_Fork();
• }

However, the solution given above has a potential deadlock situation if each philosopher executes the locking of the left fork, prior to the locking of the right fork. (One correct solution is to have odd numbered philosophers lock the left fork before the right fork, while even numbered philosophers lock the right fork before the left.)