闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSSE7610

Concurrency: Theory and Practice

SEMESTER TWO FINAL EXAMINATION 2020

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)

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)

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.

// Lock-free Queue

public class LockFreeQueue<E> {

class Node<E> {

E item;

AtomicReference<Node> next;

Node(E item) {this .item = item;}

}

AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(); AtomicReference<Node<E>> tail = head;

public void enqueue(E item) {

Node q = new Node(item);

Node<E> p;

do {

p = tail .get();

success = p.next.compareAndSet (null, q);

if(!success) tail.compareAndSet(p, p.next);

} while (!success)

tail .compareAndSet(p, q);

}

public E dequeue() throws EmptyQueueException {

...

}

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)

3. Complete the dequeue() method. (5 marks)

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

p1: p2: p3: p4: p5: p6: p7: p8: p9: p10: p11: