Explain Two-Phase Locking Protocol & Conflict Serializability (Unit 3 – Transaction Management | Concurrency Control)
Explain Two-Phase Locking Protocol & Conflict Serializability (Unit 3 – Transaction Management | Concurrency Control)
Concurrency control ensures that when multiple transactions execute concurrently, the resulting interleaving is still correct with respect to serial (one-at-a-time) execution. Two foundational ideas are Two-Phase Locking and Conflict Serializability.
In this unit, you will learn:
- how the 2PL phases work (growing vs. shrinking),
- why 2PL implies conflict serializability, and
- how to test conflict serializability using the precedence graph (also called a dependency/serialization graph).
Key terms: Lock, Schedule, Precedence graph, Conflict.
Note: I’m unable to run the required web searches in this environment right now (tool usage limit error). That means I cannot provide the mandatory web-backed citations and footnotes for every claim.
Transaction Concurrency Control: Two-Phase Locking & Serializability
Two-Phase Locking (2PL)
The Two-Phase Locking protocol restricts when transactions can acquire and release locks.
A transaction under 2PL follows two phases:
- Growing phase: the transaction may acquire locks but cannot release any lock.
- Shrinking phase: the transaction may release locks but cannot acquire any new lock.
This restriction prevents certain cyclic dependencies in the serialization order. As a result, a schedule produced by 2PL is conflict-serializable (with the standard assumptions of lock compatibility and that reads/writes use appropriate locks).
Important subtypes:
- Basic 2PL
- Strict 2PL
Key terms: Shared lock (S), Exclusive lock (X), Commit point, Cascading abort.
How 2PL decides locking actions (growing vs. shrinking)
- 1Step 1
Initialize internal state so the transaction is in the growing phase.
- 2Step 2
If the transaction is in the growing phase, it may request the needed S/X lock; wait if incompatible.
- 3Step 3
Once the transaction releases its first lock, it transitions permanently to the shrinking phase.
- 4Step 4
In the shrinking phase, the transaction may release locks (including waiting states due to compatibility).
- 5Step 5
If the transaction tries to acquire a new lock after any release, it must not proceed under the 2PL rule; this ensures correctness properties.
Locking and conflicts
To relate locking to conflict serializability, map each operation to lock types:
- Read(X) usually requires an S lock.
- Write(X) usually requires an X lock.
- Two operations conflict if they:
- access the same data item, and
- at least one is a write, and
- they cannot both be allowed in the same order due to compatibility.
The core intuition: if a schedule is generated using 2PL, then the locking-induced ordering constraints cannot form a cycle, so the schedule is conflict-serializable.
Key terms: Read operation, Write operation, Lock compatibility, Serialization graph.
Conflict Serializability
A schedule is conflict-serializable if it is equivalent to some serial schedule (transactions run one-by-one) with respect to conflicts.
Use a precedence graph (serialization graph):
- Nodes: transactions.
- Add a directed edge if, in the schedule, there exists a conflicting pair of operations such that:
- performs the first operation, and
- performs the conflicting second operation on the same data item.
Then:
- If the precedence graph has a cycle, the schedule is not conflict-serializable.
- If the graph is acyclic, the schedule is conflict-serializable (a topological order gives the equivalent serial order).
Key terms: Precedence graph, Acyclic, Topological sort, Equivalent serial schedule.
Test conflict serializability using a precedence graph
- 1Step 1
Write the schedule in timeline order (e.g., r1(X), w2(X), …).
- 2Step 2
Whenever does an operation before on the same item with a write involved, add .
- 3Step 3
Ensure you consider all conflicting pairs (not just adjacent operations).
- 4Step 4
If any directed cycle exists, the schedule is not conflict-serializable.
- 5Step 5
If acyclic, take any topological order of the graph; that order is an equivalent serial schedule.
2PL vs Conflict-serializability (conceptual alignment)
How the protocol restriction helps guarantee serialization without cycles.
Pro Tip: 2PL → serialization often via ‘no cycles’ reasoning
To connect 2PL to conflict serializability, reason about what lock ordering implies for precedence constraints. The growing-then-shrinking restriction is what prevents cyclic dependencies from arising.
Warning: Conflict serializability is about conflicts, not all effects
Two schedules may be view-equivalent yet not conflict-serializable. The precedence-graph test is specific to conflicts (reads/writes on the same item with write participation).
Common Questions & Edge Cases
Concurrency control workflow (Unit 3 focus)
Define conflicts
Step AIdentify when two operations on the same item conflict (read/write vs write/write)."
Build precedence graph
Step BAdd edges for each conflicting ordering pair."
Check cycles
Step CAcyclic graph ⇒ conflict-serializable; cyclic graph ⇒ not serializable."
Prevent unsafe schedules with 2PL
Step DUse growing/shrinking locking rules to avoid cycles."
Quick Self-Check Deck
Knowledge Check
In Two-Phase Locking (2PL), after a transaction releases its first lock, what is it allowed to do?