Deadlock: erkennen, verhindern und auflösen

Ein Deadlock (auch Verklemmung) ist ein Zustand, in dem mehrere Prozesse im Kreis aufeinander warten. Jeder beteiligte Prozess wartet darauf, dass ein Betriebsmittel frei wird, das ein anderer beteiligter Prozess schon für sich allein belegt hat. Betriebsmittel (Ressourcen) sind zum Beispiel ein Bildschirm oder ein Drucker.

Verklemmungen können in Systemen eintreten, die mehrere Prozesse parallel ablaufen lassen können und bei denen die Reihenfolge der Betriebsmittelvergabe nicht festgelegt ist. Liegen die Ausführungszeiten der im Kreis abhängigen Prozesse weit genug auseinander, kommt es nicht zum Deadlock. Ein Prozess, der nur ein Betriebsmittel benötigt, kann nicht verklemmen.

Nach Coffman et al. sind vier Bedingungen hinreichend für die Möglichkeit einer Verklemmung (siehe Tabelle). Gelten alle vier, ist ein Deadlock also möglich, aber nicht sicher. Wird mindestens eine Bedingung nicht erfüllt, spricht man von einer Verhinderung. Im Ablauf mit π1 und π2 siehst du nur zwei Bedingungen: Hold and Wait und Circular Wait. Ob die Betriebsmittel exklusiv sind und ob man sie entziehen kann, bleibt in diesem Beispiel offen. Aus diesem einen Beispiel folgt daher nicht, dass dort alle vier gelten.

Zwei Abgrenzungen: Bei einem Deadlock um Betriebsmittel müssen immer mehrere gemeinsam genutzte Ressourcen vorhanden sein, gegenseitiges Blockieren allein genügt nicht. Die Kreuzung ist deshalb nur ein Deadlock-Beispiel, wenn du sie in mehrere Ressourcen aufteilst, etwa in Kreuzungsviertel. Beim Livelock verharren die Prozesse nicht im Wartezustand, sondern wechseln ständig zwischen Zuständen, aus denen sie nicht mehr entkommen. Jeder Prozess bleibt dabei aktiv, kann aber seine Aufgabe nicht abarbeiten.

Ein Betriebsmittelzuteilungsgraph (englisch Resource Allocation Graph, RAG) ist ein gerichteter Graph: Seine Kanten haben eine Pfeilrichtung. Er stellt Ressourcen und Prozesse in Beziehung und dient der Analyse von Deadlocks. Jeder Knoten ist entweder ein Prozessknoten Pi oder ein Ressourcenknoten Rj.

Die Pfeilrichtung trägt die Bedeutung. Eine Kante von Rj zu Pi bedeutet: Der Prozess Pi hält die Ressource Rj. Eine Kante von Pk nach Rj bedeutet: Der Prozess Pk wartet darauf, dass die Ressource Rj frei wird.

Ein Zyklus ist in einem Graphen ein Kantenzug mit unterschiedlichen Kanten, bei dem Start- und Endknoten gleich sind. In einem gerichteten Graphen heißt er gerichteter Zyklus. Folge also immer den Pfeilen, nie gegen sie. Algorithmisch lassen sich Zyklen durch eine modifizierte Tiefensuche finden. Gibt es im RAG keinen Zyklus, kann kein Deadlock auftreten.

Ein Zyklus in Pfeilrichtung ist der Wartezyklus, also das Beispiel für die Bedingung Circular Wait. Er zeigt nur diese eine Bedingung. Ob ein Deadlock vorliegt, sagt dir der Zyklus allein nicht. In den Aufgaben suchst du deshalb nur den Zyklus in Pfeilrichtung.

Die drei Begriffe unterscheiden sich darin, wann sie eingreifen. In der Literatur werden Verhinderung und Vermeidung auch öfter vertauscht. Hier gelten die Begriffe so, wie sie unten stehen.

Prävention (Verhinderung): Mindestens eine der vier Bedingungen wird nicht erfüllt. Die Tabelle zeigt je eine Maßnahme. Das konservative 2-Phasen-Sperrprotokoll (Preclaiming) setzt zu Beginn einer Transaktion alle benötigten Sperren auf einmal und verhindert so in jedem Fall Deadlocks. Es führt aber zu einem hohen Verlust an Parallelität, und man muss im Voraus wissen, welche Sperren nötig sind.

Vermeidung: Deadlocks sind dabei theoretisch möglich, das System überwacht die Prozesse aber so, dass sie nicht verklemmen. Dafür müssen alle möglichen folgenden Vorgänge bekannt sein. Grundlage ist der sichere Zustand. Der Bankieralgorithmus (Dijkstra, 1965) dient der Vermeidung. Er kennt A (verfügbare Ressourcen), C (an einen Prozess vergebene) und R (von ihm noch benötigte). Gilt R ≤ A für jede Ressourcenart einzeln, wird der Prozess abgearbeitet und gibt danach seine Ressourcen frei: A = A + C. Findet der Algorithmus eine Reihenfolge, in der alle Prozesse ohne Verklemmung ablaufen, ist der Zustand sicher. Sonst heißt er unsicher: Ein Deadlock ist dann möglich, aber nicht sicher eingetreten. In der Praxis findet der Bankieralgorithmus kaum Anwendung, weil er voraussetzt, dass alle zur Laufzeit benötigten Ressourcen schon vorher genau bekannt sind.

Auflösung (Beseitigung): Der Deadlock ist schon eingetreten und wird beseitigt. Die einfachste Art ist das gezielte Abbrechen von Prozessen. Dabei geht meist Daten verloren. Das lässt sich durch geschickte Prozessauswahl verringern, deshalb lässt sich das Verfahren nur sehr schlecht automatisieren. Weitere Möglichkeiten sind, einen Prozess zu suspendieren und später fortzusetzen, oder ein Rollback auf den zuletzt gesicherten Zustand. Nicht alle Prozesse lassen sich problemlos zurücksetzen. Ein Festplatten-Schreibvorgang eignet sich in den meisten Fällen besser als ein CD/DVD-Brennvorgang.

Eine Maßnahme begründest du so: Nenne die Bedingung oder den Zeitpunkt, den sie trifft, und prüfe ihre Voraussetzung. Das Preclaiming braucht zum Beispiel den Bedarf im Voraus, der Bankieralgorithmus ebenfalls.