Lock-Based Concurrency Control and Two-Phase Locking

A concurrency-control protocol decides, operation by operation, whether a transaction may proceed, must wait, or must abort, so that every schedule it lets through is serializable. Locking is the most widely used approach: a transaction must hold a lock on an item before accessing it, and incompatible locks make other transactions wait. Locks alone do not guarantee serializability; the two-phase locking (2PL) rule about when locks are released does.

The questions to answer are whether a lock sequence obeys 2PL or strict 2PL, whether a schedule could have been produced by 2PL, what 2PL guarantees (serializability) and what it does not (freedom from deadlock and from cascading aborts).

Lock modes.

A request is granted only if it is compatible with every lock other transactions hold on the item; otherwise the requester waits.

Notation: $SL_i(X)$ and $XL_i(X)$ request locks, $U_i(X)$ releases one.

Two-phase locking (2PL). Each transaction has a growing phase, in which it may acquire locks but not release any, followed by a shrinking phase, in which it may release locks but not acquire any. The moment it acquires its last lock is its lock point. Upgrading S to X is allowed only in the growing phase, downgrading X to S only in the shrinking phase.

Variants.

Why 2PL gives conflict serializability. If $T_i \to T_j$ is an edge of the precedence graph, some item was locked incompatibly by $T_i$ first and released by $T_i$ before $T_j$ could lock it. $T_i$ released a lock, so it had passed its lock point; $T_j$ then acquired one, so its lock point comes later. Every edge goes from an earlier lock point to a later one, so the graph is acyclic and the lock-point order is an equivalent serial order.

Deadlock. 2PL does not prevent deadlock: $T_1$ holds $X(A)$ and requests $B$ while $T_2$ holds $X(B)$ and requests $A$. Systems handle it by:

Starvation is a separate risk: a transaction can wait forever if the lock manager keeps granting S locks to newcomers while it waits for X, or if it is always chosen as the deadlock victim. Fair (FIFO) granting and counting how often a transaction has been a victim prevent it.

2PL produces a strict subset of CSR. Every 2PL schedule is conflict serializable, but not every conflict-serializable schedule can be produced by 2PL, because 2PL also fixes the serial order to the lock-point order and forbids a transaction from releasing one lock before acquiring another.

Testing whether a schedule could come from 2PL. Choose a lock point for each transaction; then each lock is held over the shortest interval allowed: from the earlier of its first use and the lock point, to the later of its last use and the lock point (for strict 2PL, X locks to the commit). Check interval compatibility per lock mode: S-to-X upgrades occur in the growing phase and X-to-S downgrades in the shrinking phase. A later write does not make the entire item interval X-locked. The schedule is 2PL-producible only when a compatible phase-respecting mode schedule exists; use mode-specific intervals, not one blanket X interval for an eventually written item.

Cascading aborts under basic 2PL. A transaction may release an X lock after its lock point but before commit; another transaction can then read the uncommitted value. Strict 2PL closes exactly this gap, which is why it is the variant used in practice.

Example 1: a 2PL transaction (Figure 2). $T_1$ reads $C$ and moves an amount from $A$ to $B$:

Locks held rise $1, 2, 3$; the lock point is $XL_1(B)$; then $2, 1, 0$. This is 2PL but not strict: $U_1(A)$ releases an X lock before $C_1$. The strict version keeps $U_1(C)$ where it is and moves both $U_1(A)$ and $U_1(B)$ after $C_1$. Releasing $A$ right after $W_1(A)$, before $XL_1(B)$, would break 2PL.

Example 2: locking without 2PL is not enough. $T_1$: $XL_1(A)\, W_1(A)\, U_1(A)\, XL_1(B)\, W_1(B)\, U_1(B)$; $T_2$: $XL_2(A)\, XL_2(B)\, W_2(A)\, W_2(B)\, U_2(A)\, U_2(B)$. The lock table allows $T_2$ to run entirely between $U_1(A)$ and $XL_1(B)$, giving $W_1(A)\, W_2(A)\, W_2(B)\, W_1(B)$: edges $T_1 \to T_2$ on $A$ and $T_2 \to T_1$ on $B$, a cycle. $T_1$ is not two-phase (it acquires $B$ after releasing $A$).

Example 3: CSR but not producible by 2PL. $S = R_1(A)\, W_2(A)\, R_3(B)\, W_1(B)$. Edges $T_1 \to T_2$ and $T_3 \to T_1$: conflict serializable, equivalent to $T_3 T_1 T_2$. Under 2PL, $T_1$ must release its lock on $A$ before $W_2(A)$ (second operation) but cannot hold its X lock on $B$ before $R_3(B)$ (third operation), so it would acquire after releasing. No 2PL execution produces $S$.

Example 4: basic but not strict 2PL. $S = R_1(A)\, W_1(A)\, R_2(A)\, C_1\, C_2$ is producible by basic 2PL ($T_1$ unlocks $A$ after $W_1(A)$) but not by strict 2PL, which keeps $X(A)$ until $C_1$ and so blocks $R_2(A)$. Moving $C_1$ before $R_2(A)$ gives a schedule strict 2PL allows.

Example 5: deadlock. $T_1$: $XL_1(A)$, then requests $XL_1(B)$; $T_2$: $XL_2(B)$, then requests $XL_2(A)$. Wait-for graph: $T_1 \to T_2$ and $T_2 \to T_1$, a cycle. Both obey 2PL. Conservative 2PL (lock both items before starting) or locking items in a fixed order ($A$ before $B$) would prevent it.

Example 6: shared locks allow concurrency. $T_1$ and $T_2$ both execute $SL(A)\, R(A)$. Both locks are granted at once. If $T_3$ then requests $XL_3(A)$, it waits until both release.

Example 7: strict but not rigorous. $S = R_1(A)\, W_2(A)\, C_2\, W_1(B)\, C_1$. Precedence: $T_1 \to T_2$ only, so $S$ is CSR, equivalent to $T_1 T_2$, although $T_2$ commits first. Strict 2PL can produce it:

$T_1$ reaches its lock point when it gets $XL_1(B)$, then releases its shared lock on $A$, which strict 2PL permits; its X lock on $B$ is held to $C_1$. Rigorous 2PL cannot produce $S$: $T_1$ would hold $SL_1(A)$ until $C_1$, so $W_2(A)$ could not run before $C_1$. This matches the rule that rigorous 2PL serializes in commit order, and here the serial order $T_1 T_2$ is the reverse of the commit order.

Example 8: one table for the three variants. Can the schedule be produced?

In the third row both shared locks coexist and $T_2$ upgrades to an X lock on $A$ after $C_1$. The last row is conflict serializable, which shows again that CSR does not imply producible by 2PL.

Common misconceptions.