2pl Variants - Learning Module

Loading content...

0/252

Conservative Two-Phase Locking (Conservative 2PL)

Eliminating Deadlocks by Design

Strict 2PL and Rigorous 2PL solve the recoverability problem, but they share a dangerous vulnerability: deadlocks. When two transactions each hold locks that the other needs, both block forever, unable to proceed. Every production database must detect and break these deadlocks—typically by aborting one transaction and rolling back its work.

But what if deadlocks were impossible? What if, by design, the locking protocol guaranteed that circular wait conditions could never form?

Conservative Two-Phase Locking (also called Static 2PL or Pre-claiming 2PL) achieves exactly this. It requires that a transaction acquire ALL its locks at the very beginning, before executing any operations. If any lock cannot be obtained, the transaction doesn't start—it waits until all locks are available simultaneously.

This radical approach trades flexibility for certainty: you must know every data item you'll access before you begin, but in exchange, you'll never be aborted due to deadlock.

What You Will Learn

By the end of this page, you will understand why Conservative 2PL is deadlock-free, how pre-declaring all locks at transaction start prevents circular wait conditions, the significant practical challenges that limit its adoption, and the specific scenarios where this approach is actually viable and beneficial.

The Deadlock Problem Revisited

Before diving into Conservative 2PL's solution, let's crystallize why deadlocks occur in standard 2PL protocols. Understanding the conditions that create deadlocks reveals how Conservative 2PL eliminates them.

Classic Deadlock Scenario in Strict 2PL
Time	T₁	T₂	Locks Held
t₁	lock-X(A)		A: T₁
t₂		lock-X(B)	A: T₁, B: T₂
t₃	read(A), compute		A: T₁, B: T₂
t₄		read(B), compute	A: T₁, B: T₂
t₅	lock-X(B) BLOCKED!		A: T₁, B: T₂ — T₁ waits
t₆		lock-X(A) BLOCKED!	A: T₁, B: T₂ — T₂ waits
t₇	DEADLOCK	DEADLOCK	Circular wait: T₁→T₂→T₁

The Four Conditions for Deadlock:

Computer science identifies four necessary conditions that must all hold simultaneously for a deadlock to occur:

Mutual Exclusion — Resources (locks) cannot be shared; if one transaction holds a lock, others must wait
Hold and Wait — Transactions hold resources while waiting for additional resources
No Preemption — Resources cannot be forcibly taken away; transactions must release voluntarily
Circular Wait — A cycle exists in the wait-for graph: T₁ waits for T₂, T₂ waits for T₃, ... Tₙ waits for T₁

Eliminate ANY one of these conditions, and deadlocks become impossible.

Conservative 2PL's Strategy

Conservative 2PL eliminates the 'Hold and Wait' condition. A transaction never holds any locks while waiting for more—it either has ALL its locks or NONE of them. Without hold-and-wait, circular waits cannot form, and deadlocks are impossible.

Conservative 2PL: Pre-Claiming All Locks

Conservative Two-Phase Locking modifies the standard 2PL protocol with a radical requirement:

Before a transaction begins execution, it must acquire ALL locks for ALL data items it will access throughout its entire execution.

This means:

The transaction must declare its complete read-set and write-set upfront
All locks are requested atomically as a batch
If any lock is unavailable, the transaction waits without holding any locks
Only when ALL locks are granted simultaneously does execution begin
After execution completes, all locks are released together

Formal Definition

Conservative 2PL = 'A transaction T must lock all data items in its read-set and write-set before T performs any read/write operations. T holds these locks until it commits or aborts, at which point all locks are released together.'

Converting Mermaid diagram...

The Lock Acquisition Protocol:

Procedure: ConservativeAcquire(transaction T, lockSet L)
    WHILE true:
        IF all locks in L are available:
            Atomically acquire all locks in L
            RETURN success
        ELSE:
            Release any locks (should have none)
            Wait for notification that a lock became available

The key insight is that the transaction NEVER holds a subset of its locks while waiting. It's an all-or-nothing acquisition. This eliminates the hold-and-wait condition that enables deadlocks.

Why Conservative 2PL Is Deadlock-Free

Let's rigorously prove that Conservative 2PL cannot produce deadlocks by showing that circular wait conditions cannot form.

Proof by Contradiction

Assume a deadlock exists in a Conservative 2PL system. We'll show this leads to a contradiction, proving deadlocks are impossible.

Proof:

Assume deadlock exists. Then there is a cycle of transactions:

