Deadlocks und Verklemmungsvermeidung

Zusammenfassung

Eine Verklemmung (Deadlock) entsteht, wenn zwei oder mehr Transaktionen zyklisch aufeinander warten, weil jede eine Sperre haelt, die die andere benoetigt. Das DBMS erkennt Deadlocks durch Zyklensuche im Wartegraph und loest sie durch Rollback (Opfer). Vermeidungsstrategien wie Preclaiming (alle Sperren vorab) sowie die Zeitstempel-Verfahren Wait-Die und Wound-Wait verhindern Zyklen bereits im Vorfeld.

Kernkonzepte

Deadlock (Verklemmung)

Ein Deadlock liegt vor, wenn zwei oder mehr Transaktionen zyklisch aufeinander warten. T1 haelt eine Sperre auf A und benoetigt B, waehrend T2 B haelt und A benoetigt. Ohne Eingriff wartet beides ewig. Voraussetzung ist typischerweise das strenge 2PL-Protokoll, das Sperren bis EOT haelt. Deadlocks sind ein Konsistenzsicherungs-Problem und muessen vom DBMS entdeckt und aufgeloest werden.

Zwei Transaktionen, zwei Sperren, kreuzweise gefordert = Deadlock.

Wait-for-Graph (Wartegraph)

Der Wartegraph ist ein gerichteter Graph mit Knoten fuer Transaktionen und Kanten Ti -> Tj, wenn Ti auf eine Sperre wartet, die Tj haelt. Er wird aus der Lock-Tabelle des DBMS gebildet. Enthaelt der Graph einen Zyklus, liegt ein Deadlock vor. Zyklenerkennung erfolgt per Tiefensuche. Zur Aufloesung wird eine Transaktion aus dem Zyklus ausgewaehlt, zurueckgesetzt (abort + R1-Recovery) und dadurch koennen beide Zyklen mit einem einzigen Opfer aufgebrochen werden, wenn dieses gemeinsame Knoten liegt.

Zyklus im Wartegraph = Deadlock, Opfer bricht den Kreis.

Preclaiming

Beim Preclaiming muss jede Transaktion vor Ausfuehrung ihrer Operationen ALLE benoetigten 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 koennen niemals zwei Transaktionen wechselseitig auf Sperren warten. Nachteil: geringere Parallelitaet und man muss im Voraus wissen, welche Objekte gebraucht werden.

Alles vorab sperren, dann arbeiten - keine Kreise moeglich.

Wound-Wait (Junge warten auf Alte)

Zeitstempel-basierte Vermeidung. Jede Transaktion bekommt beim Start einen eindeutigen Zeitstempel. Aeltere TAs haben kleinere Stempel. Fordert T1 eine Sperre an, die T2 haelt: Ist T1 aelter als T2, wird T2 abgebrochen (wound) und zurueckgesetzt, T1 laeuft weiter. Ist T1 juenger, wartet T1 regulaer. Wound-Wait bevorzugt aeltere Transaktionen, indem sie juengere verdraengen.

Alte darf junge verletzen - junge warten geduldig.

Wait-Die (Alte warten auf Junge)

Zweite Zeitstempel-Strategie. Fordert T1 eine Sperre, die T2 haelt: Ist T1 aelter als T2, wartet T1 auf die Freigabe. Ist T1 juenger, wird T1 abgebrochen (die) und mit gleichem Zeitstempel neu gestartet. Bei Wait-Die duerfen nur aeltere Transaktionen warten, juengere sterben und werden neu gestartet. Beide Strategien vermeiden Zyklen, weil die Warterichtung immer nur in eine Zeitstempel-Richtung geht.

Alte warten geduldig, junge sterben und starten neu.

Erkennung vs. Vermeidung

