For each of these, you have to give a convincing argument as to why the stated c
ID: 3665787 • Letter: F
Question
For each of these, you have to give a convincing argument as to why the stated claim is true. It is
not enough just to give an example. However, if you like, you can use an example to illustrate your convincing
argument.
(a) Show that the basic two-phase locking protocol guarantees conict serializability.
(b) Show that the conservative two-phase locking protocol guarantees that there will be no deadlock.
(c) Show that the wound-wait protocol guarantees that there will be no deadlock and no starvation.
Explanation / Answer
(a) Show that the basic two-phase locking protocol guarantees conict serializability.
This proof is by contradiction, and assumes binary locks for simplicity. A similar proof can be made for shared/exclusive locks.)Suppose we have n transactions T1, T2, ..., Tn such that they all obey the basictwo-phase locking rule (i.e. no transaction has an unlock operation followed by a lockoperation. Suppose that a non-(conflict)-serializable schedule S for T1, T2, ..., Tndoes occur, the precedence (serialization) graph for S must have a cycle. Hence, there must be some sequence within the schedule of the form:S: ...; [o1(X); ...; o2(X);] ...; [ o2(Y); ...; o3(Y);] ... ; [on(Z); ...; o1(Z);]...where each pair of operations between square brackets [o,o] are conflicting (either [w,w], or [w, r], or [r,w]) in order to create an arc in the serialization graph. Thisimplies that in transaction T1, a sequence of the following form occurs:T1: ...; o1(X); ... ; o1(Z); ...Furthermore, T1 has to unlock item X (so T2 can lock it before applying o2(X) to followthe rules of locking) and has to lock item Z (before applying o1(Z), but this must occur after Tn has unlocked it). Hence, a sequence in T1 of the following form occurs:T1: ...; o1(X); ...; unlock(X); ... ; lock(Z); ...; o1(Z); ...This implies that T1 does not obey the two-phase locking protocol (since lock(Z) followsunlock(X)), contradicting our assumption that all transactions in S follow the two-phaselocking protocol.
(b) Show that the conservative two-phase locking protocol guarantees that there will be no deadlock.
Two-phase locking does not ensure freedom from deadlocks .Cascading roll-back is possible under two-phase locking. To avoid this, follow a modified protocol called strict two-phase locking. Here a transaction must hold all its exclusive locks till it commits/aborts. Rigorous two-phase locking is even stricter: here all locks are held till commit/abort. In this protocol transactions can be serialized in the order in which they commit.
(c) Show that the wound-wait protocol guarantees that there will be no deadlock and no starvation.
wound-wait scheme — preemptive older transaction wounds (forces rollback) of younger transaction instead of waiting for it. Younger transactions may wait for older ones. Less prone to rollbacks than wait-die scheme.
Both in wait-die and in wound-wait schemes, a rolled back transactions is restarted with its original timestamp. Older transactions thus have precedence over newer ones, and starvation is hence avoided. Timeout-Based Schemes:
a transaction waits for a lock only for a specified amount of time. After that, the wait times out and the transaction is rolled back. thus deadlocks are not possible simple to implement; but starvation is possible. Also difficult to determine good value of the timeout interval.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.