GATE CS 2016 Set 1 Q51 — Transactions and Concurrency Control

To determine the properties of the given protocol, let us analyze serializability and deadlock-freedom separately:

1. Serializability

• Under the Two-Phase Locking (2PL) protocol, a transaction cannot acquire any new locks once it has released any lock. This divides the transaction execution into a growing phase (acquiring locks) and a shrinking phase (releasing locks).
• In the given protocol:
• Step 1 is the growing phase where all exclusive locks are acquired.
• Step 3 is the shrinking phase where all locks are released.
• Since no lock is acquired after any lock is released, this protocol strictly adheres to the 2PL rules. Therefore, it guarantees conflict serializability.

2. Deadlock-freedom

• A deadlock occurs when there is a circular wait among transactions (e.g., $T_1$ holds resource $R_1$ and waits for $R_2$, while $T_2$ holds $R_2$ and waits for $R_1$).
• In this protocol, every transaction must acquire locks in a strict, globally defined order (increasing order of their memory/disk addresses: $O_1, O_2, \ldots, O_k$).
• If all transactions request resources in the same linear order, a cycle in the wait-for graph is mathematically impossible. For example, if $T_1$ holds $O_i$ and waits for $O_j$, then $i < j$. For a cycle to exist, we would need a sequence of transactions such that $i_1 < i_2 < \dots < i_1$, which is a contradiction.
• Thus, ordering resource acquisition prevents circular wait, which guarantees deadlock-freedom.

Since the protocol guarantees both serializability and deadlock-freedom, the correct option is A.