Essende Philosophen

Dieses Problem wurde von Dijkstra gestellt: Für fünf Philosophen besteht das Leben nur aus abwechselnden Phasen des Essens und des Denkens. Wenn ein Philosoph hungrig wird, versucht er nacheinander sein linkes und sein rechtes Stäbchen aufzunehmen. Hat er erfolgreich beide Stäbchen aufgenommen, ißt er eine Weile, legt dann die Stäbchen wieder ab und setzt das Denken fort.

Figure: Essende Philosophen

Übersetzt in die Welt der Prozesssynchronisation bildet jeder Philosoph einen Prozess, der nacheinander das linke bzw. das rechte Stäbchen aufnimmt. Angenommen alle Philosophen nehmen zunächst das linke Stäbchen auf. Dann kann keiner mehr sein rechtes Stäbchen aufnehmen. Wir haben einen Deadlock erreicht. Eine Idee dieses Problem zu lösen wäre, dass jeder Philosoph das linke Stäbchen wieder ablegt, wenn das rechte nicht mehr aufgenommen werden kann. Der Philosoph wartet dann eine bestimmte Zeit und versucht es erneut. Nun kann es passieren, dass alle Philosophen gleichzeitig starten. Dann ergibt sich ebenfalls keine Lösung, weil sie dann immer gleichzeitig Stäbchen aufnehmen und wieder hinlegen. Diesen Zustand nennt man Verhungern. Eine mögliche Lösung wäre die Wartezeit zufällig zu wählen. In der Regel wird das zur Lösung führen. Allerdings ist dies eine unsichere Lösung, die bei kritischen Steuerungen, wie Flugzeugen oder Atomkraftwerken sicher nicht angebracht ist.

Eine sichere Lösung ist die Benutzung von Hilfsmitteln der Prozesssynchronisation. Wir geben nun eine Lösung in Java an.

Figure: Java-Lösung für das essende Philosophen-Problem

Das Array state repräsentiert den Zustand des jeweiligen Philosophen. Die zugehörigen Prozesse werden in der Methode pickup blockiert, falls ein Nachbar eines hungrigen Philosophen gerade ißt. Wenn nun ein Philosoph das Essen beendet (Prozedur putdown) wird überprüft, ob ein Nachbar hungrig ist (blockiert ist). Nach Möglichkeit wird dieser dann aufgeweckt in den essenden Zustand versetzt. In Java ist es notwendig, dass nun durch notifyAll() alle Threads aufgeweckt werden, weil man mit notify() keinen ausgewählten Thread aufwecken kann. Mit notify() wird ein beliebiger Thread aufweckt.

In Abbildung ist der Thread implementiert, der die Philosophen repräsentiert.

Figure: Thread, der die Philosophen repräsentiert

Für weitere interessante klassische Synchronisationsprobleme sei auf die Literatur verwiesen [Tan94,SG98].