Multiprocessor programming: lock-free stacks

Question

In preperation for my upcoming Concurrent Systems exam, I am trying to complete some questions from the text book "The Art of Multiprocessor Programming". One question is bugging me:

Exercise 129: Does it make sense to use the same shared BackOff object for both pushes and pop in our LockFreeStack object? How else could we structure the backoff in space and time in the EliminationBackOffStack?.

This question bugs me because the first thing that comes to my mind is that it does not make sense because all a backoff object does is make a process wait, so why not share it? The second part of the question totally eludes me and any help is most welcome.

The code for the LockFreeStack:

public class LockFreeStack<T> {

    AtomicReference<Node> top = new AtomicReference<Node>(null);

    static final int MIN_DELAY = ...;
    static final int MAX_DELAY = ...;
    Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY);

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

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

Answer 1

Not sure if any of my ramblings help but I'll press the "Post" button anyway.

The answer depends on the implementation of backoff(). Since the goal here is to avoid synchronization, there won't be any local storage -- maybe some in a ThreadLocal. If the backoff algorithm uses a randomizer it will need to be reentrant as well. So most likely you are able to share it between pop and push -- now do you want to. Since push and pop are both trying to alter the top reference, it would be good if the backoff gave successive threads vastly different numbers. Is there more contention around push or pop? Do we need to be more aggressively backing off with one or the other method? If this is a generic stack then you won't know.

In terms of how the backoff can be "restructured", I'm also not sure. Could you use a successful push or pop as a opportunity to throttle back on the backoff times? How about the difference between random backoff waits versus prime numbers in a sequence assigned by ThreadLocal?

Answer 2

Approaching the first question from a synchronization stand point, I believe it would make sense to allow the same BackOff object for both pushes and pops. Regardless of the implementation of this class. The reason for this is that if we have a stack we must maintain a consistent state across the removal and addition of items to the stack. If however, we were only doing a peek (looking at the first element or top of the stack) than we could have more than one BackOff object looking at it as reads should not make a lock on the data source in question. The second question is going to require the code be posted for that class.