Philosophenproblem

Kernidee und Bedeutung

Das Philosophenproblem, auf Englisch dining philosophers problem, ist ein Fallbeispiel aus der theoretischen Informatik. Es wurde von Edsger W. Dijkstra formuliert und dient dazu, Nebenläufigkeit zu erklären. Nebenläufigkeit bedeutet, dass mehrere Prozesse oder Threads scheinbar gleichzeitig arbeiten und dabei gemeinsame Mittel benutzen.

Das Beispiel zeigt besonders die Gefahr einer Verklemmung, auch Deadlock genannt. Ein Deadlock ist ein Zustand, in dem mehrere parallele Prozesse blockiert sind, weil jeder auf ein Ereignis oder eine Ressource wartet, die wegen der Blockade nicht frei wird. In Betriebssystemen ist das wichtig, weil dort viele Prozesse gleichzeitig auf gemeinsame Ressourcen zugreifen, zum Beispiel Speicherbereiche, Dateien oder Geräte.

Das Szenario wird oft verwendet, um Interprozesskommunikation und Ressourcenverwaltung zu veranschaulichen. Interprozesskommunikation beschreibt, wie Prozesse miteinander Informationen austauschen oder sich abstimmen. Ressourcenverwaltung bedeutet, dass gemeinsame Ressourcen so vergeben werden, dass Prozesse korrekt und möglichst ohne Blockade arbeiten können.

Aufbau des Beispiels

Im klassischen Aufbau sitzen fünf Philosophen an einem Tisch. Sie sind von eins bis fünf nummeriert und jeder hat seinen festen Platz. Zwischen je zwei Tellern liegt genau eine Gabel. Das servierte Gericht sind Spaghetti, die mit zwei Gabeln gegessen werden müssen.

Für einen einzelnen Philosophen wäre das kein Problem, denn links und rechts von seinem Teller liegt jeweils eine Gabel. Da die Gabeln aber zwischen den Tellern liegen, teilen sich Nachbarn jeweils eine Gabel. Deshalb können zwei benachbarte Philosophen nicht gleichzeitig essen.

Die Gabeln stehen in diesem Beispiel für gemeinsam genutzte Ressourcen. Die Philosophen stehen für Prozesse oder Threads. Ein Thread ist ein Ausführungsstrang innerhalb eines Programms. Das Essen steht dafür, dass ein Prozess seine Arbeit nur ausführen kann, wenn er mehrere Ressourcen gleichzeitig besitzt.

Wie der Deadlock entsteht

Die Philosophen denken zunächst über philosophische Probleme nach. Wird ein Philosoph hungrig, nimmt er zuerst die Gabel links von seinem Teller. Danach nimmt er die rechte Gabel und beginnt zu essen. Wenn er satt ist, legt er beide Gabeln zurück und denkt weiter. Ist eine Gabel nicht verfügbar, wartet der Philosoph, bis sie wieder an ihrem Platz liegt.

Solange nur einzelne Philosophen hungrig sind, funktioniert dieses Verfahren. Das Problem entsteht, wenn alle fünf Philosophen gleichzeitig essen wollen. Dann greift jeder zuerst zu seiner linken Gabel. Dadurch nimmt jeder seinem linken Nachbarn dessen rechte Gabel weg.

Nun besitzt jeder Philosoph genau eine Gabel und wartet auf die rechte Gabel. Diese wird aber nicht frei, weil keiner seine linke Gabel zurücklegt. Alle warten also gegenseitig aufeinander. In der Bildgeschichte verhungern die Philosophen; in der Informatik bedeutet das, dass die beteiligten Prozesse dauerhaft blockiert sind.

Lösung durch Ressourcenhierarchie

Eine Lösung ist die Ressourcenhierarchie. Dabei werden die Gabeln von eins bis fünf durchnummeriert. Jeder Philosoph muss immer zuerst versuchen, die Gabel mit der niedrigeren Nummer aufzunehmen. Erst wenn das gelungen ist, darf er die Gabel mit der höheren Nummer aufnehmen.

Diese Regel verhindert, dass alle Philosophen gleichzeitig in derselben Kreisstruktur jeweils eine Ressource halten und auf die nächste warten. Wenn alle gleichzeitig essen möchten, können nicht alle zugleich die Gabel mit der niedrigeren Nummer aufnehmen. Besonders die Gabel mit der Nummer eins kann nur von einem der beiden benachbarten Philosophen aufgenommen werden.

Nimmt der erste Philosoph die Gabel mit der Nummer eins, dann bekommen er, der zweite und der dritte Philosoph jeweils eine Gabel und warten auf eine höher nummerierte Gabel. Der vierte Philosoph bekommt zwei Gabeln und kann essen. Der letzte Philosoph bekommt keine Gabel und wartet auf die niedrigere Nummer. Nimmt dagegen der letzte Philosoph die Gabel mit der Nummer eins, wartet der erste Philosoph ohne Gabel; der zweite und dritte besitzen eine Gabel; der vorletzte und letzte Philosoph konkurrieren um Gabel Nummer fünf. Wer sie zuerst bekommt, kann mit zwei Gabeln essen.

Der Artikel zeigt dazu auch eine C++11-Implementierung für drei Philosophen. Dort werden drei Gabeln als drei Mutexe dargestellt. Ein Mutex ist ein Sperrmechanismus, mit dem verhindert wird, dass mehrere Threads gleichzeitig dieselbe Ressource benutzen. Drei Philosophen werden als drei Threads ausgeführt. Die Funktion sleep_for() simuliert die Zeit, die normalerweise mit Geschäftslogik verbracht wird. Die Reihenfolge der Mutexe bildet die Ressourcenhierarchie nach.

Alternative Lösung und ihre Grenze

Eine andere Lösungsidee lautet: Ein hungriger Philosoph darf entweder beide Gabeln gleichzeitig aufnehmen oder gar keine. Es ist nicht erlaubt, nur eine Gabel zu behalten, wenn die zweite gerade nicht verfügbar ist. Dadurch wird verhindert, dass alle Philosophen jeweils eine Gabel festhalten und auf die zweite warten.

Diese Variante beseitigt aber nicht jedes Problem. Es kann passieren, dass immer abwechselnd Philosoph eins und drei und danach Philosoph zwei und vier essen. Dann kommt Philosoph fünf nie an die Reihe und verhungert. In der Informatik entspricht das einem Fairnessproblem oder Verhungern eines Prozesses: Ein Prozess ist nicht unbedingt blockiert durch einen Deadlock, bekommt aber dauerhaft keine Gelegenheit, weiterzuarbeiten.

Typische technische Mittel

Zur Lösung solcher Nebenläufigkeitsprobleme werden typischerweise fortschrittliche Mutexe oder Semaphore zur Sequentialisierung verwendet. Sequentialisierung bedeutet, dass Zugriffe auf gemeinsame Ressourcen in eine geordnete Reihenfolge gebracht werden, damit sie sich nicht gegenseitig blockieren.

Semaphore sind Synchronisationsmechanismen, mit denen die Anzahl gleichzeitiger Zugriffe auf eine Ressource kontrolliert werden kann. Mutexe erlauben meist nur einem Prozess oder Thread gleichzeitig den Zugriff auf eine bestimmte Ressource. Der Artikel nennt als Beispiel scoped_lock aus C++17. Solche Werkzeuge helfen dabei, gemeinsame Ressourcen so zu sperren und freizugeben, dass Deadlocks vermieden oder zumindest besser kontrolliert werden können.