The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
6.4k 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 (106k points)
edited by | 6.4k views

5 Answers

+32 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.5k 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?
+7
http://www.ankurgupta.net/wp-content/uploads/GATE_Solutions/GATE_CS2010Solution.pdf
Two phase locking ensures only conflict serializability, whereas time stamp ensure both.
+6
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).
+10 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.1k points)
+7 votes

Timestamp Based Ordering Protocol is :

answered by Loyal (8.1k 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

0 votes

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.1k 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

42,599 questions
48,600 answers
155,661 comments
63,732 users