多处理器编程:无锁堆栈

Question

在为即将到来的并发系统考试做准备的过程中,我试图从教科书"多处理器编程的艺术"中完成一些问题.一个问题是困扰我:

练习129:在我们的LockFreeStack对象中使用相同的共享BackOff对象进行推送和弹出是否有意义？我们怎样才能在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，如果退避给连续的线程提供截然不同的数字，那就太好了。关于push 和pop 是否存在更多争议？我们是否需要更积极地采用一种或另一种方法？如果这是一个通用堆栈，那么您将不知道。

至于如何“重组”退避，我也不确定。您能否利用成功的推送或弹出作为减少退避时间的机会？随机退避等待与由 指定的序列中的素数之间的差异如何ThreadLocal？