1
BCSE302 – Database
Systems
Module 6 – Concurrency control in
Transaction Processing
Dr. K.P. Vijayakumar,
VIT Chennai
Dr. K.P. Vijayakumar, VIT Chennai
Module 6 2
Module: 6 Concurrency control in Transaction Processing
Concurrent Transactions – Lost Update Problem -
Concurrency Control Techniques: Time Stamp Based
Protocols, Thomas Write Rule, Lock Based Protocols, Lock
Compatibility Matrix, - Two-Phase Locking Protocol - Lock
Conversions - Graph Based Protocols for Concurrency Control
- Tree Protocol for Concurrency Control – Deadlocks Based on
Locks in Transactions – Deadlock Handling Techniques –
Transaction Deadlock Detection Techniques – Transaction
Deadlock Prevention Techniques – Multi-Granularity Locking
for avoiding Transaction Deadlocks
Dr. K.P. Vijayakumar, VIT Chennai
3
Concurrency Control Technique
A database must provide a mechanism that will
ensure that all possible schedules are:
either conflict or view serializable, and
recoverable and preferably cascadeless
A policy in which only one transaction can execute
at a time generates serial schedules, but provides a
poor degree of concurrency
Goal – to develop concurrency control protocols
that will assure serializability.
Source: Database System Concepts by Abraham Silberschatz, Henry F.Korth and
S.Sudarshan, Tata Mc Graw Hill, 2011 Dr. K.P. Vijayakumar, VIT Chennai
Initial value of A=1000
4
T1 T2
Concurrent Transactions
Read(A) Lost update Problem
A=A+50 Read(A) 1000 Transaction T1 updates the data item A with 1050
Transaction T2 overwrites the data item A with 1100
Write(A) 1050
A=A+100 This situation leads to loss of change of A done by
Write(A) 1100 Transaction T1
That is, write operation performed by T1 is lost.
DB DB
A =1050 A =1100
Source: Database System Concepts by Abraham Silberschatz, Henry F.Korth and
S.Sudarshan, Tata Mc Graw Hill, 2011 Dr. K.P. Vijayakumar, VIT Chennai
5
Concurrent Transactions
Initial value of A=1000
Dirty Read Problem
Transaction T2 updates the data item A which was
produced by T1 and completes successfully
T1 T2
But, transaction T1 becomes failure
Read(A)
A=A+50
Write(A) 1050
Read(A)
-- Failure --- A=A+100
Write(A) 1150
Read(B) --Commit---
Source: Database System Concepts by Abraham Silberschatz, Henry F.Korth and
S.Sudarshan, Tata Mc Graw Hill, 2011 Dr. K.P. Vijayakumar, VIT Chennai
A -> 1000 Lock based Protocol 6
T1 T2 The data items are accessed in a mutually exclusive
Read(A) 1000 manner in order to guarantee
A=A+50 Read(A) 1000
Write(A) 1050 A=A+100 i.e, When a data item is accessed by a Transaction then
Write(A) 1100 no other transaction modify the same data item
To satisfy this condition, a transaction is allowed to
access the data item if it holds a Lock on that data item
A -> 1100 (Wrong) T1 T2
A should be Read(A)
1150 A=A+50 Read(A)
Write(A) A=A+100
Write(A)
Dr. K.P. Vijayakumar, VIT Chennai
Lock-Based Protocols 7
A lock is a mechanism to control concurrent access to a data item
Data items can be locked in two modes :
1. Exclusive (X) mode. Data item can be both read as well as
written. X-lock is requested using LOCK-X instruction.
2. Shared (S) mode. Data item can only be read. S-lock is
requested using LOCK-S instruction.
Lock requests are made to concurrency-control manager.
Transaction can proceed only after request is granted.
Dr. K.P. Vijayakumar, VIT Chennai
Lock-Based Protocols 8
Lock-compatibility matrix
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,
but if any transaction holds an exclusive on the item no other
transaction may hold any lock on the item.
If a lock cannot be granted, the requesting transaction is made to
wait till all incompatible locks held by other transactions have
been released. The lock is then granted.
Image Source: Database System Concepts by Abraham Silberschatz, Henry F.Korth and
S.Sudarshan, Tata Mc Graw Hill, 2011 Dr. K.P. Vijayakumar, VIT Chennai
T1 : read(A);
A := A − 50; Lock-Based Protocols 9
write(A);
read(B); T2: read(A)
B := B + 50; read(B)
write(B); display(A+B)
T1 with Lock Example of a transaction performing locking: T2 with Lock
T1 : lock-X(A); T2: lock-S(A);
read(A); read (A);
A := A − 50;
unlock(A);
write(A);
unlock(A); lock-S(B);
lock-X(B); read (B);
read(B); unlock(B);
B := B + 50; display(A+B)
write(B);
unlock(B).
Dr. K.P. Vijayakumar, VIT Chennai
Lock-Based Protocols 10
T1 : lock-X(A); Example of a transaction performing locking:
read(A); T2: lock-S(A);
A := A − 50; read (A);
write(A); unlock(A);
unlock(A);
lock-X(B); lock-S(B);
read(B); read (B);
B := B + 50; unlock(B);
write(B); display(A+B)
unlock(B). Locking as above is not sufficient to guarantee serializability — if
A and B get updated in-between the read of A and B, the
displayed sum would be wrong.
A locking protocol is a set of rules followed by all transactions
while requesting and releasing locks. Locking protocols restrict
the set of possible schedules.
Dr. K.P. Vijayakumar, VIT Chennai
T1 T2
Pitfalls of Lock-Based
11
Lock –X(A)
Read(A)
Write(A)
Protocols
Lock-X(B)
Read(B) The potential for deadlock exists in most locking protocols.
Write(B)
Lock-X(B) Deadlock Occur when 2 transactions exist in the following mode:
Read(B)
Write(B)
T1 = access data item A and B
Lock –X(A) T2 = Access data items B and A
Read(A)
Write(A)
Unlock-X(A) If T1 does not unlock A, T2 cannot begin
Unlock-X(B)
Unlock-X(B) If T2 does not unlock B, T1 cannot continue
Unlock-X(A)
T1 Request for B
T1 & T2 wait indefinitely for each other to unlock data
Such a situation is called a deadlock.
Holds B
To handle a deadlock one of T1 or T2 must be rolled back
Holds A
and its locks released.
T1 T2
Deadlocks are only possible if a transaction wants an Exclusive
Lock (No Deadlocks on Shared Locks)
T2 Request for A Dr. K.P. Vijayakumar, VIT Chennai
Pitfalls of Lock-Based
12
Protocols
The potential for deadlock exists in most locking protocols.
Starvation is also possible if concurrency control manager is
badly designed. For example:
Starvation
A transaction may be waiting for an X-lock on an item, while a
sequence of other transactions request and are granted an S-lock on
the same item.
Therefore, this transaction never get a chance to progress and it is
referred as Starved.
T1 T2 T3 T4 T….
Lock-s(A) Lock-x(A) Lock-s(A) Lock-s(A) Lock-s(A)
Granted wait Granted Granted Granted…..
Dr. K.P. Vijayakumar, VIT Chennai
The Two-Phase Locking
13
Protocol
Growing Phase
This protocol ensures conflict-serializable schedules.
T1 T2
Phase 1: Growing Phase
Lock –X(A)
Read(A) transaction may obtain lock, but may not release locks
Write(A)
Lock-X(B) Phase 2: Shrinking Phase
Read(B)
Write(B) transaction may release locks, but may not obtain any new
Lock-X(B) locks
Read(B)
Write(B)
Lock –X(A)
The protocol assures serializability. It can be proved that the
Read(A) transactions can be serialized in the order of their lock points
Write(A)
Unlock-X(A) (i.e. the point where a transaction acquired its final lock).
Unlock-X(B)
Unlock-X(B)
Unlock-X(A)
Shrinking Phase
Dr. K.P. Vijayakumar, VIT Chennai
The Two-Phase Locking
14
Protocol
Issues in Two Phase locking Protocol
Two-phase locking does not ensure freedom from
deadlocks
Cascading roll-back is possible under two-phase
locking.
Strict two-phase locking - a transaction must hold
all its exclusive locks till it commits/aborts.
Rigorous two-phase locking is even stricter: here all
locks are held till commit/abort. In this protocol
transactions can be serialized in the order in which
they commit.
Dr. K.P. Vijayakumar, VIT Chennai
15
Lock Conversion
Upgrade
conversion from shared to exclusive lock or mode
Upgrading can take place in only the growing phase
Downgrade
conversion from exclusive to shared lock or mode
downgrading can take place in only the shrinking
phase
Dr. K.P. Vijayakumar, VIT Chennai
16
Lock Conversion
Upgrade and Downgrade
Dr. K.P. Vijayakumar, VIT Chennai
17
Timestamp-Based Protocols
T1 - TS(T1) 10
Time Stamps
T1 T2
Each transaction is issued a timestamp when it
Read(A)
A=A+50 Read(A) enters the system. If an old transaction Ti has time-
Write(A) A=A+100
Write(A)
stamp TS(Ti), a new transaction Tj is assigned time-
stamp TS(Tj) such that TS(Ti) <TS(Tj).
The protocol manages concurrent execution such
T2 TS(T2)
-
that the time-stamps determine the
TS(T1) < TS(T2) serializability order.
11
10< 11
T1 is Older
T2 is Younger Dr. K.P. Vijayakumar, VIT Chennai
18
Timestamp-Based Protocols
T1 - TS(T1) 10
TimeStamp Ordering Protocol (TO)
TS T1 T2
In order to assure such behavior, the protocol
12 Read(A)
13 A=A+50 maintains for each data Q two timestamp values:
14 Write(A) Read(A)
15 A=A+100 W-timestamp(Q) is the largest time-stamp of any
16 Write(A) transaction that executed write(Q) successfully.
R-timestamp(Q) is the largest time-stamp of any
T2 - TS(T2)
transaction that executed read(Q) successfully.
TS(T1) < TS(T2)
11
10< 11
R-timestamp(A) - 12
Transaction T1
T1 is Older
W-timestamp(A) - 14
T2 is Younger Dr. K.P. Vijayakumar, VIT Chennai
5 10
19
TS T1 T2 Timestamp-Based Protocols
12 Read(A)
13 A=A+50 Suppose that transaction Ti issues write(Q).
14 Write(A) Read(A) 1. If TS(Ti) < W-timestamp(Q), then Ti is attempting to
15 A=A+100
16 Write(A)
write an obsolete value of Q.
Hence, this write operation is rejected, and Ti
TS(T1) < W-timestamp(A) is rolled back.
5<0
write operation is allowed 2. Otherwise, the write operation is executed, and
W-timestamp(Q) is set to TS(Ti).
TS T1 T2
12 Read(A)
13 A=A+50 If TS(Ti) < WTS(Q)
14 Write(A) Read(A) Rollback Ti
15 A=A+100 TS(T2) < W-timestamp(A) Else
16 Write(A)
10 < 14 Execute Write(Q)
Rollback T2 Set WTS(Q)
Dr. K.P. Vijayakumar, VIT Chennai
5 10 11
20
TS T0 T1 T2
Timestamp-Based Protocols
6 Read(A)
7 ..
The timestamp ordering protocol ensures that any
8 Write(A) conflicting read and write operations are executed in
… timestamp order.
12 Read(A)
13 A=A+50 Read(A) Suppose a transaction Ti issues a read(Q)
14 Write(A) A=A+100 1. If TS(Ti) < W-timestamp(Q), then Ti needs to read a
15 Write(A)
value of Q that was already overwritten.
TS T0 T1 T2 Hence, the read operation is rejected, and Ti is
6 Read(A) rolled back.
7 .. 2. Otherwise, the read operation is executed, and R-
8 Write(A)
… timestamp(Q) is set to max(R-timestamp(Q), TS(Ti)).
12 Read(A)
13 A=A+50 Read(A)
14 Write(A) A=A+100
15 Write(A)
Dr. K.P. Vijayakumar, VIT Chennai
T1 T2
21
Lock –X(A)
Read(A)
Dead Lock Handling
Write(A)
Lock-X(B) A system is in a deadlock state if there exists a set
Read(B) of transactions such that every transaction in the
Write(B)
Lock-X(B)
set is waiting for another transaction in the set
Read(B)
Write(B)
Lock –X(A) T1 Request for B
Read(A)
Write(A)
Unlock-X(A) Holds A Holds B
Unlock-X(B) T1 T2
Unlock-X(B)
Unlock-X(A)
Solution T2 Request for A
T1 or T2 must be rolled back and
its locks released
Dr. K.P. Vijayakumar, VIT Chennai
22
Dead Lock Handling
Two methods to deal dead lock situation
Deadlock prevention
ensure that the system will never enter a
deadlock state.
Deadlock detection and deadlock
recovery
Allows the system to enter a deadlock state,
and then try to recover by using a deadlock
detection and deadlock recovery scheme
Dr. K.P. Vijayakumar, VIT Chennai
23
T1 T2 Dead Lock Handling
Lock –X(A)
Read(A) Deadlock Prevention
Write(A)
Lock-X(B) Two approaches
Read(B)
Write(B)
wait–die Scheme
Lock-X(B) It is a non preemptive technique
Read(B) wound–wait Scheme
Write(B)
Lock –X(A) Preemptive technique
Read(A)
Write(A)
Unlock-X(A)
Unlock-X(B)
Unlock-X(B)
Unlock-X(A)
Dr. K.P. Vijayakumar, VIT Chennai
1 2
24
T1 - TS(T1) T2 - TS(T2) Dead Lock Handling
T1 T2
Lock –X(A)
Deadlock Prevention
Read(A)
Write(A) Lock-X(B)
Wait – Die Scheme
Read(B) It is a non preemptive technique
Write(B)
Lock-X(B)
Time Stamp is provided to the Transactions
Read(B) When T1 request data item currently held by T2
Write(B) Lock –X(A)
Read(A)
Write(A) If TS(T1) < TS(T2) 1<2
Unlock-X(A) T1 waits until T2 Completes T1 waits
Unlock-X(B) Unlock-X(B) Otherwise
Unlock-X(A)
T1 is rolled back or died
Dr. K.P. Vijayakumar, VIT Chennai
25
Dead Lock Handling
Deadlock Prevention
Wait – Die Scheme
Example : Transactions T14, T15, and T16 have time
stamps 5, 10, and 15, respectively.
If T14 requests a data item held by T15, then T14 will
wait. That is,
If T16 requests a data item held by T15, then T16 will
be rolled back.
Dr. K.P. Vijayakumar, VIT Chennai
26
T1 - TS(T1) T2 - TS(T2) Dead Lock Handling
T1 T2
Lock –X(A)
Deadlock Prevention
Read(A)
Write(A) Lock-X(B)
Wound – Wait Scheme
Read(B) It is a preemptive technique
Write(B)
Lock-X(B)
Time Stamp is provided to the Transactions
Read(B) When T1 request data item currently held by T2
Write(B) Lock –X(A)
Read(A)
Write(A) If TS(T1) > TS(T2)
Unlock-X(A) T1 waits until T2 Completes
Unlock-X(B) Unlock-X(B) Otherwise
Unlock-X(A)
T2 is rolled back or killed
Dr. K.P. Vijayakumar, VIT Chennai
27
Dead Lock Handling
Deadlock Prevention
Wound – Wait Scheme
Example :Transactions T14, T15, and T16 have time
stamps 5, 10, and 15, respectively.
if T14 requests a data item held by T15, then the data
item will be preempted from T15, and T15 will be
rolled back.
If T16 requests a data item held by T15, then T16 will
wait.
Dr. K.P. Vijayakumar, VIT Chennai
28
Dead Lock Handling
Deadlock detection and Recovery
Deadlock Detection
a directed graph called a wait-for graph.
Transaction T17 is waiting for transactions T18 and
T19.
Transaction T19 is waiting for transaction T18.
Transaction T18 is waiting for transaction T20.
There is no presence of Cycle
Dr. K.P. Vijayakumar, VIT Chennai
29
Dead Lock Handling
Deadlock detection and Recovery
Deadlock Detection
a directed graph called a wait-for graph.
Transaction T17 is waiting for transactions T18 and
T19.
Transaction T18 is waiting for transaction T20,
Transaction T20 is waiting for transaction T19 and
Presence of Cycle Transaction T19 is waiting for transaction T18 (forms
a cycle)
Dr. K.P. Vijayakumar, VIT Chennai
30
Dead Lock Handling
Deadlock Recovery
Selection of a victim - Cost factor
How long the transaction has computed?
How much longer the transaction will compute before it completes its designated task.?
How many data items the transaction has used.?
How many more data items the transaction needs for it to complete?
How many transactions will be involved in the rollback?
Rollback
Total rollback
Partial rollback
Starvation
picked as a victim only a (small) finite number of times Dr. K.P. Vijayakumar, VIT Chennai
31
Dr. K.P. Vijayakumar, VIT Chennai
