Chapter Four

Concurrency Control Techniques

Outline:
 Locking Techniques for Concurrency Control
 Concurrency Control Based ON Timestamp Ordering
 Multi-version Concurrency Control Techniques
 Validation (Optimistic) Concurrency Control Techniques
 Granularity of Data Items and Multiple Granularity Locking
 Using Locks for Concurrency Control in Indexes

1 5/21/2024
Introduction
 Concurrency Control is the process of managing simultaneous operations on the
database without having them interfere with one another. Prevents interference
when two or more users are accessing database simultaneously and at least one is
updating data.
 Although two transactions may be correct in themselves, interleaving of operations
may produce an incorrect result.
 Three basic concurrency control techniques:
1. Locking methods
2. Time stamping
3. Optimistic
• Locking and Time stamping are pessimistic approaches since they delay
transactions.
• Both Locking and Time stamping are conservative approaches: delay transactions in
2 case they conflict with other transactions. 5/21/2024
Locking Techniques for Concurrency Control
 The optimistic approach allows us to proceed and check conflicts at the end.
 Optimistic methods assume conflict is rare and only check for conflicts at
commit.

Locking Method
 The locking method is a mechanism for preventing simultaneous access on a
shared resource for a critical operation
 A LOCK is a mechanism for enforcing limits on access to a resource in an
environment where there are many threads of execution. Locks are one way
of enforcing concurrency control policies. Transaction uses locks to deny
access to other transactions and so prevent incorrect updates.
 Lock prevents another transaction from modifying item or even reading it, in
the case of a write lock.
3 5/21/2024
 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.

Types of a Lock
[Link] lock: A Read operation does not change the value of a data item. Hence
a data item can be read by two different transactions simultaneously under share
lock mode. So only to read a data item T1 will do: Share lock (X), then Read (X),
and finally Unlock (X).
[Link] lock: A write operation changes the value of the data item. Hence
two write operations from two different transactions or a write from T1 and a read
from T2 are not allowed. A data item can be modified only under Exclusive lock.
To modify a data item T1 will do: Exclusive lock (X), then Write (X) and finally
Unlock (X).
4 5/21/2024
 When these locks are applied, then a transaction must behave in a special way. This
special behavior of a transaction is referred to as well-formed.
Well-formed: A transaction is well- formed if it does not lock a locked data item and it
does not try to unlock an unlocked data item.
Locking - Basic Rules
 If transaction has a shared lock on an item, it can read but not update the item.
 If a transaction has an exclusive lock on an item, it can both read and update the
item.
 Reads cannot conflict, so more than one transaction can hold shared locks
simultaneously on same item.
 Exclusive lock gives transaction exclusive access to that item.
 Some systems allow transaction to upgrade a shared lock to an exclusive lock, or
vice-versa.

5 5/21/2024
Examples: T1 and T2 are two transactions. They are executed under locking as
follows. T1 locks A in exclusive mode. When T2 wants to lock A, it finds it locked by
T1 so T2 waits for Unlock on A by T1. When A is released then T2 locks A and begins
execution.

Suppose a lock on a data item is applied, the data item is processed and it is unlocked
immediately after reading/writing is completed as follows.
Initial values of A = 10 and B = 20.

6 5/21/2024
 Serial Execution of T1 and then T2
