Two-Phase Locking (2PL) - Shared, Exclusive, Deadlock

▶

Steps

setup

Initialize Lock Table

The lock table is initialized with data items A and B, each with no locks held and empty waiting queues. Transactions T1, T2, and T3 are ready to request locks.

💡 Starting with an empty lock table clarifies how locks accumulate and how waiting queues form as transactions request locks.

Line:

lock_table = {'A': {'locks': [], 'waiting': []}, 'B': {'locks': [], 'waiting': []}}

💡 The lock table structure is the foundation for managing concurrent access and detecting conflicts.

insert

Transaction T1 Requests Shared Lock on A

Transaction T1 requests a shared lock on data item A. Since no locks are held on A, the lock is granted immediately.

💡 Granting shared locks when no conflicts exist shows the optimistic concurrency control aspect of 2PL.

Line:

if lock_table['A']['locks'] == []:
    lock_table['A']['locks'].append(('T1', 'S'))

💡 Shared locks allow multiple transactions to read concurrently without conflict.

insert

Transaction T2 Requests Shared Lock on A

Transaction T2 requests a shared lock on data item A. Since T1 holds a shared lock, T2's shared lock is compatible and granted immediately.

💡 Multiple shared locks can coexist, enabling concurrent reads.

Line:

if all(lock[1] == 'S' for lock in lock_table['A']['locks']):
    lock_table['A']['locks'].append(('T2', 'S'))

💡 Shared locks do not block each other, allowing concurrent read access.

insert

Transaction T3 Requests Exclusive Lock on A

Transaction T3 requests an exclusive lock on data item A. Since T1 and T2 hold shared locks, T3's exclusive lock request conflicts and must wait.

💡 Exclusive locks require exclusive access, so conflicting shared locks block the request.

Line:

if any(lock[1] == 'S' for lock in lock_table['A']['locks']):
    lock_table['A']['waiting'].append(('T3', 'X'))

💡 Exclusive locks block other locks and must wait until all conflicting locks are released.

insert

Transaction T1 Requests Shared Lock on B

Transaction T1 requests a shared lock on data item B. Since B has no locks, the shared lock is granted immediately.

💡 Lock requests on different data items are independent and can proceed concurrently.

Line:

if lock_table['B']['locks'] == []:
    lock_table['B']['locks'].append(('T1', 'S'))

💡 Locks are managed per data item, allowing parallelism across different items.

insert

Transaction T2 Requests Exclusive Lock on B

Transaction T2 requests an exclusive lock on data item B. Since T1 holds a shared lock, T2's exclusive lock request conflicts and must wait.

💡 Exclusive lock requests must wait if any shared or exclusive locks exist.

Line:

if lock_table['B']['locks']:
    lock_table['B']['waiting'].append(('T2', 'X'))

💡 Waiting queues serialize conflicting lock requests to maintain consistency.

delete

Transaction T1 Releases Shared Lock on A

Transaction T1 releases its shared lock on data item A. This may allow waiting transactions to proceed.

💡 Releasing locks triggers checks to grant waiting lock requests.

Line:

lock_table['A']['locks'].remove(('T1', 'S'))

💡 Lock release is the key event that can unblock waiting transactions.

insert

Grant Exclusive Lock to T3 on A After Release

After T1 releases its lock, T3's exclusive lock request on A is checked. Since only T2 holds a shared lock, T3 still must wait.

💡 Exclusive locks require all conflicting locks to be released before granting.

Line:

if lock_table['A']['locks'] == [('T2', 'S')]:
    # T3 still waits

💡 All conflicting locks must be released before exclusive lock grants.

delete

Transaction T2 Releases Shared Lock on A

Transaction T2 releases its shared lock on A, freeing the data item from shared locks.

💡 Releasing the last conflicting lock can unblock exclusive lock requests.

Line:

lock_table['A']['locks'].remove(('T2', 'S'))

💡 Exclusive locks can now be granted after all shared locks are released.

insert

Grant Exclusive Lock to T3 on A

With no conflicting locks on A, T3's exclusive lock request is granted and removed from the waiting queue.

💡 Granting exclusive locks after waiting ensures serializability and prevents conflicts.

