Lock-based Protocols

DSA, Database System & Operating System — Transaction Processing, Concurrency Control & Recovery, NEC licence examination syllabus (Nepal Engineering Council).

Lock-Based Protocols

Two-phase locking — the protocol that guarantees serializability by construction.

🌍 Where this lives: every time a query "hangs" and you find it in pg_stat_activity with wait_event = Lock, you are watching 2PL work as designed. And the single most common production incident from locking is a long-running transaction holding locks it acquired minutes ago — because under strict 2PL, locks are held until COMMIT, so one slow transaction blocks everything behind it. That is why "never leave a transaction open across a user interaction" is a hard rule, and why ORMs that keep a transaction open for the duration of a web request cause outages under load. Search "long running transaction blocking lock contention".

Lock modes and compatibility

TWO BASIC MODES: SHARED (S) read lock. Several transactions may hold it simultaneously. EXCLUSIVE (X) write lock. Only one holder, and no S locks may coexist. COMPATIBILITY MATRIX — the whole of locking in four cells: requested S X held S YES no X no no · S with S compatible — many readers · S with X incompatible · X with S incompatible · X with X incompatible This matrix is exactly the conflict matrix from the previous topic: read–read is the only non-conflicting pair, so it is the only compatible lock pair. OPERATIONS: lock-S(X) request a shared lock; blocks if X is X-locked by another transaction lock-X(X) request exclusive; blocks if held in any mode unlock(X) release upgrade S → X (may deadlock — see below) downgrade X → S LOCK GRANULARITY — what you lock matters enormously: database maximum concurrency loss, minimum overhead table one writer per table page a compromise row maximum concurrency, most lock overhead attribute rarely implemented TRADE-OFF: finer granularity means more concurrency and more locks to track. A 1,000,000-row UPDATE taking row locks needs 1,000,000 lock entries; most systems ESCALATE to a table lock past a threshold. INTENTION LOCKS solve the granularity problem. Before locking a row, you take an INTENTION lock on the table so a would-be table-locker knows to wait: IS intention shared "I intend to S-lock some row" IX intention exclusive "I intend to X-lock some row" SIX shared + intention exclusive This is MULTIPLE GRANULARITY LOCKING, and it is why a table lock request can be detected as conflicting without scanning every row lock.

Two-phase locking

2PL RULE: every transaction has two phases, and once it releases any lock it may never acquire another. GROWING phase (expanding) acquire locks, release none SHRINKING phase (contracting) release locks, acquire none LOCK POINT — the instant of the last acquisition. Serial order is determined by lock-point order. locks held │ ┌────────┐ │ ╱ ╲ │ ╱ ╲ │ ╱ growing ╲ shrinking │ ╱ ╲ └─────────────────────────► time ▲ lock point THEOREM: if every transaction follows 2PL, every resulting schedule is CONFLICT-SERIALIZABLE. Proof sketch: order transactions by lock point. If Ti → Tj in the precedence graph, Ti's lock point precedes Tj's. A cycle would require a transaction's lock point to precede itself. Contradiction. 2PL guarantees serializability but NOT freedom from deadlock, and NOT recoverability. Hence the variants: STRICT 2PL all EXCLUSIVE locks held until commit/abort (S locks may be released earlier) → produces STRICT schedules, so no cascading rollback → what most real systems implement RIGOROUS 2PL all locks (S and X) held until commit/abort → simpler to reason about, slightly less concurrency → PostgreSQL's row locks behave this way CONSERVATIVE 2PL acquire ALL locks BEFORE starting → DEADLOCK-FREE, because a transaction that cannot get everything waits without holding anything → requires knowing the full lock set in advance, which is usually impossible → the only deadlock-free variant Conservative → no deadlock, impractical Strict → no cascading rollback, deadlocks possible Rigorous → strictest, deadlocks possible

locking.sql

-- Verified on PostgreSQL 18. PostgreSQL uses MVCC for reads,
-- so readers do not take S locks on rows — but WRITES take
-- row-level exclusive locks, and explicit lock requests
-- behave exactly as 2PL describes.

-- ===== EXPLICIT ROW LOCKING =====
-- SESSION A                        SESSION B
BEGIN;
SELECT balance FROM account
  WHERE id = 1 FOR UPDATE;   -- takes an X row lock
                             -- BEGIN;
                             -- SELECT balance FROM account
                             --   WHERE id=1 FOR UPDATE;
                             -- ← BLOCKS, waiting for A
UPDATE account SET balance = 11000 WHERE id = 1;
COMMIT;                      -- lock released
                             -- ← B now proceeds and sees
                             --   the COMMITTED 11000