Concurrent Execution of T1 and T2
T1 T2
Lock (A) T1 T2
read (A) {A = 10} Lock (A)
read (A) {A = 10}
A := A + 100 A := A + 100
write (A) (A = 110}
write (A) (A = 110}
Unlock (A) Unlock (A)
Lock (B) Lock (B)
read (B) {B = 20} read (B) {B = 20}
B := B * 5
B := B + 10 write (B) {B = 100}
write (B) {B =30} Unlock (B)
Unlock (B) Lock (B)
Lock (B) read (B) {B = 100}
read (B) {B = 30} B := B + 10
B := B * 5 write (B) {B = 110}
write (B) {B = 150} Unlock (B)
Unlock (B) Lock (A)
Lock (A) Read (A) {A = 110}
Read (A) {A = 110} A := A + 20
A := A + 20 Write (A) {A = 130}
Write (A) {A = 130} Unlock (A)
Unlock (A) Final Result: A=130 B=110
Final Result: A=130 B=150 5/21/2024
7
 The final result of the two transactions using the two types of transaction execution (serial
and concurrent) is not the same. This indicates that the above method of locking and
unlocking is not correct. This is because although such kind of locking and unlocking
data items increases the concurrency of execution it violates the isolation and atomicity of
transactions. Immediate unlocking is not trustworthy. Thus, to preserve consistency we
have to use another approach to locking, two-phase locking scheme.
Two-Phase Locking (2PL)
 A transaction follows 2PL protocol if all locking operations precede the first unlock
operation in the transaction.
 The 2PL protocol demands locking and unlocking of a transaction to have two phases.
• Growing phase - acquires all locks but cannot release any locks. Upgrading of shared
lock to exclusive locks is done here if allowed.
• Shrinking phase - releases locks but cannot acquire any new locks. Down grading of
exclusive locks to shared lock is done here if allowed.
8 5/21/2024
Hence the 2PL protocol allows avoiding the three problems of concurrent execution.
Locking methods: problems
 Deadlock: A deadlock that may result when two (or more) transactions are each waiting
for locks held by the other to be released.
Deadlock - possible solutions
Only one way to break deadlock: abort one or more of the transactions in the deadlock.
Deadlock should be transparent to user, so DBMS should restart transaction(s).
Two general techniques for handling deadlock:
 Deadlock prevention.
 Deadlock detection and recovery.
 Timeout
The deadlock detection could be done using the technique of TIMEOUT. Every transaction
will be given a time to wait in case of deadlock. If a transaction waits for the predefined period
of time in idle mode, the DBMS will assume that deadlock occurred and it will abort and
restart the transaction.
9 5/21/2024
WFG (the Wait For Graph)
 Nodes represent transactions
 A directed edge Ti Tj is drawn if Ti is waiting to lock an item already locked by Tj.
 Dead lock exists if there is a cycle in the graph.
If every transaction in a schedule follows 2PL, schedule is serializable. However, problems
can occur with interpretation when locks can be released.

 Suppose Ti aborts, but Tj has read a data item written by Ti

 Then Tj must abort; if Tj had been allowed to commit earlier, the schedule is not recoverable.
 Further, any transaction that has read a data item written by Tj must also abort
This can lead to cascading rollback…
In order to avoid such problems, it is recommended to leave the release of locks until the
end of the transaction.
A schedule is recoverable if for each pair of transactions Ti and Tj , if Tj reads an item
previously written by Ti, then the commit operation of Ti must precede that of Tj.

10 5/21/2024
Time-stamping Method
Timestamp: a unique identifier created by DBMS that indicates relative starting time of a
transaction.
Can be generated by:
 using system clock at the time transaction started, or
 Incrementing a logical counter every time a new transaction starts.
Time-stamping  a concurrency control protocol that orders transactions in such a way that
older transactions, transactions with smaller time stamps, get priority in the event of conflict.
 Transactions ordered globally base do their timestamp so that older transactions,
transactions with earlier timestamps, get priority in the event of conflict.
 Conflict is resolved by rolling back and restarting transaction.
 Since there is no need to use lock there will be No Deadlock.
 In timestamp ordering, the schedule is equivalent to the particular serial order that
corresponds to the order of the transaction timestamps.
 To implement this scheme, every transaction will be given a timestamp which is a unique
identifier of a transaction.
11 5/21/2024
If Ti came to processing prior to Tj then TS of Tj will be larger than TS of Ti.
Again each data item will have a timestamp for Read and Write.
 WTS(A) which denotes the largest timestamp of any transaction that successfully executed
Write(A)
 RTS(A) which denotes the largest timestamp of any transaction that successfully executed
Read(A)

These timestamps are updated whenever a new Read (A) or Write (A) instruction is executed.
 Read/write proceeds only if last update on that data item was carried out by an older
