Dining philosophers problem

Aufbau des Philosophenproblems

Es handelt sich bei dem Philosophenproblem (engl. Dining Philosophers Problem) um ein Fallbeispiel aus dem Bereich der Theoretischen Informatik. Dabei soll das Problem der Nebenläufigkeit erklärt werden, und die Gefahr der Verklemmung von Prozessen. Das Problem wurde von Edsger Wybe Dijkstra formuliert.

Aufbau

Es sitzen fünf Philosophen an einem runden Tisch, und jeder hat einen Teller mit Spaghetti vor sich. Zum Essen von Spaghetti benötigt jeder Philosoph zwei Gabeln. Allerdings waren im Haushalt nur fünf Gabeln vorhanden, die nun zwischen den Tellern liegen. Die Philosophen können also nicht gleichzeitig speisen.

Ablauf

Die Philosophen sitzen am Tisch und denken über philosophische Probleme nach. Wenn einer hungrig wird, greift er zuerst die Gabel links von seinem Teller, dann die auf der rechten Seite und beginnt zu essen. Wenn er satt ist, legt er die Gabeln wieder zurück und beginnt wieder zu denken. Sollte eine Gabel nicht an ihrem Platz liegen, wenn der Philosoph sie aufnehmen möchte, so wartet er, bis die Gabel wieder verfügbar ist.

Solange nur einzelne Philosophen hungrig sind, funktioniert dieses Verfahren wunderbar. Es kann aber passieren, dass sich alle fünf Philosophen gleichzeitig entschließen zu essen. Sie ergreifen also alle gleichzeitig ihre linke Gabel und nehmen damit dem jeweils links von ihnen sitzenden Kollegen seine rechte Gabel weg. Nun warten alle fünf darauf, dass die rechte Gabel wieder auftaucht. Dies passiert aber nicht, da keiner der fünf seine linke Gabel zurücklegt. Die Philosophen verhungern.

Variante: Jeder hungrige Philosoph nimmt die zwei nächsten verfügbaren Gabeln, unabhängig ob sie zuletzt von einem Nachbarn benutzt worden sind. Damit wird z. B. der Fall möglich, dass je zwei Philosophen die Gabeln immer denselben anderen zwei Philosophen ihre Gabeln übergeben und der fünfte Philosoph verhungern müsste.

Anwendung

Das Szenario der fünf (gelegentlich auch nur drei) speisenden Philosophen wird oft gebraucht, um das Problem der Interprozesskommunikation und Ressourcenverwaltung bei der Entwicklung von Betriebssystemen zu erklären. Das Beispiel soll darstellen, was passieren kann, wenn parallele Prozesse auf die gleichen Ressourcen angewiesen sind und gleichzeitig darauf zugreifen. Dann kann es passieren, dass alle blockiert sind und auf ein Ereignis warten, das durch diese Blockade nie eintreffen wird. Ein solcher Zustand wird als Verklemmung bezeichnet.

Zur Lösung des Problems werden typischerweise Mutexe oder Semaphore zur Sequentialisierung verwendet, zum Beispiel nach dem Peterson-Algorithmus oder dem Dekker-Algorithmus.

Siehe auch

• Leser-Schreiber-Problem
• Erzeuger-Verbraucher-Problem
• Raucherproblem
• Mutex
• Verklemmung

Literatur

• Silberschatz, Abraham; Peterson, James L.: Operating Systems Concepts. Addison-Wesley 1988, 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.

Weblinks

• englische Seite über das Philosophenproblem mit Java-Applet
• Discussion of the problem with solution code for 2 or 4 philosophers
• Discussion of various solutions 1
• Discussion of various solutions 2
• Distributed symmetric solutions
• Programming the Dining Philosophers with Simulation
• Interactive example of the Philosophers problem (Java required)
• Satan Comes to Dinner
• Wot No Chickens? - Peter H. Welch proposed the Starving Philosophers variant that demonstrates an unfortunate consequence of the behaviour of Java thread monitors is to make thread starvation more likely than strictly necessary.
• ThreadMentor