Consider the following algorithm for the critical section problem.  The Doran-Thomas algorithm is a variant of Dekker’s algorithm.

(a) Provide a proof by induction that the algorithm ensures mutual exclusion.  If you require other invariants in your proof, they must appear as lemmas and also be

proved by induction.                                                                                 (5 marks)

(b) Use Linear Temporal Logic (LTL) to state that the algorithm is deadlock-free.

Argue informally whether the algorithm satisfies this property.              (5 marks)

(c) Use Linear Temporal Logic (LTL) to state that the algorithm is starvation-free.     Argue informally whether the algorithm satisfies this property for two processes. Argue informally whether the algorithm satisfies this property for n processes.

(5 marks)

Question 2                           15 marks

A queue is a first-in-first out (FIFO) data structure with operations: enqueue, to add an element to the tail of the queue and dequeue, to remove an element from the front of  the queue (or throw an exception if the queue is empty).  Consider the following          concurrent linked-list implementation of a queue in Java.

public class ConcurrentQueue<T> {

class Node<T> {

T item;

AtomicReference<Node> next;

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

}

private AtomicReference<Node<T>> head =              new AtomicReference<Node<T>>();

public void enqueue (T item) …

public T dequeue () throws EmptyQueueException … }

(a)  Provide the code for a simple implementation of the enqueue and dequeue methods

for a concurrent queue. (6 marks)

(b)  A simple implementation of a concurrent queue does not scale well. Explain why this is the case. Provide explanations of two different approaches that could be used to

improve the performance of a concurrent queue.                                       (9 marks)

Question 3                          10 marks

Let P1, P2 and P3 be three tasks. Is the earliest deadline first (EDF) scheduling algorithm   feasible for the following timing constraints? Provide a scheduling diagram which shows the first two times P3 is scheduled.

D1 = p1 = 8, e1 = 4, r1 = 0

D2 = p2 = 10, e2 = 2, r2 = 0

D3 = p3 = 12, e3 = 3, r3 = 2

where Di  is the (relative) deadline, pi  is the period, ei  is the execution time, and ri  is the release time of process Pi .

Question 4                        10 marks