Database Management SystemUnit 910 min read

Concurrency Control: Locking, 2PL, Timestamping, MVCC, and Deadlock Management

Unit 9 of Database Management System: covers the mechanisms used to manage simultaneous transaction execution, ensuring data consistency through locking protocols, timestamp ordering, multiversion techniques, and strategies for handling deadlocks and starvation in a multi-user environment.

Padhai · Based on the official syllabus and past papers
Updated 25 Sept 2026

Key points

Concurrency control ensures that interleaved execution of transactions results in a consistent database state.
Locking protocols like Two-Phase Locking (2PL) prevent conflicts by restricting access to data items during transaction execution.
Timestamp ordering provides a non-locking alternative by using transaction start times to determine execution order.
Deadlock management involves detection, prevention, and recovery strategies to handle circular wait conditions.
Granularity levels determine the trade-off between concurrency overhead and the degree of parallelism allowed.

Introduction to Concurrency Control

In a multi-user database system, many transactions may be submitted simultaneously. If these transactions access and update the same data items concurrently, it can lead to inconsistencies. Concurrency Control is the process of managing simultaneous operations on a database without having them interfere with each other.

Why do we need Concurrency Control?

Without proper concurrency control, three main problems occur:

The Lost Update Problem: Occurs when two transactions that access the same database items have their operations interleaved in a way that makes the value of some database items incorrect. One update "overwrites" another.
The Temporary Update (Dirty Read) Problem: Occurs when one transaction updates a database item and then the transaction fails for some reason. The updated item is accessed by another transaction before it is changed back to its original value.
The Incorrect Summary Problem: Occurs when one transaction is calculating an aggregate summary function on a number of records while other transactions are updating some of these records.

Locking Techniques for Concurrency Control

A lock is a variable associated with a data item that describes the status of that item with respect to possible operations that can be applied to it.

1. Binary Locks

A binary lock has two states: locked (1) and unlocked (0).

If an object is locked, no other transaction can access it.
It is too restrictive because it does not allow multiple "reads" even though reading doesn't change data.

2. Shared/Exclusive (Read/Write) Locks

To allow more concurrency, we use two types of locks:

Shared (S) Lock: Also called a Read-lock. If a transaction $T_{i}$ has a shared lock on item $X$ , it can read $X$ but cannot write. Multiple transactions can hold shared locks on the same item simultaneously.
Exclusive (X) Lock: Also called a Write-lock. If a transaction $T_{i}$ has an exclusive lock on item $X$ , it can both read and write $X$ . No other transaction can hold any lock (S or X) on that item.

Lock Compatibility Matrix:

	Shared (S)	Exclusive (X)
Shared (S)	Compatible (True)	Conflict (False)
Exclusive (X)	Conflict (False)	Conflict (False)

Two-Phase Locking (2PL) Protocol

The Two-Phase Locking protocol is a method that guarantees serializability. It requires that every transaction issue lock and unlock requests in two phases:

Growing Phase: A transaction may obtain locks but may not release any lock.
Shrinking Phase: A transaction may release locks but may not obtain any new locks.

The point where the transaction has acquired all its locks but has not yet released any is called the Lock Point.

Types of 2PL

Basic 2PL: Transactions follow the two phases strictly. It can lead to deadlocks.
Conservative 2PL (Static 2PL): Requires a transaction to lock all the items it accesses before the transaction begins execution. This prevents deadlocks but limits concurrency.
Strict 2PL: A transaction does not release any exclusive locks until it commits or aborts. This ensures that the schedule is strict (recoverable and avoids cascading rollbacks).
Rigorous 2PL: A transaction does not release any locks (shared or exclusive) until it commits or aborts.

Timestamp Ordering Protocol

Timestamp ordering (TO) is a non-locking concurrency control technique. Each transaction $T_{i}$ is assigned a unique starting timestamp $T S (T_{i})$ .

For every data item $X$ , two timestamp values are maintained:

W_TS(X): The largest timestamp of any transaction that executed write(X) successfully.
R_TS(X): The largest timestamp of any transaction that executed read(X) successfully.

The Protocol Rules

When transaction $T_{i}$ issues a read(X):

If $T S (T_{i}) < W_T S (X)$ , then $T_{i}$ is trying to read a value that was overwritten by a younger transaction. Reject read(X) and roll back $T_{i}$ .
If $T S (T_{i}) \geq W_T S (X)$ , then Execute read(X) and set $R_T S (X) = max (R_T S (X), T S (T_{i}))$ .

When transaction $T_{i}$ issues a write(X):

If $T S (T_{i}) < R_T S (X)$ , then the value of $X$ that $T_{i}$ is producing was needed previously by a younger transaction. Reject write(X) and roll back $T_{i}$ .
If $T S (T_{i}) < W_T S (X)$ , then $T_{i}$ is attempting to write an obsolete value. Reject write(X) and roll back $T_{i}$ . (Note: Thomas Write Rule relaxes this).
Otherwise, Execute write(X) and set $W_T S (X) = T S (T_{i})$ .

Thomas Write Rule

This is a modification to the Timestamp Ordering protocol. If $T S (T_{i}) < W_T S (X)$ , instead of rolling back $T_{i}$ , we simply ignore the write operation and continue. This is because the value $T_{i}$ is trying to write would have been overwritten by the transaction with $W_T S (X)$ anyway.

Deadlock and Starvation

Deadlock

A deadlock occurs when two or more transactions are in a wait state, each waiting for a resource held by the other.

