Database System Concepts

Chapter: Concurrency Control

Prof. Dr. Rafiqul Islam

13 July, 2025

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 1 / 37

Concurrency Control

When several transactions execute concurrently in the database, however,

the isolation property may no longer be preserved.
To ensure that it is, the system must control the interaction among the
concurrent transactions; this control is achieved through one of a variety of
mechanisms called concurrency control schemes.
there are a variety of concurrency-control schemes. No one scheme is clearly
the best; each one has advantages. In practice, the most frequently used
schemes are two-phase locking and snapshot isolation.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 2 / 37

Motivation for Locking

Isolation in concurrent transactions requires mutual exclusion.

Lock-based protocols ensure that data items are accessed safely.
While one transaction accesses a data item, others are restricted.
Locks are managed by the DBMS to preserve serializability.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 3 / 37

Types of Locks

Shared (S): Transaction can read, but not write.

Exclusive (X): Transaction can both read and write.
Shared locks allow multiple concurrent readers.
Exclusive locks restrict access to one transaction.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 4 / 37

Lock Compatibility Matrix

S X
S true false
X false false

Compatibility determines if multiple locks can coexist.

Shared–Shared: Compatible
Shared–Exclusive or Exclusive–Exclusive: Incompatible

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 5 / 37

Locking Operations

lock-S(Q) — Request a shared lock on item Q

lock-X(Q) — Request an exclusive lock on item Q
unlock(Q) — Release the lock on item Q
Locks must be held for the duration of access.
Unlocking too early may violate serializability.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 6 / 37

Transaction T1: Account Transfer

lock-X(B);
read(B);
B := B 50;
write(B);
unlock(B);
lock-X(A);
read(A);
A := A + 50;
write(A);
unlock(A);

Ensures exclusive access to accounts A and B.

Prevents interference from other transactions during transfer.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 7 / 37

Context: Concurrent Transactions

Two transactions operate on accounts A and B:

T1: Deduct 50 from each account
T2: Read A and B, display total balance
Goal: Show how locking preserves isolation and serializability
Demonstrates controlled interleaving of reads/writes

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 8 / 37

Transaction T1 (Update Accounts)

lock-X(B)
read(B)
B := B 50
write(B)
unlock(B)
lock-X(A)
read(A)
A := A 50
write(A)
unlock(A)
Requires exclusive locks to update both accounts
Ensures mutual exclusion on data items

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 9 / 37

Transaction T2 (Read and Display)

lock-S(A)
read(A)
unlock(A)
lock-S(B)
read(B)
unlock(B)
display(A + B)
Acquires shared locks to read A and B
Reads A before T1 modifies it, B after T1 modifies it

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 10 / 37

Example: Locking

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 11 / 37

Lock Grant Order

grant-X(B, T1) — T1 gets exclusive lock to modify B

grant-S(A, T2) — T2 reads A before T1 changes it
grant-S(B, T2) — T2 reads B after T1 changes it
grant-X(A, T1) — T1 modifies A after T2 releases lock

Outcome: Safe interleaving preserves consistency and prevents conflicts.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 12 / 37

Serializability and Isolation

T2 observes:
Old value of A
New value of B
The schedule is conflict-serializable
Execution order equivalent to: T1(B update) → T2(read) → T1(A
update)
No dirty reads, no lost updates

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 13 / 37

Example: Locking

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 14 / 37

Deadlock in Schedule 2: Lock Interaction Between T3 and
T4

Transaction T3 Transaction T4
lock-X(B) (holds X-lock on B) lock-S(A) (holds S-lock on A)
read(B) read(A)
B := B - 50 lock-S(B) (waits for T3)
write(B)
lock-X(A) (waits for T4)

Deadlock: T3 waits for T4 (A), and T4 waits for T3 (B) — no progress

possible.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 15 / 37

Definition: Two-Phase Locking (2PL)

A protocol that ensures conflict serializability.

Each transaction has two phases:
1 Growing phase: May acquire locks but not release any.
2 Shrinking phase: May release locks but not acquire any new ones.
Once the first unlock is issued, no new locks can be acquired.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 16 / 37

Example: Transaction T3

lock-X(B)
read(B)
lock-X(A)
read(A)
unlock(B)
write(A)
unlock(A)

Locks are acquired first (growing phase).

Unlocks start afterwards (shrinking phase).
Moving unlock(B) earlier is allowed, but no new locks after it.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 17 / 37

Lock Point and Serializability

A transaction’s lock point = final lock acquisition.

Transactions ordered by lock points determine a valid serial order.
Ensures conflict-serializability in the schedule.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 18 / 37

Lock Table

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 19 / 37

Lock Table Example with Overflow Chaining

Each data item (e.g., I4, I7, I912) has a linked list of lock requests.
Dark rectangles = granted locks; light rectangles = waiting
requests.
Overflow chaining manages collisions by maintaining linked lists.
Lock manager behavior:
Grants immediately if no existing lock.
Grants only if compatible and earlier requests are satisfied.
Unlocking triggers evaluation of pending requests.
Aborts remove all locks and requests of the transaction.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 20 / 37

Lock Table Example with Overflow Chaining

Each data item (e.g., I4, I7, I912) has a linked list of lock requests.
Dark rectangles = granted locks; light rectangles = waiting
requests.
Overflow chaining manages collisions by maintaining linked lists.
Lock manager behavior:
Grants immediately if no existing lock.
Grants only if compatible and earlier requests are satisfied.
Unlocking triggers evaluation of pending requests.
Aborts remove all locks and requests of the transaction.

Example: T23 holds locks on I912, I7, and is waiting on I4.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 20 / 37

