Chapter Four
CONCURRENCY CONTROL TECHNIQUES
Overview
❖Concurrency Control is the management procedure that is required for
controlling concurrent execution of the operations that take place on a
database.
❖But before knowing about concurrency control, we should know about
concurrent execution.
Slide 2
Overview
❖In a multi-user system, multiple users can access and use the same database at one
time, which is known as the concurrent execution of the database. It means that the
same database is executed simultaneously on a multi-user system by different users.
❖There occurs the requirement of using the database by multiple users for
performing different operations, in that case, concurrent execution of the database is
performed.
❖The simultaneous execution that is performed should be done in an interleaved
manner, and no operation should affect the other executing operations, thus
maintaining the consistency of the database.
Slide 3
Problems with Concurrent
Execution
1. Lost Update Problems (W - W Conflict)
❖When two different database transactions perform the read/write
operations on the same database items in an interleaved manner.
For example: Consider the below diagram where two transactions
TX and TY, are performed on the same account A where the balance of
account A is $300.
Slide 4
Cont…
2. Dirty Read Problems (W-R Conflict)
❖When one transaction updates an item of the database, and somehow
the transaction fails, and before the data gets rollback, the updated
database item is accessed by another transaction.
For example: Consider two transactions TX and TY in the below diagram
performing read/write operations on account A where the available
balance in account A is $300:
Slide 5
Cont…
3. Unrepeatable Read Problem (W-R Conflict)
❖Also known as Inconsistent Retrievals Problem that occurs when in a
transaction, two different values are read for the same database item.
❖For example: Consider two transactions, TX and TY, performing the
read/write operations on account A, having an available balance = $300.
Slide 6
Cont…
To eliminate above problems and to implement atomicity, consistency, and isolation
we need two additional operations (other than read and write), which are called Lock
and Unlock, which are applied on a data item.
▪ Lock (X): If a transaction T1 applies Lock on data item X, then X is locked and it
is not available to any other transaction.
▪ Unlock (X): T1 Unlocks X. X is available to other transactions.
Purpose of Concurrency Control
◦ To ensure Isolation property of concurrently executing transactions
◦ To preserve database consistency
◦ To resolve read-write and write-write conflicts
Slide 7
Methods of concurrency
control
▪ Lock-Based Protocols
▪ Timestamp-Based Protocols
▪ Multi-version method
▪ Validation-Based Protocol
▪ Multiple Granularities.
Slide 8
1. Lock-Based Protocols
❖Locking-procedure used to control concurrent access to data.
✓When one transaction accessing database, lock may deny access to other
transactions to prevent incorrect results.
✓Most widely used approach to ensure serializability of concurrent transactions.
✓There are several variations, but all share the same fundamental characteristic:-
transaction must claim a shared (read) or exclusive (write) lock on data item
before database read or write operation.
“Any transaction cannot read or write data until it acquires an appropriate lock on
it.”
Slide 9
Cont…
❖Data items of various sizes, ranging from the entire database down to a
field, may be locked. The size of the item determines the fineness, or
granularity, of the lock.
❖There are two types of lock:
▪ Shared lock: If a transaction has a shared lock on a data item, it can read the
item but not update it.
▪ Exclusive lock: If a transaction has an exclusive lock on a data item, it can
both read and update the item.
Slide 10
Cont…
❖Locks used in the following way:
❖Any transaction that needs to access data item must first lock item, requesting a
shared lock for read only access or an exclusive lock for both read and write
access.
❖If item is not already locked by another transaction, lock will be granted.
❖If item currently locked, DBMS determines whether request is compatible with
the existing lock.
❖If shared lock is requested on item that already has shared lock, request will be
granted; otherwise, transaction must wait until existing lock is released.
Slide 11
Cont…
❖ A transaction continues to hold lock until it explicitly releases it
either during execution or when it terminates.
❖ It only when exclusive lock has been released the effects of write
operation will be made visible to other transactions.
❖ Some systems permit transaction to issue shared lock on item and
then later to upgrade the lock to an exclusive lock.
Slide 12
Cont…
❖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
Slide 13
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(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
Slide 14
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)
Slide 16
Cont…
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,
◦ 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
◦ Lock compatibility matrix
Slide 17
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 Ptr to n
T1 X1 Read
Slide 18
Guaranteeing serializability by Two-Phase Locking
Protocol (2PL)
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).
Slide 19
Cont…
❖The following code performs the lock operation:
B: if LOCK (X) = 0 (*item is unlocked*)
then LOCK (X) 1 (*lock the item*)
else begin
wait (until lock (X) = 0) and
the lock manager wakes up the transaction);
goto B
end;
❖The following code performs the unlock operation:
LOCK (X) 0 (*unlock the item*)
if any transactions are waiting then
wake up one of the waiting the transactions
Slide 20
Cont…
❖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;
Slide 21
Cont…
❖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;
Slide 22
Cont…
For example: read write locks in transactions as described earlier by
itself does not guarantee serializability :
Slide 23
Cont…
Slide 24
Cont…
Slide 25
Cont…
Two-phase locking policy generates two locking algorithms
◦ Basic:
◦ Transaction locks data items incrementally. This may cause
deadlock
◦ Conservative:
◦ Prevents deadlock by locking all desired data items before
transaction begins execution.
Slide 26
Cont…
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 27
Cont…
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 28
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
Slide 29
Cont…
Two schemes that prevent deadlock 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 31
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.
Slide 32
2. Timestamp-Based
Protocols
◦ Time stamp is a unique identifier created by the DBMS to identify a transaction.
◦ Timestamp methods for concurrency control are quite different from locking
methods. No locks are involved, and therefore there can be no deadlock.
◦ Locking methods generally prevent conflicts by making transactions wait. With
timestamp methods, there is no waiting: transactions involved in conflict are
simply rolled back and restarted.
◦ Time stamping: a concurrency control protocol that orders transactions in such a
way that older transactions, transactions with smaller timestamps, get priority in
the event of conflict.
Slide 33
Cont…
▪The timestamp of a data item can be the following two types:
▪ WTS(Q) or W-timestamp (Q): this means the latest time when the
data item Q has been written into.
▪ RTS(Q) or R-timestamp(Q): this means the last time when the data
item Q has been read from.
▪This two timestamp are updated each time a successful read/write
operation is performed on the data item Q.
Slide 34
Cont…
For transaction T with timestamp TS(T) timestamp ordering protocol
works as follows.
(1) Transaction T issues read(x)
A. Transaction T asks to read item (x) that has already been
updated by a younger transaction TS (T) <
write_timestamp(x).
This means earlier transaction is trying to read value of an item
that has been updated by later transaction.
In this situation, transaction T must be aborted and restarted with
a new (later) timestamp.
Slide 35
Cont…
B. Otherwise, TS(T) ≥ write_timestamp(x), and the read operation can
proceed. We set read_timestamp(x)= max(TS(T), read_timestamp(x)).
(2) Transaction T issues a write(x)
A. Transaction T asks to write item (x) whose value has already been
read by a younger transaction TS(T) < read_timestamp(x).
This means later transaction is already using current value of item and it
would be error to update it now.
This occurs when transaction is late in doing write and younger
transaction has already read old value or written a new one.
Slide 36
Cont…
B. Transaction T asks to write an item (x) whose value has already been
written by a younger transaction, that is TS(T) < write_timestamp(x).
This means that transaction T is attempting to write an obsolete/outdated
value of data item x. Transaction T should be rolled back and restarted
using a later timestamp.
C. Otherwise, the write operation can proceed.
We set write_timestamp(x) = TS(T).
This scheme called basic timestamp ordering.
Slide 37
Example one:
Slide 38
Solution:
At step 1: the operation read(b) executed, as:
◦ TS(T1) < WTS(b) i.e. 200 < 0 does not follows and
◦ RST(b) is set to max(RTS(b), TS(T1)) i.e. RST(b) =200
At step 2 and 3 the same:...............
At step 4: the operation write(b) executed, as
◦ TS(T1) < RTS(b) or TS(T1) <WTS(B) i.e. 200<200 or 200<0 does not follow. WTS(b) is set to
TS(T1) i.e. WTS(b) = 200
At step 5 the operation write(a) executed same as step 4:
At step 6 T3 tries to write(a) and the read value of a i.e. WTS(a)=200. but TS(T3)<WT(a), i.e.
175<200,T3 need not to be aborted.
Slide 39
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.
Slide 40
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.
Slide 41
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)
Slide 42
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).
Slide 43
4. Validation (Optimistic) Concurrency Control Schemes
In some environments, conflicts between transactions are rare so additional processing required by locking
or time-stamping protocols is unnecessary for many of the transactions.
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
Slide 44
Cont…
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)
2. Validation phase:
▪ Serializability is checked before transactions write their updates to the database.
✓ If the transaction Ti decides that it wants to commit, the DBMS checks whether the
transaction could possibly have conflicted with any other concurrently executing
transaction.
✓ While one transaction ,Ti, is being validated , no other transaction can be
allowed to commit
✓ This phase for Ti checks that, for each transaction Tj that is either
committed or is in its validation phase, one of the following conditions
Slide 45
Cont…
1. Tj completes its write phase before Ti starts its read phase.
2. Ti starts its write phase after Tj completes its write phase and the read set of Ti has no item in common with the
write set of Tj
3. Both the read_set and write_set of Ti have no items in common with the write_set of Tj, and Tj completes its read
phase before Ti completes its read phase.
▪ When validating Ti, the first condition is checked first for each transaction Tj, since (1) is the simplest condition to
check.
▪ If (1) is false then (2) is checked and if (2) is false then (3 ) is checked.
If none of these conditions holds, the validation fails and Ti is aborted.
iii. Write phase:
On a successful validation, transactions’ updates are applied to the database; otherwise, transactions are restarted.
Slide 46
Granularity of Data Items
Granularity: - The size of data items chosen as the unit of protection by
a concurrency control.
The size or granularity of the data item that can be locked in a single
operation has a significant effect on the overall performance of the
concurrency control algorithm.
Slide 47
Cont…
Multiple Granularity
Allow data items to be of various sizes and define a hierarchy of data granularities, where
the small granularities are nested within larger ones.
Can be represented graphically as a tree (but don't confuse with tree-locking protocol).
When a transaction locks a node in the tree explicitly, it implicitly locks all the node's
descendants in the same mode.
Granularity of locking
fine granularity (lower in tree): high concurrency, high locking overhead
Coarse granularity (higher in tree): low locking overhead, low concurrency.
Slide 48
Cont… The levels, starting from the coarsest
(top) level are
➢ database
➢ area
➢ file
➢ Record
➔When a transaction locks a node, in
either shared or exclusive mode, the
transaction also has implicitly locked
all the descendants of that node in the
same lock mode.
For example, if transaction Ti gets an explicit lock on file Fc in exclusive
mode, then it has an implicit lock in exclusive mode on all the records
belonging to that file.
Slide 49
Intention Lock Modes
In addition to S and X lock modes, there are three additional lock modes with multiple granularity:
Intention-shared (IS): indicates explicit locking at a lower level of the tree but only with shared locks.
Intention-exclusive (IX): indicates explicit locking at a lower level with exclusive or shared locks
Shared and intention-exclusive (SIX): the sub-tree rooted by that node is locked explicitly in shared
mode and explicit locking is being done at a lower level with exclusive-mode locks.
Intention locks allow a higher level node to be locked in S or X mode without having to check all
descendent nodes.
Slide 50
Compatibility Matrix
Requester
IS IX S SIX X
IS yes yes yes yes no
IX yes yes no no no
Holder S yes no yes no no
SIX yes no no no no
X no no no no no
5/6/2025 51
Multiple Granularity Locking Scheme
Transaction Ti can lock a node Q, using the following rules:
1. The lock compatibility matrix must be observed.
2. The root of the tree must be locked first, and may be locked in any mode.
3. A node Q can be locked by Ti in S or IS mode only if the parent of Q is currently
locked by Ti in either IX or IS mode.
4. A node Q can be locked by Ti in X, SIX, or IX mode only if the parent of Q is
currently locked by Ti in either IX or SIX mode.
5. Ti can lock a node only if it has not previously unlocked any node (that is, Ti is two-
phase).
6. Ti can unlock a node Q only if none of the children of Q are currently locked by Ti.
Slide 52
Example 2:
Slide 53
Solution
If transaction T1 reads record Ra2 in file Fa, then transaction T1 needs to lock the
database, area A1 and file Fa in IS mode. Finally, it needs to lock Ra2 in S mode.
If transaction T2 modifies record Ra3 in file Fa, then it can do so after locking the
database, area A1 and file Fa in IX mode. Finally, it needs to lock the Ra3 in X mode.
If transaction T3 reads all the records in file Fa, then transaction T3 needs to lock the
database, and area A in IS mode. At last, it needs to lock Fa in S mode.
If transaction T4 reads the entire database, then T4 needs to lock the database in S
mode
Slide 54
Thank you!!!!!!!!
Slide 55
