Die Fähigkeit von Threads, sich gegenseitig vom Betreten eines bestimmten Programmbereichs abhalten zu können, führt zu einem Problem, das ohne das Setzen von Sperren gar nicht vorhanden ist. Das liegt daran, dass es in Java wie auch in anderen Programmiersprachen möglich ist, dass ein Thread in einem gesperrten Bereich eine weitere Sperre zu einem anderen Sperrobjekt (oder einer anderen Sperrklasse) setzen kann. (An dieser Stelle ist ein kleiner Hinweis für die Programmierpraxis angebracht: Setzt ein Java-Thread in einem gesperrten Bereich die dafür verwendete Sperre erneut, dann bleibt dies wirkungslos, ohne dass eine Ausnahme (Exception) erzeugt wird.)
In dem folgenden Beispiel wird ein java-ähnlicher Pseudocode verwendet. Beschrieben wird eine Situation, bei der ein Thread thr-1 ein Betriebsmittel A (das könnten Speicherplätze sein) für sich allein benötigt und es dadurch schützt, indem er die Sperre eines Objekts obj-1 setzt, um so andere Threads von der Benutzung von A auszuschließen. Während der Bearbeitung von A benötigt er zusätzlich auch noch ein Betriebsmittel B, und zwar ebenfalls für sich allein. Er schützt B durch das Setzen der Sperre eines Objekts obj-2. Durch dieses Vorgehen werden zwei synchronized-Blöcke ineinander geschachtelt:
Ein Problem entsteht, wenn ein anderer Thread (thr-2) ebenfalls die beiden Betriebsmittel A und B für sich allein benötigt, sie aber in umgekehrter Reihenfolge sperrt. Jetzt kann es passieren, dass, wegen der Nebenläufigkeit der beiden Threads, thr-1 das Betriebsmittel A sperrt und thr-2 B. Wenn jetzt thr-1 B benötigt und thr-2 A, dann warten beide vergeblich darauf, dass der jeweils andere seine Sperre aufhebt. Eine solche Situation wird als Verklemmung (Deadlock) bezeichnet.
Ein derartiger Sachverhalt kann durch einen sogenannten Anforderungsgraphen anschaulich dargestellt werden. Bei ihm werden für Threads Rechtecke und für Betriebsmittel Kreise verwendet werden. Dabei bedeutet
Für das Beispiel mit den Threads thr-1 und thr-2 und den Betriebsmitteln A und B kann folgender Anforderungsgraph entstehen:
In der dargestellten Situation blockieren sich die beiden Threads gegenseitig. Sie haben sich verklemmt. In einem ablaufenden Programm ist eine Verklemmung daran zu erkennen, dass im Anforderungsgraphen ein Zykel (eine Schleife) entstanden ist.
Bei Betriebs- und Datenbanksystemen sind Verklemmungen an der Tagesordnung. Da Threads (oder allgemeiner Prozesse) sich nicht selbst aus einer Verklemmung befreien können, sondern Hilfe benötigen, sind insbesondere in den beiden genannten Fachgebieten Verfahren entwickelt worden, um eine Verklemmung entweder
Beide Vorgehensweisen sind jede auf ihre Art recht aufwändig. Man denke dabei auch an rechnerübergreifende Verklemmungen, bei denen jeweils im lokalen Teil des Anforderungsgraphen kein Zykel erkennbar ist.
Um eine Verklemmung auflösen zu können, muss zunächst festgestellt werden, dass eine solche vorliegt. Dazu ist der Anforderungsgraph aufzubauen und nach Zykeln zu durchsuchen. Wird eine Verklemmung erkannt, kann sie aufgelöst werden, indem einer der an der Verklemmung beteiligten Threads beendet wird und er dadurch seine Sperren freigibt. Bei ungeschicktem Vorgehen bleiben inkonsistente Daten zurück! Die Daten bleiben konsistent, wenn der Prozess nicht beendet, sondern zurückgesetzt wird. Das ist ein Vorgang, der als Rollback bezeichnet wird. Bei ihm wird zu jedem Thread in einer Logdatei zu jedem Datum, das er ändert, der Wert des Datums vor seiner Veränderung (das sogenannte Before Image) festgehalten. Ein Einspielen dieser Werte in zeitlich rückwärtiger Reihenfolge setzt den Thread zurück. Das heißt, dass seine Auswirkungen auf die Daten ungeschehen gemacht werden.
Das Auflösen von Verklemmungen ist typisch für die Transaktionsverarbeitung in Datenbanksystemen. Dort ist der Aufwand, um die Before Images zu pflegen, in der Regel noch überschaubar. In Betriebssystemen dagegen wird üblicherweise mit Deadlockvermeidungsverfahren gearbeitet.
Im Folgenden wird einer der bekanntesten Algorithmen zur Vermeidung von Deadlocks kurz in seiner prinzipiellen Arbeitsweise vorgestellt. Er ist 1965 von dem niederländischen Informatiker Edsger W. Dijkstra (1930-2002) veröffentlicht worden. (Dijkstra ist insbesondere durch seine Arbeiten an der Entwicklung des strukturierten Programmierens bekannt gewordenen.) Sein Algorithmus lehnt sich an die Arbeitsweise eines Bankiers an und wird deshalb als Bankieralgorithmus bezeichnet. Er arbeitet folgendermaßen:
Einem Bankier ist von seiner Bank ein Verfügungsrahmen zugewiesen worden. In diesem Rahmen - und nur in ihm - kann der Bankier Kreditwünsche von Kunden bedienen. Er betreut einen festen Kundenkreis und hat jedem Kunden einen bestimmten Kreditrahmen eingeräumt. (Die Kunden entsprechen den Threads, der Verfügungsrahmen des Bankiers den vorhandenen Betriebsmitteln und die gerade in Anspruch genommen Kredite den gerade gesperrten Betriebsmitteln.)
Als Beispiel könnte eine Bank einem Bankier einen Verfügungsrahmen von 10.000 Euro zugewiesen haben. Dieser Bankier könnte vier Kunden namens A, B, C und D betreuen, denen er folgende Kreditrahmen eingeräumt hat:
Wollen alle Kunden ihren Kreditrahmen ausschöpfen, werden dafür 22.000 Euro benötigt. Da dem Bankier aber lediglich 10.000 Euro zur Verfügung stehen, hat er folgende Vergaberegel festgelegt:
Wenn bei diesem Vergabeverfahren eine Situation entsteht, bei der keiner der Kunden seinen Kreditrahmen ausgeschöpft hat, und der Bankier keinem von ihnen einen Kreditwunsch erfüllen kann, dann kann es passieren, dass alle Kunden, um weiterarbeiten zu können, ihren Kreditrahmen ausschöpfen müssen. Dann liegt eine Verklemmung vor, denn kein Kunde kann weiterarbeiten und keiner von ihnen kann einen Kredit bekommen.
In Weiterführung des einleitenden Beispiels betrachte man die folgende Situation, bei der 8.000 Euro bereits zugeteilt worden sind:
Es kann passieren, dass in dieser Situation alle Kunden ihren maximalen Kredit verlangen. Das heißt, der Kunde A fordert fordert 5.000 Euro, der Kunde B 4.000 usw. Dann entsteht keine Verklemmung, denn der Bankier kann die Anforderung des Kunden C erfüllen. Er vergibt die noch freien 2.000 Euro an diesen Kunden. Die Anderen müssen warten, bis C seinen Kredit zurückgezahlt hat, was nach der Vergaberegel nach einer festgelegten Zeit erfolgen muss. Der Bankier hat dann 4.000 Euro zur Verfügung und kann damit die Anforderung von B erfüllen, usw.
Eine Kreditvergabesituation, wie die in der Tabelle beschriebene, heißt sicher. Bleibt der Bankier in sicheren Situationen, dann kann keine Verklemmung eintreten. Angenommen, in der eben dargestellten sicheren Situation verlangt der Kunde B einen Kredit von 1.000 Euro, und weiter angenommen, der Bankier gibt diesem Ersuchen nach, dann entsteht folgende neue Situation:
Die Tabelle beschreibt jetzt eine Situation, die unsicher genannt wird. Sie kann, muss jedoch nicht zwangsläufig, zu einer Verklemmung führen. Wenn aber in dieser Situation alle Kunden ihren maximalen Kredit verlangen, dann kann keine ihrer Anforderung erfüllt werden und kein Kunde kann weiterarbeiten. Dann liegt eine Verklemmung vor. Damit kann der Bankieralgorithmus in einer sehr groben Form, die hier ausreichen soll, folgendermaßen formuliert werden:
Neben dem Bankiersalgorithmus gibt es ein weiteres weit verbreitetes Verfahren zur Verklemmungsvermeidung. Dabei werden alle zu sperrenden Betriebsmittel in einer festen Reihenfolge angeordnet, also durchnummeriert, und dürfen nur in dieser Reihenfolge gesperrt werden. Angenommen es handle sich um die Betriebsmittel B-1, B-2, ..., B-n. Und weiter angenommen, ein Thread habe bereits ein B-m (1 ≤ m ≤ n) gesperrt, dann darf er anschließend nur noch Betriebsmittel B-j mit j > m sperren. Wenn alle beteiligten Threads nur anschaulich vorwärts sperren, können im Anforderungsgraphen keine Zykel und damit kann auch keine Verklemmung entstehen.
Dieses Verfahren ist sehr einfach, allerdings auch sehr einschränkend. Angenommen, es gebe nur zwei Betriebsmittel A und B und zwar in der Anordnung A vor B. Dazu soll es zwei Threads thr-1 und thr-2 geben, die mit diesen Betriebsmitteln jeweils allein arbeiten wollen. Weiter angenommen, thr-1 benötigt erst A und dann B und thr-2 erst B und dann A. Und weiter angenommen thr-1 sperrt A und thr-2 sperrt B, dann muss thr-1, sobald er B braucht und es sperren will, auf dessen Freigabe warten. thr-2 dagegen darf A gar nicht mehr sperren und kommt deshalb nicht in eine Wartesituation, denn der Versuch A nach B zu sperren würde die festliegende Reihenfolge verletzen. thr-1 kann seine Aufgabe erfüllen, thr-2 dagegen nicht. Auch wenn thr-2 zuerst B benötigt, muss er doch zunächst A sperren (und dabei mit thr-1 konkurrieren).