Example of Deadlock:
T1: lock_X(A) ... lock_X(B)
T2: lock_X(B) ... lock_X(A)

Trace:
1. T1 locks A.
2. T2 locks B.
3. T1 requests lock on B (waits for T2).
4. T2 requests lock on A (waits for T1).
Result: Deadlock.

Handling Deadlocks:

Deadlock Prevention:
- Wait-Die: If $T_{i}$ requests a lock held by $T_{j}$ , $T_{i}$ is allowed to wait only if it is older than $T_{j}$ ( $T S (T_{i}) < T S (T_{j})$ ). If $T_{i}$ is younger, it dies (aborts).
- Wound-Wait: If $T_{i}$ requests a lock held by $T_{j}$ , $T_{i}$ is allowed to wait only if it is younger than $T_{j}$ . If $T_{i}$ is older, it "wounds" (aborts) $T_{j}$ .
Deadlock Detection: The system constructs a Wait-For Graph (WFG). If the graph has a cycle, a deadlock exists.
Deadlock Recovery: Select a "victim" transaction to abort and roll back to break the cycle.

Starvation

Starvation occurs when a particular transaction is perpetually denied the resources it needs to proceed, even though the system as a whole is making progress.

Cause: A transaction might be repeatedly selected as a victim for deadlock recovery, or younger transactions keep jumping ahead in a priority queue.
Solution: Use a "First-Come-First-Served" (FCFS) queue for lock requests or increase the priority of a transaction every time it is rolled back.

Multiversion Concurrency Control (MVCC)

In MVCC, the system keeps old versions of a data item when it is updated.

When a transaction $T_{i}$ reads an item, the system selects one of the versions to ensure serializability.
Advantage: Reads never block writes, and writes never block reads. This is highly effective for databases with many read-only queries.
Mechanism: Each version is tagged with the timestamp of the transaction that created it. A read request for $X$ by $T_{i}$ is satisfied by the version of $X$ whose timestamp is the largest version $\leq T S (T_{i})$ .

Optimistic Concurrency Control (Validation-based)

Optimistic protocols assume that conflicts are rare. Transactions execute without acquiring locks. A transaction is divided into three phases:

Read Phase: The transaction executes, reading data and performing computations in local private variables. All writes are performed on local copies.
Validation Phase: The system checks if the transaction's updates violate serializability. If a conflict is detected, the transaction is aborted.
Write Phase: If validation succeeds, the local updates are applied to the actual database.

Granularity of Data Items

Granularity refers to the size of the data item being locked.

Fine Granularity: Locking individual records/fields. (High concurrency, high overhead).
Coarse Granularity: Locking entire files or the whole database. (Low concurrency, low overhead).

Multiple Granularity Locking (MGL)

To manage different levels of granularity, we use a hierarchy (Tree) and Intention Locks.

Hierarchy:
    Database
       |
     Files
       |
     Pages
       |
    Records

Intention Locks:

IS (Intention-Shared): Indicates that shared locks will be requested at a lower level.
IX (Intention-Exclusive): Indicates that exclusive locks will be requested at a lower level.
SIX (Shared with Intention-Exclusive): The current node is locked in shared mode, but exclusive locks will be requested at a lower level.

Rule: To lock a node in S or IS, the parent must be locked in IS or IX. To lock a node in X, IX, or SIX, the parent must be locked in IX or SIX.

Comparison Table: Locking vs. Timestamping

Feature	Locking (2PL)	Timestamp Ordering
Approach	Pessimistic (prevents conflict)	Optimistic (detects conflict)
Mechanism	Uses locks (S/X)	Uses Read/Write Timestamps
Deadlock	Possible (except Conservative)	Deadlock-free
Starvation	Possible	Possible
Overhead	Lock maintenance and monitoring	Timestamp storage and rollback
Cascading Rollback	Possible (unless Strict 2PL)	Possible

Worked Example: Timestamp Ordering Trace

Consider two transactions:

$T_{1}$ with $T S (T_{1}) = 10$
$T_{2}$ with $T S (T_{2}) = 20$
Initial $R_T S (A) = 0, W_T S (A) = 0$

Time	Transaction	Operation	Action/Result	Updated TS
1	$T_{1}$	`read(A)`	$10 \geq 0$ . OK.	$R_T S (A) = 10$
2	$T_{2}$	`write(A)`	$20 \geq 10$ and $20 \geq 10$ . OK.	$W_T S (A) = 20$
3	$T_{1}$	`write(A)`	$10 < R_T S (A)$ (10) is false, but $10 < W_T S (A)$ (20) is True.	Abort $T_{1}$

Note: If Thomas Write Rule was used at Time 3, $T_{1}$ 's write would simply be ignored instead of aborting.

Exam tip

In the TU/PU exams, this unit is frequently tested with the following focus:

2PL Protocol: Always explain the two phases (Growing and Shrinking) and mention why Strict 2PL is used in practice (to avoid cascading rollbacks).
Deadlock: Be prepared to draw a Wait-For Graph and explain Wait-Die vs. Wound-Wait schemes.
Timestamp Ordering: Memorize the rules for read(X) and write(X). If a numerical trace is asked, show the comparison of $T S (T_{i})$ with $R_T S$ and $W_T S$ clearly.
Comparison: Often, a short note or a distinction between "Locking vs. Timestamping" or "Binary vs. Shared Locks" is asked.
Granularity: Understand the "Intention Locks" (IS, IX, SIX) as they are the core of Multiple Granularity questions.

Based on the TU BSc CSIT syllabus for Database Management System (CSC265), unit 9.

Discussion

Loading…