CHAPTER 4

CONCURRENCY CONTROL TECHNIQUES

Prepared By: Bekretsyon B. (MSc.)

Concurrency Control
Concurrency : the ability to execute more than one program or task
simultaneously.
◼ 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
◼ Purpose of Concurrency Control
◼ To ensure Isolation property of concurrently executing
transactions
◼ To preserve database consistency

◼ To resolve read-write and write-write conflicts

2
Concurrency Control
Concurrency Control in Database Management System is a
procedure of managing simultaneous operations without
conflicting with each other.

It ensures that Database transactions are performed concurrently

and accurately to produce correct results without violating data
integrity of the respective Database.

3
Concurrency Control Protocols
◼ Different concurrency control protocols offer different benefits
between the amount of concurrency they allow and the amount of
overhead that they impose. Following are the Concurrency Control
techniques in DBMS:

• Lock-Based Protocols

• Two Phase Locking Protocol

• Timestamp-Based Protocols

• Validation-Based Protocols

4
Concurrency Control (cont…)
1. Concurrency control using Locks protocol
Lock Based Protocols in DBMS is a mechanism in which a
transaction cannot Read or Write the data until it acquires an
appropriate lock.

Lock based protocols help to eliminate the concurrency problem in

DBMS for simultaneous transactions by locking or isolating a
particular transaction to a single user.

Slide 3 2
Concurrency Control (cont…)
1. Concurrency control using Locks protocol
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
◼ Ui (X): Transaction Ti releases (“unlocks”) its lock on
database element X

Slide 3 2
Concurrency Control (cont…)
Types of locks and system lock tables
◼ Binary locks

◼ Can have two states or values: locked and unlocked(0 or 1)

◼ Lock(x)=1 or Lock(X)=0
◼ If the value of the lock on X is 1, item X can not be accessed by
a database operation that request the item
◼ At most one transaction can hold the lock on a particular item.
Thus, no two transactions can access the same item
concurrently.

Slide 7
 Binary locks properties
◼ A transaction T must issue the operation lock_item(X)
before any read_item(X) or write_item(X) operations are
performed in T.
◼ A transaction T must issue the operation unlock_item(X)
after all read_item(X) and write_item(X) operations are
completed in T.
◼ A transaction T will not issue a lock_item(X) operation if it
already holds the lock on item X
◼ A transaction T will not issue an unlock_item(X) operation
unless it already holds the lock on item X.

8
Shared/Exclusive (or read /write) locks
◼ In shared/exclusive method, data items can be locked in
two modes :
◼ Shared mode: shared lock (X)

◼ More than one transaction can apply shared 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

Slide 9
Concurrency Control (cont…)
Lock conversion
◼ 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.
◼ 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)

Slide 10
Concurrency Control (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 to identify transaction that

lock the data item

Transaction ID Data item id lock mode Ptr to
T1 X1 Read

Slide 11
Serializability in DBMS
◼ Serializability is the concept in a transaction that helps to
identify which non-serial schedule is correct and will maintain
the database consistency. It relates to the isolation property of
transaction in the database.

◼ Serializability is the concurrency scheme where the execution of

concurrent transactions is equivalent to the transactions which
execute serially.

12
Serializability in DBMS
◼ Serializable Schedule

◼ A serial schedule is always a serializable schedule because any

transaction only starts its execution when another transaction
has already completed its execution. However, a non-serial
schedule of transactions needs to be checked for Serializability.

13
Serializability in DBMS
Serial Schedules Serializable Schedules

No concurrency is allowed. Concurrency is allowed.

Thus, all the transactions necessarily Thus, multiple transactions can
execute serially one after the other. execute concurrently.

Serializable schedules improve both

Serial schedules lead to less resource
resource utilization and CPU
utilization and CPU throughput.
throughput.

Serial Schedules are less efficient as Serializable Schedules are always

compared to serializable schedules. better than serial schedules.
(due to above reason) (due to above reason)

14
Concurrency Control (cont…)
Using binary or read write locks in transactions as described
earlier by itself does not guarantee serializability :
→Consider the following transactions based on shared/exclusive lock
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);

Slide 15
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);

Slide 16
Two Phase Locking Protocol
◼ Two Phase Locking Protocol also known as 2PL protocol is a method
of concurrency control in DBMS that ensures serializability by applying
a lock to the transaction data which blocks other transactions to access
the same data simultaneously.

◼ This locking protocol divides the execution phase of a transaction into

three different parts.

17
Two Phase Locking Protocol
• In the first phase, when the transaction begins to execute, it requires
permission for the locks it needs.

• The second part is where the transaction obtains all the locks. When a
transaction releases its first lock, the third phase starts.

• In this third phase, the transaction cannot demand any new locks.
Instead, it only releases the acquired locks.

18
Two Phase Locking Protocol
◼ A transaction is said to follow Two Phase Locking protocol if
Locking and Unlocking can be done in two phases.

1. Growing Phase: New locks on data items may be acquired but

none can be released.

2. Shrinking Phase: Existing locks may be released but no new

locks can be acquired.

19
Two Phase Locking Protocol example
T1 T2

0 LOCK_S(A)

1 LOCK_S(A)

2 LOCK_X(B)

4 UNLOCK_S(A)

5 LOCK_X(C)

6 UNLOCK_S(B)

7 UNLOCK_S(A)

8 UNLOCK_S(A)
20
Two Phase Locking Protocol
◼ The following way shows how unlocking and locking work with 2-
PL.
◼ Transaction T1:
• Growing phase: from step 0-2
• Shrinking phase: from step 4-6
• Lock point: at 2
◼ Transaction T2:
• Growing phase: from step 1-5
• Shrinking phase: from step 7-8
• Lock point: at 5