-- FOR UPDATE is how you opt into pessimistic locking under
-- MVCC. Without it, B would read the old value and the lost
-- update from the previous topic becomes possible.

-- ===== THE FOUR ROW-LOCK STRENGTHS in PostgreSQL =====
--   FOR UPDATE         strongest; blocks all other lockers
--   FOR NO KEY UPDATE  weaker; allows concurrent FK checks
--   FOR SHARE          shared; several readers, blocks writers
--   FOR KEY SHARE      weakest; only blocks key changes
--
-- FOR SHARE is a genuine S lock: 
BEGIN;
SELECT * FROM account WHERE id=1 FOR SHARE;
-- another session may ALSO take FOR SHARE (S/S compatible)
-- but FOR UPDATE will block (S/X incompatible) ✔ matches
-- the compatibility matrix

-- ===== TABLE-LEVEL LOCKS =====
LOCK TABLE account IN ACCESS EXCLUSIVE MODE;
-- 8 table lock modes in PostgreSQL, from ACCESS SHARE
-- (taken by SELECT) to ACCESS EXCLUSIVE (taken by DROP,
-- TRUNCATE, ALTER). The matrix is larger but the principle
-- is identical.

-- ===== INSPECTING LOCKS — the practical diagnostic =====
SELECT pid, locktype, relation::regclass, mode, granted
FROM   pg_locks
WHERE  NOT granted;          -- who is WAITING

SELECT a.pid, a.wait_event_type, a.wait_event,
       a.state, LEFT(a.query, 50) AS query
FROM   pg_stat_activity a
WHERE  a.wait_event_type = 'Lock';
-- This is the first query to run when the application
-- "hangs". It shows exactly which session is blocked and
-- what it is waiting for.

Timestamp ordering — the alternative to locking

Instead of locks, give every transaction a TIMESTAMP TS(T) at start and enforce that conflicting operations execute in timestamp order. For each data item X, keep: W-TS(X) the largest timestamp of any transaction that successfully wrote X R-TS(X) the largest timestamp of any transaction that read X BASIC TIMESTAMP ORDERING PROTOCOL: T wants to READ(X): if TS(T) < W-TS(X): → T is trying to read a value that a NEWER transaction has already overwritten → REJECT: roll back T else: execute the read; R-TS(X) := max(R-TS(X), TS(T)) T wants to WRITE(X): if TS(T) < R-TS(X): → a newer transaction already read the old value; writing now would invalidate that read → REJECT: roll back T if TS(T) < W-TS(X): → a newer transaction already wrote X → the THOMAS WRITE RULE: this write is obsolete, so simply IGNORE it (do not roll back) else: execute the write; W-TS(X) := TS(T) PROPERTIES: ✔ deadlock-free — nothing ever waits, so no cycle of waits ✗ may cause cascading rollbacks ✗ starvation possible — a long transaction may be repeatedly restarted ✗ not recoverable without extra rules WORKED EXAMPLE TS(T1)=100, TS(T2)=200. Initially R-TS(A)=W-TS(A)=0. T2: R(A) TS=200 ≥ W-TS=0 → OK, R-TS(A)=200 T1: W(A) TS=100 < R-TS(A)=200 → REJECT, roll back T1 (T2 already read the value T1 would invalidate) Compare with 2PL: T1 would have BLOCKED instead of aborting. That is the fundamental difference — locking makes transactions WAIT; timestamp ordering makes them ABORT. WHY LOCKING WON IN PRACTICE: aborting and restarting wastes all the work done so far, whereas waiting preserves it. Under low contention timestamp ordering is fine; under high contention it thrashes. Real systems use locking (or MVCC, which is timestamp-like for reads and lock-based for writes).

🌍 Go further: PostgreSQL's answer to lock contention is that readers never block writers — MVCC gives each reader a snapshot instead of an S lock, so a long report cannot block an UPDATE. The cost is that old row versions must be cleaned up, which is what VACUUM does, and a long-open transaction prevents that cleanup — producing table bloat instead of blocking. So MVCC does not remove the "don't hold transactions open" rule; it changes the symptom from blocking to bloat. Search "PostgreSQL MVCC vacuum bloat long transactions".

💡 Exam angle: reproduce the lock compatibility matrix (only S/S is compatible) and define the two phases of 2PL with the lock point. State the theorem — 2PL guarantees conflict serializability — and know the three variants: strict (X locks to commit, no cascading rollback, what real systems use), rigorous (all locks to commit), and conservative (all locks first, the only deadlock-free one). For timestamp ordering, know the read and write rules and the Thomas write rule, and state the key contrast: locking makes transactions wait, timestamp ordering makes them abort.

Syllabus points

Shared/exclusive locks
Two-phase locking (2PL)

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.