In DBMS describe Two-Phase Locking Techniques with Algorithm

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

    T1                      T2                   Result

read_lock (Y);                        read_lock (X);           Initial values: X=20; Y=30

read_item (Y);                       read_item (X);        Result of serial execution

unlock (Y);                                 unlock (X);                T1 followed by T2

write_lock (X);                      Write_lock (Y);          X=50, Y=80.

read_item (X);                       read_item (Y);          Result of serial execution

X:=X+Y;                                         Y:=X+Y;                            T2 followed by T1 

write_item (X);                     write_item (Y);         X=70, Y=50

unlock (X);                                 unlock (Y); 

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.