Concurrency: Locks & Deadlocks

When thousands of users try to update the same row simultaneously (e.g., booking the last seat on a flight), we need Concurrency Control to prevent data corruption.

Locking is the primary mechanism used by databases to ensure correct concurrent execution.

---

Learning Objectives

After completing this chapter, you will be able to:

• Differentiate between Shared (S) and Exclusive (X) locks.
• Understand lock compatibility.
• Explain Two-Phase Locking (2PL) and its variants.
• Differentiate between Strict 2PL and Rigorous 2PL.
• Understand deadlocks — detection and prevention.
• Explain Wait-Die and Wound-Wait protocols.
• Answer concurrency interview questions.

---

Lock Types

Shared Lock (S) — Read Lock

Multiple transactions can hold a Shared Lock on the same data item simultaneously.

• Allows reads
• Prevents writes by other transactions

Exclusive Lock (X) — Write Lock

Only ONE transaction can hold an Exclusive Lock.

• Allows reads and writes
• Prevents both reads and writes by other transactions

Lock Compatibility Matrix

Requested → / Held ↓	Shared (S)	Exclusive (X)
Shared (S)	Compatible	Not Compatible
Exclusive (X)	Not Compatible	Not Compatible

Two shared locks can coexist. An exclusive lock blocks everything else.

---

Two-Phase Locking (2PL)

2PL is a protocol that guarantees Conflict Serializability. It divides a transaction into two phases:

Phase 1: Growing Phase

• Transaction acquires locks
• Cannot release any lock

Phase 2: Shrinking Phase

• Transaction releases locks
• Cannot acquire any new lock

Lock Count
    ↑
    |   Growing Phase      |  Shrinking Phase
    |   ▲                  |  ▼
    |  /|\                |  \|/
    | / | \               |   |
    |/  |  \              |   |
    └─────────────────────┴──────────→ Time
       acquire locks         release locks

---

2PL Variants

Standard 2PL

• Growing phase (acquire) → Shrinking phase (release)
• Problem: If a transaction releases a lock and then aborts, other transactions that read that released data may need to be rolled back too — Cascading Rollback

Strict 2PL (Most common in practice)

• All Exclusive (X) locks are held until COMMIT/ROLLBACK
• Shared (S) locks can be released earlier
• Prevents cascading rollbacks
• Used in most real-world databases

Rigorous 2PL

• ALL locks (S and X) are held until COMMIT/ROLLBACK
• Even stricter than Strict 2PL
• Simplifies recovery but reduces concurrency

---

Lock Conversion (Upgrade)

A transaction can convert a Shared Lock → Exclusive Lock (upgrade).

Example:

T1: Lock-S(A) → Read(A) → Lock-X(A) → Write(A)  (Upgrade)

The upgrade may fail if another transaction holds a Shared Lock on A. The transaction waits.

---

Deadlock

A Deadlock occurs when two or more transactions are stuck waiting for each other’s locks.

Example

T1: Lock-X(A)                      → Request Lock-X(B) → WAIT
T2:                  Lock-X(B)      → Request Lock-X(A) → WAIT

T1 holds A and wants B. T2 holds B and wants A. Neither can proceed.

Deadlock Detection

The DBMS builds a Wait-For Graph:

• Nodes = transactions
• Edge Ti → Tj = Ti is waiting for a lock held by Tj
• If a cycle exists → deadlock detected

Resolution: The DBMS chooses a victim transaction and aborts it, releasing its locks. The victim is typically the one with the lowest cost to rollback.

Deadlock Prevention

Protocol	Rule
Wait-Die	Older transaction waits for younger; younger dies (aborts itself)
Wound-Wait	Older transaction wounds (pre-empts) younger; younger waits for older

Both use timestamps to determine “older” vs “younger.” Older = started first (smaller timestamp).

---

Deadlock vs Starvation

	Deadlock	Starvation
Definition	Two transactions waiting for each other	A transaction never gets the locks it needs
Cause	Circular wait	Lock scheduling unfairness
Resolution	Abort a victim	Wait for higher-priority tx to finish
Example	T1→T2→T1 cycle	Low-priority tx always bypassed

---

Interview Deep Dive

---

Key Takeaways

• Shared Lock (S): Read allowed, write blocked. Multiple S-locks can coexist.
• Exclusive Lock (X): Both read and write blocked for others.
• 2PL: Growing phase (acquire only) → Shrinking phase (release only).
• Strict 2PL: Hold all X-locks until COMMIT/ROLLBACK — prevents cascading rollbacks.
• Lock Upgrade: S → X (may cause deadlocks with other S holders).
• Deadlock: Circular wait — detected via Wait-For Graph, resolved by aborting a victim.
• Wait-Die: Older waits for younger (conservative).
• Wound-Wait: Older pre-empts younger (aggressive).
• Goal: Maximum parallelism while maintaining Isolation (ACID).