GATE CSE 2016 | Set 1 | Question: 51

Question

Consider the following two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects $\{O_1,\ldots,O_k \}$. This is done in the following manner:

• $\text{Step 1}$. $T$ acquires exclusive locks to $O_1,\ldots,O_k$ in increasing order of their addresses.
• $\text{Step 2}$. The required operations are performed .
• $\text{Step 3}$. All locks are released

This protocol will

• A.  guarantee serializability and  deadlock-freedom 
• B.  guarantee neither serializability nor deadlock-freedom 
• C.  guarantee serializability but not deadlock-freedom  
• D.  guarantee deadlock-freedom but not serializability.

Comments

One thing to be noted is that unlike Conservative 2PL which completely eliminates Hold-and-Wait. Here, transaction can successfully hold locks on \(O_{1}\) and \(O_{2}\) while waiting for \(O_{3}\). So Hold-and-Wait is allowed here..
However, because of the strict address ordering rule, a transaction holding a lower address can never be waited on by a transaction holding a higher address.

Therefore, a cycle is completely impossible, breaking the Circular Wait condition. Therefore no deadlock!

---

Deadkock freedom can be proved by "Proof of Contradiction"

References : https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html

Lets assume that protocol allows a deadlock

A deadlock requires a circular wait in the system's Wait-For graph. Suppose a cycle exists: $T_1 \rightarrow T_2 \rightarrow \dots \rightarrow T_n \rightarrow T_1$.

An edge $T_i \rightarrow T_j$ means transaction $T_i$ holds a lock on an object $O_{x}$ and is waiting for a lock on an object $O_{y}$ held by $T_j$.

According to the protocol's rule in Step 1, $T_i$ must acquire locks in increasing address order. Since $T_i$ already holds $O_{x}$ and is waiting for $O_{y}$, it must mathematically hold that $\text{address}(O_{x}) < \text{address}(O_{y})$.

$T_1$ waits for $T_2 \implies \text{address}(O_{x1}) < \text{address}(O_{x2})$

$T_2$ waits for $T_3 \implies \text{address}(O_{x2}) < \text{address}(O_{x3})$

............

$T_n$ waits for $T_1 \implies \text{address}(O_{xn}) < \text{address}(O_{x1})$

By the transitive property,

$\text{address}(O_{x1}) < \text{address}(O_{x2}) < \dots < \text{address}(O_{xn}) < \text{address}(O_{x1})$

 $\text{address}(O_{x1}) < \text{address}(O_{x1})$, which is a contradiction

So ,our initial assumption is false. A cycle can never form, and the protocol completely guarantees deadlock-freedom.

---

References : Navathe 

Answer 1

Option A is correct (Bcz It is conservative 2PL)

Easy Explanation ; It is saying T acquire Exclusive lock (it can be shared also doesn't matter)

so if Lock Acquires at beginning 

then operation performed (Read/write)

then lock released (means Unlock)

So it is conservative 2PL ( guarantee serializability and  deadlock-freedom )

 

 

Answer 2

The given protocol is a variant of two-phase locking (2PL) where a transaction acquires all exclusive locks in increasing order of object addresses, performs operations, and then releases all locks. This protocol guarantees both serializability and deadlock-freedom,--

Serializability

- Serializability ensures that the concurrent execution of transactions is equivalent to some serial execution.
- In this protocol, all locks are acquired before any operations are performed, and all locks are released only after all operations are completed. This adheres to the two-phase rule: a growing phase (acquiring locks) followed by a shrinking phase (releasing locks). Since no lock is released until all locks are acquired, the protocol ensures that the transaction has a consistent view of the data throughout its execution, which guarantees serializability. This is a fundamental property of 2PL.

Deadlock-Freedom

- Deadlock occurs when two or transactions are waiting for each other to release locks, resulting in a circular wait.
- In this protocol, locks are acquired in increasing order of object addresses. This imposes a total order on lock acquisition across all transactions. Since every transaction must acquire locks in the same order, circular wait cannot occur. For example, if transaction T1 locks object O1 (with a lower address) and transaction T2 requests O1, T2 must wait for T1 to release O1. T1 will eventually release all locks after completing its operations, allowing T2 to proceed. Thus, no deadlock is possible.

Answer :- A

Answer 3

2pl Ensure conflict serializable and Deadlock free as they are in increasing order and only 1 Exclusive Lock

Answer 4

Here is the comparison between all 2pl's

Answer 5

Answer: A

Conflict Serializability:

Two-Phase Locking (2PL) is a standard concurrency control protocol that guarantees conflict serializability.

Since any transaction does not acquire locks AFTER releasing them it follows the 2PL protocol and therefore, it guarantees conflict serializability.

Freedom from Deadlock:

Since locks acquired on objects are exclusive and in strictly increasing order of their addresses, any transaction CANNOT hold and wait for a lock. Thus, the protocol is deadlock free.