1 (40 points). Below is pseudocode for a mutual exclusion algorithm based on a shared queue q. Ench process P (i=0,1) enqueues its index into q when it wishes to enter the critical section. When P's index is at the head of q. P. can enter. Hence, q can take on the following values: (empty). [O] (contains index 0), [1] (contains index 1). [01] (contains index 0 at head and index 1 at tail), [10] (contains index 1 at bcad and index 0 at tail). q is accessed using three operations: 1. head(9) returns the head, c.g., head([1 0]) = 1 and 2. taill() returns the tail, e.g., lail([10])=0 3. enqueue(q,c) returns the result of inserting item e at the end of a and is modified by the usual assignment statement. Initially 4 is empty Pia Po: while true do choose skip or go to next statement; 4:= enqucue(q,0); while head(9) *0 skip; critical region; q=tail(); while true do choose skip or go to next statement; 9: enqueue(4, 1); while head() #1 skip; critical region; 9:= taill): Assume that each assignment statement executes atomically, i.e., its substeps do not interleave with those of statements from the other process (a) Either prove that mutual exclusion of the critical sections holds, i.e., that both Po and Pare not in their critical regions at the same time, or give a counterexample. (b) Either prove that that absence of starvation holds, i.e., if P; (i = 0 or i = 1) inserts its index into q, then it will eventually enter its critical region, or give a counterexample. Now remove the atomicity assumption, so that, for example, the reads and writes that are substeps of an assignment statement can interleave with the substeps of an assignment from the other process. One way to mode this is to break down the assignments into primitive steps, which gives the following program, where to and are local variables of process Ph and respectively. PE while true do choose skip or go to next statement; Po:: while true do choose skip or go to next statement; to: engucuc(1o,0); 9:=lo; while head(9) 40 skip: critical region; Lo :- Lo := tail(lo); q=toi enqueue(t, 1); 9=11; while head() #1 skip; critical region 4 11:= taill.); Now repeat (n) and (b) for the above program