Dual data stractures

Question 1

Idea of Dual data structures

Answer 1

reduce synchronization overhead of the synchronous queue. split enq and deq into 2 steps

Question 2

How does the deq work?

Answer 2

if try to remove from empty queue:
put reservation object in queue. wait for enq. Spin on flag in reservation

Question 3

how does enq work?

Answer 3

if sees reservation:
Fulfill by depositing item. set flag to notify dequer

can also enq its own reservations and spin on flag waiting for deq

Question 4

What does the queue consist of(what is the queue made up of)?

Answer 4

either enq reservation, deq reservations or is empty

Question 5

What is good about dual data structures

Answer 5

waiting threads spin on locally cached flag. is linearizable. Ensures fairness

Question 6

how do the nodes of the dual data structure look?

Answer 6

private enum NodeType {ITEM, RESERVATION};
private class Node {
volatile NodeType type;
volatile AtomicReference<T> item;
volatile AtomicReference<Node> next;
Node (T myItem, NodeType myType) {
item = new AtomicReference<T> (myItem);
next = new AtomicReference<Node>(null);
type = myType;
}
}</Node></T></Node></T>

Question 7

how does the enq code look like?

Answer 7

public void enq(T e) {
Node offer = new Node (e, ITEM);
while (true) {
Node t = tail.get(), h = head.get();
if (h == t || t.type == ITEM) {
Node n = t.next.get();
if (t == tail.get()) {
if (n != null) {
tail.compareAndSet(t, n);
} else if (t.next.CAS(n, offer)) {
tail.compareAndSet(t, offer);
while (offer.item.get() == e) {}
h = head.get();
if (offer == h.next.get())
head.compareAndSet(h, offer);
return; }}
} else {
Node n = h.next.get();
if (t != tail.get() || h != head.get() || n ==
null) {
continue;
}
boolean success = n.item.compareAndSet(null,e);
head.compareAndSet(h, n);
if (success)
return;
}}}