(Fortsetzung von hier.) Jetzt sind meine drei immer noch schönen Blogeinträge zu Threads auch schon 9 Jahre her. Mir fiel vor ein paar Tagen auf, dass inhaltlich noch ein Rest fehlt, nämlich die zyklische Verklemmung, a.k.a Deadlock, das hole ich hier nach; ohne die anderen Einträge dazu sieht dieser vielleicht etwas zusammenhanglos aus.

Grundsätzliches

In den vorherigen Beitträgen ging es darum, was Threads sind und warum sie nützlich sein können, was es für ein Problem geben kann und welche Lösung es gibt, was es dann aber auch noch als Problem geben kann und was die Lösung für dieses weitere Problem ist. Fehlt noch das dritte Problem, für das es keine allgemeine technische Lösung gibt: das zyklische Warten, auch Verklemmung, auch Deadlock genannt. Dabei warten mehrere Threads jeweils aufeinander und können nicht weiter machen. Das kann dann geschehen, wenn:

• es mehr als eine Ressource gibt,
• die Ressourcen nicht gleichzeitig, sondern nur exklusiv benutzt werden können,
• die Threads zum Arbeiten mehr als eine Ressource benötigen,
• sich diese Ressourcen nacheinander in beliebiger Reihenfolge holen,
• und nicht wieder hergeben, auch wenn sie noch auf ihre fehlende Ressourcen warten.

Das Philosophenproblem

Das Standardbeispiel ist das Philosophenproblem. Man hat einen runden Tisch mit n Tellern, für jeden Gast einen. Stühle und eine Tischdecke wird es auch noch geben, aber die sind für das Modell nicht wichtig. Wichtig sind aber die Gabeln: zwischen jeweils zwei Tellern liegt immer 1 Gabel. Wenn es also n Teller gibt, gibt es auch n Gabeln, eine links und eine rechts von jedem Teller.

Zum Essen braucht man in diesem Modell immer 2 Gabeln. Man nimmt zuerst entweder die Gabel links vom eigenen Teller oder die Gabel rechts vom eigenen Teller und ists, sobald man beide Gabeln hat. Wenn man fertig ist, legt man die Gabeln zurück. Das ist wichtig, weil der Nebenphilosoph vielleicht darauf wartet, dass die – ja gemeinsam benutzte – Gabel endlich frei wird.

Dieses komische Verfahren kann manchmal gut gehen. Aber es kann auch vorkommen, dass alle Philosophen gleichzeitig ihre linke Gabel ergreifen und dann alle darauf warten, dass einmal ihre rechte Gabel frei wird – was nicht geschehen wird, da alle Gabeln in linken Händen sind.

Benjamin D. Esham / Wikimedia Commons, An illustration of the dining philosophers problem, CC BY-SA 3.0

Wenn Plato, Konfuzius, Sokrates, Voltaire und Frans Hals jeweils ihre linke Gabel nehmen, ist keine rechte mehr frei. (Frauen fehlen.) Hier als Film:

Vermeiden oder Auflösen

Verklemmungen kann man auflösen oder vermeiden:

• jeder Philosoph muss beide gewünschte Gabeln gleichzeitig nehmen (gleichzeitiges Reservieren aller benötigten Ressourcen)
• jeder Philosoph hat die Möglichkeit, aufzugeben und reservierte Gabeln auch mal wiede auf den Tisch zurück zu legen (freiwilliges Aufgeben von Ressourcen)
• jemand von außen kann kommen und einem Philosophen eine Gabel wegnehmen und auf den Tisch legen (zwangsweise Zurückgeben von nicht verwendeten Ressourcen)
• die Gabel mit der kleinsten Nummer muss zuerst genommen werden (das ist für einen der Philosophen nämlich die rechte, für die anderen die linke, zum Beispiel), bevor man an die andere darf (feste Reihenfolge der Ressourcen)

Kein gutes Beispiel

Als Beispiel für eine Verklemmung wird auch oft eine Kreuzung genannt, mit rechts vor links und vier Autos, die zyklisch aufeinander warten. Steht so bei Wikipedia deutsch, und ähnlich bei Wikipedia englisch, stimmt aber trotzdem oft nicht, habe eben kommentiert dort, werde berichten. („Diskussion“ heißt der Bereich auf Deutsch, „Talk“ auf Englisch.)

Denn: Wenn die Kreuzung 1 Ressource ist, kann es gar keine Verklemmung geben, es könnte jederzeit ein Auto fahren. Zur Verklemmung gehören immer mindestens 2 Ressourcen. Damit also eine Verklemmung entstehen kann, muss man das Kreuzungsinnere als 4 Quadranten betrachten, also 4 Ressourcen, von denen jedes Auto die 2 vor ihm liegenden zum Durchfahren braucht. Wenn jedes Auto den Quadranten vor sich reserviert, also zum Beispiel hineinfährt, dann haben wir eine Verklemmung, verkehrstechnisch: gridlock.

Rgoogin at the English Wikipedia, New York City Gridlock, CC BY-SA 3.0