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.
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!
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.
Conservative 2-PL –
A.K.A 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.
Image – Venn Diagram showing categories of languages under 2-PL
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?
T1 | T2 | |
---|---|---|
1 | Read(A) | |
2 | Read(A) | |
3 | Read(B) | |
4 | Write(B) | |
5 | Commit | |
6 | Read(B) | |
7 | Write(B) | |
6 | Commit |
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:
T1 | T2 | |
---|---|---|
1 | Lock-S(A) | |
2 | Read(A) | |
3 | Lock-S(A) | |
4 | Read(A) | |
5 | Lock-X(B) | |
6 | Read(B) | |
7 | Write(B) | |
8 | Commit | |
9 | Unlock(A) | |
10 | Unlock(B) | |
11 | Lock-X(B) | |
12 | Read(B) | |
13 | Write(B) | |
14 | Commit | |
15 | Unlock(A) | |
16 | Unlock(B) |
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.
By now, I guess you must’ve got the idea how to differentiate between types of 2-PL. Remember the theory as problems come in the examination sometimes just based on theoretical knowledge. Next we’ll look at some examples on Conservative 2-PL and how does it differs from the above two types of 2-PL. What makes it Deadlock free and also so difficult to implement. Then we’ll conclude the topic of 2-PL. Shortly we’ll move on to another type of Lock based Protocols- Graph Based Protocols. They are also very interesting and provides unique method to deal with the problem of Deadlocks! So we’ll learn a new type of locking protocol, that will conclude the topic of Lock based Protocol for GATE, till then Happy Learning.
GATE related question:
GATE CS | IT 2004 | Question 77
leave a comment
0 Comments