transaction. Otherwise, transaction requesting read/write is restarted and given a new
timestamp.
 The timestamp ordering protocol ensures that any conflicting read and write operations are
executed in the timestamp order.
 The protocol manages concurrent execution such that the time-stamps determine the
serializability order.
12 5/21/2024
 Rules for permitting execution of operations in Time-stamping Method
Suppose that Transaction Ti issues Read(A)
 If TS(Ti) < WTS(A): this implies that Ti needs to read a value of A which was already
overwritten. Hence the read operation must be rejected and Ti is rolled back.
 If TS(Ti) >= WTS(A): then the read is executed and RTS(A) is set to the maximum of
RTS(A) and TS(Ti).
Suppose that Transaction Ti issues Write(A)
 If TS(Ti) < RTS(A): then this implies that the value of A that Ti is producing was
previously needed and it was assumed that it would never be produced. Hence, the Write
operation must be rejected and Ti is rolled back.
 If TS(Ti) < WTS(A): then this implies that Ti is attempting to Write an object value of A.
hence, this write operation can be ignored.
 Otherwise the Write operation is executed and WTS(A) is set to the maximum of WTS(A)
or TS(Ti).
 A transaction that is rolled back due to conflict will be restarted and be given a new timestamp.
13 5/21/2024
 Optimistic Technique
Locking and assigning and checking timestamp values may be unnecessary for some
transactions
Assumes that conflict is rare.
When transaction reaches the level of executing commit, a check is performed to
determine whether conflict has occurred. If there is a conflict, transaction is rolled
back and restarted.
Based on assumption that conflict is rare and more efficient to let transactions proceed
without delays to ensure serializability.
At commit, check is made to determine whether conflict has occurred.
If there is a conflict, transaction must be rolled back and restarted.
Potentially allows greater concurrency than traditional protocols.
Three phases:
1. Read
2. Validation
14 3. Write 5/21/2024
 [Link] Techniques - Read Phase
 Extends from start until immediately before commit.
 Transaction reads values from database and stores them in local variables.
Updates are applied to a local copy of the data.

2. Optimistic Techniques - Validation Phase

 Follows the read phase.
 For read-only transaction, checks that data read are still current values. If no
interference, transaction is committed, else aborted and restarted.
 For update transaction, checks transaction leaves database in a consistent state,
with serializability maintained.
[Link] Techniques - Write Phase
 Follows successful validation phase for update transactions.
 Updates made to local copy are applied to the database.

15 5/21/2024
 Granularity of data items
 Granularity is the size of the data items chosen as the unit of protection by a concurrency
control protocol.
 The entire database
 A file
 A page (a section of physical disk in which relations are stored)(sometimes also called a
block)
 A record
 A field value of a record
 The granularity has effect on the performance of the system. As locking will
prevent access to the data, the size of the data required to be locked will
prevent other transactions from having access.
 If the entire database is locked, then consistency will be highly maintained but
less performance of the system will be witnessed.
16 5/21/2024
 If a single data item is locked; consistency maybe at risk but concurrent processing and
performance will be enhanced.
 Thus, as one go from the entire database to a single value, performance and concurrent
processing will be enhanced but consistency will be at risk and needs good concurrency
control mechanism and strategy. Database

File1 File2 File3

Page1 Page2 Page3

Record1

Record2

Record3

Field1

Firld2

Field3 Fig. Granularity of data items

17 5/21/2024
Transaction Subsystem
 Transaction manager
 Scheduler
 Recovery manager
 Buffer manager
 Transaction Manager in DBMS coordinates transactions on behalf of application
programs. Communicates with scheduler (lock manager) which is responsible for
implementing a strategy for concurrency control.
 The Scheduler in the DBMS ensures that the individual steps of different transactions
preserve consistency.
 Recovery Manager: Ensures that database is restored to the original state in case failure
occurs.
 Buffer Manager: responsible for transfer of data between disk storage and main memory.

18 5/21/2024
19 5/21/2024