Q1 (8p). (Part a). q1, q2, q3, q4, q1, p1. (1p). (Part b). q1, q2, p1, p2, p3, q3, q1, q2, q3, q4, q1, p1. (2p). (Part c). p1,q1,q2,q3,p2,p3,q4,p1,q1. (2p) (Part d). p1,p2,p3,(p1,p2,p3,q1,q2,q3)* (3p) (Part e). p1,q1,q2,q3,q4,p2,p3* — Also correct solution for d) (2p) Q2 (12p). (Parts a through c). n Pseudo code: static Semaphore starteven = new Semaphore(0); static Semaphore startodd = new Semaphore(0); static Semaphore done = new Semaphore(0); static class Manager implements Runnable { public void run() { boolean evenround = true; while (true) { // Start a round by releasing on the start semaphore if (evenround) { starteven.release(WORKERS); } else { startodd.release(WORKERS); } // Wait for workers to finish done.acquire(WORKERS); // Update the round parity evenround = !evenround; } } } static class Specialist implements Runnable { public void run() { boolean evenround = true; while (true) { // Wait for the start of the next round if (evenround) { starteven.acquire(); } else { startodd.acquire(); } // Do the work // Signal to the manager that work is done done.release(); // Update the round parity evenround = !evenround; } } } And in full Java code: static Semaphore starteven = new Semaphore(0); static Semaphore startodd = new Semaphore(0); static Semaphore done = new Semaphore(0); static class Boss6 extends Boss { protected void start() { Semaphore start; if (this.count % 2 == 0) { start = starteven; } else { start = startodd; } start.release(WORKERS); } protected void finish() { boolean act = false; while (!act) { try { done.acquire(WORKERS); act = true; } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } } } } static class Worker6 extends Worker implements Runnable { Worker6(int id) { super(id); } public void run() { while (count < ROUNDS) { Semaphore start; if (this.count % 2 == 0) { start = starteven; } else { start = startodd; } boolean act = false; while (!act) { try { start.acquire(); doWork(); done.release(); act = true; } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } } } } } Q2 (Part d). (3p) The simplest way to do this with binary semaphores is to declare arrays of binary semaphores start and done, one array element per worker. When a house is completed, the manager signals all the starts, and then waits for each done semaphore in the array order (even if the workers don’t finish in that order). Q3 (12p). (Part a) (4p). The table is: State=(pi, qi, S) next state if p moves next state if q moves 1. (p2, q2, Z) (p3, q2, P) (p2, q3, Q) 2. (p2, q3, Q) (p3, q3, QP) (p2, q5, Q) 3. (p2, q5, Q) (p3, q5, QP) (p2, q2, Z) 4. (p3, q2, P) (p5, q2, P) (p3, q3, PQ) 5. (p3, q3, PQ) (p5, q3, PQ) no move 6. (p3, q3, QP) no move (p3, q5, QP) 7. (p3, q5, QP) no move (p3, q2, P) 8. (p5, q2, P) (p2, q2, Z) (p5, q3, PQ) 9. (p5, q3, PQ) (p2, q3, Q) no move (Part b) There is no state with (p5, q5, S) (2p). (Part c) Every state has at least one move. (2p). (Part d). Prove that every p2-state leads to a p5-state. By defn, 8 and 9 are in M. 5 has to lead to 9. So M = {5, 8, 9} 4 leads to 8 or 5. So M = {4, 5, 8, 9} 6 and 7 have to lead to 4. So M = {4, 5, 6, 7, 8, 9} 1-2-3 can loop by doing only q moves. By fairness, one of them must do a p step at some point, leading to 4, 6, or 7. So M = {1, 2, 3, 4, 5, 6, 7, 8, 9}. ------------------------------------------------------------------------------ Q4. Let Mp = p4-> (S=P v S=PQ). 4a. Show that Mp is invariant. If !p4, Mp holds. Can p arrive at p4 when the consequent is false? p4 can only happen if p does p3. Then the await ensures (S = P v S = PQ). Suppose p is at p4, the consequent is true, and then q spoils it. But only q2 and q5 assign to S. (S = P v S = PQ) followed by q2 yields S=PQ. (S = P v S = PQ) followed by q5 also yields S=P v S=PQ. So []Mp ---------------------------- 4b. Show mutex, Mq = q4-> (S=Q v S=QP). p4 & q4 -> false (no agreement on S). So no such state exists. ---------------------------- 4c. Show that there cannot be deadlock. Suppose [](p3 & q3). Then both awaits wait. So S=Z. But after p2 or q2 (one of them must be the last thing before p3&q3), S cannot remain Z, and neither produces Z. So S is P or QP or Q or PQ. So [](p3 & q3) is impossible. ------------------------------------------------------------------------------ Question 5. (Part a). (2p) init_graders(0) -> ok ; init_graders(N) -> spawn(fun() -> grader() end), init_graders(N-1). (Part b). (6p) grader() -> examiner ! {idle, self()}, receive finished -> ok ; {grade, Exam} -> examiner ! {ready, grade(Exam)}, grader() end. (Part c). The message passing is synchronous. The examiner is blocking while the grader is blocking. Only one worker is working at any given time. (2p) (Part d). Improvement: the communication is now asynchronous and multiple workers can run simultaneously because the examiner doesn’t block. [1 point] Problem: the same ungraded exam could be given to multiple graders, resulting in duplication of work, since the examiner does not keep track of which exams are pending. (Although if you assume get ungraded exam does take this into account, then that should be ok). [2 points] (3p) Q6. (10p). Part a. Method incXY() updates X and Y non-atomically, and hence may run into race conditions. For example, if two threads call incXY() they may interleave so that some increments are lost (as in the concurrent counter example). The getter methods instead are atomic and hence thread safe. (5p). Part b. (5p). Variable lock is a private attribute attached to a Lock object. Only incXY has to be redefined since it is the only state-modifying operation. class LockedPair extends Pair { private Lock lock = new Lock(); @Override public void incXY() { lock.lock(); try { super.incXY(); } finally { lock.unlock(); } } }