8.5 Deadlock-Behandlung

8.5.2 Deadlock-Vermeidung

Bei der Deadlock-Vermeidung (avoidance) werden potentielle Deadlocks im voraus erkannt und durch entsprechende Maßnahmen vermieden; im Gegensatz zur Verhütung ist also eine Laufzeitunterstützung zur Deadlock-Behandlung erforderlich. Die Vermeidung der Deadlocks erfolgt generell durch Zurücksetzen von möglicherweise betroffenen Transaktionen. Ein einfacher Vermeidungsansatz wäre, im Falle eines Sperrkonfliktes die in Konflikt geratene Transaktion bzw. den Sperrbesitzer abzubrechen, so daß keine Blockierungen auftreten. Dieser Ansatz scheidet jedoch aufgrund der hohen Anzahl von Rücksetzungen aus. Wir betrachten stattdessen Alternativen, welche weniger Rücksetzungen verursachen und Zeitmarken bzw. Zeitintervalle zur Deadlock-Vermeidung verwenden.

Wait/Die und Wound/Wait

Zwei einfache Verfahren zur Deadlock-Vermeidung sind Wait/Die und Wound/Wait [RSL78]. Bei ihnen wird wie für Zeitmarkenverfahren (Kap. 8.2) jeder Transaktion T bei BOT eine global eindeutige Zeitmarke ts (T) zugewiesen, wobei hier die Kombination aus lokaler Uhrzeit und Knoten-ID ausreicht. Im Gegensatz zu den Zeitmarkenverfahren erfolgt jetzt die Synchronisation jedoch mit einem Sperrprotokoll. Die Transaktions-Zeitmarken werden lediglich im Falle eines Sperrkonfliktes herangezogen, um Deadlocks zu vermeiden. Dies kann erreicht werden, wenn vorgeschrieben wird, daß bei einem Sperrkonflikt stets nur die ältere (bzw. die jüngere) der beteiligten Transaktionen warten darf und anderenfalls der Konflikt durch Rücksetzung einer Transaktion aufgelöst wird. Denn dann kann sich keine zyklische Wartebeziehung mehr bilden.

Die bei Wait/Die bzw. Wound/Wait verwendete Behandlung von Sperrkonflikten zeigt Abb. 8-9. Im Wait/Die-Verfahren (Abb. 8-9a) darf die die Sperre anfordernde Transaktion Ti nur dann warten, wenn sie älter ist als die Transaktion Tj, welche die Sperre besitzt[34]. Ist dagegen Ti jünger als Tj, so muß Ti "sterben" (die), d.h., sie wird zurückgesetzt. Damit warten bei diesem Ansatz stets ältere Transaktionen auf jüngere, jedoch nicht umgekehrt. Im Wound/Wait-Verfahren (Abb. 8-9b) dagegen warten stets jüngere Transaktionen auf ältere. Ist die anfordernde Transaktion Ti älter als der Sperrbesitzer Tj, so wird jedoch nicht die anfordernde Transaktion, sondern der Sperrbesitzer abgebrochen ("verwundet", wound). Es handelt sich dabei also um einen preemptiven Ansatz[35]. Beide Strategien vermeiden Deadlocks ohne zusätzliche Kommunikationsvorgänge, da die Zeitstempel lokal zugewiesen und die Zeitstempelvergleiche im Konfliktfall lokal durchgeführt werden können. Es kann allerdings zu Rücksetzungen kommen, ohne daß ein Deadlock vorliegt.

Abb. 8-9: Konfliktbehandlung bei Wait/Die und Wound/Wait
(Sperranforderung von Ti gerät in Konflikt mit Tj)

Beispiel 8-13

Für den Schedule in Abb. 8-1a tritt mit einem RX-Protokoll ein Sperrkonflikt auf (Beispiel 8-2), es liegt jedoch kein Deadlock vor. Für Wait/Die wird der Sperrkonflikt dennoch durch Rücksetzung von T2 aufgelöst, da T2 jünger als T1 ist. Für Wound/Wait dagegen wartet T2 auf die Sperrfreigabe durch T1.

Beispiel 8-14

Für den in Abb. 8-8 gezeigten Deadlock (Beispiel 8-11) sei T1 älter als T2, d.h. ts (T1) < ts (T2). Bei Wait/Die wartet T1 beim Sperrkonflikt in Rechner R2, da sie älter als T2 ist. Dagegen muß T2 beim Sperrkonflikt in R1 sterben. Bei Wound/Wait wird beim Sperrkonflikt von T1 in R2 der jüngere Sperrbesitzer T2 verwundet, also zurückgesetzt. In beiden Fällen wird der Deadlock also durch Rücksetzen der jüngeren Transaktion T2 aufgelöst.

