Problem des Monats Juli
Wie fünf Philosophen am gedeckten Tisch verhungern – Das Philosophenproblem
Parallelverarbeitung ist heute die wichtigste Technik, um leistungsfähige Systeme zu realisieren. Und das nicht für Hochleistungsrechenaufgaben auf Supercomputern, sondern auch im Privatbereich verlangen die zahlreichen Apps und Programme dem heimischen PC oder dem Smartphone immer mehr Rechenleistung ab, die verteilt auf mehrere Prozessoren schneller und effizienter ablaufen kann.
Das Problem, das beim Ressourcenzugriff in der Parallelverarbeitung entstehen kann, hat Edsger W. Dijkstra 1971 als „Philosophenproblem“ formuliert. In der einfachsten Variante handelt es von fünf Philosophen, die gemeinsam eine Mahlzeit einnehmen möchten und dabei philosophieren. Jeder Philosoph hat einen Teller voller Spaghetti, zwischen je zwei Tellern liegt eine Gabel. Die Philosophen essen nicht die gesamte Zeit, sondern philosophieren auch. Möchte ein Philosoph essen, nimmt er sich die Gabel links von seinem Teller, dann die rechts und beginnt mit beiden Gabeln zu essen. Ist er satt, legt er beide Gabeln wieder zurück und philosophiert weiter, bis er wieder Hunger bekommt.
Die fünf Philosophen an einem Tisch. (Bild: Benjamin D. Esham)
Bekommen nun plötzlich alle Philosophen gleichzeitig Hunger, greifen sie jeweils ihre linke Gabel, ihre rechte Gabel ist aber nun von ihrem rechten Sitznachbarn belegt. Da alle auf ihre zweite Gabel warten, verhungern sie schließlich.
Was hat das nun mit Parallelverarbeitung zu tun? Die Philosophen stehen für Programmteile, die parallel ausgeführt werden, die Gabeln für Ressourcen. Um ihre Arbeit zu erledigen, benötigen die Programmteile gewisse Ressourcen, um die sie konkurrieren. Blockieren sie einander damit gegenseitig vom Zugriff, sodass keiner seine Arbeit erledigen kann, spricht man von einer Verklemmung (engl. deadlock).
Zur Lösung dieses Problems kommen beispielsweise Mutex-Verfahren in Frage. Dabei wird ein Abschnitt definiert, in dem sich nur ein Programmteil jeweils befinden darf, sodass kein weiterer Prozess noch mit der Ergreifung von Ressourcen beginnt, während ein anderer noch auf eine Ressource wartet. Auf die Philosophen bezogen bedeutet das: während ein Philosoph auf eine zweite Gabel wartet, darf kein anderer eine erste Gabel ergreifen.