Zwei Grundansaetze: Deadlock-Erkennung (detection) laesst Deadlocks entstehen und loest sie ueber den Wartegraph auf. Deadlock-Vermeidung (avoidance/prevention) verhindert Deadlocks strukturell, z.B. durch Preclaiming oder Zeitstempel. Erkennung erlaubt hoehere Parallelitaet, kostet aber Zyklensuche. Vermeidung ist proaktiv, reduziert aber Nebenlaeufigkeit oder erzeugt unnoetige Rollbacks.

Erkennen und aufloesen oder vermeiden bevor es passiert.

Strenges 2PL als Voraussetzung

Deadlocks sind ein typisches Problem des strengen Zwei-Phasen-Sperrprotokolls (S2PL). Dort werden alle Sperren bis zum EOT gehalten, damit kaskadierendes Ruecksetzen ausgeschlossen ist. Genau dieses lange Halten der Sperren macht aber Zyklen im Wartegraph moeglich. Ohne 2PL waeren Deadlocks im klassischen Sinn nicht das Hauptproblem, dafuer aber Inkonsistenzen wie Dirty Read und Lost Update.

S2PL sichert Konsistenz, oeffnet aber Tuer fuer Deadlocks.

Aufloesung durch Rollback (Opferwahl)

Wird ein Zyklus erkannt, waehlt das DBMS ein Opfer im Zyklus aus (haeufig die juengste, die mit wenigsten Sperren oder die mit geringsten Kosten). Das Opfer erhaelt abort und wird per R1-Recovery zurueckgesetzt. Die freigewordenen Sperren erlauben den anderen TAs, weiterzulaufen. Liegt ein Knoten in mehreren Zyklen, kann sein Rollback mehrere Verklemmungen gleichzeitig loesen.

Ein Opfer, ein Rollback - der Zyklus zerfaellt.

Wichtige Details

Deadlock-Voraussetzungen: mindestens zwei TAs, mindestens zwei Sperren, wechselseitiges Warten, keine Praemption der Sperren.
Der Wartegraph wird aus der Lock-Tabelle konstruiert; Kante Ti -> Tj bedeutet: Ti wartet auf eine Sperre, die Tj haelt.
Zyklenerkennung erfolgt per Tiefensuche (DFS) im Wartegraphen.
Ein Rollback kann gleichzeitig mehrere Zyklen aufloesen, wenn das Opfer in allen Zyklen liegt (Beispiel T3 im Foliensatz).
Preclaiming garantiert Deadlockfreiheit, senkt aber die Parallelitaet und erfordert Vorabkenntnis der Zugriffe.
Wound-Wait: aeltere Transaktion darf juengere abbrechen - juengere warten nur.
Wait-Die: aeltere Transaktion darf warten - juengere sterben (abort + Neustart mit gleichem TS).
Zeitstempel-Verfahren funktionieren ohne zentralen Scheduler, TAs setzen sich selbst zurueck.
Beim Neustart nach wait-die/wound-wait behaelt die Transaktion ihren urspruenglichen Zeitstempel, damit sie irgendwann alt genug ist (kein Starvation).
MVCC vermeidet Lese-Deadlocks komplett: Writers do not block readers, readers do not block writers.

Beispiele

Klassischer Deadlock mit zwei TAs

T1 haelt X-Sperre auf A und will B; T2 haelt S-Sperre auf B und will A. Beide warten unendlich.

Schritt 1: T1: BOT
Schritt 2: T1: lockX(A)
Schritt 3: T2: BOT
Schritt 4: T2: lockS(B)
Schritt 5: T2: read(B)
Schritt 6: T1: read(A)
Schritt 7: T1: write(A)
Schritt 8: T1: lockX(B) -> muss warten auf T2
Schritt 9: T2: lockS(A) -> muss warten auf T1
=> Deadlock (Wartegraph: T1 -> T2 -> T1)

Wartegraph mit zwei Zyklen und einem Opfer

Fuenf TAs bilden zwei ueberlappende Zyklen. T3 liegt in beiden. Rollback von T3 loest beide Verklemmungen gleichzeitig.

