2 Phase Locking

Need of 2 Phase Locking

Binary locks or shared and exclusive locks in transaction does not guarantee serializability of schedules on its own.
For example, consider a banking transaction where the read write locking rules are used, but we get a non serializable schedule which give incorrect result.

2 phase Locking Example

To ensure the serializability, we use two phase locking.

Two Phase Locking (2PL)

In this scheme, each transaction makes lock and unlock request in 2 phases :

  1. A Growing Phase( or An Expanding Phase or First Phase)  : In this phase, new locks on the desired data item can be acquired but none can be released.
  2. A Shrinking Phase (or Second Phase) : In this phase, existing locks can be released but no new locks can be acquired.

2 phase Locking 1

A 2 phase locking always results serializable schedule but it does not permit all possible serializable schedules i.e. some serializable schedules will be prohibited by the protocol.

Strategy :

A transaction T does not allowed to request any lock if T has performed already some unlock operation and every equivalent serial schedule is based on the order of the LOCK point.

2 phase Locking 2

Question : Consider the scenario and find out weather it is in 2 phase locking or not?
Solution : 
             2 phase Locking 3

This technique is also called as Basic 2PL.

Points About 2 Phase Locking

  • Every non serializable schedule failed to execute using two phase locking.
  • 2 phase locking always results serializable schedule.
  • Equivalent serial schedule is based on the order of the lock point.
  • If schedule is allowed to execute bye 2pl then schedule is conflict serializable but not vice versa.
    2 phase Locking 2PL1
  • If schedule is not conflict serializable, then schedule is not allowed to execute by 2pl.
  • A schedule is allowed to execute by 2 PL , then it is always serializable.
  • 2 phase Locking 2PL2

Combining Two Phase Locking and Binary Locking

2 phase Locking 7

  1. The first problem in binary locking + 2 phase locking is that it leads to deadlock. In the given example, T1 is waiting for T2 to get B and T2 is waiting for T1 to get A. Hence deadlock occurred.
  2. The second problem in binary locking + 2 phase locking is that it provides less concurrency because in binary locking, 2 or more transactions simultaneously not allowed to perform read operation. This can easily be shown in the below figure 9.
    2 phase Locking 8
  3. The third problem(shown in fig 10) in binary locking + 2 phase locking is that the same lock is used for read as well as write, so we are unable to differentiate whether the transaction locks a data item for reading purpose or for writing purpose.

Combining 2 Phase Locking + Shared and Exclusive Locking

Only shared and exclusive locks may not ensure serializability i.e. non serializable schedule is possible to execute using shared and exclusive locking. For example,

2 phase Locking 9

But when we combine both 2 phase locking and shared and exclusive locking, then it always results serializable schedule and the equivalent serial schedule is based on the order of LOCKING.

2 phase Locking 10

Problems occurred in (2 Phase Locking + Shared and Exclusive Locking)

  1. The first problem in 2PL + S/X Locking is that however, we get a serializable schedule but it may not free from irrecoverability.
    Example : The schedule in figure 11 is not recoverable schedule.
    To avoid irrecoverability, the Exclusive lock is called until commit/rollback. Hence other transaction is not allowed either to read or write.( no dependency so no problem).
    2 phase Locking 14.1
  2. The second problem in 2PL + S/X Locking is that it is not free from deadlock. For example
    2 phase Locking 11
    To recover from deadlock, deadlock prevention algo is used. But the deadlock prevention algorithm takes more CPU time than the actual work and 99.9 % times the algorithm returns safe. Therefore it is a wastage of precious CPU time. So Unix/Windows/Solaris don’t use deadlock prevention algorithm.
    2 phase Locking 13
  3. The third problem in 2PL + S/X Locking is that the schedule is not free from starvation.
    2 phase Locking 12

Variations of 2 Phase Locking :

There are number of variations of 2 Phase Locking :

  • Basic 2PL
  • Conservative 2pl ( or static 2PL)
  • Strict 2PL
  • Rigorous 2PL

Basic 2PL

The technique of two phase locking describe above is known as Basic 2PL.

Conservative 2PL( or Static 2PL)

In Conservative 2PL protocol, a transaction has to lock all the items it access before the transaction begins execution. To avoid deadlocks, we can use Conservative 2PL.

Basic 2pl + all locks required to execute the transaction should be hold before starting its execution
Advantages of Conservative 2PL :
  1. No possibility of deadlock.
  2. Ensure serializability.
Drawbacks of Conservative 2PL :
  1. Less throughput.
  2. Less resource utilisation because it holds the resources before the transaction begins execution.
    2 phase Locking 15
  3. Less concurrency
  4. Prediction of all the required resources before execution is also too complex.
  5. Irrecoverability possible since no restriction on unlock operation.
  6. However conservative 2pl is a deadlock free protocol but it is difficult to use in practice.
  7. Starvation is possible.
How Starvation is possible ??
 Question : What if some required resource is not available at the time of holding i.e. before the transaction begins execution?
Solution : It will unlock all other resources hold by it because they were free.
 It may cause starvation. Because if at a time A is not available, another point of time B is not available and in another point of time C is not available.

     2 phase Locking 16

Strict 2PL

A transaction T does not release any of its exclusive(write) locks until after it commits or aborts.

Basic 2pl + all the exclusive locks should we hold until commit / rollback.

2 phase Locking 17

Points about Strict 2PL

  1. Strict  2PL ensures serializability and the equivalent serial schedule is based on the lock point.
    2 phase Locking 18
  2. Strict 2PL also ensures strict recoverable schedule.
  3. Strict 2PL may not free from deadlock and starvation.

Rigorous 2PL Protocol

Transaction does not release any of its write locks and read locks until after it commits or aborts.

Basic 2PL + All S/X locks should be hold until commit / rollback.

Rigorous 2pl protocol ensures serializability and the equivalent serial schedule is based on the order of COMMIT.

Example 2 phase Locking 19

Difference Between 2PL and Rigorous 2PL Protocol

Strict 2PL Rigorous 2PL
Equivalent serial schedule is based on the lock point. Equivalent serial schedule is based on the order of commit.
Only exclusive locks should hold up to commit / rollback. Both S / X locks are to be hold.

Expressive Power of Variations of 2 Phase Locking

Expressive Power of Variations of 2 Phase Locking

There is no comparison between conservative 2PL and ( Strict 2PL, Basic 2PL and Rigorous 2PL)

Relation Between Conflict Serializable, View Serializable and 2 Phase Locking Schedules

2 phase Locking 2PL3


Previous Home Next
Shared and Exclusive Locks Timestamp Ordering Protocols

     

Incoming search terms:

  • advantages and disadvantages of two phase locking protocol
  • two phase locking protocol in dbms
  • advantages of two phase locking protocol in dbms
  • two phase locking protocol in dbms with example
  • two phase locking protocol
  • 2 phase lock
  • 2pl in dbms
  • two phase
  • c code for strict2 phase locking
  • how does 2pl guarantee serializability

Leave a Reply