Unbounded Lock free stack

Question 1

Is an unbounded Lock free stack atomic?

Answer 1

Yes. Lock free = atomic

Question 2

What methods does it use to change the link values in the list?

Answer 2

compareAndSet

Question 3

Give the code to tryPush code

Answer 3

public boolean tryPush(Node node){
Node oldTop = top.get();
node.next = oldTop;
return(top.compareAndSet(oldTop, node))
}

Question 4

When does the tryPush return false?

Answer 4

When another thread has already modified the top. There is high contention

Question 5

When is it better to use a backoff?

Answer 5

when there is high contention

Question 6

Give the push function code

Answer 6

public void push(T value) {
Node node = new Node(value);
while (true) {
if (tryPush(node)) {
return;
} else backoff.backoff();
}}

Question 7

Give the code for the pop function

Answer 7

public T pop() throws EmptyException {
while (true) {
Node returnNode = tryPop();
if (returnNode != null)
return returnNode.value;
else
backoff.backoff();
}
}

Question 8

Give the code for the tryPop

Answer 8

protected Node tryPop() throws EmptyException {
Node oldTop = top.get();
if (oldTop == null)
throw new EmptyException()
Node newTop = oldTop.next;
if (top.compareAndSet(oldTop, newTop))
return oldTop;
else
return null;
}

Question 9

What is good/bad about the lock-free stack

Answer 9

Good: No locking
Bad: Even with backoff there is huge contention at the top. no real parallelism

Question 10

Does the lock-free stack scale properly? And why?

Answer 10

No.
Stack’s top field is a source of contention
Sequential bottleneck ( Method calls can proceed only one after the other)

Question 11

Does exponential backoff help for the lock free stack?

Answer 11

No. Makes contention better but does nothing for bottleneck