无锁队列中哪里有bug？

Question

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

错误可以通过异常("null head")可见。这是不可能的状态，因为存在保持当前队列大小的原子整数。队列有一个存根元素。它规定读取器线程不更改尾指针，写入线程不更改头指针。

队列长度变量保证链接列表永远不会为空。这是信号量。

采取的方法的行为就像它得到偷来的长度值一样。

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()中使用计数器有错误，当删除存根时，长度会减少1，但是在末尾添加存根时不要重新增加它，因为使用addNode()而不是add()。假设您成功地添加了一个元素，所以您的队列如下所示：

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

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

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

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

编辑:好的食物对我有好处，我想出了一个触发head空异常的序列。让我们从一个有效的队列开始，其中包含一个元素，如前面所示：

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

现在我们有四个线程，两个尝试takeOrNull()，两个并发添加()。两个添加线程都正确地移动了尾指针，第一个线程将尾指针从第一个移动到第二个，然后暂停。第二个添加线程将尾从第二个移动到第三个，然后更新旧的尾(秒)的下一个指针，然后递增计数器并退出。我们只剩下：

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

现在，两个takeOrNull线程唤醒并执行，因为长度为3，两个线程都可以获得一个元素！第一个将头从存根移动到第一个，第二个将头从第一个移动到NULL。现在HEAD为null，每当takeOrNull()被调用next时，异常！