Two-phase locking: growing/shrinking, lock point, guarantees

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Which lock modes are compatible? from Lesson 6.6.1
2. What does an acyclic precedence graph mean? from Lesson 6.4.2
3. Which recoverability class forbids reading uncommitted data? from Lesson 6.5.1

1 · The Hook

The problem in Lesson 6.6.1 was a transaction that released a lock and later acquired another. Two-phase locking forbids exactly that: first only acquire, then only release. This simple rule guarantees conflict serializability. GATE asks whether a given transaction or schedule follows 2PL and what 2PL does and does not guarantee.

2 · Predict First

T: lock-S(A) R(A) lock-X(B) unlock(A) W(B) unlock(B). Does T follow two-phase locking? What if lock-X(B) came after unlock(A)?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Yes: all locks (S(A), X(B)) are acquired before the first unlock. If lock-X(B) came after unlock(A), T would acquire after releasing: not 2PL.

Two-phase locking (2PL)

Each transaction has two phases:

1. Growing phase: may acquire locks (and upgrade), may not release any.
2. Shrinking phase: may release locks (and downgrade), may not acquire any.

The moment a transaction acquires its last lock (the end of the growing phase) is its lock point.

Guarantee

If every transaction follows 2PL, every schedule produced is conflict serializable, and an equivalent serial order is the order of the transactions' lock points.

Why: if Ti → Tj in the precedence graph, Tj had to wait for a lock Ti released, so Ti's lock point comes first. A cycle would need a lock point before itself.

What 2PL does not guarantee

• Freedom from deadlock: T1 holds X(A) and wants X(B); T2 holds X(B) and wants X(A). Both are in their growing phase; both wait forever.
• Recoverability / no cascading rollback: under basic 2PL a transaction may release an X lock before committing; another transaction can then read the uncommitted value (dirty read) and commit first.
• Every conflict serializable schedule is not reachable by 2PL: 2PL schedules are a proper subset of CS schedules.

Checking a transaction

Scan its operations: once an unlock appears, no lock may follow. Lock conversions count: an upgrade (S → X) is an acquisition (growing phase only).

Checking a schedule against 2PL

"Could this schedule have been produced under 2PL?" Try to place locks and unlocks: each transaction needs X locks around its writes and S around its reads, conflicting locks cannot overlap, and no transaction may acquire after releasing. If a conflict forces a transaction to release a lock and later get a new one, the schedule is not 2PL-possible.

4 · Visual

number of
locks held
   ^            lock point
   |             _______
   |           /         \
   |         /             \
   |       /                 \
   |_____/                     \______> time
     growing phase    shrinking phase
     (only acquire)   (only release)

5 · Worked Examples

Example 1 Easy

Is this 2PL? lock-X(A) W(A) lock-S(B) R(B) unlock(A) unlock(B).

Solution

Yes: both locks before the first unlock.

Example 2 Medium

Is this 2PL? lock-S(A) R(A) unlock(A) lock-X(B) W(B) unlock(B).

Solution

No: lock-X(B) comes after unlock(A).

Example 3 GATE

Under 2PL, T1 reaches its lock point at time 5, T2 at time 9, T3 at time 3. Which serial order is the schedule equivalent to?

Solution

Order of lock points: T3, T1, T2.

8 · Connect the Dots

Lesson 6.6.1 gave locks; this lesson gave the release rule that makes them produce serializable schedules. Next: stronger variants of 2PL that also give strict schedules or freedom from deadlock.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — 2PL

Which transaction violates 2PL?

1. (A) lock-S(A) lock-X(B) unlock(A) unlock(B)
2. (B) lock-X(A) unlock(A) lock-X(B) unlock(B)
3. (C) lock-S(A) lock-S(B) unlock(B) unlock(A)
4. (D) lock-X(A) lock-X(B) unlock(B) unlock(A)

Q2 · MCQ · 1 mark(s) — Guarantee

Basic 2PL guarantees:

1. (A) strict schedules
2. (B) freedom from deadlock
3. (C) conflict serializability
4. (D) cascadeless schedules

Q3 · MCQ · 2 mark(s) — Order

Under 2PL, lock points occur in the order T2, T3, T1. The schedule is conflict equivalent to:

1. (A) T1, T2, T3
2. (B) T3, T2, T1
3. (C) T2, T3, T1
4. (D) any serial order

Q4 · MSQ · 2 mark(s) — Facts

Which are true?

1. (A) An S → X upgrade is allowed only in the growing phase.
2. (B) 2PL can lead to deadlock.
3. (C) Every conflict serializable schedule can be produced by 2PL.
4. (D) Every 2PL schedule is conflict serializable.

Q5 · MCQ · 2 mark(s) — Deadlock

T1: lock-X(A) … wants X(B). T2: lock-X(B) … wants X(A). Both follow 2PL. What happens?

1. (A) 2PL forbids this situation
2. (B) Both proceed
3. (C) Deadlock
4. (D) T1 commits first automatically

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

two-phase locking (2PL)growing phaseshrinking phaselock point2PL ⇒ conflict serializability2PL deadlock