Two Phase Locking Protocol | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

Introduction

There are two types of Locks available Shared S(a) and Exclusive X(a). Implementing this lock system without any restrictions gives us the Simple Lock based protocol (or Binary Locking), but it has its own disadvantages, they does not guarantee Serializability. Schedules may follow the preceding rules but a non-serializable schedule may result.
To guarantee serializablity, we must follow some additional protocol concerning the positioning of locking and unlocking operations in every transaction. This is where the concept of Two Phase Locking(2-PL) comes in the picture, 2-PL ensures serializablity. Now, let’s dig deep!

Two Phase Locking

A transaction is said to follow Two Phase Locking protocol if Locking and Unlocking can be done in two phases.

1. Growing Phase: New locks on data items may be acquired but none can be released.
2. Shrinking Phase: Existing locks may be released but no new locks can be acquired.

Note: If lock conversion is allowed, then upgrading of lock( from S(a) to X(a) ) is allowed in Growing Phase and downgrading of lock (from X(a) to S(a)) must be done in shrinking phase.

Let’s see a transaction implementing 2-PL.

This is just a skeleton transaction which shows how unlocking and locking works with 2-PL. Note for:

Transaction T₁:

• Growing Phase is from steps 1-3.
• Shrinking Phase is from steps 5-7.
• Lock Point at 3

Transaction T₂:

• Growing Phase is from steps 2-6.
• Shrinking Phase is from steps 8-9.
• Lock Point at 6

What is LOCK POINT? The Point at which the growing phase ends, i.e., when transaction takes the final lock it needs to carry on its work. Now look at the schedule, you’ll surely understand.
I have said that 2-PL ensures serializablity, but there are still some drawbacks of 2-PL. Let’s glance at the drawbacks:

• Cascading Rollback is possible under 2-PL.
• Deadlocks and Starvation is possible.

1. Cascading Rollbacks in 2-PL
Let’s see the following Schedule:

Take a moment to analyze the schedule. Yes, you’re correct, because of Dirty Read in T₂ and T₃ in lines 8 and 12 respectively, when T1 failed we have to rollback others also. Hence Cascading Rollbacks are possible in 2-PL. I have taken skeleton schedules as examples because it’s easy to understand when it’s kept simple. When explained with real time transaction problems with many variables, it becomes very complex.
2. Deadlock in 2-PL
Consider this simple example, it will be easy to understand. Say we have two transactions T1 and T2.
Schedule: Lock-X₁(A)   Lock-X₂(B)  Lock-X₁(B)  Lock-X₂(A)
Drawing the precedence graph, you may detect the loop. So Deadlock is also possible in 2-PL.
Two-phase locking may also limit the amount of concurrency that occur in a schedule because a Transaction may not be able to release an item after it has used it. This may be because of the protocols and other restrictions we may put on the schedule to ensure serializability, deadlock freedom and other factors. This is the price we have to pay to ensure serializability and other factors, hence it can be considered as a bargain between concurrency and maintaining the ACID properties.
The above mentioned type of 2-PL is called Basic 2PL. To sum it up it ensures Conflict Serializability but does not prevent Cascading Rollback and Deadlock. Further we will study three other types of 2PL, Strict 2PL, Conservative 2PL and Rigorous 2PL.

Categories of Two Phase Locking (Strict, Rigorous & Conservative)

Now that we are familiar with what is Two Phase Locking (2-PL) and the basic rules which should be followed which ensures serializablity. Moreover we came across the problems with 2-PL, Cascading Aborts and Deadlocks. Now, we turn towards the enhancements made on 2-PL which tries to make the protocol nearly error free. Briefly we allow some modifications to 2-PL to improve it. There are three categories:

• Strict 2-PL
• Rigorous 2-PL
• Conservative 2-PL

Now recall the rules followed in Basic 2-PL, over that we make some extra modifications. Let’s now see what are the modifications and what drawbacks they solve.
1. Strict 2-PL
This requires that in addition to the lock being 2-Phase all Exclusive(X) Locks held by the transaction be released until after the Transaction Commits.
Following Strict 2-PL ensures that our schedule is:

• Recoverable
• Cascadeless

Hence it gives us freedom from Cascading Abort which was still there in Basic 2-PL and moreover guarantee Strict Schedules but still Deadlocks are possible!
2. Rigorous 2-PL
This requires that in addition to the lock being 2-Phase all Exclusive(X) and Shared(S) Locks held by the transaction be released until after the Transaction Commits.
Following Rigorous 2-PL ensures that our schedule is:

• Recoverable
• Cascadeless

