Home | | Database Management Systems | Two-Phase Locking Techniques: The algorithm

Chapter: Database Management Systems : Transaction Processing And Concurrency Control

Two-Phase Locking Techniques: The algorithm

The timing of locks is also important in avoiding concurrency problems. A simple requirement to ensure transactions are serializable is that all read and write locks in a transaction are issued before the first unlock operation known as a two-phase locking protocol.

Two-Phase Locking Techniques: The algorithm

 

The timing of locks is also important in avoiding concurrency problems. A simple requirement to ensure transactions are serializable is that all read and write locks in a transaction are issued before the first unlock operation known as a two-phase locking protocol.

 

Transaction divided into 2 phases:

growing - new locks acquired but none released

shrinking - existing locks released but no new ones acquired

 

 

During the shrinking phase no new locks can be acquired!

 

–  Downgrading ok

–  Upgrading is not

 

 

Rules of 2PL are as follows:

If T wants to read an object it needs a read_lock 

If T wants to write an object, it needs a write_lock

Once a lock is released, no new ones can be acquired.

 

 

The 2PL protocol guarantees serializability

Any schedule of transactions that follow 2PL will be serializable 

We therefore do not need to test a schedule for serializability

 

 

But, it may limit the amount of concurrency since transactions may have to hold onto locks longer than needed, creating the new problem of deadlocks.

 

Two-Phase Locking Techniques: The algorithm

 

 

 

Here is a example  without 2PL:-

 





 

Two-phase policy generates four locking algorithms:-

 

1.     BASIC

 

2.     CONSERVATIVE

3.     STRICT

 

         Previous technique knows as basic 2PL

 

         Conservative 2PL (static) 2PL: Lock all items needed BEFORE execution begins by predeclaring its read and write set

 

– If any of the items in read or write set is already locked (by other transactions), transaction waits (does not acquire any locks)

 

–  Deadlock free but not very realistic

         Strict 2PL: Transaction does not release its write locks until AFTER it aborts/commits

 

– Not deadlock free but guarantees recoverable schedules (strict schedule: transaction can neither read/write X until last transaction that wrote X has committed/aborted)

 

–  Most popular variation of 2PL

         Rigorous 2PL: No lock is released until after abort/commit

Transaction is in its expanding phase until it ends

 

The Two-Phase Locking Protocol

 

Introduction

 

This is a protocol, which ensures conflict-serializable schedules.

 

Phase 1: Growing Phase

 

Transaction may obtain locks.

 

Transaction may not release locks.

 

Phase 2: Shrinking Phase

 

Transaction may release locks.

 

Transaction may not obtain locks.

 

The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points.

 

–Lock points: It is the point where a transaction acquired its final lock.

 

Two-phase locking does not ensure freedom from deadlocks

 

Cascading rollback is possible under two-phase locking.

 

There can be conflict serializable schedules that cannot be obtained if two-phase locking is used.

 

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.

 

Lock Conversions

 

Two-phase locking with lock conversions:

 

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.

 

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 transaction has a grant Ti a lock-S read( D)

until no other lock-X on D on 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 Dto lock-X

 

else

 

grant Ti a lock-X on D write( D)

 

end;All locks are released after commit or abort

 

 

 

Graph-Based Protocols

 

It is an alternative to two-phase locking.

 

Impose a partial ordering on the set D = f d1, d2 , ..., dhg of all data items.

 

If di! dj, then any transaction accessing both di and dj must access di before accessing dj.

 

Implies that the set D may now be viewed as a directed acyclic graph, called a database

 

graph.

Tree-protocol is a simple kind of graph protocol.

Tree Protocol

 

Only exclusive locks are allowed.

The first lock by Ti may be on any data item. Subsequently, Ti can lock a data item Q, only if Ti currently locks the parent of Q.

 

Data items may be unlocked at any time.

 

A data item that has been locked and unlocked by Ti cannot subsequently be re-locked by Ti.

 

The tree protocol ensures conflict serializability as well as freedom from deadlock.

 

Unlocking may occur earlier in the tree-locking protocol than in the twophase locking protocol.

 

However, in the tree-locking protocol, a transaction may have to lock data items that it does not access.

 

Increased locking overhead, and additional waiting time. Schedules not possible under two-phase locking are possible under tree

 

protocol, and vice versa.

 

Granularity of data items and Multiple Granularity Locking

 

A lockable unit of data defines its granularity. Granularity can be coarse (entire database) or it can be fine (a tuple or an attribute of a relation).

Data item granularity significantly affects concurrency control performance. Thus, the degree of concurrency is low for coarse granularity and high for fine granularity.

Example of data item granularity:

1.     A field of a database record (an attribute of a tuple)

2.     A database record (a tuple or a relation)

3.     A disk block

4.     An entire file

 

5.     The entire database