Line:

lock_table['A']['locks'].append(('T3', 'X'))
lock_table['A']['waiting'].remove(('T3', 'X'))

💡 Waiting queues are processed in order to maintain fairness and correctness.

insert

Deadlock Scenario: T3 Requests Exclusive Lock on B

Transaction T3 requests an exclusive lock on B. T1 holds a shared lock, and T2 is waiting for exclusive lock on B, creating a cycle of waiting.

💡 Deadlocks occur when transactions wait on each other in a cycle, blocking progress.

Line:

lock_table['B']['waiting'].append(('T3', 'X'))

💡 Waiting queues and lock holders form a wait-for graph that can contain cycles.

compare

Detect Deadlock Cycle

The system detects a deadlock cycle involving T2 and T3 waiting on each other for locks on B and A respectively.

💡 Deadlock detection algorithms identify cycles in the wait-for graph to prevent indefinite waiting.

Line:

if detect_deadlock(wait_for_graph):
    abort_transaction(victim)

💡 Deadlock detection is essential to maintain system liveness.

delete

Abort Transaction T3 to Resolve Deadlock

Transaction T3 is aborted to break the deadlock. Its locks and waiting requests are removed from the lock table.

💡 Aborting a transaction frees locks and allows other transactions to proceed.

Line:

abort_transaction('T3')
remove_locks_and_waiting('T3')

💡 Transaction abort is a last-resort mechanism to maintain system progress.

insert

Grant Exclusive Lock to T2 on B After T3 Abort

With T3 aborted, T2's exclusive lock request on B is now granted as no conflicting locks remain.

💡 Removing deadlock victims allows waiting transactions to proceed.

Line:

lock_table['B']['locks'].append(('T2', 'X'))
lock_table['B']['waiting'].remove(('T2', 'X'))

💡 Deadlock resolution restores lock granting and system throughput.

traverse

Final Lock Table State

The final lock table shows T3 aborted, T1 holding shared locks on A and B, and T2 holding an exclusive lock on B. No waiting transactions remain.

💡 The final state confirms that 2PL maintains consistency and resolves deadlocks.

Line:

return lock_table

💡 The system is in a consistent state with no deadlocks or conflicts.

lock_table = {'A': {'locks': [], 'waiting': []}, 'B': {'locks': [], 'waiting': []}}  # STEP 1

# STEP 2
if lock_table['A']['locks'] == []:
    lock_table['A']['locks'].append(('T1', 'S'))

# STEP 3
if all(lock[1] == 'S' for lock in lock_table['A']['locks']):
    lock_table['A']['locks'].append(('T2', 'S'))

# STEP 4
if any(lock[1] == 'S' for lock in lock_table['A']['locks']):
    lock_table['A']['waiting'].append(('T3', 'X'))

# STEP 5
if lock_table['B']['locks'] == []:
    lock_table['B']['locks'].append(('T1', 'S'))

# STEP 6
if lock_table['B']['locks']:
    lock_table['B']['waiting'].append(('T2', 'X'))

# STEP 7
lock_table['A']['locks'].remove(('T1', 'S'))

# STEP 8
# T3 still waits because T2 holds shared lock

# STEP 9
lock_table['A']['locks'].remove(('T2', 'S'))

# STEP 10
lock_table['A']['locks'].append(('T3', 'X'))
lock_table['A']['waiting'].remove(('T3', 'X'))

# STEP 11
lock_table['B']['waiting'].append(('T3', 'X'))

# STEP 12
def detect_deadlock(wait_for_graph):
    # Detect cycle in wait-for graph
    pass

if detect_deadlock(None):
    abort_transaction('T3')

# STEP 13
def abort_transaction(tid):
    for item in lock_table:
        lock_table[item]['locks'] = [l for l in lock_table[item]['locks'] if l[0] != tid]
        lock_table[item]['waiting'] = [w for w in lock_table[item]['waiting'] if w[0] != tid]

abort_transaction('T3')

# STEP 14
lock_table['B']['locks'].append(('T2', 'X'))
lock_table['B']['waiting'].remove(('T2', 'X'))

# STEP 15
return lock_table

