Lock-Based Protocols & Two-Phase Locking

Lock-based protocols use locks to control concurrent access to data items, ensuring that transactions do not interfere with each other.

Lock-Based Protocols

Lock-based protocols use locks to control concurrent access to data items, ensuring that transactions do not interfere with each other.

A lock is a mechanism that restricts access to a data item when a transaction is using it.

Types of Locks

Shared Lock (S-Lock / Read Lock)

Allows the transaction to read a data item
Multiple transactions can hold a shared lock on the same item simultaneously
No write allowed while shared lock is held by others

Exclusive Lock (X-Lock / Write Lock)

Allows the transaction to read AND write a data item
Only one transaction can hold an exclusive lock at a time
No other lock (shared or exclusive) can be granted simultaneously

Lock Compatibility Matrix

Request → Hold ↓ S-Lock X-Lock ────────────────────────── S-Lock │ YES │ NO │ X-Lock │ NO │ NO │ None │ YES │ YES │

Lock Operations

Operation	Description
lock-S(X)	Request shared lock on item X
lock-X(X)	Request exclusive lock on item X
unlock(X)	Release lock on item X

Two-Phase Locking (2PL)

Two-Phase Locking (2PL) is the most widely used locking protocol. It divides lock operations into two distinct phases:

Phase 1 — GROWING PHASE: Transaction can ACQUIRE locks (S or X). Transaction CANNOT release any lock. Phase 2 — SHRINKING PHASE: Transaction can RELEASE locks. Transaction CANNOT acquire any new lock. Lock Point = moment of maximum lock holding (transition point)

2PL Diagram

/	\
/	\
/	\
/	\
/	\

2PL Example

Transaction T1: Phase 1 (Growing): lock-S(A) ← acquire read(A) lock-X(B) ← acquire read(B) write(B) ← LOCK POINT (maximum locks) Phase 2 (Shrinking): unlock(A) ← release unlock(B) ← release COMMIT

2PL Theorem

A schedule produced by 2PL transactions is conflict serializable.

The serial order is determined by the lock points — transactions are ordered by when they reach their lock point.

Variants of 2PL

Basic 2PL

Standard two-phase protocol — locks released during shrinking phase.

Problem: Allows cascading rollbacks (a rollback of T1 may force rollback of T2 which read T1's dirty write).

Strict 2PL

All exclusive (X) locks are held until the transaction commits or aborts.

Strict 2PL: lock-X(A) ← held until commit write(A) ... COMMIT → unlock(A) ← only released at commit

Benefit: Eliminates cascading rollbacks — no transaction reads dirty data.

Rigorous 2PL

All locks (both S and X) are held until commit/abort.

Rigorous 2PL: lock-S(A) ← held until commit lock-X(B) ← held until commit ... COMMIT → unlock(A), unlock(B)

Benefit: Simplest to implement; equivalent serial order is same as commit order.

Comparison of 2PL Variants

Protocol	When are locks released?
Basic 2PL	Anytime during shrinking phase
Strict 2PL	Exclusive locks held until commit/abort
Rigorous 2PL	ALL locks held until commit/abort

Lock Manager

The Lock Manager is a DBMS component that:

Maintains a lock table (hash table indexed by data item)
Processes lock requests and grants/denies them
Maintains queues for waiting transactions

Lock Table Entry for data item X: ┌──────────────────────────────────────────────┐ │ Item X: Granted={T1:S, T2:S}, Waiting={T3:X} │ └──────────────────────────────────────────────┘ T1 and T2 hold shared locks. T3 is waiting for exclusive lock (blocked).

Locking Granularity

Locks can be applied at different levels:

Database Level	One lock for entire DB (too coarse)
Table Level	Lock entire table
Page Level	Lock a disk page
Row Level	Lock individual rows (most common)
Attribute Level	Lock individual columns (very fine)

Fine granularity (row-level): High concurrency, high overhead Coarse granularity (table-level): Low overhead, low concurrency

Intention Locks (Multi-Granularity)

Used in multi-granularity locking to indicate intent at higher levels:

Lock	Meaning
IS (Intention Shared)	Intends to set S lock on descendant
IX (Intention Exclusive)	Intends to set X lock on descendant
SIX (Shared + Intention Exclusive)	S on current + IX on descendant