Drawbacks of Basic 2PL

Does not prevent deadlocks:

T3 and T4 may still be deadlocked.
Allows cascading rollbacks:
If T5 aborts, T6 and T7 may need to rollback.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 21 / 37

Variants of Two-Phase Locking

Strict 2PL:
Holds all exclusive locks until commit.
Prevents cascading rollback.
Rigorous 2PL:
Holds all locks (shared and exclusive) until commit.
Ensures serializability in commit order.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 22 / 37

Improving Concurrency

In standard 2PL, exclusive locks reduce concurrency.

Example: T8 and T9
T8 needs X-lock on a1 only when writing.
If S-lock → X-lock upgrade allowed, both could access a1, a2 in
parallel.
Suggests potential benefit of lock conversion mechanisms.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 23 / 37

What is a Deadlock?

A system is in a deadlock state if there exists a set of transactions

{T, T, ..., T} such that:
T waits for a lock held by T
T waits for a lock held by T
...
T waits for a lock held by T
None can proceed — circular wait.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 24 / 37

Deadlock Example

Transaction T3 Transaction T4
lock-X(B) lock-S(A)
read(B) read(A)
write(B) lock-S(B) (waits)
lock-X(A) (waits)
T3 ↔ T4 deadlock: each waits for a lock held by the other

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 25 / 37

Visualizing with Wait-For Graph

waits for A
T3 T4
waits for B

Cycle detected ⇒ Deadlock

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 26 / 37

Handling Deadlocks

Rollback one or more transactions

Can be partial rollback — to a point before deadlock
Locks held by rolled back transactions are released
System may retry affected transactions later

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 27 / 37

Deadlock Prevention Strategies

Ordering Approach
Lock all required items upfront
Use total ordering of data items (e.g., Tree Protocol)
Timestamp-Based Preemption
Assign timestamps on start
Resolve conflicts using Wait–Die or Wound–Wait
Lock Timeout
Roll back transaction after waiting too long
Simple to implement, but tricky to tune
Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 28 / 37
Timestamp Protocols: Wait–Die vs Wound–Wait

Wait–Die (Nonpreemptive):
Older transaction waits
Younger one is rolled back
Wound–Wait (Preemptive):
Older transaction wounds younger → rollback
Younger one waits
Risk: unnecessary rollbacks still possible

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 29 / 37

Deadlock Detection with Wait-For Graph

The system models transaction dependencies using a Wait-For

Graph G = (V , E )
Vertices (V): Transactions currently active (e.g., T17, T18, T19,
T20)
Edges (E): Directed edges of the form Ti → Tj , meaning
Ti is waiting for Tj to release a lock
An edge is added when a lock request causes blocking; removed when
the lock is released
Deadlock occurs iff the graph contains a cycle

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 30 / 37

Example

Example (Figure 15.14):

T18 → T20 → T19 → T18 forms a cycle
All three transactions are deadlocked

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 31 / 37

Deadlock Recovery Strategy
Recovery Steps:
1 Victim Selection

Roll back the transaction(s) with minimum cost

Cost factors include:
Execution time consumed vs. remaining
Number of data items held or needed
Rollback impact on other transactions
2 Rollback Extent
Total rollback: Abort and restart
Partial rollback: Undo only up to lock causing deadlock
Requires tracking lock request history and update sequence
3 Starvation Prevention
Avoid selecting same victim repeatedly
Use rollback count as part of cost metric

Goal: Break cycle, release locks, allow others to proceed

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 32 / 37
Definition: Timestamp Protocol

Each transaction Ti is assigned a unique timestamp TS(Ti ) when it

starts.
Timestamps determine serialization order — older transactions get
precedence.
Protocol ensures schedules are conflict-serializable by following
timestamp logic.

Purpose: Prevents deadlocks and ensures consistency without locks.

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 33 / 37

Timestamp Validation Rules

For a transaction Ti accessing data item X :

Maintain:
W TS(X ): Timestamp of latest write to X
R TS(X ): Timestamp of latest read on X
Read Rule: Allow Ti to read X only if:

TS(Ti ) ≥ W TS(X )
Write Rule: Allow Ti to write X only if:

TS(Ti ) ≥ R TS(X ) and TS(Ti ) ≥ W TS(X )

Otherwise: abort and restart

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 34 / 37

Example: Transaction Validation

Assume:
TS(T1 ) = 10, TS(T2 ) = 20
W TS(X ) = 12, R TS(X ) = 18
T1 wants to read X:

TS(T1 ) = 10 < W TS(X ) = 12 ⇒ abort

T2 wants to write X:

TS(T2 ) = 20 ≥ R TS(X ) = 18 and

TS(T2 ) ≥ W TS(X ) = 12 ⇒ write allowed

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 35 / 37

Wait–Die Protocol

Nonpreemptive Strategy:
If Ti wants resource held by Tj :
If TS(Ti ) < TS(Tj ): Ti waits
Else: Ti rolls back (dies)
Example:

TS(T14 ) = 5, TS(T15 ) = 10 ⇒ T14 waits for T15

TS(T24 ) = 15 ⇒ rolled back if it requests a lock from T15

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 36 / 37

Wound–Wait Protocol

Preemptive Strategy:
If Ti wants resource held by Tj :
If TS(Ti ) < TS(Tj ): Tj is rolled back (wounded)
Else: Ti waits
Example:

TS(T14 ) = 5, TS(T15 ) = 10 ⇒ T15 rolled back when T14 requests its lock

TS(T16 ) = 15 ⇒ T16 waits if requesting lock from T15

Prof. Dr. Rafiqul Islam Database System Concepts 13 July, 2025 37 / 37