Hence it gives us freedom from Cascading Abort which was still there in Basic 2-PL and moreover guarantee Strict Schedules but still Deadlocks are possible!

Note the difference between Strict 2-PL and Rigorous 2-PL is that Rigorous is more restrictive, it requires both Exclusive and Shared locks to be held until after the Transaction commits and this is what makes the implementation of Rigorous 2-PL more easy.

3. Conservative 2-PL
Static 2-PL, this protocol requires the transaction to lock all the items it access before the Transaction begins execution by predeclaring its read-set and write-set. If any of the predeclared items needed cannot be locked, the transaction does not lock any of the items, instead it waits until all the items are available for locking.
Conservative 2-PL is Deadlock free and but it does not ensure Strict schedule(More about this here!). However, it is difficult to use in practice because of need to predeclare the read-set and the write-set which is not possible in many situations. In practice, the most popular variation of 2-PL is Strict 2-PL.
The Venn Diagram below shows the classification of schedules which are rigorous and strict. The universe represents the schedules which can be serialized as 2-PL. Now as the diagram suggests, and it can also be logically concluded, if a schedule is Rigorous then it is Strict. We can also think in another way, say we put a restriction on a schedule which makes it strict, adding another to the list of restrictions make it Rigorous. Take a moment to again analyze the diagram and you’ll definitely get it.
Venn Diagram showing categories of languages under 2-PL

Q. Now, let’s see the schedule below, tell me if this schedule can be locked using 2-PL and if yes, show how and what class of 2-PL does your answer belongs?

I recommend you to try before looking at the solution.
Yes, the schedule is conflict serializable so we can try implementing 2-PL. So, let’s try….
Solution:

Now, this is one way I choose to implement the locks on A and B. You may try a different sequence but remember to follow the 2-PL protocol. With that said, observe that our locks are released after Commit operation so this satisfies Rigorous 2-PL protocol.

Two Phase Locking (2-PL) Concurrency Control Protocol

Now, we know both Strict 2-PL and Rigorous 2-PL avoids Cascading Rollbacks and ensures a Strict schedule but still cannot guarantee that our schedule is Deadlock free. We have seen both Strict and Rigorous 2-PL are similar in application and a general misconception is common that Conservative 2-PL also follows the same sets of protocols as the above two. For clarity let’s go through Conservative 2-PL in detail.

Conservative 2-PL
Static 2-PL, this protocol requires the transaction to lock all the items it access before the Transaction begins execution by predeclaring its read-set and write-set. If any of the predeclared items needed cannot be locked, the transaction does not lock any of the items, instead, it waits until all the items are available for locking. So the operation on data cannot start until we lock all the items required.
Now let’s see an interesting example on Conservative 2-PL. Tell me if the following schedule follows Conservative 2-PL?
Schedule:   Lock-X(A)  Lock-X(B)  Read(A)  Read(B)  Write(A)  Unlock(A)  Commit  Unlock(B)
Do you think the above Schedule does not follow Conservative 2-PL? Don’t confuse the protocol as just a modified version of Rigorous 2-PL, We can release the locks whenever we want, but we need to lock all the data items before carrying out any operation. This is what makes it Deadlock-free. The above schedule follows Conservative 2-PL.
Some interesting traits about Conservative 2-PL:

• Schedule following this will not have a Growing Phase as we’ve seen in Basic, Strict and Rigorous 2-PL. As locking the data before using it is mandatory so this protocol has no Growing phase. Moreover, this rule makes it Deadlock free as if an item is not available for locking the transaction releases all the locks and tries again later, i.e, no Hold and Wait. This makes one of the four necessary conditions for deadlock void.
• We only have to lock all the items beforehand, so releasing or unlocking them has no restrictions as we had in Strict or Rigorous 2-PL.
• As no operations are done before acquiring all the locks, we have no Growing phase in this protocol unlike Basic, Strict, Rigorous 2-PL.
• Although we get a Deadlock free schedule in this protocol, we may still face drawbacks like Cascading Rollbacks. So this protocol doen not ensure Strict Schedules. This is a disadvantage in comparison to Strict and Rigorous 2-PL.

Let’s discuss an example now. See how the schedule below follows Conservative 2-PL but does not follow Strict and Rigorous 2-PL.

Look at the schedule, it completely follows Conservative 2-PL, but fails to meet the requirements of Strict and Rigorous 2-PL, that is because we unlock A and B before the transaction commits.

How can cascading abort happen in Conservative 2-PL?
This can happen because a Transaction may carry out a Dirty Read from another Transaction. We don’t have such restrictions in our protocol so this situation is possible.