Classle

Two Phase Locking Protocol

TWO PHASE LOCKING

 

A transaction is said to follow the two-phase locking protocol if all locking operations (read_lock, write_lock) precede the first unlock operation in the transaction. Such a transaction can be divided into two phases:

Phase 1: Growing Phase

i)  transaction may obtain locks

ii)  transaction may not release locks

Phase 2: Shrinking Phase

i)  transaction may release locks

ii)  transaction may not obtain locks

 

If lock conversion is allowed, then upgrading of locks (from read-locked to write-locked) must be done during the expanding phase, and downgrading of locks (from write-locked to read-locked) must be done in the shrinking phase. Hence, a read_lock(X) operation that downgrades an already held write lock on X can appear only in the shrinking phase.

 

The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points  (i.e. the point where a transaction acquired its final lock). Two-phase locking does not ensure freedom from deadlocks.

 

Types of 2PL:

 

  • Basic 2PL – described above.
  • Conservative 2PL (Static 2PL) - requires a transaction to lock all the items it accesses before the transaction begins execution, by predeclaring its read-set and write-set.
  • Cascading roll-back is possible under two-phase locking. To avoid this, follow a modified protocol called strict two-phase locking. Here a transaction must hold all its exclusive locks till it commits/aborts.
  • Rigorous two-phase locking is even stricter: here all locks are held till commit/abort. In this protocol transactions can be serialized in the order in which they commit.

There can be conflict serializable schedules that cannot be obtained if two-phase locking is used.  However, in the absence of extra information (e.g., ordering of  access to data), two-phase locking is needed for conflict serializability in the following sense:

    Given a transaction Ti that does not follow two-phase locking, we can find a transaction Tj that uses two-phase locking, and a schedule for Ti and Tj that is not conflict serializable.

 

Automatic Acquisition of Locks

A transaction Ti issues the standard read/write instruction, without explicit locking calls.

The operation read(D) is processed as:

                      if Ti has a lock on D

                         then

                                read(D)

                         else begin

                                   if necessary wait until no other 

                                       transaction has a lock-X on D

                                   grant Ti a  lock-S on D;

                                   read(D)

                                end

write(D) is processed as:

     if Ti has a  lock-X on D

        then

          write(D)

       else begin

            if necessary wait until no other trans. has any lock on D,

            if Ti has a lock-S on D

                 then

                    upgrade lock on D  to lock-X

                else

                    grant Ti a lock-X on D

                write(D)

         end;

All locks are released after commit or abort

 

 

References:

www.wikipedia.org

codex.cs.yale.edu/avi/db-book/slide-dir/ch16.ppt  

 


Dear Guest,
Spend a minute to Register in a few simple steps, for complete access to the Social Learning Platform with Community Learning Features and Learning Resources.
If you are part of the Learning Community already, Login now!
0
Your rating: None

Collaborate

Posted by



Thu, 05/21/2009 - 11:47

Share