java - 多处理器编程: lock-free stacks

在准备即将进行的并发系统考试时，我正在尝试完成教科书“多处理器编程的艺术”中的一些问题。一个问题困扰着我:



这个问题困扰着我，因为我首先想到的是它没有任何意义，因为所有退避对象所做的只是让一个进程等待，所以为什么不共享它呢？问题的第二部分完全使我难以理解，欢迎您提供任何帮助。

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();
            }
        }
    }

最佳答案

不确定我是否有任何帮助，但我还是要按“发布”按钮。

答案取决于backoff()的实现。由于此处的目标是避免同步，因此将没有任何本地存储-可能在ThreadLocal中。如果退避算法使用随机化器，则它也需要重新进入。因此，很可能您现在可以在pop和push之间共享它了。由于push和pop都在尝试更改top引用，因此，如果退避给连续线程提供大大不同的数字，那将是很好的选择。推送或弹出式广告有更多争议吗？我们是否需要更积极地支持一种或另一种方法？如果这是通用堆栈，那么您将不知道。

关于如何“重组”补偿，我也不确定。您能否利用成功的推送或弹出来减少退避时间的机会？在ThreadLocal分配的序列中，随机退避等待与素数之间的区别如何？

关于java - 多处理器编程: lock-free stacks，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4052259/