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

Two Phase Locking protocol is conflict serializable. So this is a modified version of the basic $2PL$ protocol, So serializabilty should be guaranteed.. and we can get a serializable scheduling by ordering based on Lock points(same as in basic $2PL$
)..
Now in Step $1,$ exclusive locks are aquired to $O_1,O_2,O_3$.... in increasing order of addresses..since it is mentioned as exclusive lock, only one transaction can lock the object..
Due to acquiring of locks based on ordering of addresses.. and locks aren't released until the transaction completes its operation.. we can prevent the circular wait condition, and hence making it deadlock free.

So, the answer should be (A) guarantees serializability and deadlock freedom

Comments

  @talha hashim it only cares about acquiring of all locks before proceeding/executing, it has no condition on when can the locks be freed. so it does not ensure any recoverability. 

---

@Madhab
If it were acquiring shared locks, the answer would still be the same (with the same explanation given for the exclusive case).

---

Yes!!
Free from DEADLOCK but Not from STARVATION

Answer 2

It is Conservative 2PL Protocol which ensures Deadlock Freedom. Therefore A is the correct answer.

Comments

We can say that,but that is not the same thing,by definition they are different and more importantly they will be implemented differently,suppose you implement a schedule i.e rigorous 2pl so can you say that you also implemented conservative 2pl(no,because you have to write different set of programs for that).

---

YES, in conservative-2PL no locks will be acquired until all the needed-resources are available at same time.

Here according to the problem statement, we are acquiring locks based on increasing order of addresses even if 1 resource out of "n"-needed is available.

So, Given schedule is NOT A CONSERVATIVE 2-PL.

---

Source : Fundamentals of database systems by Navathe 6-th edition

Answer 3

A is correct option .....

Comments

yup A because there is only 1 transaction ..no any problem of serializablity and deadlock !

---

nope bro it is  general rule defined for any transaction.

---

This is conservative 2PL scheduler with partial ordering of data items.

 

Conservation 2pl ensure both deadlock free and conflict serializatibily.

Partial ordering too ensures deadlock free.

So the resulting schedule(not because it is having only one transaction) will be serializable and deadlock free.

---

@sourav. 
The line “Suppose a transaction T …” is just describing how each transaction behaves under this protocol, not that there is only one transaction in the system.

Answer 4

Answer : (A)

Schedule is Serializable since , it uses 2PL .

For Deadlock :  Here note that transaction acquire lock in increasing order only , there for there is never be scenario such that transaction wanted lock on Oj and holding lock on Oi , such that i > j , hence it is deadlock free(In short , it is free from circular wait) .

Answer 5

EVEN THOUGH THERE IS MORE THAN ONE LOCKS EITHER EXCLUSIVE OR ANY GROWING LOCKS AND RELESING LOCKS DOES NOT OCCUR  DEADLOCK  SO OPTION A IS CORRECT

Comments

OPTION A IS APPROPIATE ONE

Answer 6

In the question it is given that 2PL is being used .

So no matter what they mention in next few lines of questions we can be absolutely sure of one thing, that is , the schedule generated will be conflict serializable. (REASON: If transactions follow 2PL(or any variation of it may be Strict 2PL , Rigorous 2PL , Conservative 2PL) Conflict serializability is always ensured).

Now about deadlock :      

If any transaction is applying locks on all the database items it may need in future then this makes one thing very clear, that such a transaction will never depend on any other transaction for releasing a lock.

This means there can never be a deadlock

 

Ans A