Two-Phase Locking
Eine Möglichkeit, Serialisierbarkeit von Schedules (siehe Schedule) zu garantieren, ist das Two-Phase Locking.
Die Serialisierbarkeit wird durch sogenannte Locks erreicht, die Aktionen konkurrierender Transaktionen mit einem Datenobjekt verhindern.
Ein Multimode-Lock hat drei Zustände:
• unlocked,
• read-locked (shared lock) und
• write-locked (exclusive lock).
Aus dem unlocked-Zustand kommt man mit der Operation readlock in den read-locked-Zustand. In diesem Zustand sind weitere readlock-Operationen durch andere Transaktionen möglich.
Falls die Sperre zu einem Datenobjekt durch eine einzige Transaktion im read-locked-Zustand gehalten wird, kann diese Transaktion die Sperre durch Ausführen von writelock in den write-locked Zustand bringen. In allen anderen Fällen sind keine writelock-Operationen erlaubt.
Wenn für jede readlock-Operation eine korrespondierende unlock-Operation ausgeführt wurde, gelangt man wieder in den unlocked-Zustand.
In den write-locked-Zustand gelangt man mit der writelock-Operation. Die ausführende Transaktion hat nun exklusiven Zugriff auf das Datenobjekt. Keine Transaktion kann eine readlock- oder writelock-Operation für dieses Datenobjekt durchführen, bis die Sperre wieder mit unlock in den unlocked-Zustand gebracht wird.
Das Two-Phase Locking Protokoll fordert nun, daß vor jeder Leseaktion r(X) eine readlock(X)-Operation ausgeführt wird. Entsprechend muß vor jeder w(X) Schreibaktion ein writelock(X) erfolgen. Für jede lock-Operation muß eine unlock-Operation durchgeführt werden. Der frühestmögliche Zeitpunkt für die Freigabe der Sperre ist gegeben, wenn
• auf das Datenobjekt in der restlichen Transaktion nicht mehr zugegriffen wird und
• keine lock-Operationen mehr folgen.
Der entstehende Schedule ist deswegen serialisierbar, weil der waitFor-Graph bezüglich der Sperren der Transaktionen ein Teilgraph eines Konfliktgraphs (siehe Konflikt-Äquivalenz) eines seriellen Schedules ist.
Der waitFor-Graph darf keine Kreise enthalten, da der Graph dann nicht einem Teilgraphen eines seriellen Schedules entsprechen kann (diese sind immer kreisfrei).
Falls mindestens ein Kreis im waitFor-Graph auftritt, spricht man von einem Deadlock. Dann muß eine Transaktion zurückgerollt werden, um den oder die Kreise aufzulösen.
Deadlocks können durch geeignete Maßnahmen vermieden werden. Eine Möglichkeit ist das konservative (conservative) Zwei-Phasen Sperrprotokoll, bei dem alle Locks in einem unteilbaren Schritt vor Beginn der Transaktion angefordert werden. Dann können ausschließlich Transaktionen parallel verarbeitet werden, zwischen denen keine Konflikte existieren.
Eine weitere Möglichkeit zur Deadlock-Vermeidung ist das Vorschreiben einer Ordnung, in der die Locks angefordert werden müssen. Durch Ordnen der Locking-Reihenfolge können keine Kreise im waitFor-Graph auftreten.
Kreise im waitFor-Graphen können auch durch die Methoden
• wait-die,
• wound-wait,
• no waiting und
• cautious waiting
vermieden werden.
Durch das Zwei-Phasen Sperrprotokoll werden kaskadierende Rollbacks nicht verhindert. Wenn die Locks erst beim Ende der Transaktion (also nach commit oder abort) freigegeben werden, spricht man vom strikten Zwei-Phasen Sperrprotokoll. Andere Transaktionen können veränderte Datenelemente dann erst lesen, wenn die verändernde Transaktion erfolgreich abgeschlossen wurde.
Die Serialisierbarkeit wird durch sogenannte Locks erreicht, die Aktionen konkurrierender Transaktionen mit einem Datenobjekt verhindern.
Ein Multimode-Lock hat drei Zustände:
• unlocked,
• read-locked (shared lock) und
• write-locked (exclusive lock).
Aus dem unlocked-Zustand kommt man mit der Operation readlock in den read-locked-Zustand. In diesem Zustand sind weitere readlock-Operationen durch andere Transaktionen möglich.
Falls die Sperre zu einem Datenobjekt durch eine einzige Transaktion im read-locked-Zustand gehalten wird, kann diese Transaktion die Sperre durch Ausführen von writelock in den write-locked Zustand bringen. In allen anderen Fällen sind keine writelock-Operationen erlaubt.
Wenn für jede readlock-Operation eine korrespondierende unlock-Operation ausgeführt wurde, gelangt man wieder in den unlocked-Zustand.
In den write-locked-Zustand gelangt man mit der writelock-Operation. Die ausführende Transaktion hat nun exklusiven Zugriff auf das Datenobjekt. Keine Transaktion kann eine readlock- oder writelock-Operation für dieses Datenobjekt durchführen, bis die Sperre wieder mit unlock in den unlocked-Zustand gebracht wird.
Das Two-Phase Locking Protokoll fordert nun, daß vor jeder Leseaktion r(X) eine readlock(X)-Operation ausgeführt wird. Entsprechend muß vor jeder w(X) Schreibaktion ein writelock(X) erfolgen. Für jede lock-Operation muß eine unlock-Operation durchgeführt werden. Der frühestmögliche Zeitpunkt für die Freigabe der Sperre ist gegeben, wenn
• auf das Datenobjekt in der restlichen Transaktion nicht mehr zugegriffen wird und
• keine lock-Operationen mehr folgen.
Der entstehende Schedule ist deswegen serialisierbar, weil der waitFor-Graph bezüglich der Sperren der Transaktionen ein Teilgraph eines Konfliktgraphs (siehe Konflikt-Äquivalenz) eines seriellen Schedules ist.
Der waitFor-Graph darf keine Kreise enthalten, da der Graph dann nicht einem Teilgraphen eines seriellen Schedules entsprechen kann (diese sind immer kreisfrei).
Falls mindestens ein Kreis im waitFor-Graph auftritt, spricht man von einem Deadlock. Dann muß eine Transaktion zurückgerollt werden, um den oder die Kreise aufzulösen.
Deadlocks können durch geeignete Maßnahmen vermieden werden. Eine Möglichkeit ist das konservative (conservative) Zwei-Phasen Sperrprotokoll, bei dem alle Locks in einem unteilbaren Schritt vor Beginn der Transaktion angefordert werden. Dann können ausschließlich Transaktionen parallel verarbeitet werden, zwischen denen keine Konflikte existieren.
Eine weitere Möglichkeit zur Deadlock-Vermeidung ist das Vorschreiben einer Ordnung, in der die Locks angefordert werden müssen. Durch Ordnen der Locking-Reihenfolge können keine Kreise im waitFor-Graph auftreten.
Kreise im waitFor-Graphen können auch durch die Methoden
• wait-die,
• wound-wait,
• no waiting und
• cautious waiting
vermieden werden.
Durch das Zwei-Phasen Sperrprotokoll werden kaskadierende Rollbacks nicht verhindert. Wenn die Locks erst beim Ende der Transaktion (also nach commit oder abort) freigegeben werden, spricht man vom strikten Zwei-Phasen Sperrprotokoll. Andere Transaktionen können veränderte Datenelemente dann erst lesen, wenn die verändernde Transaktion erfolgreich abgeschlossen wurde.
Abbildung: Zustände eines Multimode-Lock.