T₁ → T₂ → T₃ → ... → Tₙ → T₁

where T₁ is waiting for a lock held by T₂, T₂ is waiting for a lock held by T₃, and so on.

Key Observation: In Conservative 2PL, a transaction can only be in one of two states:

Waiting — Has no locks, waiting to acquire all locks atomically
Executing — Has all locks, performing operations

Now analyze the cycle:

T₁ is waiting for T₂. This means T₁ does not have all its locks (otherwise it would be executing). Under Conservative 2PL, if T₁ doesn't have all locks, it has no locks.
But T₁ → T₂ means T₂ is waiting for a lock held by T₁.
This is a contradiction: T₁ holds a lock that T₂ needs, but T₁ is also waiting, which means T₁ has no locks.

Therefore, no such cycle can exist. ∎

Alternative Understanding:

Think of it this way: for a deadlock cycle to form, each transaction in the cycle must:

Hold at least one resource another transaction needs
Wait for at least one resource another transaction holds

But Conservative 2PL's rule is: you cannot hold any resources while waiting for resources.

If you're waiting, you hold nothing. If you hold anything, you hold everything you need and aren't waiting. There's no state where you're both holding and waiting—and without that state, cycles cannot form.

Deadlock Prevention Properties

•No Hold-and-Wait — Transactions never hold partial lock sets while waiting for more locks
•Atomic All-or-Nothing — Lock acquisition is a single atomic operation: all locks or no locks
•No Incremental Acquisition — Cannot acquire locks during execution; all known upfront
•Simple Wait State — Waiting transactions have no resources, so they cannot block others
•Progress Guarantee — At least one transaction can always proceed (the one whose locks are all available)

The Pre-Declaration Challenge

Conservative 2PL's deadlock freedom comes at a significant cost: you must know everything you'll access before you start. This requirement is often impractical or impossible in real applications.

The Fundamental Problem

Many transactions cannot determine their complete access set in advance. Data-dependent control flow means the items accessed depend on values that are only known during execution—which requires locks to read—creating a chicken-and-egg problem.

Examples of Data-Dependent Access:

data_dependent_access.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
-- Example 1: Conditional Access
-- Cannot know department_id until we read the employee
BEGIN TRANSACTION;
    SELECT department_id INTO :dept FROM employees WHERE id = :emp_id;
    -- Now we need to lock department :dept... but we didn't know which one at start!
    UPDATE departments SET employee_count = employee_count + 1 WHERE id = :dept;
COMMIT;
 
-- Example 2: Tree Traversal
-- Which nodes we visit depends on values at each level
BEGIN TRANSACTION;
    SELECT left_child, right_child INTO :l, :r FROM tree_nodes WHERE id = :root;
    IF :search_value < :node_value THEN
        -- Need to lock left subtree... determined dynamically
        SELECT * FROM tree_nodes WHERE id = :l;
    ELSE
        -- Need to lock right subtree instead
        SELECT * FROM tree_nodes WHERE id = :r;
    END IF;
COMMIT;
 
-- Example 3: Join-Based Access
-- Which order_items we access depends on which orders exist
BEGIN TRANSACTION;
    SELECT order_id FROM orders WHERE customer_id = :cust AND status = 'pending';
    -- Now we need order_items for those specific order_ids...
    UPDATE order_items SET status = 'shipped' WHERE order_id IN (:found_orders);
COMMIT;

The Over-Locking Workaround:

One approach to the pre-declaration problem is over-locking: lock more than you need to ensure you've covered all possibilities.

Scenario	Precise Locking	Over-Locking
Access employee's department	Lock that 1 department	Lock ALL departments
Traverse tree to find node	Lock nodes traversed	Lock ENTIRE tree
Update orders for a customer	Lock their specific orders	Lock ALL orders in system

The Problem: Over-locking dramatically reduces concurrency. If you lock 100 items when you only need 1, you block 99x more transactions than necessary. The cure can be worse than the disease.

When Pre-Declaration Fails

•Data-dependent control flow (if-then-else based on values)
•Dynamic query generation (user-driven filters)
•Graph/tree traversals (paths discovered at runtime)
•Aggregations over unknown result sets
•Foreign key chains (parent → child → grandchild)

When Pre-Declaration Works

•Static transactions (same access pattern every time)
•Primary-key only access (IDs known upfront)
•Predefined stored procedures
•Batch processing with known input sets
•Configuration updates (known key set)

Implementation Strategies

