Sperrprotokolle - DB Klausur

Zusammenfassung

⭐ Laut Dozent: Sperrprotokolle mit Grafik erklären können — Deadlock, 2PL und Preclaiming. Stammt aus DB-I-Skript 05 Transactions.

Sperrprotokolle sind das zentrale Mittel des DBMS-Schedulers, um konfliktserialisierbare Historien im Mehrbenutzerbetrieb zu erzwingen. Das Zwei-Phasen-Sperrprotokoll (2PL) teilt jede Transaktion in eine Wachstumsphase (nur Sperren anfordern) und eine Schrumpfphase (nur Sperren freigeben) und garantiert damit Serialisierbarkeit. Striktes 2PL hält alle Sperren bis EOT und verhindert Dirty Reads sowie kaskadierendes Rücksetzen; Preclaiming fordert alle Sperren am BOT an und schließt Deadlocks konstruktiv aus.

Kernkonzepte

Sperren (Locks) und Kompatibilitätsmatrix

Transaktionen fordern zusätzlich zu read/write auch Sperren an und geben sie wieder frei. Es gibt zwei Sperrmodi: S (shared, Lesesperre) und X (exclusive, Schreibsperre); NL bedeutet keine Sperre. Mehrere Leser können sich einen S-Lock teilen (S-S verträglich). Sobald jemand ein X-Lock hält, ist keine weitere Sperre möglich. Der Scheduler im DBMS verwaltet die Lock Table.

Merksatz: S verträgt S, alles Übrige mit X ist tabu.

Zwei-Phasen-Sperrprotokoll (2PL)

Jede Transaktion durchläuft genau zwei Phasen: die Wachstumsphase, in der Sperren angefordert, aber keine freigegeben werden dürfen, und die Schrumpfphase, in der Sperren freigegeben, aber keine neuen mehr angefordert werden dürfen. Sobald die erste Sperre freigegeben wird, ist die Wachstumsphase beendet. 2PL garantiert konfliktserialisierbare Historien.

Merksatz: Erst alle Sperren sammeln, dann nur noch abbauen.

Striktes 2PL (S2PL)

Erweiterung von 2PL: ALLE Sperren werden bis zum Transaktionsende (EOT, also commit oder abort) gehalten und erst dann freigegeben. Damit sind Dirty Reads unmöglich, weil kein anderer Nutzer während der Transaktion auf modifizierte Daten zugreifen kann. Kaskadierendes Rücksetzen ist ausgeschlossen. S2PL ist Standard in kommerziellen DBMS.

Merksatz: Strikt = Sperren erst am EOT loslassen.

Preclaiming (Konservatives 2PL)

Jede Transaktion muss ALLE benötigten Sperren bereits am Transaktionsbeginn (BOT) anfordern. Erst wenn ALLE Sperren gewährt wurden, darf die Transaktion starten. Da keine Transaktion inkrementell auf weitere Sperren wartet, kann kein Wartezyklus entstehen - Deadlocks sind konstruktiv ausgeschlossen. Nachteil: reduzierte Nebenläufigkeit.

Merksatz: Alles vorab sperren oder gar nicht anfangen.

Deadlock und Erkennung

Beim reinen 2PL können zwei oder mehr Transaktionen zyklisch aufeinander warten. Beispiel: T1 hält X(A) und wartet auf B, T2 hält S(B) und wartet auf A. Zur Erkennung wird ein Wartegraph geführt (Kante T_i -> T_j wenn T_i auf eine Sperre wartet, die T_j hält). Ein Zyklus ist ein Deadlock. Auflösung durch Rollback einer Transaktion.

Merksatz: Wartegraph mit Zyklus = Deadlock.

Verklemmungsvermeidung über Zeitstempel

Alternative zur Erkennung: Jede Transaktion bekommt einen eindeutigen Zeitstempel. Bei wound-wait bricht eine ältere TA eine jüngere ab und läuft selbst weiter (Junge warten auf Alte). Bei wait-die wartet eine ältere TA auf die jüngere, aber eine jüngere wird sofort abgebrochen. Damit sind Zyklen im Wartegraphen ausgeschlossen.

