Assignment 4 due Monday April 28 at the beginning of class

1. Suppose the following is an input schedule (a sequence of read and
write requests).  Give an output schedule including the locks and
unlocks which could be produced by a two-phase locking scheduler.

s = r2(x) w1(x) r2(y) c2 r1(z) c1

Assume that the two-phase locking scheduler unlocks all locks of a
transaction right after accepting the commit of the transaction and
that the first request waiting for a lock on an object is granted and
any other COMPATIBLE lock requests are also granted before the next
operation input after the commit is considered by the scheduler. (So if
r1(y) and r2(y) are waiting for a lock held by w3(y) and then we have
"c3 w4(y)" in the input schedule, t1 and t2 get the shared read lock
before the request for the write lock from t4 is considered.)

Assume lock requests which have not been granted are waiting in order
on a queue. (So if w3(x) is waiting for a lock held by w1(x) and a
later request w4(x) arrives, t3 gets the lock before t4.)

2. Same as question one with

s = r1(x) w2(x) w3(x) r1(y) c1 w2(y) c2 c3


3. Show that the following history could not be output by a two-phase 
locking scheduler. Also show that it is conflict serializable and give a
serial history which is equivalent to s.

s = r1(x) w2(x) c2 w3(x) c3 r4(y) c4 w1(y) c1 

4. Which of the following input schedules would produce deadlock under a 
two phase locking scheduler? Give the waits-for graph for each deadlock and
show an output schedule for each non-deadlock.

a) s = r1(x) r2(x) r3(x) w1(x) c1 w2(x) c2 w3(x) c3

b) s = r1(x) w2(x) w2(y) c2  r1(y) c1 

c) s = r1(x) w2(x) r1(y) c1 w2(y)  c2

d) s = r1(x) w2(y) r1(y) w2(x) c1 c2