Two-phase locking and its variants

Why it exists

Serializability tells us which schedules are acceptable but not how to produce them. The most common method is locking: a transaction must hold a lock on an item before accessing it, and the lock manager makes other transactions wait when their requests are incompatible. Locking alone is not enough (a transaction could lock, use and release an item, then lock another); the two-phase rule makes it enough.

Prerequisites

You need serializability (schedules and serializability) and the idea of a deadlock with a cycle of waiting (deadlock conditions).

Precise definitions

Lock modes. $\text{S}(X)$, a shared (read) lock, and $\text{X}(X)$, an exclusive (write) lock. A transaction needs an S or X lock to read and an X lock to write. Requests are granted by the lock manager according to the compatibility matrix:

Many readers can share an item; a writer is alone. A transaction that holds S may ask to upgrade to X; this succeeds only if nobody else holds a lock on the item.

The two-phase rule. A transaction is two-phase if all its lock requests come before its first unlock: a growing phase (acquire locks, release none) followed by a shrinking phase (release locks, acquire none). The moment of the last lock acquisition is the lock point.

Variants (they differ in when locks are released):

How it works

Why two-phase guarantees serializability

Theorem. Every schedule produced by transactions that obey the locking rules and are two-phase is conflict serializable, and the order of the lock points is an equivalent serial order.

Proof (lock points). Suppose the precedence graph has an edge $T_i \to T_j$: an operation of $T_i$ on $X$ came before a conflicting operation of $T_j$ on $X$. The locks are incompatible, so $T_i$ released its lock on $X$ before $T_j$ acquired its lock on $X$. By the two-phase rule $T_i$'s lock point is before that release, and $T_j$'s lock point is after that acquisition, so the lock point of $T_i$ is before the lock point of $T_j$. A cycle would give a lock point before itself; hence the graph has no cycle, and sorting transactions by lock point is a topological order. $\blacksquare$

The converse is false: a schedule from non-two-phase transactions may happen to be serializable (the "not two-phase" row below). The textbooks quote a theorem that for every transaction that is not two-phase there is another (two-phase) transaction and a schedule of the two that is not serializable.

What basic 2PL does not give

Each row is a legal lock schedule of one discipline. The basic 2PL sample is conflict serializable ($T_1 \to T_2$; lock points $T_1$ at its second lock, $T_2$ later, in that order) but not recoverable: $T_1$ releases the exclusive lock on $A$ before committing, $T_2$ reads that value and commits first. If $T_1$ aborted afterwards, $T_2$ would have committed a dirty read. Holding exclusive locks to the end (strict) prevents reads and writes of uncommitted data, so schedules are strict and no cascading aborts occur; holding all locks to the end (rigorous) also prevents the write-after-uncommitted-read. In the rigorous variant the serial order is the order of commits.

The last row is not two-phase ($T_1$ unlocks $A$ and later locks $B$) and yet its schedule is serializable: two-phase is sufficient, not necessary, for one schedule.

Systems normally use strict or rigorous 2PL.

A lock manager at work

$T_1$ locks and updates $A$ and then $B$; when $T_2$ asks for the lock on $A$ it waits, because $T_1$ holds an exclusive lock. After $T_1$ commits all its locks are released and $T_2$ proceeds. The result is the serial schedule $T_1\,T_2$.

When the two-phase rule is dropped

Every request is legal and each item is protected when it is touched, but $T_1$ releases $A$ and acquires $B$ later (not two-phase). The schedule has the conflicts $T_1 \to T_2$ (on $A$) and $T_2 \to T_1$ (on $B$): not serializable.

Deadlock

Locking can make transactions wait for each other forever. The wait-for graph has an edge $T_i \to T_j$ when $T_i$ waits for a lock held by $T_j$; a cycle is a deadlock (the circular wait of deadlock conditions).

$T_1$ holds $A$ and wants $B$; $T_2$ holds $B$ and wants $A$. Two-phase locking does not prevent deadlock. Another common source is the upgrade:

Both transactions hold shared locks on $A$ and both ask for the upgrade: each waits for the other to release. Taking the exclusive lock at the first access (when a read is followed by a write) avoids this particular deadlock.

Handling deadlock (as presented in the textbooks): prevention (conservative 2PL acquires everything at once, or impose an order on the items so that no cycle can form; the timestamp schemes wait-die and wound-wait decide who waits, quoted), detection (build the wait-for graph and look for a cycle, then choose a victim and roll it back, releasing its locks), or timeouts (abort a transaction that has waited too long). Conservative 2PL is deadlock free if all its locks are acquired atomically, but it needs to know the items in advance and reduces concurrency.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The wait-for graph is the resource allocation graph of the operating system with transactions as processes (deadlock conditions). Timestamp ordering (timestamp ordering) is a different way to guarantee serializability without locks. The classes of schedules strict 2PL produces are those of recoverability.

PYQs

A company maintains records of sales made by its
salespersons and pays them commission based on each
individual's total sales made in a year. This data is
maintained in a table with following schema:

salesinfo = (salespersonid, totalsales, commission)

In a certain year, due to better business results, the
company decides to further reward its salespersons by
enhancing the commission paid to them as per the
following formula:

If commission < = 50000, enhance it by 2%
If 50000 < commission < = 100000, enhance it by 4%
If commission > 100000, enhance it by 6%

The IT staff has written three different SQL scripts to
calculate enhancement for each slab, each of these scripts
is to run as a separate transaction as follows:

DATABASE MANAGEMENT  SYSTEM
  T1
Update salesinfo Set commission
= commission * 1.02 Where
commission < = 50000;
 T2
Update salesinfo Set commission
= commission * 1.04 Where
commission > 50000 and
commission is < = 100000;
 T3
Update salesinfo Set commission
= commission * 1.06 Where
commission > 100000;

Which of the following options of running these
transactions will update the commission of all
salespersons correctly

Which of the following statements about the Two Phase
Locking (2PL) protocol is/are TRUE?

Consider the following two statements about database
transaction schedules:

I. Strict two-phase locking protocol generates conflict
serializable schedules that are also recoverable.

II. Timestamp-ordering concurrency control protocol with
Thomas write rule can generate view serializable schedules
that are not conflict serializable.

Which of the above statements is/are TRUE?

Consider the following two phase locking protocol.
Suppose a transaction T accesses (for read or write
operations), a certain set of objects {O1,.....Ok}. This is
done in the following manner:

Step 1. T acquires exclusive locks to O1,....Ok in
increasing order of their addresses.

Step 2. The required operations are performed.

Step 3. All locks are released.

This protocol will ?

Which of the following concurrency control protocols
ensure both conflict serializability and freedom from
deadlock?

I. 2-phase locking

II. Time-stamp ordering

Consider the following two transactions: T1 and T2.

T1:
read(A);

read(B);

if A = 0 then B ← B + 1;
 write(B);
T2:
 read(B);
 read(A);
 if B ≠ 0 then A ← A -
1;
 write(A);

Which of the following schedules, using shared and
exclusive locks, satisfy the requirements for strict two-
phase
locking
(Strict
2PL)
for
the
above
transactions?

Self-check

Revision card

References