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