CSSE7610 Concurrency: Theory and Practice SEMESTER TWO FINAL EXAMINATION 2020 INSTRUCTIONS 1. This examination paper contains FOUR (4) questions and comprises SIX (6) pages. 2. There are 50 marks in total. 3. Answer all questions. The marks for each question are indicated at the beginning of each question. 4. Write your answers on blank pages. At the end of the exam, scan or take photos of all your pages, combine them into a single PDF file and upload to the Blackboard assignment link. Question 1 (15 marks) Recall the atomic statements introduced in lectures. An atomic statement encloses more than one statements that are executed with no possible interleaving among them. That is, no statements by other threads can occur among those statements. The algorithm below attempts to solve the critical section problem for two threads, p and q. Remember the assumption of the critical section problem that the critical section must progress, and the non-critical section needs not progress. Solving critical section problem with atomic statements integer global ← 1 p q integer localp ← 0 integer localq ← 0 loop forever loop forever p1: non-critical section q1: non-critical section repeat repeat p2: atomic{localp ← global; q2: atomic{localq ← global; global ← 0} global ← 0} p3: until localp = 1 q3: until localq = 1 p4: critical section q4: critical section p5: atomic{localp ← 0; global ← 1} q5: atomic{localq ← 0; global ← 1} Let lp, lq , g stand for localp, localq and global, respectively. (i) Prove the following formula is invariant: lp+ lq + g = 1. (2 marks) (ii) Prove that the algorithm ensures mutual exclusion. If you require other invariants in your proof, they must appear as lemmas and also be proved. (3 marks) (iii) Use Linear Temporal Logic (LTL) to state the deadlock freedom in this algorithm. Does the algorithm satisfy this property? If yes, prove it; otherwise, give a fragment of the state diagram as a counterexample. (5 marks) (iv) Use Linear Temporal Logic (LTL) to state the starvation freedom in this algorithm. Does the algorithm satisfy this property? If yes, prove it; otherwise, give a fragment of the state diagram as a counterexample. (5 marks) 2 Question 2 (10 marks) A CSSE7610 student Hypo works as a part-time waiter in a restaurant. The restaurant has a kitchen, several seats and a staff room. Hypo serves the customer at the seat, and serves only one customer at a time. When Hypo finishes serving one customer, he checks whether there are others waiting. If there are, he starts serving one of them; if there are none, he enters the staff room and works on his CSSE7610 assignments. When Hypo is inside the staff room, if the desk bell rings, he comes out and restarts serving the customer. During COVID-19 time, the government requires that the total number of customers in any store must not exceed 10 at any time. Following this, each customer, when they arrive, checks the number of customers that are currently inside the restaurant. If it is ≥ 10, the customer leaves; otherwise, the customer enters the restaurant and checks what the waiter is doing. If the waiter is serving others, the customer seats himself/herself and waits his/her turn. If the waiter is in the staff room, the customer rings a desk bell. (i) Solve this synchronisation problem with semaphores. Do not worry about fairness, and do not give preference to any customer. Any semaphore used must be a weak semaphore, i.e., the process blocked on the semaphore are in a set, not a queue. Use language-independent notation. Clearly state your assumptions if any. Restaurant //define your global variables here waiter customer (6 marks) (ii) Modify your answer to (i) to ensure fairness. Any semaphore used must be a weak semaphore. (4 marks) 3 Question 3 (13 marks) A queue is a first-in-first-out (FIFO) data structure with an operation, enqueue, to add an element to the tail of the queue, and an operation, dequeue, to remove the element from the head of the queue (or throw an exception when the queue is empty). Consider the following partial non-blocking implementation of a queue where head is a dummy node that does not represent an item on the queue, but which points to the element at the head of the queue. Three sub-questions are listed. 1 // Lock-free Queue 2 public class LockFreeQueue
{ 3 class Node { 4 E item; 5 AtomicReference next; 6 Node(E item) {this.item = item;} 7 } 8 9 AtomicReference> head = new AtomicReference>(); 10 AtomicReference> tail = head; 11 12 public void enqueue(E item) { 13 Node q = new Node(item); 14 Node p; 15 do { 16 p = tail.get(); 17 success = p.next.compareAndSet(null, q); 18 if(!success) tail.compareAndSet(p, p.next); 19 } while (!success) 20 tail.compareAndSet(p, q); 21 } 22 23 public E dequeue() throws EmptyQueueException { 24 ... 25 } 26 } 1. Provide a scenario in which the second compareAndSet call of the enqueue() method (line 18) is reached and a second scenario in which the final compareAndSet call (line 20) fails, i.e., return false. (5 marks) 2. Use the while loop instead of the do...while loop to rewrite the enqueue()method. You are allowed to use the similar compareAndSet calls. (3 marks) 4 3. Complete the dequeue() method. (5 marks) 5 Question 4 (12 marks) The Ricart-Agrawala algorithm provides distributed mutual exclusion for a set of nodes in a distributed system. Two sub-questions are listed. Ricart-Agrawala algorithm integer myNum ← 0 set of node IDs deferred ← empty set integer highestNum ← 0 boolean requestCS ← false main loop forever p1: non-critical section p2: requestCS ← true p3: myNum ← highestNum + 1 p4: for all other nodes N p5: send(request, N, myID, myNum) p6: await reply’s from all other nodes p7: critical section p8: requestCS ← false p9: for all nodes N in deferred p10: remove N from deferred p11: send(reply, N, myID) receive Integer source, reqNum loop forever p12: receive(request, source, reqNum) p13: highestNum ← max(highestNum, reqNum) p14: if (not requestCS) or (reqNum < myNum) or ( (reqNum = myNum) and (source < myID) ) p15: send(reply, source, myID) p16: else add source to deferred 1. Discuss what would happen if several nodes have the same value for “myID”. (6 marks) 2. Can the statements p9 — p11 be executed before the statement p8? Explain why or why not. (6 marks) END OF PAPER 6 欢迎咨询51作业君