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.

(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

oldHead  =  top.get(  );

2

newHead.next  =  oldHead;

3

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.

(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)


2023-11-01