Merksatz: wound-wait - Alter schlägt Junges; wait-die - Junges stirbt.

Konfliktserialisierbarkeit als Ziel

Ziel der gesamten sperrbasierten Synchronisation ist es, aus einer verzahnten parallelen Ausführung eine Historie zu erzeugen, die äquivalent zu einer seriellen ist. Konfliktoperationen (write-write, write-read, read-write) müssen in einer eindeutigen Reihenfolge stehen. 2PL sichert dies, weil eine TA erst dann ihre erste Sperre freigibt, wenn alle Konflikte abgeschlossen sind.

Merksatz: Korrekt = konfliktserialisierbar; 2PL erzwingt das.

Wichtige Details

Zwei Sperrmodi: S (shared/read) und X (exclusive/write); Kompatibilität nur zwischen S und S sowie mit NL.
2PL besteht aus Wachstumsphase (nur Anforderung) und Schrumpfphase (nur Freigabe); erste Freigabe leitet Phase 2 ein.
Klassisches 2PL garantiert Serialisierbarkeit, aber NICHT Rückgewinnbarkeit - Dirty Reads und kaskadierendes Rücksetzen möglich.
Striktes 2PL (S2PL): alle Sperren werden bis EOT gehalten - keine Dirty Reads, keine Kaskade.
Preclaiming (konservatives 2PL): alle benötigten Sperren werden am BOT angefordert - garantierte Deadlock-Freiheit.
Preclaiming + S2PL ergibt Rechteck-Sperrverlauf, maximaler Isolationsschutz, aber niedrigste Nebenläufigkeit.
Deadlock-Erkennung erfolgt über Wartegraph; ein Zyklus im Graph markiert einen Deadlock, Auflösung per Rollback eines Opfers.
Deadlock-Vermeidung ohne zentralen Scheduler via Zeitstempel: wound-wait oder wait-die.
Konzeptuelle Regeln: sperren vor Zugriff, keine Doppelanforderung, inkompatible Sperren führen zu Warteschlange, zwei Phasen einhalten, alle Sperren spätestens am EOT zurückgeben.
Reihenfolge der äquivalenten seriellen Historie unter 2PL = Reihenfolge der ersten Sperrfreigaben der Transaktionen.

Beispiele

2PL Ablauf zweier verzahnter Transaktionen (Überweisung + Summierung)

T1 modifiziert A und B (Überweisung), T2 liest A und B (Kontostände summieren). Zeigt Wachstums- und Schrumpfphase. T2 muss auf lockS(A) warten, bis T1 unlockX(A) ausführt, dann darf T2 lesen. Analog für B.

1.  T1: BOT
2.  T1: lockX(A)
3.  T1: read(A)
4.  T1: write(A)
5.  T2: BOT
6.  T2: lockS(A) -> muss warten
7.  T1: lockX(B)  [Wachstumsphase T1]
8.  T1: read(B)
9.  T1: unlockX(A) [Schrumpfphase T1 startet] -> T2 wecken
10. T2: read(A)
11. T2: lockS(B) -> muss warten
12. T1: write(B)
13. T1: unlockX(B) -> T2 wecken
14. T2: read(B)
15. T1: commit
16. T2: unlockS(A)
17. T2: unlockS(B)
18. T2: commit

2PL erlaubt Dirty Read + kaskadierendes Rücksetzen

Klassisches 2PL erlaubt Freigabe vor commit. Wenn T1 unlockX(A) macht und T2 danach read(A) ausführt, aber T1 dann abort ausführt, hat T2 einen nicht-committeten Wert gelesen. T2 muss ebenfalls zurückgesetzt werden. Genau dieses Problem löst striktes 2PL.

T1: lockX(A), write(A), unlockX(A) [zu frueh!]
T2: lockS(A), read(A)   <- Dirty Read!
T1: abort               <- Wert von A verworfen
T2: muss ebenfalls abort  <- Kaskade

Deadlock unter 2PL

Zwei Transaktionen sperren über Kreuz. T1 hält X-Lock auf A und will B, T2 hält S-Lock auf B und will A. Beide warten unendlich. Erkennung über Wartegraph mit Zyklus. Auflösung durch Abbruch einer Transaktion.

