java多处理器编程：无锁堆栈

Question

在为即将到来的并发系统考试做准备时，我试图完成教科书《多处理机编程的艺术》中的一些问题。有一个问题困扰着我：

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?.

这个问题困扰着我，因为我想到的第一件事是它没有意义，因为退避对象所做的就是让进程等待，所以为什么不共享它呢？问题的第二部分我完全想不起来，欢迎提供任何帮助

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

不确定我的闲聊是否有用，但我还是会按“发布”按钮

答案取决于backoff()的实现。因为这里的目标是避免同步，所以在ThreadLocal中不会有任何本地存储。如果退避算法使用随机化器，那么它也需要是可重入的。所以你很可能能够在pop和push之间分享它，现在你想分享吗。由于push和pop都试图改变top引用，因此如果回退给出的连续线程的数量相差很大，那就更好了。关于推送或流行音乐有更多的争论吗？我们需要用一种或另一种方法更积极地退让吗？如果这是一个通用堆栈，那么你就不知道了

至于退让如何“重组”，我也不确定。你能利用一次成功的推送或弹出作为一个机会来限制退避时间吗？随机退避等待与由ThreadLocal指定的序列中的素数之间的差异如何

Answer 2

从同步的角度来看第一个问题，我认为允许push和pop使用相同的BackOff对象是有意义的。不管这个类的实现如何。这样做的原因是，如果我们有一个堆栈，我们必须在移除和向堆栈中添加项的过程中保持一致的状态。然而，如果我们只进行了一次查看（查看第一个元素或堆栈顶部），那么我们可能会有多个BackOff对象在读取时查看它，而不应该锁定所讨论的数据源。第二个问题将要求发布该类的代码