Das Kefk Network Wiki befindet sich im Testbetrieb.
Philosophenproblem
Aus Kefk.
Es handelt sich bei dem Philosophenproblem (engl. Dining Philosophers Problem) um ein Fallbeispiel aus dem Bereich der Theoretischen Informatik. Dabei soll erklärt werden, wie ein Deadlock bei Prozessen entstehen kann. Das Problem wurde von Edsger Dijkstra formuliert.
Inhaltsverzeichnis |
Aufbau
| [[Hilfe:Cache|Fehler beim Thumbnail-Erstellen]]: convert: unable to open image `/var/www/kefk/w/images/6/6a/Dining_philosophers.png': No such file or directory. |
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. (Als alternatives Beispiel sind auch „Reis und Essstäbchen“ denkbar.)
Ablauf
Die Philosophen sitzen am Tisch und diskutieren über philosophische Probleme. 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 wendet sich wieder der Diskussion zu. Sollte eine Gabel nicht an ihrem Platz liegen, wenn der Philosoph sie aufnehmen möchte, so wartet er, bis die Gabel wieder da 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.
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 ihre Blockiertheit nie eintreffen wird. So ein Zustand wird als Deadlock bezeichnet.
Zur Lösung des Problems werden typischerweise Mutexe oder Semaphore zur Sequentialisierung verwendet, zum Beispiel nach dem Peterson-Algorithmus oder dem Dekker-Algorithmus.
