The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
7.2k views

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock?

  1. 2-phase locking
  2. Time-stamp ordering
    1. I only
    2. II only
    3. Both I and II
    4. Neither I nor II
asked in Databases by Veteran (97.7k points)
edited by | 7.2k views

6 Answers

+35 votes
Best answer
In basic two phase locking there is a chance for deadlock

Conservative 2pl is deadlock free

I go with B.
answered by Boss (11.1k points)
edited by
0
In the question it's just mentioned 2pl locking. They haven't mentioned which version on 2pl. Of course basic 2pl has deadlock problem. It could also be conservative or strict. So how to decide?
+9
http://www.ankurgupta.net/wp-content/uploads/GATE_Solutions/GATE_CS2010Solution.pdf
Two phase locking ensures only conflict serializability, whereas time stamp ensure both.
+14
Basic 2PL==>(ensure serializability) + (but deadlock and starvation possible).

Strict 2PL ==>(ensure serializability) +(ensure recoverability) + (but deadlock and starvation possible).

Conservative 2PL ==>(ensure serializability)+ (no deadlock) +(but starvation possible).

time stamp ordering ==>(ensure serializability)+ (no deadlock) +(avoid starvation by using wait-die and wound -wait scheme).
+3
Rigorous 2PL ==> (ensure serializability) + (no cascading rollback)+ (but deadlock and starvation possible)
+1

strict 2PL and rigorous  2PL both produce strict schedule so by the definition  both will be recoverable . where as conservative 2PL may produce cascading (means not cascadeless) schedule .

must read given link

one more point : deadlock has been taken care by locking strategy but cascading is care by unlocking strategy.

+11 votes
Answer is B.

2PL ensures conflict serializability but is not deadlock free.

Timestamp ordering ensures conflict serializability because if any action causes violation in serializability order that was being followed from beginning of schedule, then the transaction is rolled back and again started with new timestamp.

It also ensures freedom from deadlock because there are no locks.. which means no mutual exclusion.
answered by Active (1.2k points)
+7 votes

Timestamp Based Ordering Protocol is :

answered by Loyal (7.4k points)
+5 votes

Two phase locking ensures conflict serializable schedules, but does not ensure freedom from deadlock.

One the other hand, Timestamp ordering protocol ensures freedom from deadlock but does not ensure conflict serializable schedules.

ensure = every schedule is conflict serializable. Hence the answer is D

Reference: http://codex.cs.yale.edu/avi/db-book/db4/slide-dir/ch16-2.pdf

Additional info: Tree based protocol ensures both, freedom from deadlocks and conflict serializable schedule.

answered by Active (3.5k points)
+3

The timestamp-ordering protocol guarantees serializability since

all the arcs in the precedence graph are of the form one node to other thus there will be no cycle in the graph.

In TO protocol if any conflict pair does not follow the order then it is rollback , because we consider conflict action so schedule must conflict serializable.

so option B correct

+1 vote

2 Phase Locking (2PL) is a concurrency control method that guarantees serializability. 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. 2PL may be lead to deadlocks that result from the mutual blocking of two or more transactions. See the following situation, neither T3 nor T4 can make progress.

Timestamp-based concurrency control algorithm is a non-lock concurrency control method. In Timestamp based method, deadlock cannot occur as no transaction ever waits.

answered by Loyal (9.7k points)
0 votes
B is answer
answered by Junior (757 points)
Answer:

Related questions

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
49,811 questions
54,533 answers
188,417 comments
75,581 users