CHAPTER 4

CONCURRENCY CONTROL

Concurrency Control
 Outline
2

 Purpose of Concurrency Control

 Two-Phase locking
 Concurrency control based on Timestamp ordering
 Multiversion Concurrency Control techniques
 Lock Compatibility Matrix
 Lock Granularity

DBMS/ Concurrency Control Techniques

 Database Concurrency Control
3

 Concurrency Control: the process of managing simultaneous

operations on the database without having them interfere with
one another.
 Purpose of Concurrency Control

 To enforce Isolation (through mutual exclusion) among

conflicting transactions.
 Topreserve database consistency through consistency
preserving execution of transactions.

DBMS/ Concurrency Control Techniques

 Database Concurrency Control
4

 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.
Conflict matrix
Read Write
Read

Y N
Write

N N

DBMS/ Concurrency Control Techniques

Concurrency Control (cont…)

1. Concurrency control using Locks

 A lock is a mechanism to control concurrent access to a data item
 Locking is an operation which secures
 (a) permission to Read
 (b) permission to Write a data item for a transaction.

 Notation :
:Li(X) –Transaction Ti requests a lock on database element X
 Unlocking is an operation which removes these permissions from the data item.
 Notation :
 Ui (X): Transaction Ti releases (“unlocks”) its lock on database element X

 Lock and Unlock are Atomic operations.

DBMS/ Concurrency Control Techniques Slide 5

 Concurrency Control (cont…)

Types of locks and system lock tables

 Binary locks
 Can have two states or values: locked and unlocked(0 or 1)

 A distinct lock is associated with each database item X

 If the value of the lock on X is 1, item X can not be accessed by a database

operation that request the item
 Too restrictive for database items because at most one transaction can hold a
lock on a given item
 Shared/Exclusive (or read /write) locks
 Allow several transactions to access the same item x if they all access x for
reading purposes

DBMS/ Concurrency Control Techniques Slide 6

Database Concurrency Control

 In shared/exclusive method, data items can be locked in

two modes :
 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

 Exclusive mode: Write lock (X)

 Only one write lock on X can exist at any time and no shared lock can be
applied by any other transaction on X
DBMS/ Concurrency Control Techniques Slide 7
 Concurrency Control (cont…)

 When we use the shared/exclusive locking scheme, the system must enforce the
following rules:
1. A transaction must issue the operation read_lock(x) or write_lock(x) before any
read_item (x) operation is performed in T
2. A transaction T must issue the operation write_lock(x) before any write_item (x)
operation is performed in T
3. A transaction T must issue the operation unlock_lock(x) after all read_item(x) and
write_item (x) operation are completed in T
4. A transaction will not issue a read_lock(x) operation if it already holds a
read(shared) lock or a write (exclusive) lock on item X
5. A transaction will not issue a write_lock(x) operation if it already holds
read(shared) lock or write(exclusive) lock on item x
6. A transaction T will not issue an unlock(x) operation unless it already holds a
read(shared) lock or a write(exclusive) lock on item x

DBMS/ Concurrency Control Techniques Slide 8

 Concurrency Control (cont…)

Lock conversion
 Sometimes, it is desirable to relax condition 4 and 5 in the coding list in order
to allow lock conversions. That is :
 Under certain conditions, a transaction that already holds a lock on item X
is allowed to convert the lock from one lock state to another.
 For example, it is possible for a transaction T to issue a read_lock (X) and
then later on to upgrade the lock by issuing a write_lock(x) operation
 If T is the only transaction holding a read lock on x at the time it issues the
write_lock (x) operation, the lock can be upgraded ;otherwise, the
transaction must wait.
 It is also possible for a transaction T to issue a write_lock(X) and then later
on to downgrade the lock by issuing a read_lock(X) operation

DBMS/ Concurrency Control Techniques Slide 9

Concurrency Control (cont…)

 Lock upgrade: change 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: change existing write lock to read lock

If Ti has a write-lock (X) (*no transaction can have any lock on X*)

convert write-lock (X) to read-lock (X)

DBMS/ Concurrency Control Techniques Slide 10

 Concurrency Control (cont…)

Slide 11

 The DBMS has lock manager subsystem to control locks

 Lock Manager:
 Manages locks on data items.

 Lock table:
 Lock manager uses it to store the identify of transaction that
lock the data item

Transaction ID Data item id lock mode Ptr to

T1 X1 Read
 Concurrency Control (cont…)

Using binary or read write locks in transactions as described earlier by itself

does not guarantee serializability :

