Chapter: Database Management Systems : Transaction Processing And Concurrency Control
Two-Phase Locking Techniques: The algorithm
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
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;
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(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
Related Topics