n        The following diagram illustrates a hierarchy of granularity from coarse (database) to fine (record).


 


To manage such hierarchy, in addition to read and write, three additional locking modes, called intention lock modes are defined:

o Intention-shared (IS): indicates that a shared lock(s) will be requested on some descendent nodes(s).

o Intention-exclusive (IX): indicates that an exclusive lock(s) will be requested on some descendent node(s).some descendent node(s). 

Shared-intention-exclusive (SIX): indicates that the current node is locked in shared mode but an exclusive lock(s) will be requested on some descendent nodes(s).

 

 

These locks are applied using the following compatibility matrix:

 

 

 

     The set of rules which must be followed for producing serializable schedule are

 

1.     The lock compatibility must adhered to.

 

2.     The root of the tree must be locked first, in any mode..

 

3.     A node N can be locked by a transaction T in S or IX mode only if the parent node is already locked by T in either IS or IX mode.

 

4.     A node N can be locked by T in X, IX, or SIX mode only if the parent of N is already locked by T in either IX or SIX mode.

 

5.     T can lock a node only if it has not unlocked any node (to enforce 2PL policy).

 

6.     T can unlock a node, N, only if none of the children of N are currently locked by T.

 

 

Granularity of data items and Multiple Granularity Locking: An example of a serializable execution:

 

T1                    T2                           T3

 

IX(db)

 

IX(f1)

 

IX(db)

 

IS(db) IS(f1)

 

IS(p11)

 

IX(p11)

 

X(r111)

 

IX(f1)

 

X(p12)

 

S(r11j)

 

IX(f2)

 

IX(p21)

 

IX(r211)

 

Unlock (r211)

 

Unlock (p21)

 

Unlock (f2)

 

S(f2)

DEAD LOCKS:-

 

Two Problems with Locks

 

–  Deadlock

–  Starvation

 

Dead locks occurs when each transaction Ti in a set of two or more is waiting on an item locked by some other transaction Tj in the set

 

Dead lock example:

 

T’1                       T’2

 

read_lock (Y);                                  T1 and T2 did follow two-phase

 

read_item (Y);                                  policy but they are deadlock

 

read_lock (X);

read_item (X);

 

write_lock (X);

 

(waits for X) write_lock (Y); (waits for Y)

 

 

Deadlock Prevention

 

 

 

 

         Locking as deadlock prevention leads to very inefficient schedules (e.g., conservative 2PL)

         Better, use transaction timestamp TS(T)

 

–  TS is unique identifier assigned to each transaction

–  if T1 starts before T2, then TS(T1) < TS(T2) (older has smaller timestamp value)

–  Wait-die and wound-wait schemes

 

 

Wait-Die Scheme

 

         Assume Ti tries to lock X which is locked by Tj

 

         If TS(Ti) < TS(Tj) (Ti older than Tj), then Ti is allowed to wait

 

         Otherwise, Ti younger than Tj, abort Ti (Ti dies) and restart later with SAME timestamp

 

         Older transaction is allowed to wait on younger transaction

 

         Younger transaction requesting an item held by older transaction is aborted and restarted

 

 

 

 

 

Wound-Wait Scheme

 

         Assume Ti tries to lock X which is locked by Tj

 

         If TS(Ti) < TS(Tj) (Ti older than Tj), abort Tj (Ti wounds Tj) and restart later with SAME timestamp

 

         Otherwise, Ti younger than Tj, Ti is allowed to wait

 

         Younger transaction is allowed to wait on older transaction

 

         Older transaction requesting item held by younger transaction preempts younger one by aborting it

 

         Both schemes abort younger transaction that may be involved in deadlock

 

         Both deadlock free but may cause needless

More Deadlock Prevention

 

         Waiting schemes (require no timestamps)

 

         No waiting: if transaction cannot obtain lock, aborted immediately and restarted after time t needless restarts

 

         Cautious waiting:

 

–  Suppose Ti tries to lock item X which is locked by Tj

–  If Tj is not blocked, Ti is blocked and allowed to wait

–  O.w. abort Ti

–  Cautious waiting is deadlock-free

Deadlock Detection

 

         DBMS checks if deadlock has occurred

 

–  Works well if few short transactions with little interference

–  O.w., use deadlock prevention

         Two approaches to deadlock detection:

 

1.     Wait-for graph

–  If cycle, abort one of the transactions (victim selection)

2.     Timeouts

 

 

Starvation

 

         Transaction cannot continue for indefinite amount of time while others proceed normally

 

         When? Unfair waiting scheme with priorities for certain transactions E.g., in deadlock detection, if we choose victim always based on cost factors, same transaction may always be picked as victim

 

–  Include rollbacks in cost

 

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Database Management Systems : Transaction Processing And Concurrency Control : Two-Phase Locking Techniques: The algorithm |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.