21
Database Concurrency Control
◼ Two-phase locking policy generates two locking algorithms
◼ (a) Basic

◼ (b) Conservative

◼ Basic:
◼ Transaction locks data items incrementally. This may cause

deadlock
◼ Conservative:
◼ Prevents deadlock by locking all desired data items before

transaction begins execution.

Slide 22
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)

Slide 23
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

Slide 24
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 waits and tries again to

lock all the items it needs
◼ This solution limits concurrency and generally not a

practical assumption

Slide 25
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
◼ 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)

Slide 26
Deadlock and Starvation (cont…)
◼ Deadlock prevention
◼ 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.

Slide 27
Deadlock and Starvation (cont…)
◼ Deadlock prevention
◼ two possible strategies for resolving conflicts between transactions
in a database system using the two-phase locking (2PL)
concurrency control mechanism.
◼ Wait-Die Example:
➢ Suppose T1 and T2 are two transactions that both need to access a
resource R. T1 acquires a shared lock on R, and then T2 attempts
to acquire an exclusive lock on R.
➢ If T1 is older than T2, T2 is blocked and waits for T1 to release its
shared lock.
➢ If T2 is older than T1, T1 is blocked, and T2 is allowed to acquire
the exclusive lock on R.

Slide 28
 Deadlock and Starvation (cont…)
◼ Deadlock prevention
◼ In the wait-die strategy, younger transactions wait for older

transactions to release their locks, while older transactions are

allowed to wait for younger transactions to release their locks.
Wound-Wait Example:
◼ Suppose T1 and T2 are two transactions that both need to access a
resource R. T1 acquires an exclusive lock on R, and then T2
attempts to acquire a shared lock on R.
◼ If T2 is older than T1, T1 releases its exclusive lock on R, and T2

acquires the shared lock.

◼ If T1 is older than T2, T2 is blocked, and waits for T1 to release its

exclusive lock.
◼ In the wound-wait strategy, younger transactions can "wound"

older transactions and force them to release their locks.

Slide 29
Deadlock and Starvation (cont…)
◼ Starvation
◼ Starvation occurs when a particular transaction consistently
waits or restarted and never gets a chance to proceed further
◼ In Wound-Wait scheme, a younger transaction may always
be wounded (aborted) by a long running older transaction
which may create starvation

Slide 30
Timestamp based Protocol
◼ Timestamp based Protocol in DBMS is an algorithm which
uses the System Time or Logical Counter as a timestamp to
serialize the execution of concurrent transactions.

◼ The Timestamp-based protocol ensures that every conflicting

read and write operations are executed in a timestamp order.

◼ The Timestamp Ordering Protocol is used to order the

transactions based on their Timestamps. The order of transaction
is nothing but the ascending order of the transaction creation.

31
Timestamp based Protocol

◼ The older transaction is always given priority in this method. It uses

system time to determine the time stamp of the transaction. This is
the most commonly used concurrency protocol.

◼ Timestamp-based protocols manage conflicts as soon as an

operation is created.

◼ Let's assume there are two transactions T1 and T2. Suppose the
transaction T1 has entered the system at 007 times and transaction
T2 has entered the system at 009 times. T1 has the higher priority,
so it executes first as it is entered the system first.

32
2. Concurrency control based on Timestamp ordering
◼ Basic Timestamp ordering protocol works as follows:
◼ 1. Check the following condition whenever a transaction
Ti issues a Read (X) operation:
o If W_TS(X) >TS(Ti) then the operation is rejected.
o If W_TS(X) <= TS(Ti) then the operation is executed.
o Timestamps of all the data items are updated.

Slide 33
Timestamp ordering (cont…)
2. Basic Timestamp Ordering (TO):
◼ Whenever some transaction T tries to issue a read_item(X) or a
write_item(X) operation, the basic algorithm compares the
timestamp of T with read_TS(X) and write_TS(X)
2. Check the following condition whenever a transaction Ti issues
a Write(X) operation:
If TS(Ti) < R_TS(X) then the operation is rejected.
If TS(Ti) < W_TS(X) then the operation is rejected and Ti is rolled
back otherwise the operation is executed.
Where, TS(TI) denotes the timestamp of the transaction Ti.
R_TS(X) denotes the Read time-stamp of data-item X.
W_TS(X) denotes the Write time-stamp of data-item X.
Slide 34
Validation Based Protocol
◼ Validation based Protocol in DBMS also known as
Optimistic Concurrency Control Technique is a method
to avoid concurrency in transactions.
◼ In this protocol, the local copies of the transaction data
are updated rather than the data itself, which results in
less interference while execution of the transaction.
◼ In this technique, serializability is checked only at the
time of commit and transactions are aborted in case of
non-serializable schedules

35
Validation (Optimistic) Concurrency Control
Schemes
◼ The Validation based Protocol is performed in the
following 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)

Slide 36
Validation Based Protocol
◼ Validation Phase
◼ In Validation Phase, the data is checked to ensure that there is
no violation of serializability while applying the transaction
updates to the database.
◼ Write Phase
◼ In the Write Phase, the updates are applied to the database if the
validation is successful, else; the updates are not applied, and
the transaction is rolled back.

37
Validation Based Protocol
◼ Here each phase has the following different timestamps:

◼ Start(Ti): It contains the time when Ti started its execution.

◼ Validation (Ti): It contains the time when Ti finishes its read phase
and starts its validation phase.

◼ Finish(Ti): It contains the time when Ti finishes its write phase.

38