Zweiphasen-Sperrprotokoll (Two-Phase Locking, 2PL):

Regel 1: Bevor eine Transaktion auf ein Objekt zugreift, muß das Objekt für die Transaktion gesperrt werden ("Wachstumsphase" der Transaktion).

Regel 2: Nachdem eine Transaktion eine Sperre freigegeben hat, darf sie keine weiteren Sperren mehr erwerben ("Schrumpfungsphase" der Transaktion).

Satz:

Das Zweiphasen-Sperrprotokoll garantiert, daß alle entstehenden Schedules serialisierbar sind.

Beweis:

Sei s ein Schedule, der unter dem 2PL entstanden ist.

Annahme: s ist nicht serialisierbar.

-> es gibt einen Zyklus im Abhängigkeitsgraphen T1-> T2->T3-> ... -> Tk-> T1

Dann gibt es Konfliktpaare (p1(x1),p2(x1)), (p2(x2),p3(x2)), ... (pk(xk),p1(xk))

Wegen Regel 1 und der allgemeinen Vereinbarung, dass im Konfliktfalle ein Lock erst erworben werden kann, wenn vorher ein Unlock vorkommt:

U1(x1)<L2(x1), U2(x2)<L3(x2),..., Uk(xk)<L1(xk)

Wegen Regel 2 des 2PL gilt ausserdem

L2(x1)<U2(x2), L3(x2)<...Uk(xk)

Daher U1(x1)<L2(x1)<U2(x2)<...Uk(xk)<L1(xk) ==> U1(x1)<L1(xk) ==> W!

Previous slide

Next slide

Back to first slide

View graphic version