Eine Verklemmung (Deadlock) entsteht, wenn zwei oder mehr Transaktionen zyklisch aufeinander warten, weil jede eine Sperre hält, die die andere benötigt. Das DBMS erkennt Deadlocks durch Zyklensuche im Wartegraph und löst sie durch Rollback (Opfer). Vermeidungsstrategien wie Preclaiming (alle Sperren vorab) sowie die Zeitstempel-Verfahren Wait-Die und Wound-Wait verhindern Zyklen bereits im Vorfeld.
Ein Deadlock liegt vor, wenn zwei oder mehr Transaktionen zyklisch aufeinander warten. T1 hält eine Sperre auf A und benötigt B, während T2 B hält und A benötigt. Ohne Eingriff wartet beides ewig. Voraussetzung ist typischerweise das strenge 2PL-Protokoll, das Sperren bis EOT hält. Deadlocks sind ein Konsistenzsicherungs-Problem und müssen vom DBMS entdeckt und aufgelöst werden.
Der Wartegraph ist ein gerichteter Graph mit Knoten für Transaktionen und Kanten Ti -> Tj, wenn Ti auf eine Sperre wartet, die Tj hält. Er wird aus der Lock-Tabelle des DBMS gebildet. Enthält der Graph einen Zyklus, liegt ein Deadlock vor. Zyklenerkennung erfolgt per Tiefensuche. Zur Auflösung wird eine Transaktion aus dem Zyklus ausgewählt, zurückgesetzt (abort + R1-Recovery) und dadurch können beide Zyklen mit einem einzigen Opfer aufgebrochen werden, wenn dieses gemeinsame Knoten liegt.
Beim Preclaiming muss jede Transaktion vor Ausführung ihrer Operationen ALLE benötigten Sperren auf einmal erwerben. Erst wenn alle Sperren vorhanden sind, startet die eigentliche Arbeit. In Verbindung mit strengem 2PL bedeutet dies, dass die Sperrmenge sofort auf Maximum steht und bis EOT gehalten wird. Dadurch können niemals zwei Transaktionen wechselseitig auf Sperren warten. Nachteil: geringere Parallelität und man muss im Voraus wissen, welche Objekte gebraucht werden.
Zeitstempel-basierte Vermeidung. Jede Transaktion bekommt beim Start einen eindeutigen Zeitstempel. Ältere TAs haben kleinere Stempel. Fordert T1 eine Sperre an, die T2 hält: Ist T1 älter als T2, wird T2 abgebrochen (wound) und zurückgesetzt, T1 läuft weiter. Ist T1 jünger, wartet T1 regulär. Wound-Wait bevorzugt ältere Transaktionen, indem sie jüngere verdrängen.
Zweite Zeitstempel-Strategie. Fordert T1 eine Sperre, die T2 hält: Ist T1 älter als T2, wartet T1 auf die Freigabe. Ist T1 jünger, wird T1 abgebrochen (die) und mit gleichem Zeitstempel neu gestartet. Bei Wait-Die dürfen nur ältere Transaktionen warten, jüngere sterben und werden neu gestartet. Beide Strategien vermeiden Zyklen, weil die Warterichtung immer nur in eine Zeitstempel-Richtung geht.
Zwei Grundansätze: Deadlock-Erkennung (detection) lässt Deadlocks entstehen und löst sie über den Wartegraph auf. Deadlock-Vermeidung (avoidance/prevention) verhindert Deadlocks strukturell, z.B. durch Preclaiming oder Zeitstempel. Erkennung erlaubt höhere Parallelität, kostet aber Zyklensuche. Vermeidung ist proaktiv, reduziert aber Nebenläufigkeit oder erzeugt unnötige Rollbacks.
Deadlocks sind ein typisches Problem des strengen Zwei-Phasen-Sperrprotokolls (S2PL). Dort werden alle Sperren bis zum EOT gehalten, damit kaskadierendes Rücksetzen ausgeschlossen ist. Genau dieses lange Halten der Sperren macht aber Zyklen im Wartegraph möglich. Ohne 2PL wären Deadlocks im klassischen Sinn nicht das Hauptproblem, dafür aber Inkonsistenzen wie Dirty Read und Lost Update.
Wird ein Zyklus erkannt, wählt das DBMS ein Opfer im Zyklus aus (häufig die jüngste, die mit wenigsten Sperren oder die mit geringsten Kosten). Das Opfer erhält abort und wird per R1-Recovery zurückgesetzt. Die freigewordenen Sperren erlauben den anderen TAs, weiterzulaufen. Liegt ein Knoten in mehreren Zyklen, kann sein Rollback mehrere Verklemmungen gleichzeitig lösen.
T1 hält X-Sperre auf A und will B; T2 hält S-Sperre auf B und will A. Beide warten unendlich.
Fünf TAs bilden zwei überlappende Zyklen. T3 liegt in beiden. Rollback von T3 löst beide Verklemmungen gleichzeitig.
T1 (ts=5, alt) will Sperre, die T2 (ts=10, jung) hält. T1 verletzt T2 -> T2 wird abgebrochen.
Gleiche Situation, aber Wait-Die-Strategie.