Concurrency Control
Lock based protocol:
This protocol requires that all the data items must be accessed in a mutually exclusive manner, i.e. when one transaction is executing then no other transaction should interrupt the same object.
To implement lock based protocol we need 2 types of locks.
Shared Lock: When we take this lock we can just read the item but cannot write.
-
Exclusive Lock: In this type of lock we can write as well as read the data item.
Below table will give clear idea about what we can do and cannot while having shared or exclusive lock.
| Shared | Exclusive | |
|---|---|---|
| Shared | Yes | No |
| Exclusive | No | No |
Now we will discuss some of the problems because of locking:
Below we have one schedule (set of transactions), here we have first given a serial schedule. i. e. we can either execute T1 before T2 or T2 before T1.
| T1: A->B (Transferring 50 rupees to B) | T2: Display (B+A) |
|---|---|
| Lock-x(A) | Lock-s(B) |
| Read(A) | Read(B) |
| A=A-50 | Unlock(B) |
| write(A) | Lock-s(A) |
| Unlock(A) | Read(A) |
| Lock-x(B) | Unlock(A) |
| Read(B) | Display(A+B) |
| Lock-x(B) | Unlock(A) |
| B=B+50 | |
| write(B) | |
| Unlock(B) |
As we can see that there is no problem when we execute T1->T2 or T2->T1. But if we try to interleave the transactions then we will face the problems.
Problem 1: Inconsistency in the database
Below we have one schedule (set of transactions), here we have first given a serial schedule. i. e. we can either execute T1 before T2 or T2 before T1.
| T1: A->B (Transferring 50 rupees to B) | T2: Display (B+A) |
|---|---|
| Lock-x(A) | |
| Read(A) | |
| A=A-50 | |
| write(A) | |
| Unlock(A) | |
| Lock-s(B) | |
| Read(B) | |
| Unlock(B) | |
| Lock-s(A) | |
| Read(A) | |
| Unlock(A) | |
| Display(A+B) | |
| Read(B) | |
| Lock-x(B) | |
| B=B+50 | |
| write(B) | |
| Unlock(B) |
So above we have shown one interleaving and we could understand the data flow by below example:
Output:
Let say in the start of the schedule A=100 and B=200 so in total we should have 300 always.
But as we see that after Till Display (B+A) we have A=50 and B=200 to total=250 but it should be 300 to make consistency.
Problem 2: Deadlock Problem
Let’s say T2 is waiting for T1 to unlock (A) and T1 is waiting for T2 to unlock (B)
Above problem could be seen from the below schedule:
| T1 | T2 |
|---|---|
| Lock-x(A) | |
| Read(A) | |
| A=A-50 | |
| write(A) | |
| Lock-s(B) | |
| Read(B) | |
| Lock-s(A) | |
| Read(A) | |
| Display(A+B) | |
| Unclock(B) | |
| Unlock(A) | |
| Lock-x(B) | |
| Read(B) | |
| B=B+50 | |
| write(B) | |
| Commit | |
| Unlock(B) | |
| Unlock(A) |
Two phase locking Protocol
It requires both lock and unlocks being done in two phases:
- Growing Phase: Obtain locks that means when we are writing something on A and B, then we will take locks on A and B like below: W(A) and W(B)
- Shrinking Phase: Release locks, Unlock the objects in a row like unlock (A) and unlock (B)
Lock Point
When a transaction takes the final lock is called lock point.
Here growing and shrinking phase confirms serializability.
How to create serializable schedule:
Just find out last lock taken from the schedule and put the order, in below example we have explained that.
So the highlighted parts are the last locks taken, i. e. we can say that the serial schedule could be: T2 -> T3 -> T1
Note:
But 2 PL won’t be able to solve other problems such as cascading rollback.
Cascading Rollback Problem
Here we could see cascading rollback by the following example:
So if transaction T1 rollbacks then transaction T2 and T3 has to rollback.DeadLock Problem Example
So T1 is waiting for B and T2 is waiting for A and both A and B are held by T1 and T2 respectively.
Note:
In 2 PL we have seen:
- Serializability: It is guaranteed to happen
- Cascading Rollback: It is possible which is bad.
- Deadlock: It is possible.
There are some variants cascading rollback using which we can avoid cascading rollback.
- Strict 2 phase locking Protocol: All exclusive mode locks are taken by a transaction must be unlocked after commit. However we don’t bother about shared locks. Using this method schedule will be recoverable and cascade less.
- Rigorous 2 Phase Locking Protocol: All locks must be hold until the transaction commit.
- Conservative 2PL: Obtain the lock then start the transaction otherwise don’t. So hold and wait is gone. But Concurrency is gone. And also requirement of locks which will be taken in future- this decision is difficult.
Note: Both of them can avoid cascading rollback but Deadlock is still possible.
Note:
So when we say a schedule is conservative then it will be Rigorous as well as Strict 2 PL but vice versa is not true.
Below we have some examples:
Example 1:
| T1 |
|---|
| Lock-s(A) |
| Read(A) |
| Lock-x(B) | >
| Read(B) |
| Unlock(A) | >
| Write(B) |
| Unlock(B) | >
Now we will see what is the above schedule following the properties discussed above
2 PL: There is growing and shrinking phase.
Strict 2 PL: There is Lock-x(B) and it is unlocked before commit so no strict 2 PL.
Rigorous: If it is not strict 2 PL then it can’t be Rigorous.
Conservative: If it is not strict 2 PL then it can’t be conservative.
Example 2:
| T1 |
|---|
| Lock-s(A) |
| Read(A) |
| Lock-x(B) | >
| Unlock(A) |
| Read(B) | >
| Write(B) |
| commit | >
| Unlock(B) |
Strict 2 PL: Exclusive locks are unlocked after commit. So yes it is.
Rigorous: We have taken Lock-s(A) and we have unlocked it before commit. So no rigorous.
Conservative: We have not taken all the locks at first then start the transaction so no conservative.
Example 3:
| T1 |
|---|
| Lock-s(A) |
| Read(A) |
| Lock-x(B) | >
| Read(B) |
| Write(B) | >
| commit |
| Unlock(B) | >
| Unlock(A) |
Strict 2 PL: Exclusive locks are unlocked after commit. So yes it is.
Rigorous: We have unlocked all the locks after commit so it is rigorous.
Conservative: We have not taken all the locks at first then start the transaction so no conservative.
Example 4:
| T1 |
|---|
| Lock-s(A) |
| Lock-x(B) |
| Read(B) | >
| Write(B) |
| Read(A) | >
| commit |
| Unlock(A) | >
| Unlock(B) |
Strict 2 PL: Exclusive locks are unlocked after commit. So yes it is.
Rigorous: We have unlocked all the locks after commit so it is rigorous.
Conservative: We have taken all the locks at first then start the transaction so yes it is conservative.
Example 5:
| T1 |
|---|
| Lock-s(A) |
| Read(A) |
| Unlock(A) | >
| Lock-x(B) |
| Read(B) | >
| Write(B) |
| Unlock(B) | >
| Unlock(A) |
| Commit | >
Strict 2 PL: Because it is not 2 P L so not either of it.
Rigorous: Because it is not 2 P L so not either of it.
Conservative:Because it is not 2 P L so not either of it.