Bei Wait/Die und Wound/Wait werden im Gegensatz zu den Zeitmarkenverfahren (Kap. 8.2) ältere Transaktionen bevorzugt, da im Falle einer Rücksetzung stets die jüngere der am Konflikt beteiligten Transaktionen zurückgesetzt wird. Daher empfiehlt es sich generell, bei Wait/Die und Wound/Wait nach einer Rücksetzung die ursprüngliche Zeitmarke beizubehalten, um die Wahrscheinlichkeit weiterer Rücksetzungen zu begrenzen. Die Bevorzugung älterer Transaktionen ist besonders ausgeprägt bei Wound/Wait, wo sogar der Sperrbesitzer abgebrochen wird, falls er jünger ist als die anfordernde Transaktion. Bei Wait/Die ist das Durchkommen älterer Transaktionen auch gesichert, jedoch nimmt mit zunehmendem Alter die Wahrscheinlichkeit von Blockierungen zu. Bei Wait/Die sollte eine zurückgesetzte Transaktion T2 auch erst dann wieder gestartet werden, wenn die in Konflikt stehende, ältere Transaktion T1 beendet ist. Denn anderenfalls würde beim erneuten Zugriff auf das betreffende Objekt wiederum ein Abbruch von T2 erfolgen. Diese Gefahr besteht bei Wound/Wait nicht, da hier der (jüngere) Sperrbesitzer zurückgesetzt wird. Bei einem erneuten Zugriff auf das Objekt während der Wiederausführung erfolgt für die jüngere, anfordernde Transaktion jedoch keine Rücksetzung, sondern sie kann auf die Sperrfreigabe warten.
In der Simulationsstudie [ACM87] zeigte Wound/Wait ein konsistent besseres Leistungsverhalten als Wait/Die.

Dynamische Zeitmarken und Zeitintervalle

Wait/Die und Wound/Wait basieren beide auf statischen Zeitmarken, da sie während der Ausführung der Transaktion nicht mehr geändert werden. In [BEHR82] wurde die Verwendung dynamischer Zeitmarken vorgeschlagen, wobei Transaktionen zunächst ohne Zeitmarke gestartet werden. Erst wenn der erste Konflikt mit einer anderen Transaktion erfolgt, wird eine Transaktions-Zeitmarke bestimmt. Dabei kann stets eine Zeitmarke gewählt werden, so daß der Konflikt ohne Rücksetzung überstanden wird. Damit überlebt eine Transaktion zumindest den ersten Sperrkonflikt, womit die Anzahl von Rücksetzungen gegenüber der Verwendung statischer Zeitmarken reduziert wird.

Beispiel 8-15

Für den Schedule in Abb. 8-1a verursachte Wait/Die die Rücksetzung von T2, obwohl kein Deadlock vorlag (Beispiel 8-13). Diese Rücksetzung kann mit dynamischen Zeitmarken vermieden werden, da die Zuordnung der Zeitmarken für T1 sowie T2 erst vorgenommen wird, wenn es aufgrund des Lesezugriffs von T2 zum Sperrkonflikt mit T1 kommt. Im Falle von Wait/Die weist man T2 zu diesem Zeitpunkt eine kleinere Zeitmarke als T1 zu, so daß T2 auf die Sperre warten kann, anstatt zurückgesetzt zu werden.

Eine Verallgemeinerung der Nutzung dynamischer Zeitmarken stellt die Verwendung von Zeitintervallen dar [BEHR82]. Dabei wird jeder Transaktion anstelle einer Zeitmarke ein Zeitintervall zugeordnet, das die mögliche Position der Transaktion in der Serialisierungsreihenfolge eingrenzt. Das zunächst unendliche Zeitintervall wird bei jedem Sperrkonflikt dynamisch verkleinert. Ein leeres Zeitintervall, das eine Rücksetzung erzwingt, ergibt sich für eine Transaktion erst bei einem Sperrkonflikt mit einer Transaktion mit disjunktem Zeitintervall, welches in falscher zeitlicher Relation zum eigenen Intervall steht. Durch geschickte Wahl der Zeitintervalle kann das Ausmaß unnötiger Rücksetzungen jedoch i.a. geringer als mit statischen oder dynamischen Zeitintervallen gehalten werden [KP85, NW87]. Dafür ergibt sich eine höhere Komplexität der Realisierung.

[34] Sollten mehrere Transaktionen eine inkompatible Sperre halten, müssen diese alle jünger als die anfordernde Transaktion sein.
[35] Bei Wound/Wait kann auf das Zurücksetzen des Sperrbesitzers verzichtet werden, wenn (lokal) erkannt wird, daß diese Transaktion nicht blockiert ist, da dann kein Deadlock möglich ist. Insbesondere kann das Zurücksetzen entfallen, wenn die Transaktion sich bereits in der Commit-Behandlung befindet und die Sperren daher ohnehin bald freigibt.
Wait/Die und Wound/Wait
Dynamische Zeitmarken und Zeitintervalle