Das Problem der essenden Philosophen (dining philosopher problem) macht die Grundannahme, dass fünf Philosophen abwechseln denken und Spaghetti essen. Das ist (ausser für Philosophen) an sich noch kein Problem, es sei denn, es ist zu wenig Besteck vorhanden (siehe Abbildung).

Damit ein Philosoph essen kann, muss er zwei Gabeln nehmen. Da nur soviel Gabeln vorhanden sind wie Philosophen, können nicht alle Philosophen gleichzeitig essen. Gesucht ist nun ein Algorithmus, der es erlaubt, dass möglichst viele Philosophen gleichzeitig essen und kein Philosoph benachteiligt wird.

Jeder Philosoph führt nacheinander und wiederholt die Schritte

denken (think),
Gabeln nehmen (takeForks),
essen (eat) und
Gabeln wieder hinlegen (putForks)

aus.

Ein einfacher Algorithmus, der den oben genannten Anforderungen genügt, repräsentiert jede Gabel durch einen Semaphor mit Initial- und Maximalwert 1. Jeder Philosoph führt während des Schritts takeForks ein aquire für seine beiden Gabel-Semaphoren aus und beim Schritt putForks ein release für die beiden Semaphoren. Damit kein Deadlock entsteht, nummeriert man die Gabeln und stellt sicher, dass alle Philosophen immer zuerst ein aquire auf dem Gabel-Semaphor ausführt, der mit der niedrigeren Zahl beschriftet ist.


Literatur

Andrew S. Tanenbaum: Modern Operating Systems; Kapitel 2.3.1

Abbildung: Tisch mit zu wenig Besteck.