WikiDer > Philosophenproblem
In dem Informatik ist der Das Problem des Philosophen ein ansprechendes Beispiel für das Problem der Synchronisation.Das Problem ist in 1965 durch Edsger Dijkstraße erstmals als Prüfungsfrage gestellt; es ging um fünf Computer, die Zugriff auf fünf Bandlaufwerke haben wollten. Die Neuformulierung, in der Computer und Bandlaufwerke durch Philosophen und Forks ersetzt wurden, wurde kurz darauf von Tony Hoare.
Das Problem
Fünf Philosophen sitzen an einem runden Tisch um eine riesige Schüssel SpaghettiJeder Philosoph sollte ab und zu Spaghetti essen. (Ein Philosoph, der nicht isst, denkt.)
Auf dem Tisch liegen fünf Gabeln: eine zwischen je zwei Philosophen.
Um zu essen, muss ein Philosoph beide Gabeln auf beiden Seiten halten. Ein Philosoph kann diese Gabeln aufheben, aber nur eine nach der anderen und natürlich nur, wenn der Nachbar die Gabel gerade nicht hält. Ein Philosoph kann eine aufgenommene Gabel zurücklegen.
Die Philosophen können keine anderen Handlungen oder Beobachtungen durchführen.
Das Problem besteht jetzt darin, den Philosophen solche Anweisungen zu geben (die sich also nur auf das Aufnehmen und Zurücksetzen der Gabeln auf beiden Seiten beziehen), dass kein Philosoph garantiert verhungern wird.
Dies ist ein Beispiel für ein Problem in der verteilte Programmierung.Solche Probleme sind in der Regel nicht so einfach zu lösen.
Nehmen wir zum Beispiel an, dass jeder Denker die Philosophie verwendet: Ich greife so schnell wie möglich zu einer Gabel, wenn beides verfügbar ist, zuerst die linke Gabel; sobald ich beide Gabeln in der Hand habe, esse ich etwas; dann lege ich die Gabeln wieder hin. Auf den ersten Blick scheint das ein vernünftiger Plan zu sein. Leider kann es vorkommen, dass jeder Philosoph die linke Gabel in der linken Hand hat und jeder Philosoph dann ewig auf die rechte Gabel warten wird Die Situation ist ein Beispiel für Sackgasse: Kein Fortschritt im System mehr möglich. Jeder Philosoph wird verhungern.
Es gibt Techniken, um zu einer Lösung zu gelangen, die Sackgasse nachweisbares Aussehen; Dijkstra hat das Problem erfunden, um solche Techniken zu demonstrieren.
Bei solchen Lösungen können zusätzliche Beobachtungen und/oder Aktionen eingegeben werden. Da wir es mit einem verteilten System zu tun haben, sind alle Beobachtungen und Aktionen Kommunikationen zwischen den beteiligten Parteien.
Zum Beispiel können wir die Denker nummerieren und jeden Denker nur dann eine Gabel aufheben lassen, wenn kein Denker mit einer höheren Nummer bereits eine Gabel hält. Jetzt ist Sackgasse unmöglich. (Aber ist diese Lösung praktikabel? Das Problem wurde jetzt dadurch geändert, dass ein Philosoph irgendwie wissen muss, ob ein Nachbar mit einer höheren Nummer bereits eine Gabel in der anderen Hand hat. Also muss diese Information irgendwie Wie? Angenommen, ein Philosoph kann beobachten, ob ein Nachbar hat eine Gabel in der anderen Hand. Das reicht nicht: Wenn der Philosoph sieht, dass dies nicht der Fall ist und sich auf dieser Grundlage entscheidet, die Pick-Up-Gabel zu verwenden, kann der Nachbar in der Zwischenzeit die andere Gabel aufnehmen.)
Sackgasse Dies ist jedoch nicht die einzige Art von Situation, die beim Design ausgeschlossen werden sollte.Angenommen, wir lassen einen Denker nicht nach einer Gabel greifen, wenn ein höherer Nummernkreis dasselbe gleichzeitig versucht. Dann wird immer der mit der höchsten Nummer essen, während der Rest verhungert. Eine solche Situation wird Hunger erwähnt.
Dies kann noch weiter verschärft werden, indem zum Beispiel gefordert wird, dass das System „fair“ ist, in dem Sinne, dass Philosophen nicht nur immer, sondern sogar genauso oft die Chance bekommen, zu essen; oder indem gefordert wird, dass die Gesamtwartezeit so gering wie möglich ist.
Relevanz
Diese Situation veranschaulicht die Probleme, die beim Synchronisieren des Zugriffs auf Ressourcen (die Gabeln), zum Beispiel von verschiedenen Faden (die Philosophen) in einem Computerprogramm. Wenn anders Faden Wenn Sie dieselben Variablen oder Dateien verwenden, ist es nicht sicher, dass sie gleichzeitig versuchen, sie zu ändern; Daher kann es unvermeidlich sein, dass Threads aufeinander warten müssen. Wenn diese Synchronisation nicht richtig ausgelegt ist, kommt ein Thread möglicherweise nie an die Reihe (Hunger) oder ob das sogar für jeden Thread gilt (Sackgasse).