Advanced Database Systems

Chapter Three

Concurrency Control Techniques

Contents
4.1 Two-Phase Locking Techniques for Concurrency Control
4.1.1 Types of Locks and System Lock Tables
4.1.2 Guaranteeing Serializability by Two-Phase Locking
4.1.3 Dealing with Deadlock and Starvation
4.2 Concurrency Control Based on Timestamp Ordering
4.2.1 Timestamps
4.2.2 The Timestamp Ordering Algorithm for Concurrency Control
4.3 Multiversion Concurrency Control Techniques
4.3.1 Multiversion Technique Based on Timestamp Ordering
4.4 Validation (Optimistic) Techniques Concurrency Control
4.5 Granularity of Data Items and Multiple Granularity Locking
4.5.1 Granularity Level Considerations for Locking
4.5.2 Multiple Granularity Level Locking
Slid
e2
Concurrency Control Techniques

 Purpose of Concurrency Control

◦ To ensure Isolation property of concurrently
executing transactions
◦ To preserve database consistency
◦ 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 controller decides if
T1 or T2 should get A and which transaction
should be rolled-back or waits.
3
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. 4
Concurrency control using Locks(cont.…)
Types of locks and system lock tables
 Binary locks
◦ Two states (values)
▪ Locked (1)
- Item cannot be accessed
▪ Unlocked (0)
- Item can be accessed when requested
o A distinct lock is associated with each database item X
o If the value of the lock on X is 1, item X can not be
accessed by a database operation that request the item
o 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 5
Lock and unlock operations for binary locks

6
Shared/Exclusive (or Read/Write) Locks
 Read operations on the same item are not conflicting
 Must have exclusive lock to write
 Three locking operations
o read_lock(X)
o write_lock(X)
o unlock(X)
 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. 7
Locking and unlocking
operations for two-mode
(read/write, or
shared/exclusive) locks.

8
Shared/Exclusive (or Read/Write) Locks…
 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) 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 9
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. 10
Lock conversion…
• 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)

11
Lock compatibility
• A transaction may be granted a lock on an item if
the requested lock is compatible with locks already
held on the item by other transactions
• Any number of transactions can hold shared locks on an
item,
o But if any transaction holds an exclusive lock on the
item no other transaction may hold any lock on the item.
• If a lock cannot be granted, the requesting
transaction will be made to wait until all
incompatible locks held by other transactions have
been released
o Lock compatibility matrix

12
Cont…
 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

T1 X1 Read

13
Lock Table  Black rectangles indicate granted
locks, white ones indicate waiting
requests
 Lock table also records the type of
lock granted or requested
 New request is added to the end
of the queue of requests for the
data item, and granted if it is
compatible with all earlier locks
 Unlock requests result in the
request being deleted, and later
requests are checked to see if they
Granted can now be granted
Waiting  If transaction aborts, all waiting or
granted requests of the transaction
are deleted

14
Cont…
Using binary or read write locks in transactions as described
earlier by itself does not guarantee serializability :

Transactions that do not obey two-phase locking.

15
Transactions that do not obey two-phase locking

A non-serializable schedule S that uses locks.

16
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).
17
Two-Phase Locking Protocol (2 PL)…

18
Two-Phase Locking Protocol (2 PL)…

T’1 and T’2 follow two-phase policy but they are subject to deadlock
19
Variations of Two-Phase Locking
 Two-phase locking policy generates two locking algorithms
◦ (a) Basic
◦ (b) Conservative
◦ Basic 2PL:
 Technique described on previous slides
 Transaction locks data items incrementally. This may
cause deadlock.
◦ Conservative (static) 2PL:
 Requires a transaction to lock all the items it accesses
before the transaction begins
 Predeclare read-set and write-set.
 Prevents deadlock by locking all desired data items
before transaction begins execution (Deadlock-free
protocol). 20
Dealing with Deadlock and Starvation
 Deadlock
o Occurs when each transaction T in a set is waiting for some item
locked by some other transaction T’.
o Both transactions stuck in a waiting queue.
 Example of deadlock situation

21
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

22
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
waits and tries again to lock all the items it
needs
 This solution limits concurrency and
generally not a practical assumption.

23
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)
24
Deadlock prevention (cont.…)
 Two schemes that prevent dead lock based on time stamp
includes
o Wait-die
o 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. 25
Deadlock prevention (cont.…)
 Another group of protocols that prevent deadlock do not
require timestamps
 No waiting (NW) algorithm – 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) algorithm – 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 blocked and allowed to wait; otherwise abort Ti
 Deadlock detection
 System checks to see if a state of deadlock exists
 Wait-for graph
