Sperrprotokolle - DB Klausur

Zusammenfassung

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 haelt alle Sperren bis EOT und verhindert Dirty Reads sowie kaskadierendes Ruecksetzen; Preclaiming fordert alle Sperren am BOT an und schliesst Deadlocks konstruktiv aus.

Kernkonzepte

Sperren (Locks) und Kompatibilitaetsmatrix

Transaktionen fordern zusaetzlich 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 koennen sich einen S-Lock teilen (S-S vertraeglich). Sobald jemand ein X-Lock haelt, ist keine weitere Sperre moeglich. Der Scheduler im DBMS verwaltet die Lock Table.

Merksatz: S vertraegt S, alles Uebrige mit X ist tabu.

Zwei-Phasen-Sperrprotokoll (2PL)

Jede Transaktion durchlaeuft genau zwei Phasen: die Wachstumsphase, in der Sperren angefordert, aber keine freigegeben werden duerfen, und die Schrumpfphase, in der Sperren freigegeben, aber keine neuen mehr angefordert werden duerfen. 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 unmoeglich, weil kein anderer Nutzer waehrend der Transaktion auf modifizierte Daten zugreifen kann. Kaskadierendes Ruecksetzen ist ausgeschlossen. S2PL ist Standard in kommerziellen DBMS.

Merksatz: Strikt = Sperren erst am EOT loslassen.

Preclaiming (Konservatives 2PL)

Jede Transaktion muss ALLE benoetigten Sperren bereits am Transaktionsbeginn (BOT) anfordern. Erst wenn ALLE Sperren gewaehrt wurden, darf die Transaktion starten. Da keine Transaktion inkrementell auf weitere Sperren wartet, kann kein Wartezyklus entstehen - Deadlocks sind konstruktiv ausgeschlossen. Nachteil: reduzierte Nebenlaeufigkeit.

Merksatz: Alles vorab sperren oder gar nicht anfangen.

Deadlock und Erkennung

Beim reinen 2PL koennen zwei oder mehr Transaktionen zyklisch aufeinander warten. Beispiel: T1 haelt X(A) und wartet auf B, T2 haelt S(B) und wartet auf A. Zur Erkennung wird ein Wartegraph gefuehrt (Kante T_i -> T_j wenn T_i auf eine Sperre wartet, die T_j haelt). Ein Zyklus ist ein Deadlock. Aufloesung durch Rollback einer Transaktion.

Merksatz: Wartegraph mit Zyklus = Deadlock.

Verklemmungsvermeidung ueber Zeitstempel

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

Merksatz: wound-wait - Alter schlaegt Junges; wait-die - Junges stirbt.

Konfliktserialisierbarkeit als Ziel

Ziel der gesamten sperrbasierten Synchronisation ist es, aus einer verzahnten parallelen Ausfuehrung eine Historie zu erzeugen, die aequivalent zu einer seriellen ist. Konfliktoperationen (write-write, write-read, read-write) muessen 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); Kompatibilitaet 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 Rueckgewinnbarkeit - Dirty Reads und kaskadierendes Ruecksetzen moeglich.
Striktes 2PL (S2PL): alle Sperren werden bis EOT gehalten - keine Dirty Reads, keine Kaskade.
Preclaiming (konservatives 2PL): alle benoetigten Sperren werden am BOT angefordert - garantierte Deadlock-Freiheit.
Preclaiming + S2PL ergibt Rechteck-Sperrverlauf, maximaler Isolationsschutz, aber niedrigste Nebenlaeufigkeit.
Deadlock-Erkennung erfolgt ueber Wartegraph; ein Zyklus im Graph markiert einen Deadlock, Aufloesung 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 fuehren zu Warteschlange, zwei Phasen einhalten, alle Sperren spaetestens am EOT zurueckgeben.
Reihenfolge der aequivalenten seriellen Historie unter 2PL = Reihenfolge der ersten Sperrfreigaben der Transaktionen.

Beispiele

2PL Ablauf zweier verzahnter Transaktionen (Ueberweisung + Summierung)

T1 modifiziert A und B (Ueberweisung), T2 liest A und B (Kontostaende summieren). Zeigt Wachstums- und Schrumpfphase. T2 muss auf lockS(A) warten, bis T1 unlockX(A) ausfuehrt, dann darf T2 lesen. Analog fuer 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 Ruecksetzen

Klassisches 2PL erlaubt Freigabe vor commit. Wenn T1 unlockX(A) macht und T2 danach read(A) ausfuehrt, aber T1 dann abort ausfuehrt, hat T2 einen nicht-committeten Wert gelesen. T2 muss ebenfalls zurueckgesetzt werden. Genau dieses Problem loest 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 ueber Kreuz. T1 haelt X-Lock auf A und will B, T2 haelt S-Lock auf B und will A. Beide warten unendlich. Erkennung ueber Wartegraph mit Zyklus. Aufloesung 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 moeglich, keine Dirty Reads, kein Kaskadieren. Nachteil: geringe Nebenlaeufigkeit.

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 schraeger Schrumpfphase. Rechts oben: S2PL mit senkrechter Freigabe am EOT. Unten links: Preclaiming + S2PL bildet ein Rechteck. Unten rechts: Kompatibilitaetsmatrix der Sperrmodi.

FAQ

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

Klassisches 2PL garantiert nur Serialisierbarkeit, nicht aber Rueckgewinnbarkeit. Weil Sperren vor commit freigegeben werden duerfen, koennen andere Transaktionen Dirty Reads bekommen. Faellt T1 danach in abort, muss kaskadierend zurueckgesetzt 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 Ruecksetzen 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 moeglich. X ist exklusiv.

Was bewirkt Preclaiming und welches Problem loest es?

Preclaiming zwingt jede Transaktion, ALLE benoetigten Sperren bereits am Beginn (BOT) anzufordern, bevor die erste Operation startet. Da keine Transaktion inkrementell auf weitere Sperren wartet, ist keine zyklische Wartesituation moeglich - 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 haelt. Enthaelt der Graph einen Zyklus, liegt ein Deadlock vor. Aufloesung durch Ruecksetzen einer Transaktion aus dem Zyklus.

Warum garantiert 2PL Serialisierbarkeit?

Weil in Phase 2 keine neuen Sperren angefordert werden duerfen, entspricht die Reihenfolge der aequivalenten 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 erhaelt. Sobald die erste Sperre freigegeben wird, endet Phase 1 und die Schrumpfphase beginnt. Ab da darf keine neue Sperre mehr angefordert werden, sonst waere das Protokoll verletzt.

Welche Sperrmodi kennt das Grundprotokoll?

S (shared, read lock, Lesesperre) und X (exclusive, write lock, Schreibsperre). Zusaetzlich NL (kein Lock). S-S ist vertraeglich, alles mit X ist unvertraeglich.

Pruefungsfragen

0 von 12 Fragen beantwortet