📊

Two-Phase Locking (2PL) - Shared, Exclusive, Deadlock - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization reveals the dynamic behavior of locks and transactions, making the abstract concepts of 2PL concrete and understandable.

setup

leaf

leaf

Lock table initialized with data items A (node 1) and B (node 2), no locks held.

insertKey: S(T1)

S(T1)

leaf

leaf

T1 granted shared lock on A; no conflicts.

insertKey: S(T2)

S(T1)S(T2)

leaf

leaf

T2 granted shared lock on A; compatible with T1's shared lock.

insertKey: X(T3)

S(T1)S(T2)

leaf

leaf

T3 requests exclusive lock on A but must wait due to shared locks.

insertKey: S(T1)

S(T1)S(T2)

leaf

S(T1)

leaf

T1 granted shared lock on B; no conflicts.

insertKey: X(T2)

S(T1)S(T2)

leaf

S(T1)

leaf

T2 requests exclusive lock on B but must wait due to T1's shared lock.

delete

S(T2)

leaf

S(T1)

leaf

T1 released shared lock on A.

compareKey: X(T3)

S(T2)

leaf

S(T1)

leaf

T3 still waits; T2's shared lock blocks exclusive lock grant.

delete

leaf

S(T1)

leaf

T2 released shared lock on A.

insertKey: X(T3)

X(T3)

leaf

S(T1)

leaf

T3 granted exclusive lock on A after waiting.

insertKey: X(T3)

X(T3)

leaf

S(T1)

leaf

T3 requests exclusive lock on B and waits; deadlock cycle forms.

compare

X(T3)

leaf

S(T1)

leaf

Deadlock detected involving T2 and T3; system prepares to abort victim.

delete

leaf

S(T1)

leaf

T3 aborted; locks and waiting requests removed.

insertKey: X(T2)

leaf

S(T1)X(T2)

leaf

T2 granted exclusive lock on B after T3 abort.

traverse

S(T1)

leaf

S(T1)X(T2)

leaf

Final lock table state after deadlock resolution.

Key Takeaways

✓ Two-Phase Locking manages concurrent access by granting compatible locks and queuing conflicting requests.

This insight is hard to see from code alone because the dynamic interaction of locks and waiting queues is complex and best understood visually.

✓ Deadlocks arise from circular waiting dependencies and must be detected and resolved by aborting transactions.

Visualizing the wait-for graph and lock table state clarifies how deadlocks form and why aborting a victim breaks the cycle.

✓ Lock release triggers re-evaluation of waiting requests, enabling blocked transactions to proceed in order.

Seeing lock release and subsequent granting of waiting locks step-by-step reveals the fairness and correctness of 2PL.

Practice

1. Trace the sequence of events when a transaction running at Repeatable Read isolation level reads a row twice, but another concurrent transaction inserts a new row matching the query condition between the two reads. What anomaly occurs and why?

easy

A. Non-repeatable read, because the same row changed between reads

B. Phantom read, because a new row appeared between reads

C. Dirty read, because uncommitted data was read

D. No anomaly, Repeatable Read prevents all read inconsistencies

Solution

1. Step 1: Identify the Isolation Level Guarantees

   Repeatable Read prevents non-repeatable reads by locking rows read, but does not prevent phantom reads caused by new rows.

2. Step 2: Trace the Scenario

   Transaction reads rows matching condition; concurrent transaction inserts a new matching row and commits.

3. Step 3: Second Read Outcome

   Second read sees the new row, causing a phantom read anomaly.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Phantom reads are new rows appearing between reads, not changes to existing rows.

Hint: Repeatable Read prevents row changes, not new rows (phantoms)

Common Mistakes:

• Confusing phantom reads with non-repeatable reads
• Assuming Repeatable Read prevents phantoms
• Thinking dirty reads occur at Repeatable Read

2. You have a relation with multi-valued attributes and repeating groups. At which normalization step do you first ensure atomicity of attributes and eliminate repeating groups?

easy

A. When converting the relation into First Normal Form (1NF)

B. When removing partial dependencies in Second Normal Form (2NF)

C. When eliminating transitive dependencies in Third Normal Form (3NF)

