|
In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. It is a classic multi-process synchronization problem, and is included in nearly all college-level computer science curricula. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
Wikiquote has a collection of quotations related to: Edsger Dijkstra The Dining Philosophers, a classic problem involving concurrency and shared resources In computer science, concurrency is a property of systems which consist of computations that execute overlapped in time, and which may permit the sharing of common resources between those...
Parallel programming is a computer programming technique that provides for the execution of operations in parallel, either within a single computer, or across a number of systems. ...
Synchronization (or Sync) is a problem in timekeeping which requires the coordination of events to operate a system in unison. ...
In 1971, Edsger Dijkstra set an examination question on a synchronization problem where five computers competed for access to five shared tape drive peripherals. Soon afterwards the problem was retold by Tony Hoare as the dining philosophers problem. 1971 (MCMLXXI) was a common year starting on Friday. ...
Edsger Dijkstra Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 – Nuenen, August 6, 2002; IPA: ) was a Dutch computer scientist. ...
Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort, the worlds most widely used sorting algorithm, and perhaps even the worlds most widely used algorithm of any kind...
The 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 spaghetti in the center. A fork is placed in between each philosopher, and as such, each philosopher has one fork to his or her left and one fork to his or her right. As spaghetti is difficult to serve and eat with a single fork, it must be assumed that in order for a philosopher to eat, the philosopher must have two forks. In the case of the dining philosopher, the philosopher can only use the fork on his or her left or right.
 Illustration of the dining philosophers problem In some cases, the dining philosophers problem is explained using rice and chopsticks as opposed to spaghetti and forks, as it is generally easier to understand that two chopsticks are required, whereas one could arguably eat spaghetti using a single fork. In either case, only one instrument (fork or chopstick) can be picked up at a time, and the philosopher must have two instruments in order to eat. Download high resolution version (1130x1172, 1362 KB) Wikipedia does not have an article with this exact name. ...
Download high resolution version (1130x1172, 1362 KB) Wikipedia does not have an article with this exact name. ...
The philosophers never speak to each other which creates a dangerous possibility of deadlock in which every philosopher holds a left fork and waits perpetually for a right fork (or vice versa). It has been suggested that Circular wait be merged into this article or section. ...
Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a 'cycle of ungranted requests'. In this case philosopher P1 waits for the fork grabbed by philosopher P2 who is waiting for the fork 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 forks due to a timing issue. For example there might be a rule that the philosophers put down a fork after waiting five minutes for the other fork 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 fork at the same time the philosophers will wait five minutes until they all put their forks down and then wait a further five minutes before they all pick them up again. In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. ...
It has been suggested that Circular wait be merged into this article or section. ...
The lack of available forks is an analogy to the locking of shared resources in real computer programming, a situation known as concurrency. Locking a resource is a common technique to ensure the resource is accessed by only one program or chunk of code at a time. When the resource the program is interested in is already locked by another one, the program waits until it is unlocked. When several programs are involved in locking resources, deadlock might happen, depending on the circumstances. For example, one program needs two files to process. When two such programs lock one file each, both programs wait for the other one to unlock the other file, which will never happen. Parallel programming (also concurrent programming), is a computer programming technique that provides for the execution of operations concurrently, either within a single computer, or across a number of systems. ...
Solutions Image File history File links Circle-question-red. ...
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. A semaphore is a protected variable (or abstract data type) and constitutes the classic method for restricting access to shared resources (e. ...
Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the concurrent use of un-shareable resources by pieces of computer code called critical sections. ...
Dining Philosopher Problem - Simplified positioning This image may not be eligible for copyright, but just in case I, the creator of this image, hereby release it into the public domain. ...
Dining Philosopher Problem - Simplified positioning This image may not be eligible for copyright, but just in case I, the creator of this image, hereby release it into the public domain. ...
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. Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ...
In software engineering, a spinlock is a lock where the thread simply waits in a loop (spins) repeatedly checking until the lock becomes available. ...
It has been suggested that this article or section be merged with Polling (computer science). ...
In providing services in computer science, transport, and operations research a queue (pronounced kyew) is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. ...
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: Dr. K. Mani Chandy is the Simon Ramo Professor of Computer Science at the California Institute of Technology. ...
- 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.
References - Silberschatz, Abraham; Peterson, James L. (1988). Operating Systems Concepts. Addison-Wesley. ISBN 0-201-18760-4.
- Chandy, K.M.; Misra, J. (1984). The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems.
- Dijkstra, E. W. (1971, June). Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115-138.
- Lehmann, D. J., Rabin M. O, (1981). On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981 (POPL'81), pages 133-138.
POPL is the annual symposium on Principles of Programming Languages sponsored by the Association for Computing Machinery Special Interest Groups SIGPLAN and SIGACT. SIGPLAN POPL homepage Categories: | | | ...
See also In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. ...
Spontaneous symmetry breaking in physics takes place when a system that is symmetric with respect to some symmetry group goes into a vacuum state that is not symmetric. ...
The cigarette smokers problem is a concurrency problem, originally described in 1971 by S. S. Patil. ...
The dining cryptographers protocol is a method of anonymous communication. ...
In computer science, the first and second readers-writers problems are examples of a common computing problem in concurrency. ...
In computer science, the producer-consumer problem (also known as the bounded-buffer problem) is a classical example of a multi-process synchronization problem. ...
External links |
Feeds |
Contact