Deadlock (Informatik)

Begriff und Voraussetzungen

Ein Deadlock oder eine Verklemmung ist in der Informatik eine zyklische Wartesituation zwischen mehreren Prozessen. Jeder beteiligte Prozess wartet auf die Freigabe mindestens eines Betriebsmittels (einer Ressource), das bereits exklusiv von einem anderen beteiligten Prozess belegt wird. Allgemeiner liegt ein Deadlock vor, wenn jeder Prozess einer Menge auf ein Ereignis wartet, das nur ein anderer Prozess derselben Menge verursachen kann.

Ein einfaches Beispiel: Prozess π₁ besitzt den Bildschirm und benötigt zusätzlich den Drucker. Prozess π₂ besitzt den Drucker und fordert den Bildschirm. Keiner der beiden Prozesse kann weiterarbeiten oder seine Ressource freigeben.

Nach Coffman et al. sind vier Bedingungen hinreichend dafür, dass eine Verklemmung möglich ist:

• No Preemption: Betriebsmittel werden ausschließlich durch die Prozesse selbst freigegeben; ihr Ressourcenzugriff kann nicht unterbrochen werden.
• Hold and Wait: Prozesse fordern weitere Betriebsmittel an und behalten gleichzeitig den Zugriff auf bereits erhaltene.
• Mutual Exclusion: Ein Betriebsmittel darf jeweils nur von einem einzigen Prozess benutzt werden.
• Circular Wait: Mindestens zwei Prozesse stehen bezüglich ihrer Betriebsmittel in einer zirkulären Abhängigkeit.

Verklemmungen können in Multitasksystemen auftreten, wenn mehrere Prozesse parallel laufen können und die Reihenfolge der Betriebsmittelvergabe nicht festgelegt ist. Trotz zirkulärer Abhängigkeit entsteht nicht zwingend ein Deadlock, wenn die Ausführungszeiten der Prozesse genügend weit auseinanderliegen. Neben dem Ignorieren einer möglichen Verklemmung durch den Vogel-Strauß-Algorithmus kommen Prävention, Vermeidung und Beseitigung in Betracht.

Verklemmungen verhindern

Ein einzelner Prozess in einem geschlossenen System kann nicht verklemmen. Auch ein Prozess, der nur ein Betriebsmittel benötigt, kann nicht verklemmen. Da eingetretene Verklemmungen meist nicht normal beseitigt werden können, soll die Betriebsmittelverwaltung präventiv eine passende Sequentialisierung, also eine geordnete Abfolge, erreichen.

Von Verhinderung spricht man, wenn mindestens eine der vier Coffman-Bedingungen nicht erfüllt wird:

• Preemption: Einem Prozess werden Betriebsmittel entzogen und einem anderen Prozess zugeteilt.
• Hold and Wait verhindern: Jeder Prozess meldet zu Beginn alle benötigten Betriebsmittel. Er erhält sie nur dann alle auf einmal, wenn sie gleichzeitig frei sind.
• Mutual Exclusion beseitigen: Der exklusive Zugriff wird aufgehoben. Als Alternativen werden Spooling, etwa beim Drucker, oder die Virtualisierung von Betriebsmitteln, etwa der CPU, genannt.
• Circular Wait ausschließen: Betriebsmittel werden linear geordnet und dürfen nur in dieser festgelegten Reihenfolge angefordert oder zugeteilt werden.

Verklemmungen vermeiden

Bei der Verklemmungsvermeidung bleiben Deadlocks theoretisch möglich. Das System überwacht die Prozesse jedoch so, dass keine Verklemmung entsteht. Grundlage ist der sichere Zustand: Ein Zustand ist sicher, wenn mindestens eine Scheduling-Reihenfolge existiert, in der alle vorhandenen Prozesse beendet werden können, selbst wenn sie noch ihre maximalen Ressourcenanforderungen stellen.

Dafür müssen alle möglichen folgenden Vorgänge bekannt sein. Häufig wird der Bankieralgorithmus verwendet: Betriebsmittel werden nur zugeteilt, wenn danach weiterhin eine vollständige Rückgabe möglich ist. Im Beispiel besitzt π₁ fünf Betriebsmittel und benötigt noch drei; π₂ besitzt zwei und fordert noch acht. Sind drei weitere Betriebsmittel verfügbar, erhält π₁ diese drei, kann vollständig beendet werden und gibt danach insgesamt acht Betriebsmittel frei. Diese können anschließend π₂ zugeteilt werden. Praktisch ist diese Methode oft schwierig, weil sich schwer vorhersagen lässt, welcher Prozess genügend Betriebsmittel freigibt.

