General Discussions

Dining Philosopher’s Problem

dining-philosopher

The Problem
The dining philosopher’s problem is a problem frequently used in concurrent algorithm design to demonstrate the synchronization issues and methods for resolving them. It was originally formulated in 1965 by Edsger Dijkstra [1] and later, Tony Hoare gave the problem its present formulation [2].

There is a dining room containing a circular table with five chairs. At each chair is a plate, and between each plate is a single chopstick. In the middle of the table is a bowl of spaghetti. In the room are five philosophers who spend most of their time thinking, who occasionally get hungry and need to eat so they can think some more.

The conditions are:

  • A philosopher may think indefinitely
  • Every philosopher who eats will eventually finish
  • Philosophers may pickup and put down their chopsticks in either order, or non-deterministically, but these are atomic actions
  • Two philosophers cannot use a single chopstick at the same time

The problem is to design a protocol to satisfy the condition: any philosopher, who tries to EAT, eventually does.

Solutions
Several solutions have been proposed over the years by applying the principles from the various domains. The resource hierarchy solution is the one originally proposed by Dijkstra[1]. The resources will be numbered 1 through 5 and each philosopher will always pick up the lower-numbered fork first and then the higher-numbered fork. Only one philosopher will have access to that highest-numbered fork, so he will be able to eat using two forks assuring atleast one philosopher will be eating.

Another approach is to guarantee that a philosopher can only pick up either forks or none by introducing an arbitrator, e.g., a waiter. In order to pick up the forks, a philosopher must ask permission of the waiter. The waiter gives permission to only one philosopher at a time until he has picked up both his forks. The waiter can be implemented as a mutex. The problem with this approach is that if a philosopher is eating and one of his neighbors is requesting the forks, all other philosophers must wait until this request has been fulfilled even if forks for them are still available. One such solution is given by Tannenbaum in his textbook[3] using a semaphore variable. A semaphore is an integer or boolean value, s, with two associated atomic operations down(s) and up(s) where down(s) is wait until S > 0, then decrement s and up(s) is increment s. The solution uses only Boolean semaphores.

Other authors, including Dijkstra, have posed many simpler solutions. One such solution is to restrict the number of philosophers allowed access to the table. If there are N chopsticks then only N-1 philosophers allowed to compete for them, at least one will succeed, even if they follow a rigid sequential protocol to acquire their chopsticks.

K. Mani Chandy and J. Misra[4] proposed a different solution to the dining philosophers problem to allow for arbitrary agents to contend for an arbitrary number of resources. It is also completely distributed and requires no central authority after initialization. However, it violates the requirement that “the philosophers do not speak to each other” as there is circulation of request messages. The proposed solution also allows for a large degree of concurrency and solves an arbitrarily large problem. It also solves the starvation problem.

There is also a solution proposed using a monitor. A monitor is used to control access to state variables and condition variables. Monitor procedures are defined for the actions of obtaining the chopsticks and putting them down. These are used as entry and exit protocols for program segments which actually use the chopsticks.

Rick Molloy[5] has proposed an asynchronous agents based solution. The actor-based programming construct of an agent in combination with asynchronous message-passing APIs are used to provide the solution. The two moderately difficult sections: creating a thread for each philosopher to run in and coordinating the philosophers’ access to the chopsticks are handled using the asynchronous agent’s library.

The problem has also been viewed as a discrete event modeling problem. Andova et. all,[6] have defined a special component called McPal, to provide the solution for the dining philosophers problem. McPal may delegate part of its control to local adaptation managers, created on-the-fly, allowing for distribution of the adaptation to obtain the
solution.

