Does the conservative two phase locking protocol produce cascadeless schedules?

Question

Let us consider the following schedule :

\begin{array}{lcr} \mbox{$T_1$} & \mbox{$T_2$}\\ \\ \mbox{lock-exclusive(a)} \\ \mbox{lock-exclusive(b)} \\ \mbox{read(a)} \\ \mbox{a=a+50} \\ \mbox{write(a)} \\ \mbox{unlock(a)} \\ \mbox{} & \mbox{lock-exclusive(a)}\\ \mbox{} & \mbox{read(a)}\\ \mbox{} & \mbox{a=a+50}\\ \mbox{} & \mbox{write(a)}\\ \mbox{} & \mbox{unlock(a)}\\ \mbox{read(b)} \\ \mbox{b=b+100} \\ \mbox{write(b)} \\ \mbox{unlock(b)} \\ \end{array}

Since in the schedule the lock on $a$ is released, it is possible for the transaction $T_2$ to acquire the lock on $a$. Now the transaction $T_2$ reads the value of $a$ which was written by transaction $T_1$. This implies that if the transaction $T_1$ aborts, the transaction $T_2$ must be aborted for consistency purposes. Does it mean that even though a conservative two phase protocol is used, the schedules may not necesssarily be cascadeless?

Answer 1

Yes, the conservative 2PL does not garantuee cascadelessness. Requesting all locks at the beginning of the transaction is used to prevent deadlocks.

If you want to prevent cascading rollbacks, you need to have a look at how the locks are released. There are two versions of the 2PL-Protocol that garantuee cascadeless schedules: the strong 2PL and the rigorous 2PL, which is even stricter.

Schedules that satisfy the strong 2PL may release read-locks at any time and all write-lock at the end of the transaction. Schedules that satisfy the rigorous 2PL may only release all locks at the end of the transaction.

Lets have a look at what happens to your schedule if you use the conservative and rigorous (or strong) 2PL.

\begin{array}{lcr} \mbox{$T_1$} & \mbox{$T_2$}\\ \\ \mbox{lock-exclusive(a)} \\ \mbox{lock-exclusive(b)} \\ \mbox{read(a)} \\ \mbox{a=a+50} \\ \mbox{write(a)} \\ \mbox{read(b)} \\ \mbox{b=b+100} \\ \mbox{write(b)} \\ \mbox{unlock(a)} \\ \mbox{unlock(b)} \\ \mbox{} & \mbox{lock-exclusive(a)}\\ \mbox{} & \mbox{read(a)}\\ \mbox{} & \mbox{a=a+50}\\ \mbox{} & \mbox{write(a)}\\ \mbox{} & \mbox{unlock(a)}\\ \end{array}

Because $T_1$ is not allowed to do $\mbox{unlock(a)}$, $T_2$ can not request the lock and therefore can not start. $T_1$ continues until the end and releases its lock. Now $T_2$ can start.

You can also see here that a conservative, rigorous 2PL leads to a serial execution of Transactions that access the same variables.