6

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

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

3 回答 3

1

从同步的角度来看第一个问题，我相信允许相同的BackOff对象同时用于推送和弹出是有意义的。不管这个类的实现。这样做的原因是，如果我们有一个堆栈，我们必须在堆栈中删除和添加项目时保持一致的状态。但是，如果我们只是偷看（查看第一个元素或堆栈顶部），那么我们可能会有多个BackOff对象查看它，因为读取不应锁定相关数据源。第二个问题将要求为该类发布代码。

于 2010-11-03T22:14:21.417 回答
1

不确定我的任何胡言乱语是否有帮助，但无论如何我都会按下“发布”按钮。

答案取决于backoff(). 由于这里的目标是避免同步，因此不会有任何本地存储——也许在ThreadLocal. 如果退避算法使用随机化器，它也需要是可重入的。因此，您很可能能够pop在和之间共享它push——现在您想要。由于 push 和 pop 都试图改变top引用，如果退避给连续的线程提供了截然不同的数字会很好。是否有更多关于 push 或 pop 的争论？我们是否需要用一种或另一种方法更积极地退缩？如果这是一个通用堆栈，那么您将不知道。

至于如何“重组”退避，我也不确定。您能否利用成功的 push 或 pop 作为机会来缩短回退时间？随机退避等待与由 分配的序列中的素数之间的区别如何ThreadLocal？

于 2010-11-03T22:05:21.413 回答
0

在这种情况下，使用退避是过度的。

任何现实世界的应用程序都应该花费更多的时间来处理节点，而不是把东西推入和推下堆栈。相比之下，堆栈操作应该很短。因此，两个线程极不可能同时访问堆栈。但是，它有时会发生，因此您需要编写正确的代码。 

public void push(T value) { 
   Node node = new Node(value); 
   while (!tryPush(node)) 
       backoff.backoff(); 
 }

恕我直言：可以缩短为

public void push(T value) { 
   Node node = new Node(value); 
   while (!tryPush(node));
}
于 2010-11-04T19:10:27.590 回答