java - 无锁队列哪里有bug？

Question

我写了一个Java无锁队列实现。它有一个并发错误。我找不到它。这段代码并不重要。我只是担心我无法解释与 volatile 变量相关的观察到的行为。

该错误通过异常(“空头”)可见。这是不可能的状态，因为存在保存当前队列大小的原子整数。队列有一个 stub 元素。它规定读线程不改变尾指针，写线程不改变头指针。

队列长度变量保证链表永远不会为空。它就像一个信号量。

take 方法的行为就像它获取了窃取的长度值。

class Node<T> {
    final AtomicReference<Node<T>> next = new AtomicReference<Node<T>>();
    final T ref;
    Node(T ref) {
        this.ref = ref;
    }
}
public class LockFreeQueue<T> {
    private final AtomicInteger length = new AtomicInteger(1);
    private final Node stub = new Node(null);
    private final AtomicReference<Node<T>> head = new AtomicReference<Node<T>>(stub);
    private final AtomicReference<Node<T>> tail = new AtomicReference<Node<T>>(stub);

    public void add(T x) {
        addNode(new Node<T>(x));
        length.incrementAndGet();
    }

    public T takeOrNull() {
        while (true) {
            int l = length.get();
            if (l == 1) {
                return null;
            }
            if (length.compareAndSet(l, l - 1)) {
                break;
            }
        }
        while (true) {
            Node<T> r = head.get();
            if (r == null) {
                throw new IllegalStateException("null head");
            }
            if (head.compareAndSet(r, r.next.get())) {
                if (r == stub) {
                    stub.next.set(null);
                    addNode(stub);
                } else {
                    return r.ref;
                }
            }
        }
    }

    private void addNode(Node<T> n) {
        Node<T> t;
        while (true) {
            t = tail.get();
            if (tail.compareAndSet(t, n)) {
                break;    
            }
        }
        if (t.next.compareAndSet(null, n)) {
            return;
        }
        throw new IllegalStateException("bad tail next");
    }
}

Answer 1

我认为在 takeOrNull() 中使用计数器的方式存在错误，当您删除 stub 时，您将长度减少 1，但在最后添加 stub 时不要重新增加它，因为您使用 addNode() 而不是 add()。假设您成功添加了一个元素，因此您的队列如下所示:

Length is 2
STUB -> FIRST_NODE -> NULL
 ^          ^
 |          |
Head       Tail

现在一个线程开始执行 takeOrNull()，长度减少到 1，Head 移动到 FIRST_NODE，并且由于这是 STUB 节点，因此它被重新添加到末尾，所以现在您有:

Length is 1
FIRST_NODE -> STUB -> NULL
 ^             ^
 |             |
Head          Tail

你看到了吗？现在长度是1!在下一个 takeOrNull() 中，即使 FIRST_NODE 仍在队列中并且从未返回，您也会得到 NULL...您只是(暂时)丢失了一条数据。此外，您现在可以无限重复此操作并开始累积节点。就像添加三个节点一样，长度为 4，并且有 FIRST、STUB、NEW1、NEW2、NEW3。如果您随后执行三个 takeOrNull()，则最终会得到 NEW2、NEW3、STUB 和 Length 1。因此，这样您最终会丢失元素，但我承认并不完全确定这将如何触发异常。让我吃点东西再想一想。 ;-)

编辑:好吧，食物对我有好处，我想出了一个触发头空异常的序列。让我们像以前一样从一个包含一个元素的有效队列开始:

Length is 2
STUB -> FIRST_NODE -> NULL
 ^          ^
 |          |
Head       Tail

现在我们有四个线程，两个线程尝试同时执行 takeOrNull() 和两个并发的 add() 操作。两个添加线程都正确移动了尾指针，第一个线程将尾部从 FIRST 移动到 SECOND，然后暂停。第二个添加线程将尾部从第二个移动到第三个，然后更新旧尾部(第二个)的下一个指针，然后递增计数器并退出。我们剩下:

Length is 3
STUB -> FIRST_NODE -> NULL          SECOND_NODE ->  THIRD_NODE -> NULL
 ^                                                     ^
 |                                                     |
Head                                                  Tail

现在两个takeOrNull线程醒来并执行，由于Length为3，两个都将能够获取到一个元素!第一个将 Head 从 STUB 移动到 FIRST，第二个将 Head 从 FIRST 移动到 NULL。现在 HEAD 为 null，每当接下来调用 takeOrNull() 时，都会出现异常!