T1 T2 Result
read_lock (Y); read_lock (X); Initial values: X=20; Y=30
read_item (Y); read_item (X); Result of serial execution
unlock (Y); unlock (X); T1 followed by T2
write_lock (X); Write_lock (Y); X=50, Y=80.
read_item (X); read_item (Y); Result of serial execution
X:=X+Y; Y:=X+Y; T2 followed by T1
write_item (X); write_item (Y); X=70, Y=50
unlock (X); unlock (Y);

DBMS/ Concurrency Control Techniques Slide 12

 Concurrency Control (cont…)

T1 T2 Result

read_lock (Y); X=50; Y=50

read_item (Y); Nonserializable because it
unlock (Y); violated two-phase policy.
read_lock (X);
read_item (X);
Time unlock (X);
write_lock (Y);
read_item (Y);
Y:=X+Y;
write_item (Y);
unlock (Y);
write_lock (X);
read_item (X);
X:=X+Y;
write_item (X);
unlock (X);

DBMS/ Concurrency Control Techniques Slide 13

Guaranteeing serializability by Two-Phase Locking Protocol (2 PL)

 A transaction is said to follow two phase locking protocol if all locking

operations (either read_lock or write_lock) precede the first unlock operation in
the transaction
 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

 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).

DBMS/ Concurrency Control Techniques Slide 14

Database Concurrency Control

T’1 T’2
read_lock (Y); read_lock (X); T’1 and T’2 follow two-phase
read_item (Y); read_item (X); policy but they are subject to
write_lock (X); Write_lock (Y); deadlock
unlock (Y); unlock (X);
read_item (X); read_item (Y);
X:=X+Y; Y:=X+Y;
write_item (X); write_item (Y);
unlock (X); unlock (Y);

DBMS/ Concurrency Control Techniques Slide 15

 Database Concurrency Control
16

 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.

DBMS/ Concurrency Control Techniques

Dealing with Deadlock and Starvation

Deadlock :occurs when each transaction T in a set of two or more

transactions is waiting for an item that is locked by some other transaction
T’ in the set

Example of deadlock situation:

T’1 T’2
read_lock (Y); T’1 and T’2 enter deadlock
read_item (Y);
read_lock (X);
read_item (X);
write_lock (X);
(waits for X) write_lock (Y);
(waits for Y)
DBMS/ Concurrency Control Techniques Slide 17
Dealing with Deadlock and Starvation

T1 T2
read_lock (Y);
read_item (Y);
unlock (y)
read_lock (X);
read_item (X);
unlock (X)

write_lock (X);
write_lock (Y);

 There is no deadlock in this schedule since T1 unlocks y and T2

unlocks x
DBMS/ Concurrency Control Techniques Slide 18
 Deadlock and Starvation (cont…)

 Deadlock prevention

1. A transaction locks all the needed data items before it begins execution

 This way of locking prevents deadlock since a transaction never waits

for a data item

 If any of the items cannot be obtained, none of the items are locked.
Rather the transaction tries again to lock all the items it needs

 This solution limits concurrency and generally not a practical

assumption

DBMS/ Concurrency Control Techniques Slide 19

Deadlock and Starvation (cont…)

 Deadlock prevention (cont.…)

2. Making a decision about what to do with a transaction involved in a

possible deadlock situation:

 Should it be blocked and made it to wait or should it be aborted.

 Should the transaction preempt and abort another transaction

 These concepts use transaction timestamp TS(T) which is a unique identifier

assigned to each transaction based on the order they started

 If transaction T1 starts before transaction T2, then

TS (T1) < TS(T2)

DBMS/ Concurrency Control Techniques Slide 20
Deadlock and Starvation (cont…)

 Two schemes that prevent dead lock based on time stamp includes wait –die and
wound-wait

 Suppose that transaction Ti tries to lock an item X but is not able to do so because X
is locked by some other transaction Tj with a conflicting lock. The rules followed by
these two schemes are as follows:

 Wait – die: If TS(Ti) < TS(Tj) i.e Ti is older than Tj, then Ti is allowed to wait ;
other wise, abort Ti (Ti dies) and restart it later with the same time stamp

 Wound - wait: If TS(Ti) < TS(Tj), abort Tj (Ti wounds Tj) and restart it later with
the same timestamp; other wise Ti is allowed to wait.

DBMS/ Concurrency Control Techniques Slide 21

Deadlock and Starvation (cont…)

 Another group of protocols that prevent deadlock do not require

timestamps

 No waiting (NW) – If transaction is unable to obtain lock, it will be

immediately aborted and restarted after some time delay
 This method cause transactions to abort and restart transactions
