The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
257 views
Consider the following schedules involving two transactions.

$S_1 : R_1(x), W_2(y),R_2(x),W_1(y), \ commit_1, \ commit_2$

$S_2 : R_1(x), R_2(y),W_1(z), \ commit_1,R_3(y), R_3(z), W_2(y), W_3(x), commit_2, commit_3$

Which of the following statements is true?

A) Both S1 and S2 are allowed under 2PL
B) only S1 is allowed under 2PL
C) only S2 is allowed under 2PL
D)  neither S1 nor S2 is allowed under 2PL
asked in Databases by (495 points)
edited by | 257 views
0
Is it A?
+1
A is correct.
+1
@minipanda here we will consider only serializability for the transactions to satisfy 2PL as we donot have any growing or shrinking phase or there is any other approach.?
+3

arvin  I do like : putting locks on data items and releasing them such that all the operations of both transactions can take place as it is (in the order given). If we can do so then it is allowed under 2pl.

For eg take the 1st schedule :

T1 T2
S(x)  
R(x)  
  X(y)
  W(y)
  S(x)
  R(x)
  U(x) U(y)
X(y)  
W(y)  
U(y) U(x)  
c1  
  c2

Here all locks can be given and taken back such that all operations are done in the same order given.

Take this example : S: R1(A) W2(A) R1(A)

We check whether this is allowed under 2pl or not.

T1 T2
S(A)  
R(A)  
  W(A) -> This operation cannot be performed because we can't acquire lock on it as T1 has S lock on A. If T1 releases S then it's next operation cannot be performed which again requires S because once released cannot be acquired in the 2pl protocol.
R(A)  
U(A)  
  At this point W(A) can be performed but the order is already not maintained. So schedule is not allowed under 2PL.

 

+2
@minipanda : thanks a lot :p
+1
@minipanda : so it means we can acquire a lock only once for any variable in a transactiom. and unless it doesnot writes we cant remove that lock.
+2

A transaction say T1 can acquire a lock on any data item if it is already not locked by some other transaction (only S-S lock allowed). And if T1 wants to release it to hand it over to another transaction T2, then from that point of time T1 can't acquire lock on any data item. This is because it has already entered into the shrinking phase and here it can't acquire any lock again.If it already has put some locks on other data items then it may hold them or release them. But nothing can be acquired.

0
oou thanks again :p
0
@MiNiPanda, Can you please confirm that second schedule is allowed in 2PL because of lock conversion? Or any other reason
+1

According to me S2 is also allowed under 2PL.

T1 T2 T3
S(X)    
R(X)    
  S(Y)  
  R(Y)  
X(Z)    
W(Z)    
U(Z),U(X)    
COMMIT    
    S(Y)
    R(Y)
    X(Z) , X(X)
    R(Z)
    U(Y)
  X(Y)  
  W(Y)  
    W(X)
    U(X),U(Z)
  U(Y)  
  COMMIT COMMIT

 

Shubhgupta  If you find something wrong then let me know..

 

0

@MiNiPanda,but last last transaction of t3 is W(X)? I did like -

T1 T2 T3
S(X)    
R(X)    
  S(Y)  
  R(Y)  
X(Z)    
W(Z)    
U(Z),U(X)    
COMMIT    
    S(Y)
    R(Y)
    S(Z)
    R(Z)
  X(Y)  
  W(Y)  
    X(X)
    W(X)
    U(X)U(Z)
  U(Y)  
 
0

Shubhgupta Yes i did a mistake.. will edit it.

But in your table T3 is acquiring S-lock on Y and after that without releasing it T2 is acquiring X-lock on Y. That is not possible.

0
I have read it somewhere in 2PL with the help of lock conversion a shared lock can be promoted to exclusive lock in growing phase on same data item. And one more thing in 2PL can we acquire all lock for one transaction in predefined manner without knowing future need?
+1

Shubhgupta Yes lock upgradation is possible only when that lock is not being held by some other transaction. It was fine till the time when T2 and T3 had S-S lock on Y.

I am not exactly sure whether a transaction without knowing it's future need can lock all the variables..but in conservative 2pl, a transaction locks all data items that it needs in executing itself (I don't know how the transaction gets to know what it will need in future :/ ) 

0
thanks for the help [email protected]:)
this question arise because in your example you are acquiring exclusive lock on data item on X while reading z value. So how transaction will decide that in future i am having a need to do W(X) so i need acquire lock on that point only. Sounds like weird question.. Sorry.
0

No it's a good question actually.. But since in case of conservative 2pl a transaction acquires lock on all data items it will need in future i thought there is some way to determine the data items that it will work on.

syncronizing What is the answer given?

0
No Solution was given to this question.
0

@MiNiPanda It is always not possible for a transaction to declare its read set and write set before hand as is the requirement for conservative 2PL to be able to work correctly. So we can't assume that a transaction will always lock the data items that it will need in future.

https://en.wikipedia.org/wiki/Conservative_two-phase_locking

0

Thanks Somoshree Datta 5 for this clarification..

What should be the answer according to you ?

0

@MiniPanda

it is surely not strict or conservative 2PL

but 1st one can be rigorous 2PL

why u written this line

