CSSE7610 Concurrency: Theory and Practice SEMESTER TWO FINAL EXAMINATION 2022
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 2022
Question 1 (11 marks)
The algorithm below attempts to solve the critical section problem for two threads, p and q. In this algorithm, process p is given priority over process q.
Remember the assumption of the critical section problem that the critical section must progress, and the non-critical section needs not progress.
A priority mutual exclusion algorithm |
||
integer p ← 1, q ← 1 |
||
p |
q |
|
p1: p2: p3: p4: p5: p6: p7: p8: |
loop forever non-critical section p ← 0 await q = 1 critical section p ← 1 |
loop forever q1: non-critical section q2: q ← 0 q3: while p = 0 q4: q ← 1 q5: await p = 1 q6: q ← 0 q7: critical section q8: q ← 1 |
(i) Provide a proof by induction that the algorithm ensures mutual exclusion. If you require any invariants in your proof, they must appear as lemmas and also be proved. (5 marks)
(ii) Use Linear Temporal Logic (LTL) to state the starvation freedom in this algorithm.
(a) Does the algorithm ensure starvation freedom for process p? If yes, prove it; otherwise, give a fragment of the state diagram as a counterexample.
(b) Does the algorithm ensure starvation freedom for process q? If yes, prove it; otherwise, give a fragment of the state diagram as a counterexample. (6 marks)
Question 2 (14 marks)
Consider a shared savings account which holds a non-negative balance, and provides two operations deposit(k) and withdraw(k).
❼ deposit(k) adds k to the balance
❼ withdraw(k) subtracts k, if the balance is at least k, and otherwise blocks until the balance becomes k or greater.
(i) Implement this savings account as a monitor. Use language-independent notation (as in Question 1) to do this. There is no need to show the processes that use the monitor. Clearly state your assumptions if any. (5 marks)
(ii) Now, suppose there are two kinds of withdrawals: ordinary and priority. Modify the monitor to ensure that no ordinary withdrawal occurs if there is a priority withdrawal waiting. (5 marks)
(iii) The following method which transfers a sum from one account to another is added
to a Java implementation of the savings account:
1 synchronized void transfer(int k, Account other) {
2 other .withdraw(k);
3 deposit(k);
4 }
Assuming there is a thread that periodically deposits money into all bank accounts, can the use of the above transfer method lead to deadlock? Explain why or why not? (4 marks)
Question 3 (15 marks)
(i) Below is a partial Java implementation of the MCSLock.
1 public class MCSLock implements Lock {
2 class QNode {
3 boolean locked = false ;
4 QNode next = null ; 5 }
6 AtomicReference<QNode> tail = new AtomicReference<QNode>(null);
7 ThreadLocal<QNode> myNode = new ThreadLocal<QNode>( ) {
8 protected QNode initialValue( ) {
9 return new QNode( );
10 }
11 };
12 public void lock( ) {
13 QNode qnode = myNode .get( );
14 QNode pred = tail .getAndSet(qnode);
15 if (pred != null) {
16 qnode .locked = true ;
17 pred .next = qnode;
18 while (qnode .locked) { } 19 }
20 }
21 }
Implement an additional method, trylock( ), which acquires the lock only if it is immediately free. That means, trylock( ) returns without waiting for the lock to become available. The method should return true when it successfully acquires the lock, and false otherwise. (5 marks)
(ii) A stack is a last-in-first-out (LIFO) data structure with an operation, push, to add
an element to the top of the stack, and an operation, pop, to remove the element at the top of the stack. Consider the following non-blocking implementation of a stack.
1 public class LockFreeStack<E> {
2 class Node<E> {
3 E item;
4 Node<E> next;
5 Node(E item) {this .item = item;} 6 }
7 AtomicReference< Node<E> > top = new AtomicReference< Node<E> >( );
8 public void push(E item) {
9 Node<E> newHead = new Node<E>(item);
10 Node<E> oldHead;
11 do {
12 oldHead = top .get( );
13 newHead .next = oldHead;
14 } while (!top .compareAndSet(oldHead, newHead));
15 }
16 public E pop( ) {
17 Node<E> oldHead;
18 Node<E> newHead;
19 do {
20 oldHead = top .get( );
21 if (oldHead == null)
22 return null ;
23 newHead = oldHead .next;
24 } while (!top .compareAndSet(oldHead, newHead));
25 return oldHead .item; 26 }
27 }
(a) Explain why the compareAndSet operation is needed in the method push by
providing an erroneous scenario that could occur if the do-while loop were replaced by
1 2 3 |
oldHead = top .get( ); newHead.next = oldHead ; top = newHead; |
(5 marks)
(b) Provide a similar scenario to explain why the compareAndSet operation is re-quired in the pop method. (5 marks)
Question 4 (10 marks)
In a blockchain system, a leader is often needed to propose a new block. The following leader-election protocol is used to choose a unique leader node from amongst a group of nodes in a distributed system. It uses the “first declaration wins” strategy, i.e., the first node to declare itself leader becomes the leader.
First declaration wins |
set of node IDs leader ← empty set |
Send |
p1: if leader = empty set p2: for all other nodes N p3: send(declaration, N, myID) p4: add myID to leader |
Receive |
p5: receive(declaration, source) p6: add source to leader |
(i) Explain why this algorithm will not work, and provide a modification to the above which will overcome the problem. Your modification should not use token passing. (5 marks)
(ii) Provide an alternative modification to the algorithm to solve the problem using token passing. Initially, a single node should hold a token. This node need not be the one that becomes leader. (5 marks)
2022-12-05