The Story That Explains Locking
Annotating (writing) is dangerous. If two scholars annotate the same page at the same time, their notes will clash. So the librarian has a policy: if anyone wants to annotate a page, they must lock the vault door and work alone. Others — readers or writers — must wait outside until the door is unlocked.
This is exactly how a database manages shared and exclusive locks. Multiple shared locks (reads) can coexist. But an exclusive lock (write) demands sole access.
Now the tricky part: when can a scholar release the lock? If they release too early, another scholar may see a half-finished annotation, producing inconsistency. The rule that governs the timing of lock and unlock is called Two-Phase Locking (2PL).
Concurrency control is the DBMS subsystem responsible for ensuring that transactions executing in parallel do not violate the isolation property. The most widely used mechanism is lock-based concurrency control, where a transaction must obtain a lock on a data item before accessing it, and release the lock when done. Two-Phase Locking (2PL) is the most important protocol governing when locks may be acquired and released — and it is provably sufficient to guarantee conflict serializability.
Lock Types — Shared and Exclusive
Every lock request falls into one of two modes. The compatibility between them determines whether concurrency is possible.
| Property | Detail |
|---|---|
| Purpose | Allow a transaction to read a data item |
| Sharing | Multiple transactions may hold S-locks on the same item simultaneously |
| Symbol | S or lock-S(X) |
| Property | Detail |
|---|---|
| Purpose | Allow a transaction to read AND write a data item |
| Sharing | Only one transaction may hold an X-lock — no sharing at all |
| Symbol | X or lock-X(X) |
Lock Compatibility Matrix
This 2×2 matrix is the single most important table in locking. It answers: "Can transaction Tj get its requested lock if Ti already holds a lock on the same item?"
| Ti holds S-lock | Ti holds X-lock | |
|---|---|---|
| Tj requests S-lock | ✓ GRANTED | ✗ WAIT |
| Tj requests X-lock | ✗ WAIT | ✗ WAIT |
"Readers share, writers are exclusive." The only compatible combination is two shared locks. Every other pair (S-X, X-S, X-X) forces the second transaction to wait.
Basic Lock Protocol — Lock Before Access, Unlock When Done
The simplest locking rule: acquire a lock before accessing a data item, release it when you no longer need it. But "when you no longer need it" is dangerously vague — releasing too early creates problems.
Example — Early Unlock Breaks Isolation
| Time | T1 | T2 | Item A |
|---|---|---|---|
| t1 | lock-X(A) | locked by T1 | |
| t2 | R(A) = 100 | ||
| t3 | W(A) = 150 | ||
| t4 | unlock(A) | unlocked early! | |
| t5 | lock-X(A) | locked by T2 | |
| t6 | R(A) = 150 | ||
| t7 | W(A) = 200 | ||
| t8 | unlock(A) | ||
| t9 | ABORT! | A must revert to 100 |
T1 unlocked A at t4 before committing. T2 read the uncommitted value 150 and built its own work on top of it. When T1 aborts at t9, A reverts to 100 — but T2 has already used the stale value 150. T2 must also abort. This is the exact cascading-abort problem from the Schedules tutorial — caused here by releasing the lock too soon.
The fix: a protocol that enforces a disciplined lock lifecycle. That protocol is Two-Phase Locking.
Two-Phase Locking (2PL) — The Core Idea
A transaction follows the Two-Phase Locking protocol if it divides its lifetime into exactly two phases: a growing phase (only lock acquisitions, no releases) followed by a shrinking phase (only lock releases, no new acquisitions). The transition point is called the lock point.
The Lock-Count Diagram
The "hill" shape is the hallmark of 2PL: locks only go up (growing), reach a peak (lock point), then only go down (shrinking). Once you release one lock, you can never acquire another.
Theorem: If every transaction in a schedule follows 2PL, then the schedule is conflict serializable. The equivalent serial order is the order of the transactions' lock points. This is the formal bridge from locking to serializability.
Variants of Two-Phase Locking
The basic 2PL rule guarantees conflict serializability, but leaves open when exactly locks are released. Different placement of the shrinking phase yields different guarantees about recovery and cascading aborts.
Visual Comparison — When Are Locks Released?
From top to bottom, each variant holds locks progressively longer. Conservative 2PL acquires everything at BEGIN and holds to COMMIT — deadlock-free but least concurrent.
| Variant | Conflict Serializable | Cascadeless | Strict | Deadlock-free |
|---|---|---|---|---|
| Basic 2PL | ✓ | ✗ | ✗ | ✗ |
| Strict 2PL | ✓ | ✓ | ✗ | ✗ |
| Rigorous 2PL | ✓ | ✓ | ✓ | ✗ |
| Conservative 2PL | ✓ | ✓ | ✓ | ✓ |
Deadlocks — The Dark Side of Locking
Classic Deadlock Example
| Time | T1 | T2 |
|---|---|---|
| t1 | lock-X(A) | |
| t2 | lock-X(B) | |
| t3 | lock-X(B) — WAIT | |
| t4 | lock-X(A) — WAIT | |
| 💥 DEADLOCK! Both waiting forever. | ||
A cycle in the Wait-For graph = deadlock. The DBMS breaks it by aborting (rolling back) one transaction — the "victim".
Numerical 1 — Does This Transaction Follow 2PL?
Problem: Determine whether each lock sequence follows Two-Phase Locking.
Sequence A
Sequence B
Numerical 2 — Strict 2PL Walkthrough
Two transactions T1 (transfers ₹500 from A to B) and T2 (reads A+B) run under Strict 2PL. Show the lock sequence.
| Time | T1 | T2 | Locks Held |
|---|---|---|---|
| t1 | lock-X(A) | T1: X(A) | |
| t2 | R(A)=1000 | ||
| t3 | W(A)=500 | ||
| t4 | lock-X(B) | T1: X(A), X(B) | |
| t5 | lock-S(A) — WAIT | T2 blocked by T1's X(A) | |
| t6 | R(B)=2000 | waiting… | |
| t7 | W(B)=2500 | waiting… | |
| t8 | Commit → unlock all | T1 releases X(A), X(B) | |
| t9 | lock-S(A) GRANTED | T2: S(A) | |
| t10 | R(A)=500 | ||
| t11 | lock-S(B) | T2: S(A), S(B) | |
| t12 | R(B)=2500 | ||
| t13 | Commit → unlock all | clean |
T1 holds all X-locks until commit (step 8) — satisfying Strict 2PL. T2 is forced to wait at t5 because the S-lock on A is incompatible with T1's X-lock. Once T1 commits, T2 reads committed values (500 + 2500 = 3000 = original 3000). The result is consistent: no cascading abort and no lost update.
Wait-Die & Wound-Wait — Deadlock Prevention
These two timestamp-based protocols use transaction age to decide who gets priority when a lock conflict arises. Older = higher priority.
| Requester | Action |
|---|---|
| Older requests lock held by Younger | WAIT (older is patient) |
| Younger requests lock held by Older | DIE (younger aborts, retries later with same timestamp) |
| Requester | Action |
|---|---|
| Older requests lock held by Younger | WOUND (younger is forced to abort) |
| Younger requests lock held by Older | WAIT (younger is patient) |
Wait-Die: the older transaction waits, the younger dies. Wound-Wait: the older transaction wounds (kills) the younger, the younger waits for the older. In both schemes, the younger transaction is the one that gets aborted — it always re-enters with its original timestamp so it eventually becomes old enough to succeed.
Academic View vs Industry View
| Aspect | Detail |
|---|---|
| Focus | Proofs: 2PL ⇒ conflict serializable |
| Exam topics | Lock sequences, identify 2PL violations, deadlock graphs |
| Variants | Basic, Strict, Rigorous, Conservative — know the guarantees |
| Hierarchy | Basic 2PL ⊂ Strict ⊂ Rigorous ⊂ Conservative |
| Aspect | Detail |
|---|---|
| Default | Most engines use Strict or Rigorous 2PL |
| Deadlocks | Detected via wait-for graph; victim chosen by least work done |
| Lock granularity | Row-level (InnoDB), page-level, table-level — finer = more concurrency |
| MVCC alternative | PostgreSQL / Oracle use MVCC + SSI instead of lock-blocking for reads |
| Advice | Keep transactions short; access items in consistent order to reduce deadlocks |
Most production databases (PostgreSQL, MySQL/InnoDB, SQL Server) combine lock-based and MVCC strategies. Reads use MVCC snapshots (no read locks needed, so readers never block writers), while writes still acquire locks (typically row-level X-locks held until commit, i.e. Strict 2PL). This hybrid gives the serializability guarantee of 2PL with the read-concurrency advantage of MVCC.
Rapid-Fire Concept Check
| Question | Answer |
|---|---|
| Two types of locks | Shared (S) and Exclusive (X) |
| Compatible pair? | S-S only; all others block |
| What 2PL guarantees | Conflict serializability |
| The two phases | Growing (acquire) then Shrinking (release) |
| The lock point | Instant last lock is acquired |
| What Strict 2PL adds | Hold X-locks to commit → cascadeless |
| What Rigorous 2PL adds | Hold ALL locks to commit → strict schedules |
| Which variant is deadlock-free? | Conservative 2PL |
| Cycle in wait-for graph means | Deadlock |
| Wait-Die: younger requests older's lock? | Younger dies (aborts) |
| Wound-Wait: older requests younger's lock? | Older wounds (kills younger) |
| Most common engine approach today | Strict 2PL + MVCC hybrid |