For applications where Conservative 2PL is viable, the implementation requires careful design of the lock acquisition mechanism to ensure atomicity and fairness.

conservative_2pl_implementation.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Conservative 2PL Lock Manager - Pseudocode
 
class Conservative2PLLockManager {
    locks: Map<DataItem, LockEntry>
    waitQueue: PriorityQueue<Transaction>  // Fairness ordering
    
    // Request all locks atomically - the core operation
    func requestAllLocks(txn: Transaction, lockRequests: Set<(DataItem, LockMode)>): void {
        LOOP:
            // Check if ALL requested locks can be granted
            canGrantAll = true
            for (item, mode) in lockRequests:
                if not canGrant(item, mode, txn):
                    canGrantAll = false
                    break
            
            if canGrantAll:
                // Atomically acquire ALL locks
                for (item, mode) in lockRequests:
                    grantLock(item, mode, txn)
                return
            else:
                // Cannot grant all - wait WITHOUT holding any locks
                addToWaitQueue(txn, lockRequests)
                waitForNotification(txn)
                // When notified, retry the entire loop
    }
    
    // Check if a lock can be granted (considering waiting transactions)
    func canGrant(item: DataItem, mode: LockMode, txn: Transaction): bool {
        lock = locks[item]
        
        // Check for conflicting holders
        if mode == EXCLUSIVE:
            return lock.noOtherHolders(txn.id) AND noHigherPriorityWaiter(item, txn)
        else:  // SHARED
            return lock.noExclusiveHolder(txn.id) AND noHigherPriorityExclusiveWaiter(item, txn)
    }
    
    // Grant a specific lock
    func grantLock(item: DataItem, mode: LockMode, txn: Transaction): void {
        if mode == EXCLUSIVE:
            locks[item].setExclusive(txn.id)
        else:
            locks[item].addShared(txn.id)
    }
    
    // Release all locks - only on commit/abort
    func releaseAllLocks(txn: Transaction): void {
        for item in txn.heldLocks:
            locks[item].release(txn.id)
            notifyWaiters(item)
    }
    
    // Commit with lock release
    func commit(txn: Transaction): void {
        writeCommitRecord(txn)
        forceLogToDisk()
        releaseAllLocks(txn)
    }
    
    // Abort with undo and lock release
    func abort(txn: Transaction): void {
        undoChanges(txn)
        writeAbortRecord(txn)
        releaseAllLocks(txn)
    }
}

Critical Implementation Considerations:

•Atomic Check-and-Acquire — The check for all locks available and acquisition must be atomic. Otherwise, between checking and acquiring, another transaction might grab a lock.
•Fairness/Starvation Prevention — Without careful design, a transaction needing many locks might always lose to smaller transactions. Use priority queues based on arrival time or lock count.
•Efficient Waiting — Transactions should wait efficiently (condition variables) and be notified when relevant locks become available, not poll repeatedly.
•Ordered Lock Requests — Store lock requests in a canonical order to prevent issues when multiple waiters compete.
•Dead-on-Arrival Detection — If a transaction requests an impossible combination (e.g., two transactions each need exclusive access to A and B), detect this early rather than waiting forever.

The Starvation Risk

While Conservative 2PL prevents deadlock, it doesn't automatically prevent starvation. A transaction needing locks on [A, B, C, D] might wait forever if there's always at least one small transaction holding one of those locks. Implement fairness mechanisms to ensure eventual progress.

Performance Analysis

Conservative 2PL's performance profile is quite different from other 2PL variants. Understanding these characteristics helps determine when it's appropriate.

Performance Characteristics Comparison
Metric	Strict 2PL	Rigorous 2PL	Conservative 2PL
Deadlock handling	Detection + Recovery	Detection + Recovery	None needed!
Deadlock overhead	Timeout/WFG checks	Timeout/WFG checks	Zero
Transaction rollbacks	Deadlock victims + failures	Deadlock victims + failures	Failures only
Start latency	Low (immediate start)	Low (immediate start)	High (wait for all locks)
Wasted work	Work done before deadlock abort	Work done before deadlock abort	Zero (no partial execution)
Concurrency (general)	High	Medium-High	Low-Medium
Concurrency (static workloads)	High	Medium-High	Comparable (known sets help)
Resource utilization	Efficient	Efficient	Can waste lock capacity

When Conservative 2PL Wins:

Consider a system with:

High transaction abort cost (complex transactions, external side effects)
High deadlock frequency (many transactions, much lock overlap)
Predictable access patterns (static or nearly static)
Priority on completion guarantee over throughput