1. T1: BOT, lockX(A)
2. T2: BOT, lockS(B), read(B)
3. T1: read(A), write(A)
4. T1: lockX(B)  -> wartet auf T2
5. T2: lockS(A) -> wartet auf T1
=> Deadlock (Zyklus T1->T2->T1)

Preclaiming + Striktes 2PL (konservatives 2PL)

Kombination sperrt alle Objekte am BOT und gibt alle erst am EOT frei. Rechteck-Verlauf der Sperrenanzahl. Kein Deadlock möglich, keine Dirty Reads, kein Kaskadieren. Nachteil: geringe Nebenläufigkeit.

BOT:  lockX(A), lockX(B), lockS(C)  [alle Sperren sofort]
      read/write auf A, B, C
EOT:  commit, unlockX(A), unlockX(B), unlockS(C) [alle Freigaben am Ende]

Grafik: Sperrenverlauf

Links: klassisches 2PL mit schräger Schrumpfphase. Rechts oben: S2PL mit senkrechter Freigabe am EOT. Unten links: Preclaiming + S2PL bildet ein Rechteck. Unten rechts: Kompatibilitätsmatrix der Sperrmodi.

FAQ

Warum reicht das Zwei-Phasen-Sperrprotokoll allein nicht aus?

Klassisches 2PL garantiert nur Serialisierbarkeit, nicht aber Rückgewinnbarkeit. Weil Sperren vor commit freigegeben werden dürfen, können andere Transaktionen Dirty Reads bekommen. Fällt T1 danach in abort, muss kaskadierend zurückgesetzt werden.

Was ist der Unterschied zwischen 2PL und striktem 2PL?

Bei 2PL darf man in der Schrumpfphase Sperren beliebig freigeben, solange keine neuen mehr angefordert werden. Bei striktem 2PL werden ALLE Sperren erst am EOT (Transaktionsende) freigegeben. Damit sind Dirty Reads und kaskadierendes Rücksetzen ausgeschlossen.

Wann ist ein S-Lock mit einem X-Lock kompatibel?

Nie. S ist mit S kompatibel (mehrere gleichzeitige Leser erlaubt), aber sobald ein X-Lock gehalten wird, ist keine weitere Sperre möglich. X ist exklusiv.

Was bewirkt Preclaiming und welches Problem löst es?

Preclaiming zwingt jede Transaktion, ALLE benötigten Sperren bereits am Beginn (BOT) anzufordern, bevor die erste Operation startet. Da keine Transaktion inkrementell auf weitere Sperren wartet, ist keine zyklische Wartesituation möglich - Deadlocks sind ausgeschlossen.

Wie erkennt man einen Deadlock in einer Klausurskizze?

Man zeichnet den Wartegraphen: Knoten pro Transaktion, Kante T_i -> T_j falls T_i auf eine Sperre wartet, die T_j hält. Enthält der Graph einen Zyklus, liegt ein Deadlock vor. Auflösung durch Rücksetzen einer Transaktion aus dem Zyklus.

Warum garantiert 2PL Serialisierbarkeit?

Weil in Phase 2 keine neuen Sperren angefordert werden dürfen, entspricht die Reihenfolge der äquivalenten seriellen Historie der Reihenfolge, in der die Transaktionen ihre erste Sperre freigeben. Konflikte werden dadurch topologisch geordnet, ein azyklischer Konfliktgraph entsteht.

Was bedeutet die Wachstumsphase im 2PL genau?

Phase in der die Transaktion Sperren anfordert und erhält. Sobald die erste Sperre freigegeben wird, endet Phase 1 und die Schrumpfphase beginnt. Ab da darf keine neue Sperre mehr angefordert werden, sonst wäre das Protokoll verletzt.

Welche Sperrmodi kennt das Grundprotokoll?

S (shared, read lock, Lesesperre) und X (exclusive, write lock, Schreibsperre). Zusätzlich NL (kein Lock). S-S ist verträglich, alles mit X ist unverträglich.

Prüfungsfragen

0 von 12 Fragen beantwortet