If T1 releases S then it's next operation cannot be performed which again requires S because once released cannot be acquired in the 2pl protocol.

Can u elaborate?

2ndly in 2nd transaction

u releases exclusive lock U(Y) in middle

which locking protocol it can be?

 

0
@MiNiPanda I think that that S1 should be allowed under 2PL by S2 cant be allowed since T3 already holds a shared lock on data item Y, due to which transaction T2 cannot acquire an exclusive lock on Y at the same time. Moreover, T3 cant release the shared lock on Y since that would indicate the beginning of shrinking phase whereby T3 cant acquire the next lock on data item X in order to write it. Shouldn't this be the answer?
0

srestha

If you see this schedule S: R1(A) W2(A) R1(A)

T2 needs to acquire lock over A while T1 has already put S lock on A. Now if we want T2 to be successful in it's write operation then T1 has to release S lock on A. If it does so then T2 after completing write operation may release it's lock but now T1 can't acquire lock on A again because it has already entered the shrinking phase of 2pl protocol. So T1 can complete it's read op.

For your next question, I didn't get it..which one are you referring to?

0
release means unlock, right?

If after writing T2 again release then why cannot T1 again acquire this lock?
0

According to the two-phase locking protocol, a transaction handles its locks in two distinct, consecutive phases during the transaction's execution:

  1. Expanding phase (aka Growing phase): locks are acquired and no locks are released (the number of locks can only increase).
  2. Shrinking phase (aka Contracting phase): locks are released and no locks are acquired.

Somoshree Datta 5 

S2 cant be allowed since T3 already holds a shared lock on data item Y, due to which transaction T2 cannot acquire an exclusive lock on Y at the same time. Moreover, T3 cant release the shared lock on Y since that would indicate the beginning of shrinking phase 

$T_3$ can release shared lock before $T_2$ acquiring Exclusive lock on Y. Even after this some operations are done on some other data items this is valid. The only thing which is restricted is that you cannot lock some other data item after unlocking.

If you are finding this understanding from any standard resource that in shrinking phase no operation can be done in between  2 locks are released then please share with us too

0
@Mk Utkarsh my statement meant that if T3 releases the shared lock on Y for T2 to acquire an exclusive lock on it, then T3 cant acquire an exclusive lock on X which it needs later to perform the final write on X since T3 has already entered its shrinking phase. Isn't this true??
0
after $T_3$ releases the shared lock on Y, $T_3$ is in shrinking mode and is not acquiring any lock and already locked (X) in growing phase.
0
@Mk Utkarsh How is it guaranteed that T3 will know that it would require X later and hence it would lock X in the growing phase? It may not be possible for a transaction to declare its read set and write set before hand. So how can you guarantee that T3 will declare its requirement in the growing phase only?
0

In databases and transaction processing, two-phase locking (2PL) is a concurrency control method that guarantees serializability. It is also the name of the resulting set of database transaction schedules (histories). The protocol utilizes locks, applied by a transaction to data, which may block (interpreted as signals to stop) other transactions from accessing the same data during the transaction's life.

By the 2PL protocol, locks are applied and removed in two phases:

  1. Expanding phase: locks are acquired and no locks are released.
  2. Shrinking phase: locks are released and no locks are acquired.

This is the exact definition, checking the serial schedule given by MiNiPanda everything is satisfied i have any reason to disagree that schedule is not in 2PL. NO. 

Do i know the algorithm that how algorithm works and how many data items in future its checking. No

Is it required? No because definition is itself satisfied. Based on definitions algorithm will work how to grow and how to shrink. If any standard resource says that my understanding is wrong. I'll change my answer, but i still think its A.

0
@minipanda second one should not be under 2pl see in T3 you have aquired S(y)

Now before releasing shared  lock on y you can't obtain the ex lock on  (Y)in T2 and if  you have released the lock on Y then T3 is in shrinking phase and now it can't obtain Ex-(X)lock
0

Prince that's why Ex-(X) is acquired before releasing (Y)

0
@Mk Utkarsh - ya, if this is the case, why did they mention separate protocols for Conservative 2PL.

"All locks must be acquired on data items before starting the transaction".  - C2PL - Growing Phase

they could have done it in Basic 2PL only...

im totally confused !!
0

Conservative 2PL has its own limitations out of which one of the limitations are transactions not being able to declare its read set and write set before hand always. Hence conservative 2PL is not used very frequently due to this. If the question would have asked about whether the schedules are allowed under conservative 2PL, then S2 would have been possible because there would have been a way by which transactions could acquire and release locks without violating the definition of conservative 2PL. But here question is asked about basic 2PL and not conservative 2PL.

0
ya, this is what im saying.
0
@Somoshree 1st one cannot be strict 2PL
0
@Srestha ma'am yes the first schedule can't be strict 2PL..but my question is can the second one be allowed under 2PL?

1 Answer

+2 votes
Best answer

A should be the correct option, S1 is 2PL and S2 is strict 2PL.

answered by Junior (763 points)
selected by

Related questions

+1 vote
3 answers
2
0 votes
2 answers
3
0 votes
1 answer
4


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,455 questions
48,493 answers
154,717 comments
63,084 users