Miremadi [7] uses the Supremica where it is a tool for formal synthesis of discrete-event control functions based on discrete event models of the uncontrolled plant and specifications of the desired closed-loop behavior. Petrinet approach [8] is also been adopted to solve the problem. The required behavior of the system is specified by an invariant relation which must hold during operation of the system and a controller is derived which when combines with the system will ensure the required behavior. Daniel[9] proves that distributed systems of probabilistic processors are essentially more powerful than distributed systems of deterministic processors, i.e., there are certain useful behaviors that can be realized only by the former using the dining philosophers problem. It is shown that, under certain natural hypotheses, there is no way the philosophers can be programmed (in a deterministic fashion) so as to guarantee the absence of deadlock (general starvation). On the other hand, if the philosophers are given some freedom of choice one may program them to guarantee that every hungry philosopher will eat (with probability one) under any circumstances (even an adversary scheduling).

Oltea[10] generalizes the dining philosophers problem to arbitrary connection topologies. The research focuses on symmetric, fully distributed systems and addresses the problem of guaranteeing progress and lockout-freedom, even in presence of adversary schedulers, by using randomized algorithms. They propose an alternative algorithm based on the idea of letting the philosophers assign a random priority to their adjacent forks.

David[11] introduces a new solution to the drinking philosophers problem, using drinking session numbers. It is simple and easily adjusted to extensions of the problem. The number of messages per drinking session is between zero and twice the number of bottles needed for drinking, a considerable improvement over previous work.

Research is also being carried out by self-stabilizing dining philosopher’s algorithmic approach. In Gouda’s solution, one of the philosophers is required to behave differently than the others in order to introduce asymmetry. In Hoover[12] asymmetry is introduced by the token circling the ring of philosophers; where the philosophers all execute exactly the same algorithm. Only the token system requires asymmetry. The layering approach simplifies the transitions required by the philosophers versus those required by Gouda.


The above data is referenced from:
[1] E. W. Dijkstra. Co-operating Sequential Processes, Academic Press, London, 1965

[2] Hoare, C. A. R. (2004). “Communicating Sequential Processes”. usingcsp.com (originally published in 1985 by Prentice Hall International).

[3] Tanenbaum, Andrew S., Modern operating systems. Upper Saddle River, NJ: Pearson Prentice Hall, 2008

[4] Chandy, K.M.; Misra, J. (1984). The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems.

[5] Rick Molloy, Solving The Dining Philosophers Problem With Asynchronous Agents, MSDN magazine, Link: https://msdn.microsoft.com/en-us/magazine/dd882512.aspx, 2009

[6] A Andova, S., A Groenewegen, L.P.J, A de Vink, E.P., Distributed Adaption of Dining Philosophers, Formal Aspects of Component Software, Lecture Notes in Computer Science Volume 6921, 2012, pp 125-144

[7] Miremadi S.; Akesson, K.; Fabian, M.; Vahidi, A.; Lennartson, B., “Solving two supervisory control benchmark problems using Supremica,” Discrete Event Systems, 2008. WODES 2008. 9th International Workshop on , vol., no., pp.131,136, 28-30 May 2008

[8] M. J. Denham, A Petri-net Approach to the Control of Discrete-event Systems, Advanced Computing Concepts and Techniques in Control Engineering, NATO ASI Series Volume 47, 1988, pp 191-214

[9] Daniel Lehmann and Michael O. Rabin. 1981. On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem. In Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on POPL ’81. ACM, New York, NY, USA, 133-138.

[10] Oltea Mihaela Herescu and Catuscia Palamidessi. 2001. On the generalized dining philosophers problem. In Proceedings of the twentieth annual ACM symposium on Principles of distributed computing (PODC ’01). ACM, New York, NY, USA, 81-89.

[11] David Ginat, A. Udaya Shankar, A. K. Agrawala, An efficient solution to the drinking philosophers problem and its extensions, Lecture Notes in Computer Science Volume 392, 1989, pp 83-93, Jun 2005

[12] Debra Hoover, Joseph Poole, A distributed self-stabilizing solution to the dining philosophers problem, Information Processing Letters, Volume 41, Issue 4, 1992, Pages 209-213, ISSN 0020-0190.

Advertisements

Let me Know What you Think!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s