Answer sketches for the exam on 27 Oct 2018. 1a. Correct. A process can only be stuck on line 14. Assume one process is stuck here. The other process will either loop in the outer loop, eventually coming to line 15, and release the stuck process. If a process is stuck when the other process executes line 16 and finds the goal, the stuck process is released via line 21. In any case, both processes will always terminate, given a goal is found. 1b. Assume goal>0. Let p proceed till i=goal, and p is at line 17, and t=1 (points at q). Before p sets found=true, let q do a whole loop, using its turn. At line 15, it sets t=0 (p's turn). Let q continue past the whole loop, and back into line 14, where it loops. Let p exit now. q is stuck. 2a. In the transition table below, pi = "p is at Li", T = true, and so on. s = (pi, qi, z[0], z[1], t) sp=next state if p moves sq=next state if q moves s1 (p2, q2, T, T, 0) (p3, q2, F, T, 1) = s5 (p2, q3, T, F, 0) = s3 s2 (p2, q2, T, T, 1) (p3, q2, F, T, 1) = s5 (p2, q3, T, F, 0) = s3 s3 (p2, q3, T, F, 0) (p3, q3, F, F, 1) = s7 (p2, q5, T, F, 0) = s4 s4 (p2, q5, T, F, 0) (p3, q5, F, F, 1) = s8 (p2, q2, T, T, 0) = s1 s5 (p3, q2, F, T, 1) (p5, q2, F, T, 1) = s9 (p3, q3, F, F, 0) = s6 s6 (p3, q3, F, F, 0) (p5, q3, F, F, 0) = s10 no move s7 (p3, q3, F, F, 1) no move (p3, q5, F, F, 1) = s8 s8 (p3, q5, F, F, 1) no move (p3, q2, F, T, 1) = s5 s9 (p5, q2, F, T, 1) (p2, q2, T, T, 1) = s2 (p5, q3, F, F, 0) = s10 s10 (p5, q3, F, F, 0) (p2, q3, T, F, 0) = s3 no move 2b. No state (p5, q5, ...) 2c. No state where both p and q are stuck in the same state 2d. zp iff p2. zq iff q2. So we don't need zp and zq. t is needed only to separate s1-s2 and s6-s7. Elsewhere, q2 iff t1. Alternatively, p2 iff t0. So for most states, we only need pi and qj. For s1, s2, s6 and s7, we also need t. 2e. Start with S = s9, s0. Then S = s9, s10, s6. S = s9, s10, s6, s5. S = s9, s10, s6, s5, s8. S = s9, s10, s6, s5, s8, s7. That leaves s1 - s4, all p2-states, each with a p-move into S. The system can loop here, and avoid S, only by choosing q every time. 3a. Base case: s1 satisfies N. Step cases: Departing from p2 sets zp false (at L2). Returning to p2 (at L5) sets zp true. Similarly for q. 3b and 3c. Just follow the detailed instructions in the questions themselves! 4a. The network starts with ints feeding into front. Every time front sees a number N, it splits into filter(N) and front. So we have ints--filters--front. A detailed image can be found on the course web page. The program prints 2, 4, 8, 16, 32, 64. 4b. start(3,100) produces 3, 6, 12, 24, 48, 96 and start(5,100) produces 5, 10, 20, 40, 80. 4c. Yes it terminates when it reaches MAX. 4d. No, this can be tested by putting in random sleeps. Erlang process mailboxes are FIFO. Some argued that the filters doesn't matter, but front does. This is not the case, as front, after the first message, will become a filter. 4e. Change N rem P == 0 to N rem P /= 0. 5a. If w1 registers first, it will cross first. The rest is any interleaving of (e1 registers, e1 crossing) and (e2 registers, e2 crossing). If the sequence begins "e1 registers, w1 registers", then e1 will cross first. The rest can be "w1 crossing, e2 registers, e2 crossing" or "e2 registers, e2 crossing, w1 crossing". 5b. Yes, because each car only crosses once, and there can only be a finite number in each direction. 5c. Let TEW be toll + EW[E] + EW[W] and let I be the boolean 0 <= TEW <= 1. We have to show I is invariant. The three semaphores are initialized (T=1, E=W=0), so I is true at the start. Examining the program, we see that each acquire is followed by a release, although not necessarily of the same semaphore. Since there are no computations with two releases without an intervening acquire, the value of the expression cannot be larger than one. 5d. The formula (b[1] > 0) -> (b[0] = 0) is true initially, since the antecedent is false. How can the antecedent become true? Only by getting to line 23, either because b[0] = 0 at line 18, or via line 33 after line 21, which again means b[0] = 0. 6a. Lock free, but none of the other properties. 6b. Starvation-, wait-, lock-free. Can fail after 10000 iteratiobs. 6c. Do test-and-test-and-set. So embark on CAS only if current=expect. 6d. If contention very high.