多处理器编程：无锁栈

Question

为了备考我的并发系统考试，我正在尝试完成《多处理器编程艺术》这本教材中的一些问题。其中有一个问题让我很困扰：

练习 129：在我们的 LockFreeStack 对象中，是否使用相同的共享 BackOff 对象用于 push 和 pop 是有意义的？我们如何在 EliminationBackOffStack 中在空间和时间上构建 backoff？

这个问题让我觉得不可行，因为 backoff 对象所做的只是让进程等待，那么为什么不能分享它呢？问题的第二部分完全使我困惑，希望能得到任何帮助。

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

- Anton Scholtz

---

Backoff.backoff()方法实际上是实现指数退避算法，用于控制重试操作的频率和时间间隔。"EliminationBackOffStack"是一种数据结构，用于在多线程环境下执行非阻塞算法，可以加快并发处理的速度。请提供有关这些领域的更多信息。 - K Erlandsson

你能提供一些{{Backoff}}类的信息或者代码吗？它是否执行某种指数退避？ - The Alchemist

http://books.google.com/books?id=pFSwuqtJgxYC&lpg=PA253&ots=10QEvrNBh1&dq=eliminationbackoffstack&pg=PA253#v=onepage&q=eliminationbackoffstack&f=false - Remus Rusanu

Answer 1

我不确定我的胡言乱语是否有所帮助，但我还是要按下“发布”按钮。

答案取决于backoff()的实现。由于目标是避免同步，因此不会有任何本地存储——可能在ThreadLocal中有一些。如果退避算法使用随机化器，则它也需要是可重入的。因此，最有可能的情况是您可以在pop和push之间共享它——现在您想这样做吗？由于push和pop都试图更改top引用，因此如果退避给连续的线程提供极其不同的数字，那将是很好的。push或pop周围是否有更多争用？我们需要更积极地回退其中一个方法吗？如果这是一个通用堆栈，那么您将不会知道。

关于如何“重构”退避，我也不确定。您能否利用成功的push或pop作为减缓退避时间的机会？随机退避等待与由ThreadLocal分配的序列中的质数之间的差异如何？

- Gray

Answer 2

从同步的角度来看，我认为允许相同的BackOff对象用于推送和弹出操作是有意义的，无论这个类的实现方式如何。原因是如果我们有一个堆栈，我们必须在从堆栈中添加或删除项目时维护一致的状态。然而，如果我们只是查看第一个元素或堆栈的顶部，则可以有多个BackOff对象查看它，因为读取不应该对所涉及的数据源进行锁定。第二个问题需要发布该类的代码。

- Woot4Moo

Answer 3

在这种情况下，使用退避是过度杀伤力。

任何真实世界的应用程序都应该花更多时间处理节点而不是将东西推入和弹出堆栈。相比之下，堆栈操作应该非常短。因此，两个线程极不可能同时访问堆栈。然而，有时会发生这种情况，因此您需要编写正确的代码。

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

- Peter Lawrey

---

这不会导致繁忙等待吗？线程在尝试执行堆栈操作时会浪费 CPU 时间。你说得对，堆栈操作不应该花费太长时间，但如果它是有界堆栈，例如消费者需要很长时间来处理最后一个弹出的元素，那么在堆栈可以接收另一个元素之前可能需要很长时间。 - Mark Peters

没事了，我现在从例子中看到它不太可能是有界的。这只是关于堆栈操作的互斥问题。 - Mark Peters