[SOLVED] Question 2

Question 2
A deque is a double-ended queue where elements can be added and removed at both ends. The aim of this question is to develop two concurrent implementations of a deque using a linked list where each node contains one value. The first implementation should use locks in a way that operations on different ends of the deque only interfere if there are very few elements in the deque; the second one should be lock-free.
The trait of a deque is given by:
/ A total deque holding data of type T. trait Deque[T]{
/ Add x at the head of the deque. / def addFirst(x: T) : Unit
/ Add x at the tail of the deque. / def addLast(x: T) : Unit
/ Remove and return the first element of the deque.
@return Some(x) where x is the value removed from the head, or None if the deque is empty. /
def removeFirst : Option[T]
/ Remove and return the last element of the deque.
@return Some(x) where x is the value removed from the tail, or None if the deque is empty. /
def removeLast : Option[T] }
For each of the two implementations, you should write a description of your implementation, giving an overview of the datatype, a description how each operation works, and any other interesting points, such as aspects that are necessary to avoid certain errors. For an observation that holds in both implementations you may cross-reference to avoid verbatim copies.
In particular, your description and/or code comments should cover the following points:
The abstraction function and any interesting datatype invariants;
Linearization points for each operation;
Any ideas you may have as to how this implementation could be made more efficient.
You should also include a linearizability tester that can be used for each implementation, together with a very brief summary of the tests you ran.
Note that two thirds of the marks are allocated for the explanation of the design addressing the points above. Most of these marks can be achieved without finalising the coding. One third of the marks are allocated for the program itself.
(a) The first implementation should use locks in a way that allows operations on different ends of the deque to work without interference, as long as there are enough elements in the deque.
Your implementation should have the following header:
class ListDeque[T] extends Deque[T].
3

One suggestion is to use the following class of nodes:
class Node(val value: T){
@volatile var prev: Node = null @volatile var next: Node = null @volatile var mark: Boolean = false val l: Lock = Lock.FairLock
def lock = { l.lock }
def unlock = { l.unlock }
}
where the elements of the deque are the values of the unmarked nodes that are reachable from a dummy node head following the next-references, excluding the last node which is always the dummy node tail. The prev-references are meant to make the structure a doubly- linked list, but temporarily we only require that for each node n = tail we can follow the next-references from node n.prev to get back to node n. (20+10 marks)
(b) The second implementation should be lock-free. As we cannot have operations that work on two nodes atomically, one suggestion is to use a similar set-up as proposed for part (a), i.e. an approximate doubly linked list where the back pointer does not necessarily point to the immediate predecessor in the list according to the next-references from head to tail.
Your implementation should have the following header:
class LockFreeDeque[T] extends Deque[T].
A possible class of nodes to be used for the lock-free implementation could be:
class Node(val value: T){
val link = new AtomicPair[(Node,Node),Boolean](
(null.asInstanceOf[Node], null.asInstanceOf[Node]), false) def prev = link.getFirst. 1
def next = link.getFirst. 2
def mark = link.getSecond }.
4
LAST PAGE
(20+10 marks)