needlessly

 Cautious waiting (CW) – Suppose that transaction Ti tries to lock an

item X but is not able to do so because X is locked by some other
transaction Tj with a conflicting lock; the cautious rule suggest that :

 If Tj is not blocked (not waiting for some other locked item), then Ti is
DBMS/ Concurrency
blocked and allowed Control Techniques
to wait; otherwise abort Ti Slide 22
Deadlock and Starvation (cont…)

 Starvation

 Starvation occurs when a particular transaction consistently waits or

restarted and never gets a chance to proceed further

 In a deadlock resolution, it may be possible that the same transaction

may consistently be selected as victim and rolled-back

 This limitation is inherent in all priority based scheduling mechanisms

 In Wound-Wait scheme, a younger transaction may always be

wounded (aborted) by a long running older transaction which may
create starvation
DBMS/ Concurrency Control Techniques Slide 23
2. Concurrency control based on Timestamp ordering

 Timestamp (TS)

 Time stamp is a unique identifier created by the DBMS to identify a transaction

 A larger timestamp value indicates a more recent event or operation

 Timestamp based algorithm uses timestamp to serialize the execution of concurrent

transactions

 Time stamp ordering algorithm associates two time stamp values (TS) with each
database item X

1. Read_TS(x) : the read time stamp of x: This is the largest timestamp among all the
timestamps of transactions that have successfully read item x

 Read_TS(X)=TS(T) where T is the youngest transaction that has read X

successfully DBMS/ Concurrency Control Techniques Slide 24
Timestamp ordering (cont…)

2. Write_TS(X) : This is the largest of all the timestamps of transactions

that have successfully written item x – that is, write_TS(x) = TS(T),
where T is the youngest transaction that has written x successfully

 Basic Timestamp Ordering (TO):

 whenever some transaction T tries to issue a read_item(X) or a

write_item(X) operation, the basic TO algorithm compares the
timestamp of T with read_TS(X) and write_TS(X)

 The concurrency control algorithm must check whether conflicting

operations violate the timestamp ordering as in the two cases provided in
the next slide: DBMS/ Concurrency Control Techniques Slide 25
3. Multiversion concurrency control techniques

 This approach maintains a number of versions of a data item and allocates the
right version to a read operation of a transaction.

 Unlike other mechanisms a read operation in this mechanism is never

rejected

 Side effect:

 Need more storage (RAM and disk) is required to maintain multiple

versions

 To check unlimited growth of versions, a garbage collection is run when

some criteria is satisfied
DBMS/ Concurrency Control Techniques Slide 26
Multiversion techniques (cont…)

 Assume X1, X2, …, Xn are the version of a data item X created by a write
operation of transactions.

 With each Xi a read_TS (read timestamp) and a write_TS (write

timestamp) are associated.

 read_TS(Xi): The read timestamp of Xi is the largest of all the timestamps of

transactions that have successfully read version Xi.

 write_TS(Xi): The write timestamp of Xi that wrote the value of version Xi.

DBMS/ Concurrency Control Techniques Slide 27

4. Validation (Optimistic) Concurrency Control Schemes

 In this technique, serializability is checked only at the time of commit and transactions
are aborted in case of non-serializable schedules
 No checking is done while transaction is executing
 In this scheme, updates in the transaction are not applied directly to the database item
until it reaches its commit point
 Three phases:
1. Read phase
2. Validation phase
3. Write phase
1. Read phase:
 A transaction can read values of committed data items. However, updates are
applied only to local copies (versions) of the data items (in database cache)

DBMS/ Concurrency Control Techniques Slide 28

 4. Validation (Optimistic) Concurrency Control Schemes

2. Validation phase: Serializability is checked before

transactions write their updates to the database.

3. Write phase: On a successful validation

transactions’ updates are applied to the database;
otherwise, transactions are restarted

DBMS/ Concurrency Control Techniques Slide 29

Granularity of data items and Multiple Granularity Locking (MGL)

 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 database table
4. The entire database

DBMS/ Concurrency Control Techniques Slide 30

Cont.…

 To make multiple granularity level locking practical, three additional locking

modes, called intention lock modes are defined:
 Intention-shared (IS): indicates that a shared lock(s) will be requested on
some descendent nodes(s).
 Intention-exclusive (IX): indicates that an exclusive lock(s) will be
requested on 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)
 The idea behind intention locks is for a transaction to indicate what type of lock
(shared or exclusive) it will require from one of the node’s descendants

DBMS/ Concurrency Control Techniques Slide 31

32

Thank you!

DBMS/ Concurrency Control Techniques