Explain Two-Phase Locking Techniques with Algorithm In DBMS - Computer science tutorial point

Two-Phase Locking Techniques

Locking is an operation which secures (a) permission to Read or (b) permission to write a data item for a transaction.  Example: Lock (X).  Data item X is locked in behalf of the requesting transaction. 

Unlocking is an operation which removes these permissions from the data item.  Example: Unlock (X).  Data item X is made available to all other transactions. Lock and Unlock are Atomic operations

Two-Phase Locking Techniques: Essential components

1) Two locks modes (a) shared (read) and (b) exclusive (write).

Shared mode: shared lock (X).  More than one transaction can apply share lock on X for reading its value but no write lock can be applied on X by any other transaction.

Exclusive mode: Write lock (X).  Only one write lock on X can exist at any time and no shared lock can be applied by any other transaction on X.

Conflict matrix

2) Lock Manager: Managing locks on data items  Lock table: Lock manager uses it to store the identify of transaction locking a data item, the data item,lock mode and pointer to the next data item locked. One simple way to implement a lock table is through linked list.

3) Database requires that all transactions should be well- formed.  A transaction is well-formed if:

•      It must lock the data item before it reads or writes to it.

•      It must not lock an already locked data items and it must not try to unlock a free data item

4) The following code performs the lock operation:

       B:   if LOCK (X) = 0 (*item is unlocked*)

       then LOCK (X) ¬ 1 (*lock the item*)

       else begin

             wait (until lock (X) = 0) and

             the lock manager wakes up the transaction);

goto B

    end;

The following code performs the unlock operation:

LOCK (X) ¬ 0 (*unlock the item*)

if any transactions are waiting then wake up one of the waiting the transaction.

5) The following code performs the read operation:

    B: if LOCK (X) = “unlocked” then

           begin LOCK (X) ¬ “read-locked”;

               no_of_reads (X) ¬ 1;

  end

  else if LOCK (X) ¬ “read-locked” then

       no_of_reads (X) ¬ no_of_reads (X) +1

else begin wait (until LOCK (X) = “unlocked” and

  the lock manager wakes up the transaction);

                go to B

               end;

6) The following code performs the write lock operation:

    B: if LOCK (X) = “unlocked” then

          begin LOCK (X) ¬ “read-locked”;

                 no_of_reads (X) ¬ 1;

end

else if LOCK (X) ¬ “read-locked” then

   no_of_reads (X) ¬ no_of_reads (X) +1

    else begin wait (until LOCK (X) = “unlocked” and

          the lock manager wakes up the transaction);

                go to B

               end;

7) The following code performs the unlock operation:

    if LOCK (X) = “write-locked” then

       begin LOCK (X) ¬ “unlocked”;

          wakes up one of the transactions, if any

end

else if LOCK (X) ¬ “read-locked” then

    begin
          no_of_reads (X) ¬ no_of_reads (X) -1

          if  no_of_reads (X) = 0 then                    

          begin

              LOCK (X) = “unlocked”;

             wake up one of the transactions, if any

          end

Lock conversion

    Lock upgrade: existing read lock to write lock

if Ti has a read-lock (X) and Tj has no read-lock (X) (i ¹ j) then

 convert read-lock (X) to write-lock (X)

   else

    force Ti to wait until Tj unlocks X

  Lock downgrade: existing write lock to read lock

  Ti has a write-lock (X) (*no transaction can have any lock on X*)

  convert write-lock (X) to read-lock (X)

   

Two-Phase Locking Techniques: The algorithm 

Two Phases:  (a) Locking (Growing) (b) Unlocking (Shrinking).

Locking (Growing) Phase:  A transaction applies locks     (read or write) on desired data items one at a time.

Unlocking (Shrinking) Phase: A transaction unlocks its locked data items one at a time.

Requirement:  For a transaction these two phases must be mutually exclusively, that is, during locking phase unlocking phase must not start and during unlocking phase locking phase must not begin.

Two-Phase Locking Techniques: The algorithm   

T’1                                       T’2                   

read_lock (Y);         read_lock (X);             T1 and T2 follow twophase

read_item (Y);         read_item (X);         policy but they are subject to

write_lock (X);        Write_lock (Y);          deadlock, which must be

unlock (Y);                 unlock (X);               deals with.

read_item (X);         read_item (Y);  

X:=X+Y;                            Y:=X+Y;                   

write_item (X);       write_item (Y); 

unlock (X);              unlock (Y);        

Two-Phase Locking Techniques: The algorithm

Two-phase policy generates two locking algorithms (a) Basic and (b) Conservative.

Conservative:  Prevents deadlock by locking all desired data items before transaction begins execution.

Basic:  Transaction locks data items incrementally.  This may cause deadlock which is dealt with.

    Strict:  A more stricter version of Basic algorithm          where unlocking is performed after a transaction          terminates (commits or aborts and rolled back).This  is the most commonly used two-phase locking algorithm.