The following algorithm (Fig. 5) is for two threads 1 and 2, and it makes use of two registers: x which can hold three values (0, 1, and 2); and y which can hold two values (0 and 1). Both threads can read and write registers x and y. The symbol i is used to designate the thread-id, and can be 1 or 2. Figure 5

a. Show that it satisfies mutual exclusion and deadlock-freedom for two threads.

b. Does it satisfy starvation-freedom for two threads?

c. Does it satisfy deadlock-freedom for three threads? That is, i can be 1, 2 or 3.

d. Does it satisfy mutual exclusion for three threads? That is, i can be 1, 2 or 3. For each question, you should either sketch a proof, or display an execution where it fails.

Initially: 1 start: x :- 1 2 3 4 5 6 7 8 9 10 11 12 x-0 and y-0 13 14 if y0 then await y-0; goto start; end if; y := 1; if xi then y = 0 await x = 0; goto start; end if; y = 0; x = 0