Zyklus 1: T1 -> T2 -> T3 -> T4 -> T1
Zyklus 2: T2 -> T3 -> T5 -> T2
Opferwahl: T3 (in beiden Zyklen)
Aktion: abort(T3) + R1-Recovery fuer rollback
=> Beide Zyklen aufgeloest, T1, T2, T4, T5 koennen weiterlaufen.

Wound-Wait konkret

T1 (ts=5, alt) will Sperre, die T2 (ts=10, jung) haelt. T1 verletzt T2 -> T2 wird abgebrochen.

T1 (ts=5): lockX(A) -> haelt A
T2 (ts=10): lockX(B) -> haelt B
T2: lockX(A) -> T2 juenger als T1, T2 wartet (Regel: jung wartet auf alt)
T1: lockX(B) -> T1 aelter als T2, T2 wird gewound (abort + rollback), T1 bekommt B.

Wait-Die konkret

Gleiche Situation, aber Wait-Die-Strategie.

T1 (ts=5, alt): lockX(A)
T2 (ts=10, jung): lockX(B)
T1: lockX(B) -> T1 aelter als T2, T1 wartet
T2: lockX(A) -> T2 juenger als T1, T2 stirbt (abort + Neustart mit ts=10)
=> T1 bekommt B nach T2-Freigabe.

Grafik: Wartegraph und Zeitstempel-Strategien

Oben: klassischer Deadlock mit zwei TAs und dessen Wartegraph. Mitte: Wartegraph mit zwei ueberlappenden Zyklen, T3 als gemeinsames Opfer. Unten: Vergleich Wound-Wait und Wait-Die.

FAQ

Warum entstehen Deadlocks ueberhaupt im strengen 2PL?

Weil S2PL alle Sperren bis EOT haelt. Zwei TAs koennen so kreuzweise Sperren erwerben und dann wechselseitig auf die je andere Sperre warten.

Was ist der Unterschied zwischen Erkennung und Vermeidung?

Erkennung laesst Deadlocks zu und loest sie ueber den Wartegraph auf. Vermeidung verhindert sie strukturell, z.B. durch Preclaiming oder Zeitstempel.

Wie erkenne ich einen Deadlock im Wartegraph?

Ueber einen Zyklus. Ein gerichteter Kreis Ti -> ... -> Ti bedeutet, dass alle TAs im Kreis aufeinander warten.

Welche Transaktion wird geopfert?

Meist die juengste, die mit den wenigsten Sperren oder die mit geringstem Aufwand bis zum Rollback. Idealerweise ein Knoten in mehreren Zyklen, damit ein Opfer mehrere Verklemmungen loest.

Warum vermeidet Preclaiming Deadlocks garantiert?

Weil jede TA entweder ALLE benoetigten Sperren gleichzeitig erhaelt oder gar keine. Es gibt keine Situation, in der eine TA schon Sperren haelt und auf eine weitere wartet - also keinen Zyklus.

Wodurch unterscheiden sich Wound-Wait und Wait-Die?

Wound-Wait: aeltere darf juengere abbrechen, juengere wartet nur. Wait-Die: aeltere wartet, juengere stirbt (abort + Neustart). Beide vermeiden Zyklen, weil die Wartekante immer nur in eine Zeitstempel-Richtung zeigt.

Warum behaelt eine wieder gestartete TA ihren Zeitstempel?

Damit sie mit jedem Neustart aelter wirkt und irgendwann Prioritaet bekommt. Sonst droht Starvation - sie wuerde immer wieder als juengste sterben.

Was ist die Rolle der Lock-Tabelle bei der Deadlock-Erkennung?

Die Lock-Tabelle listet, welche TA welche Sperre haelt und welche wartet. Aus diesen Informationen konstruiert das DBMS den Wartegraph und sucht per Tiefensuche nach Zyklen.

Pruefungsfragen

Fortschritt 0 von 12 beantwortet