java - 这个(无锁)队列实现是线程安全的吗？

Question

我正在尝试用Java创建一个无锁队列实现，主要用于个人学习。队列应该是通用队列，允许任意数量的读者和/或作者并发。

请您审核一下，并提出您发现的任何改进/问题吗？

谢谢。

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> {
    private static class Node<E> {
        E value;
        volatile Node<E> next;

        Node(E value) {
            this.value = value;
        }
    }

    private AtomicReference<Node<T>> head, tail;

    public LockFreeQueue() {
        // have both head and tail point to a dummy node
        Node<T> dummyNode = new Node<T>(null);
        head = new AtomicReference<Node<T>>(dummyNode);
        tail = new AtomicReference<Node<T>>(dummyNode);
    }

    /**
     * Puts an object at the end of the queue.
     */
    public void putObject(T value) {
        Node<T> newNode = new Node<T>(value);
        Node<T> prevTailNode = tail.getAndSet(newNode);
        prevTailNode.next = newNode;
    }

    /**
     * Gets an object from the beginning of the queue. The object is removed
     * from the queue. If there are no objects in the queue, returns null.
     */
    public T getObject() {
        Node<T> headNode, valueNode;

        // move head node to the next node using atomic semantics
        // as long as next node is not null
        do {
            headNode = head.get();
            valueNode = headNode.next;
            // try until the whole loop executes pseudo-atomically
            // (i.e. unaffected by modifications done by other threads)
        } while (valueNode != null && !head.compareAndSet(headNode, valueNode));

        T value = (valueNode != null ? valueNode.value : null);

        // release the value pointed to by head, keeping the head node dummy
        if (valueNode != null)
            valueNode.value = null;

        return value;
}

Answer 1

代码不是线程安全的。考虑 putObject(...):

public void putObject(T value) {
    Node<T> newNode = new Node<T>(value);
    Node<T> prevTailNode = tail.getAndSet(newNode);
    prevTailNode.next = newNode;
}

第二个语句在设置前一个节点的 next 指针之前添加新节点。这只发生在第三个声明中。因此，有一个窗口，其中next 是null；即竞争条件。

即使您解决了这个问题，还有一个更隐蔽的问题。读取 Node 对象的 next 字段的线程不一定看到第二个线程刚刚写入的值。这是 Java 内存模型的结果。在这种情况下，确保后续读取始终看到较早写入值的方法是:

• 声明next为volatile，或者
• 在同一对象上的原始互斥量中进行读取和写入。

编辑:在更详细地阅读 getObject() 和 putObject() 的代码时，我可以看到没有什么强制 的非空值next 将被刷新到 putObject 中的内存中，并且没有任何东西强制 getObject 从主内存中读取 next。因此 getObject 代码可能会看到错误的 next 值，导致它在队列中确实有元素时返回 null。