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.
  1. Shared Lock: When we take this lock we can just read the item but cannot write.

  2. 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.

SharedExclusive
SharedYesNo
ExclusiveNoNo

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-50Unlock(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:

T1T2
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:

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:

There are some variants cascading rollback using which we can avoid cascading rollback.

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)
2 PL: There is growing and shrinking phase so it is 2 PL.
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)
2 PL: There is growing and shrinking phase so it is 2 PL.
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)
2 PL: There is growing and shrinking phase so it is 2 PL.
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
2 PL: There is no growing and shrinking phase so it is not 2 PL.
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.

Quantitative Aptitude
Reasoning
Programming
Interview