Two Phase Locking

What is Two-Phase Locking (2PL) ?

Two-phase locking, as the name suggests, is a concurrency control protocol that divides the execution of a transaction into two phases: the growing phase and the shrinking phase. This protocol ensures that a transaction does not release any locks it holds until it has obtained all the locks it needs, and once a lock is released, the transaction cannot acquire new locks. Let's break down these two phases:

1. Growing Phase: During this phase, a transaction can acquire locks on data items, but it cannot release any locks. It's like a transaction is "growing" its set of locked items.

2. Shrinking Phase: After a transaction releases its first lock, it enters the shrinking phase. In this phase, a transaction can release locks but cannot acquire new ones. Once a transaction enters the shrinking phase, it's moving towards completion.

Types of Locks:

• Shared Lock (S-Lock): Allows multiple transactions to read a data item simultaneously, but it prevents any transaction from acquiring an exclusive lock on that item.

• Exclusive Lock (X-Lock): Grants exclusive access to a data item, preventing any other transaction from acquiring a shared or exclusive lock on the same item.

How Two-Phase Locking Works

To better understand 2PL, let's look at how it works in practice:

1. Lock Acquisition: When a transaction needs to read or write a data item, it requests a lock for that item. The lock manager checks if the item is already locked by another transaction. If not, it grants the lock to the requesting transaction. If the item is already locked, the requesting transaction may be forced to wait until the item becomes available.

2. Lock Release: A transaction holds locks on data items until it has finished its work with those items. Once it has completed its read and write operations on a locked item, it releases the lock, making the item available for other transactions.

3. Two-Phase Aspect: The key aspect of 2PL is that a transaction does not release any locks until it's in the shrinking phase, ensuring that it doesn't interfere with other transactions by releasing locks prematurely.

It has variations that include Basic, Conservative, Strict, and Rigorous Two-Phase Locking. Each of these variations imposes different rules on how locks can be acquired and released during the execution of transactions. Here's an overview of each:

1. Basic Two-Phase Locking (2PL):

   • Acquisition Phase: In the acquisition phase, a transaction can acquire locks on data items as needed during its execution. It can request and acquire both shared and exclusive locks as necessary.

   • Release Phase: Once a transaction releases a lock, it cannot acquire any more locks. This phase begins when a transaction releases its first lock.

   • Serializability: Basic 2PL guarantees serializability of transactions, but it does not guarantee freedom from deadlocks.

2. Conservative Two-Phase Locking (Conservative 2PL):

   • Acquisition Phase: Similar to Basic 2PL, a transaction can acquire locks as needed during its execution.

   • Release Phase: Unlike Basic 2PL, a transaction in Conservative 2PL can release locks and then acquire more locks later in its execution. It doesn't enter a strict release phase.

   • Serializability: Conservative 2PL also guarantees serializability, and it can potentially reduce deadlock occurrences compared to Basic 2PL.

3. Strict Two-Phase Locking (Strict 2PL):

   • Acquisition Phase: Similar to Basic 2PL, a transaction can acquire locks on data items as needed.

   • Release Phase: In Strict 2PL, once a transaction releases a lock, it cannot acquire any more locks. This stricter release phase helps prevent deadlocks.

   • Serializability: Strict 2PL guarantees serializability and provides a higher level of deadlock prevention compared to Basic 2PL.

4. Rigorous Two-Phase Locking (Rigorous 2PL):

   • Acquisition Phase: A transaction can acquire locks on data items as needed during its execution.

   • Release Phase: Similar to Strict 2PL, once a transaction releases a lock, it cannot acquire any more locks.

   • Serialization Guarantees: Rigorous 2PL provides stronger guarantees than just serializability. It guarantees conflict-serializability, which is a more restrictive form of serializability that ensures transactions don't interfere with each other in any way.

The choice of which variation of the Two-Phase Locking protocol to use depends on the specific requirements of the database system and the desired trade-offs between concurrency and deadlock prevention. Basic 2PL is the most permissive but provides fewer deadlock guarantees, while Strict and Rigorous 2PL provide stronger deadlock prevention but may limit concurrency to some extent. Conservative 2PL falls somewhere in between, offering a balance between concurrency and deadlock prevention.

The passage you've provided discusses several strategies for dealing with deadlock and starvation in a database system. Let me summarize the key points:

1. Deadlock Prevention Protocols: These are strategies aimed at preventing deadlocks from occurring in the first place. Two protocols mentioned are:

   • Conservative Two-Phase Locking: Transactions are required to lock all needed items in advance, limiting concurrency. If any item cannot be obtained, the transaction waits and retries.

   • Item Ordering: Transactions must lock items according to a predetermined order, which is impractical in most cases.

2. Timestamp-Based Deadlock Prevention:

   • Wait-Die: Older transactions are allowed to wait for younger ones, but younger transactions requesting items held by older transactions are aborted and restarted later with the same timestamp.

   • Wound-Wait: Younger transactions are allowed to wait for older ones, but older transactions requesting items held by younger transactions preempt and abort the younger transactions, which are then restarted.

3. Timestamp-Free Deadlock Prevention:

   • No Waiting: Transactions unable to obtain a lock are immediately aborted and restarted after a time delay, without checking if a deadlock will occur. This approach can lead to unnecessary aborts.

   • Cautious Waiting: Transactions only block if the transaction they are waiting for is not itself blocked. This reduces the number of needless aborts/restarts.

4. Deadlock Detection: This approach involves periodically checking if a deadlock state exists by constructing and maintaining a wait-for graph. Deadlock is detected if and only if the graph contains a cycle.

5. Timeouts: If a transaction waits for longer than a system-defined timeout period, it is assumed to be deadlocked and aborted, regardless of whether a deadlock actually exists or not. This method is simple and low overhead.

6. Starvation: Starvation occurs when a transaction cannot proceed indefinitely while others continue normally. Strategies to mitigate starvation include fair waiting schemes like first-come-first-served queues and priority schemes that increase a transaction's priority the longer it waits.

7. Victim Selection: When aborting transactions to resolve a deadlock, it is important to select victims carefully, avoiding transactions that have been running for a long time or made many updates.

Each approach has its trade-offs in terms of complexity, concurrency, and effectiveness in preventing or detecting deadlocks. The choice of which strategy to use depends on the specific characteristics and requirements of the database system.