Deadlocks (Verklemmungen)

Die verfahrene Situation lässt sich auf übersichtliche Weise in einem resource allocation graph (deutsch: Betriebsmittelzuteilungsgraph) veranschaulichen: Es kommt hier zu einem Deadlock (deutsch: Verklemmung), bei dem keines der Kinder die angestrebte Tätigkeit ausführen kann, da ihm jeweils eine Ressource ("Betriebsmittel") fehlt.

Auch Threads benötigen oft Ressourcen (z.B. Schreibzugriff auf einen Speicherbereich, USB-Schnittstelle des Rechners, Drucker, Netzwerkschnittstelle) zu ihrer Ausführung. Sie beantragen den Zugriff darauf beim Betriebssystem und geben ihn später wieder zurück. Zu einem Deadlock kommt es dann und nur dann, wenn die vier Coffman-Bedingungen erfüllt sind:

1. mutual exclusion (gegenseitiger Ausschluss): Auf eine gegebene Ressource kann nur jeweils ein einziger Prozess Zugriff haben.
2. hold and wait (Halten und Warten): Hält ein Thread eine Ressource, so kann er zugleich andere beantragen.
3. non preemption (Ununterbrechbarkeit): Der Zugriff eines Threads auf eine Ressource kann nicht unterbrochen werden, d.h. dem Thread kann die Ressource nicht von außen entzogen werden (z.B. durch das Betriebssystem)
4. cyclic waiting (zyklisches Warten): Im resource allocation graph gibt es mindestens einen Zyklus.

Hier noch ein Beispiel für einen resource allocation graph mit deadlock:

Da Deadlocks nur dann auftreten können, wenn alle vier Coffman-Bedingungen erfüllt sind, reicht es, eine davon außer Kraft zu setzen, um Deadlocks sicher zu verhindern. Hier ein paar mögliche Strategien dazu:

• hold and wait kann ausgeschlossen werden, wenn jeder Thread zu Beginn alle Ressourcen anfordern muss, die er benötigt, und ihm das Betriebssystem nur entweder alle Ressourcen auf einmal zuspricht (und den Thread dann startet) oder keine Ressourcen zuspricht und den Thread so lange warten lässt, bis alle benötigten Ressourcen zur Verfügung stehen. Natürlich schränkt das die Möglichkeit zur nebenläufigen Ausführung möglichst vieler Threads etwas ein.
• cyclic waiting kann ausgeschlossen werden, indem die Ressourcen durchnummeriert werden und nur in der Reihenfolge dieser Nummerierung angefordert werden dürfen.
• mutual exclusion kann ausgeschlossen werden, wenn ein Betriebsmittel, das eigentlich nur ein Thread gleichzeitig benutzen kann (z.B. ein Drucker) mit einer Warteschlange versehen wird, in die die Threads ihre Aufträge an dieses Betriebsmittel ablegen können und ein eigener Thread die Warteschlange der Reihen nach abarbeitet.
• Der Ausschluss von non-preemption ist schwer machbar, kann aber beispielsweise beim Arbeitsspeicher umgesetzt werden, indem lange nicht verwendete Speicherbereiche des RAM in einen Massenspeicher (z.B. SSD) ausgelagert und nur bei Bedarf wieder zurückgeholt werden ("swapping").

Das Philosophenproblem wurde vom Informatiker Edsger W. Dijkstra formuliert um die Problematik der Nebenläufigkeit/Verklemmung zu illustrieren.

"Fünf Philosophen, nummeriert von eins bis fünf, leben in einem Haus, in dem der Tisch für sie gedeckt ist, wobei jeder Philosoph seinen eigenen Platz am Tisch hat. Ihr einziges Problem – neben dem der Philosophie – ist, dass es sich bei dem servierten Gericht um eine sehr schwierige Sorte Spaghetti handelt, die mit zwei Gabeln gegessen werden muss. Zwischen den Tellern befindet sich jeweils eine Gabel, sodass dies für einen einzelnen Philosophen kein Problem darstellt. Allerdings können zwei Nachbarn nicht gleichzeitig essen." (Quelle: Wikipedia-Artikel)