Concurrency Control Techniques

O verview

●
Introduction
●
Locking Techniques
 Introduction

●
Need for Concurrency Control
● When operations of different transactions are executed concurrently by
interleaving of operations, several problems are associated:

• Lost Update problem

• Dirty Read (Temporary Update) problem

• Incorrect Summary problem

 Introduction

●
Purpose of Concurrency Control
– To enforce Isolation (through mutual exclusion)
a m on g conflicting transactions.

– To preserve database consistency through

consistency preserving execution of transactions.

– To resolve read-write and write-write conflicts.

 Introduction

● To overcome various problems associated with concurrency, several

techniques were adopted to control it:

• Locking Techniques for Concurrency Control

• Concurrency Control Based on Timestamp Ordering

• Multiversion Concurrency Control Techniques

• Validation Techniques for Concurrency Control

 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.
 S hared / Exclus iv e Lock
●
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.

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

Read Write

Read
Y N

Write
N N
 Lock Manager
●
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.

Transaction ID Data item id lock mode Ptr to next data item

T1 X1 Read Next
 Binary Lock
●
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.
Binary Lock
 S hared / Exclus iv e Lock

●
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;
 S hared / Exclus iv e Lock

● The following code performs the write 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;
 S hared / Exclus iv e Lock
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;
 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 : 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.

• Locks are acquired, not released

● Unlocking (Shrinking) Phase: A transaction unlocks its locked data
items one at a time.

• Locks are released, new locks can not be acquired

● 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.
Two-Phase Locking : Algorithm
Two-Phase Locking : Algorithm

Transactions T1 and T2 that do not obey 2PL

 Two-Phase Locking : Algorithm
T1 and T2 follow two-phase policy but they are subject to deadlock, which
must be dealt with.

T’1 T’2
read_lock (Y); read_lock (X);
read_item (Y); read_item (X);
write_lock (X); write_lock (Y);
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);
 Two-Phase Locking : Algorithm

● Two-phase policy generates two locking algorithms (a) Basic and (b)
Conservative.

● Basic 2PL: Transaction locks data items incrementally. This may cause
deadlock which is dealt with.

● Conservative 2PL: Prevents deadlock by locking all desired data items

before transaction begins execution. (deadlock-free protocol)

● Strict 2PL: 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.
 Dealing with Deadlock

Deadlock
T’1 T’2
read_lock (Y); T1 and T2 did follow two-phase
read_item (Y); policy but they are deadlock
read_lock (X);
read_item (Y);
write_lock (X);
(waits for X) write_lock (Y);
(waits for Y)

D e a d l o c k (T’1 a n d T’2)
 Dealing with Deadlock
●
Deadlock Prevention Protocols
●
Deadlock Detection
●
Starvation
 Dealing with Deadlock
●
Deadlock Prevention Protocols
● Lock all data items before transaction begins → Conservative 2PL – is a
deadlock prevention protocol but further limits concurrency.

●
Not generally used because of unrealistic assumptions or overhead.
●
What to do with a transaction involved in a deadlock?

• Should it be blocked and made to wait ?

• Should it be aborted ?

• Should the transaction preempt and abort another transaction ?

● Transaction timestamp – TS(T) – a unique identifier assigned to each
transaction.
 Dealing with Deadlock
●
Deadlock Prevention Protocols:
● If Ti tries to lock an item X; but X is locked by Tj, then
●
Wait-die
If TS(Ti) < TS (Tj), then (Ti older than Tj)
Ti is allowed to wait;
Else
abort Ti and restart it later with the same timestamp;
●
Wound-wait
If TS(Ti) < TS (Tj), then (Ti older than Tj)
abort Tj and restart it later with the same timestamp;
Else
Ti is allowed to wait;

●
Issue: some transactions to be aborted and restarted needlessly
 Dealing with Deadlock
●
Deadlock Detection
●
In this approach, deadlocks are allowed to happen.
●
Suitable for transactions that are short and locks only a few items.
● The scheduler maintains a wait-for-graph for detecting cycle. If a cycle
exists, then one transaction involved in the cycle is selected (victim) and
rolled-back.

● A wait-for-graph is created using the lock table. As soon as a transaction

is blocked, it is added to the graph.

● One of the transaction of the cycle is selected and rolled back – select
transactions that have not made many changes.
Dealing with Deadlock

Wait-for graph to detect deadlock

 Dealing with Deadlock
●
Starvation
●
Starvation occurs when a particular transaction consistently waits or
restarted and never gets a chance to proceed further.
● In a deadlock resolution it is possible that the same transaction may
consistently be selected as victim and rolled-back.

●
This limitation is inherent in all priority based scheduling mechanisms.
●
Solution: using a first-come-first-served queue
 References

● Fundamentals of Database Systems, Elmasri and Navathe, 5th

Edition