Chapter 22 Concurrency Control Techniques Copyright 2011 Pearson Education Inc Publishing as Pearson Addison Wesley Database Concurrency Control 1 Purpose of Concurrency Control To enforce Isolation through mutual exclusion among conflicting transactions To preserve database consistency through consistency preserving execution of transactions To resolve read write and write write conflicts Example In concurrent execution environment if T1 conflicts with T2 over a data item A then the existing concurrency control decides if T1 or T2 should get the A and if the other transaction is rolled back or waits Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Essential components 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 item and it must not try to unlock a free data item Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Locking is an operation which secures Example Lock X Data item X is locked on behalf of the requesting transaction Unlocking is an operation which removes these permissions from the data item Example a permission to Read b permission to Write a data item for a transaction Unlock X Data item X is made available to all other transactions Lock and Unlock are Atomic operations Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Essential components Two locks modes 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 b exclusive write Shared mode shared lock X a shared read Only one write lock on X can exist at any time and no shared lock can be applied by any other transaction on X Read Conflict matrix Write Read Write Y N N N Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Essential components Lock Manager Managing locks on data items Lock table Lock manager uses it to store the identity 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 Transaction ID Data item id lock mode Ptr to next data item T1 X1 Read Next Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Essential components Lock and unlock operations for binary locks 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 Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Essential components 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 transactions Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Essential components Locking operation for two mode read write locks Following code performs the read 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 Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Essential components The following code performs the write lock operation B if LOCK X unlocked then LOCK X write locked else begin wait until LOCK X unlocked and the lock manager wakes up the transaction go to B end Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques Essential components 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 end Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control 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 exclusive that is during locking phase unlocking phase must not start and during unlocking phase locking phase must not begin Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques The algorithm T1 T2 Result read lock Y read item Y unlock Y write lock X read item X X X Y write item X unlock X read lock X read item X unlock X Write lock Y read item Y Y X Y write item Y unlock Y Initial values X 20 Y 30 Result of serial execution T1 followed by T2 X 50 Y 80 Result of serial execution T2 followed by T1 X 70 Y 50 Copyright 2011 Ramez Elmasri and Shamkant Navathe Database Concurrency Control Two Phase Locking Techniques The algorithm T1 read lock Y read item Y unlock Y Time write lock X read item X X X Y write item X unlock X T2 read lock X read item X unlock X write lock Y read item Y Y X Y write item Y unlock Y Copyright 2011 Ramez Elmasri and Shamkant Navathe Result X 50 Y 50 Nonserializable because it violated two phase policy Database Concurrency Control Two Phase Locking Techniques The algorithm T 1 T 2 read lock Y read item Y write lock X unlock Y read item X X X Y write item X unlock X read lock X read item X Write lock Y unlock X read item Y Y X Y write item Y unlock Y Copyright 2011 Ramez Elmasri and Shamkant Navathe T1 and T2 follow two phase policy but they are subject to deadlock which must be dealt with Database Concurrency Control Two Phase Locking Techniques The algorithm Two phase policy generates two locking algorithms a Basic 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
View Full Document
Unlocking...