GATE IT 2007 | Question: 66

Question

Consider the following two transactions$: T1$ and $T2.$

$\begin{array}{clcl} T1: & \text{read (A);} & T2: & \text{read (B);} \\ & \text{read (B);} & & \text{read (A);} \\  & \text{If}\;A = 0\; \text{then}\; B \leftarrow B + 1;  & &  \text{If}\;B \neq 0\;\text{then}\;A \leftarrow A  – 1; \\ & \text{write (B);} & & \text{write (A);}\\\hline\end{array}$

Which of the following schemes, using shared and exclusive locks, satisfy the requirements for strict two phase locking for the above transactions?

• A. $\begin{array} {c l c l}  S1: & \text{lock S(A);} & S2: & \text{lock S(B);} \\ & \text{read (A);} &  & \text{read (B);} \\ & \text{lock S(B);} & & \text{lock S(A);}  \\ & \text{read (B);} &  & \text{read (A);} \\ & \text{If}\; A = 0 & & \text{If}\; B \neq 0 \\  & \text{then}\; B \leftarrow B + 1; & & \text{then}\; A \leftarrow A - 1; \\ & \text{write (B);} & & \text{write (A);} \\  & \text{commit;} & & \text{commit;} \\ & \text{unlock (A);} & & \text{unlock (B);} \\ & \text{unlock (B);} & & \text{unlock (A);} \\ \hline\end{array}$
• B. $\begin{array} {c l c l}  S1: & \text{lock X(A);} & S2: & \text{lock X(B);} \\ & \text{read (A);} &  & \text{read (B);} \\ & \text{lock X(B);} & & \text{lock X(A);}  \\ & \text{read (B);} &  & \text{read (A);} \\ & \text{If}\; A = 0 & & \text{If}\; B \neq 0 \\  & \text{then}\; B \leftarrow B + 1; & & \text{then}\; A \leftarrow A - 1; \\ & \text{write (B);} & & \text{write (A);} \\ & \text{unlock (A);} & & \text{unlock (A);} \\  & \text{commit;} & & \text{commit;} \\ & \text{unlock (B);} & & \text{unlock (A);} \\ \hline\end{array}$
• C. $\begin{array} {c l c l} S1: & \text{lock S(A);} & S2: & \text{lock S(B);} \\ & \text{read (A);} &  & \text{read (B);} \\ & \text{lock X(B);} & & \text{lock X(A);}  \\ & \text{read (B);} &  & \text{read (A);} \\ & \text{If}\; A = 0 & & \text{If}\; B \neq 0 \\  & \text{then}\; B \leftarrow B + 1; & & \text{then}\; A \leftarrow A - 1; \\ & \text{write (B);} & & \text{write (A);} \\ & \text{unlock (A);} & & \text{unlock (B);} \\  & \text{commit;} & & \text{commit;} \\ & \text{unlock (B);} & & \text{unlock (A);} \\\hline \end{array}$
• D. $\begin{array} {c l c l} S1: & \text{lock S(A);} & S2: & \text{lock S(B);} \\ & \text{read (A);} &  & \text{read (B);} \\ & \text{lock X(B);} & & \text{lock X(A);}  \\ & \text{read (B);} &  & \text{read (A);} \\ & \text{If}\; A = 0 & & \text{If}\; B \neq 0 \\  & \text{then}\; B \leftarrow B + 1; & & \text{then}\; A \leftarrow A - 1; \\ & \text{write (B);} & & \text{write (A);} \\ & \text{unlock (A);} & & \text{unlock (A);}  \\ & \text{unlock (B);} & & \text{unlock (A);} \\  & \text{commit;} & & \text{commit;} \\ \hline\end{array}$

Comments

suppose if any schedule does not have write operation and hence it does not need to acquire an exclusive lock, so in this case, will the schedule be in Strict 2pl. I mean to ask that a schedule with no exclusive lock is in strict 2pl or not?

---

For Strict 2PL, All X_LOCKS() are held till commit in addition to to locks being 2PL.

---

@akku_126 Yes, It will be in Strict 2PL if there are no X_LOCKS() provided it follows 2PL since condition for a schedule being Strict 2PL is on X_Locks().

Answer 1

Answer is (C).

Many of you would point a DEADLOCK and I won't deny But see Question just asks for requirement to follow Strict 2PL. Requirement are

1. Exclusive locks should be released after the commit.
2. No Locking can be done after the first Unlock and vice versa.

In 2Pl deadlock may occur BUT it may be that it doesn't occur at all.

Consider that in option (C) if both execute in serial order without concurrency. Then that is perfectly valid and YES it follows Strict 2PL.

Comments

It must have to aquire exclusive lock

---

2 Phase Locking requires locking and unlocking in two phases:

1. Growing Phase: A transaction can obtain locks but can't release locks.
2. Shrinking Phase: A transaction can release the locks but can't obtain locks.

For Strict 2PL, All X_LOCKS() are held till commit in addition to to locks being 2PL.

---

in option A, write operation is performed without acquiring x-lock.

Answer 2

A) is eliminated because write (B) is done in S1 without acquiring Exclusive lock on B.

B) is eliminated because unlock (A) should happen only after commit in a strict 2pL.

D) is also eliminated. The reason is exactly same as B)

C) is the answer.

•  It can be clearly seen that it is a 2 pL because all acquired locks are released only after locking_point.
•  It is also clear that it is also a strict 2 pL as all Exclusive locks acquired by a transaction are released only after commit operation.

Comments

Check your reasons it's contradicts.

Answer 3

3) Shared lock can be unlocked anytime Exclusive only after commit
4) is 2pl
2) is Wrong Exclusive cannot take other's Exclusive Lock.

1) To write X you need Exclusive Lock So WRONG 
Correct If Wrong.

Comments

How option 4 ? 4 has commit after release of xclusive locks, it shud commit before releasing....

Moreover the option 2 and 3 i guess incorrectly given... both didnt hav release of B for A

---

@Abhinav

can u explain

2) is Wrong Exclusive cannot take other's Exclusive Lock

---

@cse23 ,  " if schedule in 2PL then it is CS " This is correct , right ?

If not CS then not 2PL is this also correct ??

Answer 4

Here in option some mistake is there in original paper.

The requirements for strict two phase locking for the above transactions  = strict two phase locking says unlock exclusive lock i.e. unlock X(); after commit or rollback.

Shared lock used for Read , exclusive lock used for  Write data.

Releasing exclusive lock after commit restrict the deadlock condition. i.e. we cannot get lock on item were exclusive lock already taken.

Comments

the exact interleaving of operations is not even shown in the diagram, how are u drawing the precedence cycle??? Moreover if every transaction in a schedule individually follows 2PL then the schedule is always serializable. Hence option C

---

Then 2PL is conflict serializable?

---

srestha Yes
https://cs.stackexchange.com/questions/113156/does-basic-2-pl-always-ensure-conflict-serializability