26
Deadlock prevention (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
27
2. Concurrency control based on Timestamp
ordering
 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.
 Do not use locks ( Deadlocks cannot occur)
 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 28
Concurrency Control Based
on Timestamp Ordering (cont’d)
2. Write_TS(X) : This 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:
29
Cont…
1. Transaction T issues a write_item(X) operation:
a) If read_TS(X) > TS(T) or if write_TS(X) > TS(T),
then a younger transaction has already read or written
the data item so abort and roll-back T and reject the
operation.
This is because a younger transaction has already read or
written the value before T had the chance to write X;
b) If the condition in part (a) does not exist, then execute
write_item(X) of T and set write_TS(X) to TS(T)
2. Transaction T issues a read_item(X) operation:
a) If write_TS(X) > TS(T), then abort and roll-back T and
reject the operation. This is because a younger
transaction has already written the value before T
had the chance to read X;
b) If write_TS(X)  TS(T), then execute read_item(X) of T
and set read_TS(X) to the larger of TS(T) and the
current read_TS(X)

30
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(reading an older
version of the item)
• 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

31
Multiversion concurrency control Based on
timestamp ordering

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

32
Multiversion concurrency control Based on
timestamp ordering(Cont.…)
• Whenever a transaction T is allowed to
execute a write_item(X) operation, a new
version Xk+1 of item X is created with both
the write_TS(Xk+1) and read_TS(Xk+1) set
to TS(T).
• Correspondingly, when a transaction is
allowed to read the value of xi, the value of
read_TS(xi) is set to the larger of the
current read_TS(xi) and TS(T)

33
Multiversion concurrency control Based on
timestamp ordering(Cont.…)
 To ensure serializability, the following two rules are used.
1) If transaction T issues write_item (X) and version i of
X has the highest write_TS(Xi) of all versions of X that
is also less than or equal to TS(T), and read _TS(Xi) >
TS(T), then abort and roll-back T; otherwise create a
new version Xj of X with read_TS(Xj) = write_TS(Xj)
= TS(T)
2) If transaction T issues read_item (X), find the version i
of X that has the highest write_TS(Xi) of all versions of
X that is also less than or equal to TS(T), then return the
value of Xi to transaction T, and set the value of
read _TS(Xi) to the largest of TS(T) and the current
read_TS(Xi)
◦ Rule 2 guarantees that a read will never be rejected.

34
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)
35
Validation Concurrency Control (Cont.…)

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

36
Granularity of data items and Multiple
Granularity Locking (MGL)
 A lockable unit of data(size) 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.
 Larger the data item size, lower the degree of concurrency
permitted(eg. entire disk block locked.
 Smaller the data item size, more locks required(Higher
overhead)
 Thus, the degree of concurrency is low for coarse granularity and high
for fine granularity.
 Best item size depends on transaction type
 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 37
Multiple Granularity Locking (Cont.…)
 Lock can be requested at any level
 The following diagram illustrates a hierarchy of
granularity from coarse to fine

A granularity hierarchy for illustrating multiple granularity level locking

38
Multiple Granularity Locking (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 descendentnodes(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(from the root
to the desired node)
39
Multiple Granularity Locking (Cont.…)

 Intention locks are applied using the following

compatibility matrix:

Lock compatibility matrix for multiple granularity locking. 40

Multiple Granularity Locking (Cont.…)
 The set of rules (multiple granularity locking, MGL) 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. 41
Multiple Granularity Locking (Cont.…)

 Rule 1 simply states that conflicting locks can not

be granted
 Rules 2,3 and 4 state the conditions when a
transaction may lock a given node in any of the lock
modes
 Rules 5 and 6 of the GML protocol enforce 2PL
rules to produce serializable schedules.
 For illustration of MGL protocol with the database
hierarchy shown on slide 34, consider the following
three conditions:
◦ T1 wants to update record r111 and record r211
◦ T2 wants to update all records on page p12
◦ T3 wants to read record r11j and the entire f2 file
42
Lock operations to illustrate a serializable schedule. 43
Multiple Granularity Locking (Cont.…)
 Lock granularity affects concurrency in the
following manner:
◦ The larger the lock granularity used, the more
concurrency is reduced.
◦ This means that row-level locking maximizes
concurrency because it leaves all but one row on
the page unlocked.
◦ On the other hand, system overhead is increased
because each locked row requires one lock.
◦ Page level locking (and table-level locking)
restricts the availability of data but decreases the
system overhead.
44