Page 8: Locking Mechanisms

Basic Locking Strategy

Simple Approach: Lock entire database

• Pros: Guarantees serializability

• Cons: Only one transaction at a time = terrible performance

Two-Phase Locking (2PL)

Better approach: Lock only needed data items

Rules:

1. Growing Phase: Can acquire locks, cannot release any

2. Shrinking Phase: Can release locks, cannot acquire new ones

Example:

CopyT₁: lock(A), read(A), lock(B), write(A), read(B), write(B)
    ↑ Growing Phase ↑        ↑ Shrinking Phase ↑
    unlock(A), unlock(B)

Lock Types

Shared Lock (S-Lock) - for reading

• Multiple transactions can hold shared lock on same item

• Example: 5 people can read account balance simultaneously

Exclusive Lock (X-Lock) - for writing

• Only one transaction can hold exclusive lock

• Example: Only 1 person can update account balance at a time

Lock Compatibility Matrix:

Copy          S    X
    S     ✓    ✗
    X     ✗    ✗

Timestamp-Based Concurrency Control

How It Works:

1. Each transaction gets unique timestamp when it starts

2. Each data item tracks:

   • Read Timestamp (RTS): Latest transaction that read it

   • Write Timestamp (WTS): Latest transaction that wrote it

Rules:

• Read Rule: Can read only if your timestamp > WTS

• Write Rule: Can write only if your timestamp > both RTS and WTS

• Violation: Transaction aborted and restarted with new timestamp

Example:

CopyT₁ (timestamp = 100) wants to read A
A's WTS = 90  → Allow (100 > 90) ✓
A's RTS = max(current RTS, 100) = 100

T₂ (timestamp = 80) wants to write A  
A's RTS = 100 → Reject (80 < 100) ✗
T₂ gets aborted and restarted

Deadlock Example

CopyT₁: lock(A)     lock(B) ← waiting for T₂ to release B
T₂: lock(B)     lock(A) ← waiting for T₁ to release A
Both wait forever = Deadlock!

Solutions:

1. Prevention: Order locks (always lock A before B)

2. Detection: Find cycles in wait-for graph, abort one transaction

3. Timeout: Abort transactions that wait too long