فكر: الحلاق والفلاسفة الخمسة.

Not Dijkstra's Solution

This is not the solution proposed in Dijkstra's paper cited below and might not even be Dijkstra's solution at all. Dijkstra's paper presents an optimal solution based on private semaphores and state variables and a global mutex, which was described in an older version of this article

Positions of philosophers and forks in ordering solution.One solution is to order the forks and require the philosophers to pick up the forks in increasing order, which mathematically eliminates the possibility of a deadlock. To illustrate this solution, label the philosophers P1, P2, P3, P4, and P5, and label the forks F1, F2, F3, F4, and F5. Each philosopher must pick up forks in a prescribed order and cannot pick up a fork another philosopher already has. Upon acquiring two forks, a philosopher may eat. Philosophers P1 through P4 follow the rule that Px must pick up fork Fx first and then may pick up fork Fx+1. For example, P1 must pick up F1 first and F2 second. Philosopher P5 must, conversely, pick up fork F1 before picking up fork F5, to respect the deadlock-preventing fork ordering rule

Although avoiding a deadlock, this solution is inefficient, because one can arrive to a situation where only one philosopher is eating and everybody else is waiting for him. For example philosophers P1 to P3 could hold forks F1 to F3, waiting to get forks F2 to F4 respectively, philosopher P5 could wait on fork F1 having no fork yet, while philosopher P4 would be eating holding forks F4 and F5. Optimally, either philosopher P1 or philosopher P2 should be able to eat in such circumstances

Preventing starvation depends on the method of mutual exclusion enforcement used. Implementations using spinlocks or busy waiting can cause starvation through timing problems inherent in these methods. Other methods of mutual exclusion that utilize queues can prevent starvation by enforcing equal access to a fork by the adjacent philosophers

Dijkstra's solution can be extrapolated to represent arbitrary contention between philosophers, but requires all the forks to be labeled correctly for such configurations



[Chandy / Misra Solution
In 1984, K. Mani Chandy and J. Misra 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 (numbered R1, ..., Rm). Unlike in Dijkstra's solution, these labelings can be arbitrary. They solved this general problem using an elegant solution:

For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID. Each fork can either be dirty or clean. Initially, all forks are dirty
When a philosopher wants to use a set of resources (i.e. eat), he must obtain the forks from his contending neighbours. For all such forks he does not have, he sends a request message
When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so
After a philosopher is done eating, all his forks become dirty. If another philosopher had previously requested one of the forks, he cleans the fork and sends it

This solution also allows for a large degree of concurrency