Two Phase Locking

Two Phase Locking

AU : May-14,18, Dec.-11,16,19, Marks 9

• The two phase locking is a protocol in which there are two phases:

i) Growing phase (Locking phase): It is a phase in which the transaction may obtain locks but does not release any lock.

ii) Shrinking phase (Unlocking phase): It is a phase in which the transaction may release the locks but does not obtain any new lock.

• Lock Point: The last lock position or first unlock position is called lock point. For example

Consider following transactions

The important rule for being a two phase locking is - All Lock operations precede all the unlock operations.

In above transactions T₁ is in two phase locking mode but transaction T₂ is not in two phase locking. Because in T₂, the Shared lock is acquired by data item B, then data item B is read and then the lock is released. Again the lock is acquired by data item A, then the data item A is read and the lock is then reloased. Thus we get lock-unlock-lock-unlock sequence. Clearly this is not possible in two phase locking.

Example 3.10.1 Prove that two phase locking guarantees serializability. AU: Dec.-11, Marks 8

Solution:                                   

• Serializability is mainly an issue of handling write operation. Because any inconsistency may only be created by write operation.

• Multiple reads on a database item can happen parallely.

• 2-Phase locking protocol restricts this unwanted read/write by applying exclusive lock.

• Moreover, when there is an exclusive lock on an item it will only be released in shrinking phase. Due to this restriction there is no chance of getting any inconsistent state.

The serializability using two phase locking can be understood with the help of following example

Consider two transactions

Step 1: Now we will apply two phase locking. That means we will apply locks in growing and shrinking phase

Note that above schedule is serializable as it prevents interference between two transactions.

The serializability order can be obtained based on the lock point. The lock point is either last lock operation position or first unlock position in the transaction.

The last lock position is in T₁, then it is in T₂. Hence the serializability will be T₁->T₂ based on lock points. Hence the sequence can be R1(A);R2(A);R1(B);W1(B)

Limitations of Two Phase Locking Protocol

The two phase locking protocol leads to two problems - deadlock and cascading roll back.

(1) Deadlock: The deadlock problem can not be solved by two phase locking. Deadlock is a situation in which when two or more transactions have got a lock and waiting for another locks currently held by one of the other transactions.

For example

(2) Cascading Rollback: Cascading rollback is a situation in which transaction failure leads to a series of transaction rollback. For example -

When T₁ writes value of C then only T₂ can read it. And when T₂ writes the value of C then only transaction T₃ can read it. But if the transaction T₁ gets failed then automatically transactions T₂ and T₃ gets failed.

The simple two phase locking does not solve the cascading rollback problem. To solve the problem of cascading Rollback two types of two phase locking mechanisms can be used.

Types of Two Phase Locking

(1) Strict two phase locking: The strict 2PL protocol is a basic two phase protocol but all the exclusive mode locks be held until the transaction commits. That means in other words all the exclusive locks are unlocked only after the transaction is committed. That also means that if T1 has exclusive lock, then T, will release the exclusive lock only after commit operation, then only other transaction is allowed to read or write. For example Consider two transactions

If we apply the locks then

Thus only after commit operation in T1, we can unlock the exclusive lock. This ensures the strict serializability.

Thus compared to basic two phase locking protocol, the advantage of strict 2PL protocol is it ensures strict serializability.

(2) Rigorous two phase locking: This is stricter two phase locking protocol. Here all locks are to be held until the transaction commits. The transactions can be seriealized in the order in which they commit.

example - Consider transactions

If we apply the locks then

Thus the above transaction uses rigorous two phase locking mechanism

Example 3.10.2 Consider the following two transactions:

T1:read(A)

Read(B);

If A=0 then B=B+1;

Write(B)

T2:read(B); read(A)

If B=0 then A=A+1

Write(A)

Add lock and unlock instructions to transactions T1 and T2, so that they observe two phase locking protocol. Can the execution of these transactions result in deadlock? AU: Dec.-16, Marks 6

Solution:

This is lock-unlock instruction sequence help to satisfy the requirements for strict two phase locking for the given transactions.

The execution of these transactions result in deadlock. Consider following partial execution scenario which leads to deadlock.

Lock Conversion

Lock conversion is a mechanism in two phase locking mechanism - which allows conversion of shared lock to exclusive lock or exclusive lock to shared lock.

Method of Conversion :

First Phase:

• can acquire a lock-S on item

• can acquire a lock-X on item

• can convert a lock-S to a lock-X (upgrade)

Second Phase:

• can release a lock-S

• can release a lock-X

• can convert a lock-X to a lock-S (downgrade)

This protocol assures serializability. But still relies on the programmer to insert the various locking instructions.

For example - Consider following two transactions -

Here if we start applying locks, then we must apply the exclusive lock on data item A, because we have to read as well as write on data item A. Another transaction T₂ does not get shared lock on A until transaction T₁ performs write operation on A. Since transaction T₁ needs exclusive lock only at the end when it performs write operation on A, it is better if T₁ could initially lock A in shared mode and then later change it to exclusive mode lock when it performs write operation. In such situation, the lock conversion mechanism becomes useful.

When we convert the shared mode lock to exclusive mode then it is called upgrading and when we convert exclusive mode lock to shared mode then it is called downgrading.

Also note that upgrading takes place only in growing phase and downgrading takes place only in shrinking phase. Thus we can refine above transactions using lock conversion mechanism as follows -

Review Questions

1. What is concurrency control? Explain two phase locking protocol with an example.    AU: May-18, Marks 7

2. Illustrate two phase locking protocol with an example.  AU: May-14, Dec.-16, Marks 6

3. Discuss elaborately the two phase locking protocol that ensures serializability. AU: Dec.-19, Marks 9