Neural Sync Active

28 - Concurrency Control

Registry Synced

28 - Concurrency Control

763 words

4 min read

Reading compass

Now · 🎯 Learning Objectives

28 - Concurrency Control

🎯 Learning Objectives

After reading this topic, you will be able to:

Explain shared and exclusive locks
Describe two-phase locking (2PL) and its variants
Understand deadlock prevention (wait-die, wound-wait) and detection
Apply timestamp ordering protocol

📖 Core Content

28.1 Lock-Based Protocols

Lock Type	Symbol	Allowed Operations
Shared (S)	Read-lock	Only read
Exclusive (X)	Write-lock	Read and write

Compatibility:

Requested	S (held)	X (held)
S	✓	✗
X	✗	✗

28.2 Two-Phase Locking (2PL)

(Diagram) Phase 1 (Growing): Can only acquire locks, cannot release Phase 2 (Shrinking): Can only release locks, cannot acquire Result: 2PL guarantees conflict serializability.

Variants

Protocol	Growing	Shrinking	Guarantees
2PL	Acquire all locks	Release any lock	Conflict serializable
Strict 2PL	Acquire all locks	Release X-locks only after commit	+ Recoverable
Rigorous 2PL	Acquire all locks	Release ALL locks only after commit	+ Cascadeless

28.3 Deadlock

Deadlock: Two or more transactions waiting for each other to release locks. (Diagram)

Prevention

Protocol	Rule	Who Gets Rolled Back?
Wait-Die (non-preemptive)	If older (smaller TS) waits, younger dies	Younger transaction
Wound-Wait (preemptive)	If older wounds younger, younger waits	Younger transaction

Where TS = timestamp (older = smaller). Wait-Die: T10 requests lock held by T20 → T10 waits. T20 requests lock held by T10 → T20 dies (and restarts with same TS). Wound-Wait: T10 requests lock held by T20 → T10 wounds (kills) T20. T20 requests lock held by T10 → T20 waits.

Detection: Wait-For Graph

Nodes = transactions
Edge $T_i \rightarrow T_j$ if $T_i$ is waiting for a lock held by $T_j$
A cycle indicates deadlock
Resolution: Kill the transaction with the least cost

28.4 Timestamp Ordering Protocol

Idea: Assign each transaction a unique timestamp (TS). Operations execute in timestamp order. Rules:

For each data item Q, track:
- $W_TS(Q)$ : largest TS of any transaction that wrote Q
- $R_TS(Q)$ : largest TS of any transaction that read Q
If $T$ issues $read(Q)$ and $TS(T) < W_TS(Q)$ : REJECT (rollback T)
If $T$ $T$ issues $write(Q)$ $w r i t e (Q)$ :
- If $TS(T) < R_TS(Q)$ or $TS(T) < W_TS(Q)$ : REJECT
- Otherwise: execute Result: Conflict serializable, no deadlocks (but may cause cascading rollbacks).

28.5 Validation (Optimistic) Protocol

Phases: Read → Validate → Write

Read: Transaction reads data, performs computation, stores updates in private workspace
Validate: Check if serialization order can be maintained
Write: If validation passes, write changes to database Best for: Low-conflict environments (mostly reads).

📐 Key Formulas

Protocol	Guarantees	Problem
2PL	Conflict serializable	Deadlocks
Strict 2PL	+ Recoverable	Deadlocks
Timestamp ordering	Conflict serializable, no deadlocks	Cascading rollbacks
Validation	Serializability	Poor under high conflict

⚠️ Common Pitfall

The Mistake: Confusing wait-die with wound-wait. Memory Aid:

Wait-Die: If older, WAIT → younger DIE
Wound-Wait: If older, WOUND (kill) → younger WAIT In both cases, the older timestamp wins, but the mechanism differs.

📝 Practice Questions

Q1. What is the difference between shared and exclusive locks?

Answer

Shared (S): Allows reading only. Multiple transactions can hold shared locks simultaneously.

Exclusive (X): Allows reading and writing. Only one transaction can hold an exclusive lock at a time.

Q2. Explain the two phases of 2PL.

Answer

Growing phase: Transaction acquires locks; cannot release any

Shrinking phase: Transaction releases locks; cannot acquire any new ones

The lock point is the point where the transaction holds all needed locks. 2PL guarantees conflict serializability.

Q3. Describe the wait-die deadlock prevention scheme.

Answer

When Ti requests a lock held by Tj:

If TS(Ti) < TS(Tj) (Ti is older): Ti waits

If TS(Ti) > TS(Tj) (Ti is younger): Ti dies (aborts and restarts with same TS)

"Older waits, younger dies." Non-preemptive (no transaction is killed while holding a lock).

Q4. What does strict 2PL add to basic 2PL?

Answer

Strict 2PL: Exclusive locks are released only AFTER the transaction commits (not during the shrinking phase). This ensures recoverability because no other transaction can read uncommitted data.

Rigorous 2PL: ALL locks (shared and exclusive) are released only after commit. Ensures cascadeless schedules.

Q5. How does timestamp ordering prevent deadlocks?

Answer

Timestamp ordering doesn't use locks — it uses timestamps to determine execution order. If an operation arrives "too late" (out of timestamp order), the transaction is rolled back. Since there are no locks, there's no waiting and therefore no deadlocks.

Trade-off: Causes more rollbacks (and cascading rollbacks) than locking.

🔗 Cross-References

Previous Topic: 27 - Serializability
Next Topic: 29 - Backup & Recovery
Related: 26 - Transactions (isolation requires concurrency control)
Textbook: Chapter 15 (Concurrency Control) Join Discord Previous27 - SerializabilityNext29 - Backup & Recovery