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
6 Node(E item) {this.item = item;}
7 }
8
9 AtomicReference
10 AtomicReference
11
12 public void enqueue(E item) {
13 Node
14 Node
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