D. When enforcing stricter dependency conditions in Boyce-Codd Normal Form (BCNF)

Solution

1. Step 1: Understand 1NF's role in normalization

   1NF requires that all attributes be atomic and that there are no repeating groups or arrays. This is the first step in normalization to ensure the relation is well-structured.

2. Step 2: Differentiate from later normal forms

   2NF and 3NF focus on removing partial and transitive dependencies, respectively, but assume atomic attributes already exist. BCNF further refines dependency conditions but does not address atomicity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Atomicity and elimination of repeating groups is the hallmark of 1NF, not later forms.

Hint: Atomicity and no repeating groups -> 1NF

Common Mistakes:

• Confusing 1NF with 2NF or 3NF responsibilities
• Thinking BCNF addresses atomicity
• Assuming partial dependencies relate to atomicity

3. Examine the following SQL query intended to perform a self join to find each employee's manager name. Identify the bug causing an SQL error.

medium

A. The alias 'A' is missing for the first table, causing ambiguous column references

B. The join condition uses 'A.manager_id' instead of 'A1.manager_id'

C. The alias 'A2' is incorrectly used for the second table

D. The SELECT clause should include 'A.manager_id' explicitly

Solution

1. Step 1: Check table aliases

   The first table is referenced as 'A' without aliasing, but the second is aliased as 'A2'. This causes ambiguity in column references.

2. Step 2: Correct alias usage

   Both tables in a self join must have distinct aliases, e.g., 'A1' and 'A2', to avoid ambiguous column references.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing alias for first table causes SQL error [OK]

Hint: Self joins require distinct aliases for the same table [OK]

Common Mistakes:

• Using same table name without alias
• Incorrect join condition references

4. Suppose a database uses snapshot isolation to handle concurrent transactions. Which scenario can still violate Consistency despite snapshot isolation, and why?

hard

A. A transaction commits without flushing changes to disk, violating durability.

B. Two concurrent transactions update different rows, causing no conflicts and preserving consistency.

C. A transaction reads uncommitted data from another transaction, causing dirty reads.

D. Two concurrent transactions read the same snapshot and update overlapping data, leading to write skew anomalies.

Solution

1. Step 1: Understand snapshot isolation

   Snapshot isolation prevents many anomalies but can allow write skew, where concurrent transactions read the same snapshot and update overlapping data inconsistently.

2. Step 2: Analyze options

   A describes the write skew anomaly possible under snapshot isolation. B is safe and consistent. C describes read uncommitted, not snapshot isolation. D relates to durability, not consistency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Write skew under snapshot isolation can violate consistency.

Hint: Snapshot isolation can allow write skew anomalies

Common Mistakes:

• Assuming snapshot isolation prevents all anomalies
• Confusing dirty reads with snapshot isolation behavior

5. Given a set of functional dependencies where some attributes can be NULL, how does the presence of NULL values affect the application of Armstrong's Axioms in inferring new dependencies?

hard

A. Armstrong's Axioms assume attributes are non-nullable, so NULLs invalidate inference results

B. NULL values do not affect Armstrong's Axioms since they are logical inference rules independent of data instances

C. Augmentation fails in presence of NULLs because adding attributes with NULL breaks dependency preservation

D. Transitivity cannot be applied if any attribute in the chain can be NULL

Solution

1. Step 1: Understand Armstrong's Axioms nature

   They are inference rules based on attribute sets and dependencies, independent of actual data values.

2. Step 2: Analyze NULL impact

   NULLs affect data instance semantics but do not change logical inference of dependencies.

3. Step 3: Evaluate options

   A is incorrect; axioms do not assume non-nullability.
   B is correct; inference is logical and data-agnostic.
   C is incorrect; augmentation is a logical rule, not data-dependent.
   D is incorrect; transitivity applies regardless of NULL presence.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Armstrong's Axioms operate on schema-level dependencies, not data values.

Hint: Armstrong's Axioms = logical rules, unaffected by NULLs

Common Mistakes:

• Confusing logical inference with data instance behavior
• Assuming NULLs break functional dependencies at schema level
• Believing augmentation or transitivity depend on data completeness