In such systems, the cost of deadlock detection, victim selection, and rollback can exceed the cost of upfront lock acquisition waiting. The guarantee of "once started, will complete" is valuable.

Quantitative Example:

Assume:

Average transaction takes 50ms to execute
Deadlock rate is 5% of transactions
Deadlock detection adds 10ms overhead per transaction
Rollback and retry costs 100ms average

Strict 2PL cost per transaction:

Base: 50ms
Detection overhead: 10ms × 1.0 = 10ms
Rollback amortized: 100ms × 0.05 = 5ms
Total: 65ms average

Conservative 2PL cost per transaction:

Lock acquisition wait: 20ms average (assume)
Base: 50ms
No deadlock overhead
Total: 70ms average

In this scenario, Conservative 2PL is slightly worse. But if deadlock rate rises to 15%:

Strict 2PL: 50 + 10 + (100 × 0.15) = 75ms
Conservative 2PL: 20 + 50 = 70ms ← Now wins!

The No-Wasted-Work Advantage

In Conservative 2PL, a transaction never does work that will be rolled back due to deadlock. Every computation, every disk I/O, every network call within the transaction contributes to the final committed result. For expensive transactions with side effects, this guarantee is invaluable.

Practical Applications

Despite its limitations, Conservative 2PL finds application in specific domains where its properties are particularly valuable.

Conservative 2PL Application Domains
Domain	Why Conservative 2PL Suits	Typical Pattern
Batch Processing	All input known before processing; predictable access	Lock all affected rows, process entire batch, release
Configuration Management	Known key set; rare but critical updates	Lock config keys, apply changes atomically, release
Resource Reservation	Known resources to reserve; must be all-or-nothing	Lock all needed resources, confirm availability, book
Stored Procedures	Static code paths; access set derivable from parameters	Analyze procedure, pre-acquire locks, execute
Embedded Systems	Limited resources; deadlock recovery expensive	Simple workloads justify pre-acquisition
Game State Updates	Known entity set per tick; consistency critical	Lock all game objects in update, apply physics, render

Case Study: Batch Processing System

Consider a nightly batch job that:

Reads customer records to calculate loyalty points
Updates account balances based on calculations
Generates statements for each customer

The access set is known from the input: all customers in the batch file.

Conservative 2PL Approach:

1. Parse batch file to extract all customer IDs
2. Request locks on: customer table rows, account table rows,
   statement table for inserts
3. Wait until all locks granted (during off-peak hours, this is fast)
4. Process entire batch with guaranteed completion
5. Commit and release all locks

Benefits:

No partial processing if something fails mid-batch
No deadlocks with concurrent OLTP (which can wait or use different data)
Guaranteed completion time once started
Simple error handling: if it fails, nothing was done

Hybrid Approaches

Many practical systems use Conservative 2PL for specific transaction types (batch jobs, admin operations) while using Strict 2PL for general OLTP. The batch job pre-acquires locks and runs without deadlock risk, while normal transactions handle their own deadlock recovery.

Summary: Conservative 2PL Fundamentals

Conservative 2PL takes a radically different approach to locking, trading flexibility for guaranteed deadlock freedom. Let's consolidate the key concepts:

Key Takeaways

•Pre-acquisition is the key — All locks must be acquired before any transaction work begins. This eliminates the hold-and-wait condition.
•Deadlock impossible by design — With no hold-and-wait, circular wait conditions cannot form. No deadlock detection or recovery needed.
•No wasted work — Transactions never execute partially and then roll back due to deadlock. Every executed operation contributes to the final result.
•Pre-declaration is limiting — Transaction must know its complete access set upfront, which is often impossible with data-dependent logic.
•Over-locking reduces concurrency — When exact access is unknown, locking more than needed prevents deadlocks but blocks other transactions unnecessarily.
•Suited for static workloads — Batch processing, configuration management, and stored procedures with known access patterns are ideal applications.

What's Next:

We've now explored three major 2PL variants: Strict, Rigorous, and Conservative. The next page provides a comprehensive comparison of all 2PL variants, analyzing their guarantees, performance characteristics, and trade-offs to help you choose the right protocol for different scenarios.

Page Complete

You now understand Conservative Two-Phase Locking—the deadlock-free variant that requires pre-declaring all lock needs. This knowledge helps you design systems where guaranteed completion and zero deadlock overhead are more important than maximum concurrency.