In Datenbanksystemen werden für Schreib- und Lesesperren die Verfahren wait/die und wound/wait verwendet. Jede Transaktion erhält bei ihrer Instanziierung einen Zeitstempel. Bei wait/die wartet eine ältere anfordernde Transaktion, wenn eine jüngere die Sperre hält; fordert eine jüngere eine von einer älteren gehaltene Sperre, startet sie neu, behält aber ihren alten Zeitstempel. Bei wound/wait wird eine jüngere Sperrbesitzerin neu gestartet, wenn eine ältere Transaktion ihre Sperre fordert; fordert dagegen eine jüngere Transaktion eine von einer älteren gehaltene Sperre, wartet sie. „Die“ setzt die anfordernde Transaktion zurück, „wound“ versucht, den Sperrbesitzer zurückzusetzen. Befindet sich dieser bereits in der Freigabe, kann auf die Rücksetzung verzichtet und gewartet werden.

Eingetretene Verklemmungen auflösen

Eine Verklemmung lässt sich durch gezielten Prozessabbruch beseitigen. Dabei sollte möglichst ein Prozess gewählt werden, dessen Abbruch die Verklemmung sicher löst. Falls nötig, wird der Vorgang wiederholt. Datenverlust lässt sich durch eine passende Auswahl begrenzen; deshalb ist dieses Verfahren nur schlecht automatisierbar.

Bei der Beseitigung durch Preemption wird ein Prozess, der eine Ressource belegt, suspendiert und später fortgesetzt. Die dadurch nicht mehr blockierten Prozesse können ihre Aufgaben beenden. Dies setzt genaue Kenntnis der Tätigkeit des unterbrochenen Prozesses voraus, um Fehler auszuschließen, und ist meist nicht automatisch umsetzbar.

Beim Rollback werden für Prozesse in festgelegten Zeitabständen Sicherungen angelegt. Bei einer Verklemmung wird ein ausgewählter verantwortlicher Prozess auf seinen zuletzt gesicherten Zustand zurückgesetzt und suspendiert. Nicht jeder Prozess eignet sich dafür gleichermaßen: Ein Festplatten-Schreibvorgang ist meist besser zurücksetzbar als ein CD/DVD-Brennvorgang. Der unterbrochene Prozess setzt erst fort, wenn seine Betriebsmittel verfügbar sind, und kann in ungünstigen Fällen verhungern.

Abgrenzung und Beispiele außerhalb der Informatik

Ein Livelock ist ebenfalls eine Blockierung, welche die weitere Programmausführung verhindert. Anders als beim Deadlock verharren die Prozesse nicht wartend in einem festen Zustand. Sie bleiben aktiv und wechseln ständig zwischen mehreren Zuständen, aus denen sie nicht entkommen, können ihre Aufgaben aber trotzdem nicht erledigen. Anschaulich weichen zwei Personen in einem Gang beide immer in dieselbe Richtung aus und blockieren sich dadurch fortwährend. Bei einem Deadlock stünden sie einander gegenüber und warteten jeweils darauf, dass die andere Person zur Seite geht.

Im Bahnbetrieb bezeichnet Deadlock eine Situation, in der zwei oder mehr Züge einander so blockieren, dass die Sicherungstechnik keine regulären Zugfahrten mehr zulässt. Jeder Zug blockiert einen Zugfolgeabschnitt und wartet auf die Einfahrt in den nächsten. In Algorithmen zur Stellwerkssteuerung zeigt sich dies beim Stellen einer Fahrstraße als Zirkelbezug.

Auch eine Kreuzung mit vier gleichzeitig zufahrenden Fahrzeugen wird oft als Beispiel genannt. Bei Rechtsverkehr würde nach „rechts vor links“ (StVO, §8) jede Fahrerin oder jeder Fahrer dem rechts stehenden Fahrzeug Vorfahrt gewähren; alle vier blockieren sich gegenseitig. Durch Handzeichen kann ein Vorfahrtsrecht vereinbart werden, sodass nach dem ersten Fahrzeug die übrigen nacheinander fahren können. Informatikfachlich ist dies nur dann ein Deadlock, wenn mehrere gemeinsam genutzte Ressourcen betrachtet werden, zum Beispiel einzelne Kreuzungsviertel, nicht die gesamte Kreuzung als eine Ressource.