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.
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
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.
Comments
Post a Comment
please subscribe my blog and let me suggest how I improve this site