线程安全和无锁队列实现

Question

我试图用Java创建一个没有锁的队列实现，主要是为了个人学习.队列应该是一个通用队列，允许任意数量的读取器和/或写入器并发。

请您回顾一下，并建议您所发现的任何改进/问题？

(来自StackOverflow的交叉邮件)

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> {
    private static class Node<E> {
        final 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

是。

• 易失性操作和比较和交换操作的组合足以确保Node对象安全地发布。
• 在这两种方法中，比较和交换必须在分配给volatile变量之前进行，所以您在这里很好。它们不需要原子化地发生。

队列表现出奇怪的行为。假设线程1在CAS之后但在最后一次赋值之前在putObject()中停止。下一个线程2完整地执行putObject()。下一个线程三调用getObject()，即使线程2已经完全完成，它也不能看到前两个对象中的任何一个。记忆中正在建立一条小链。只有在线程1完成之后，putObject()才能在队列中看到两个对象，这有点令人惊讶，并且比大多数非阻塞数据结构的语义更弱。

另一种看待奇数API的方法是，拥有一个非阻塞的put()是很好的，但是有一个非阻塞的get()是非常奇怪的。这意味着队列必须与重复轮询和休眠一起使用。

Answer 2

我不喜欢你的“放”程序。其他人注意到的“奇怪行为”意味着该算法失去了“无锁”的主要优点之一:不受优先级反转或异步终止线程的影响。如果线程在队列写入操作的中间被拦截，除非或直到队列完成工作，否则队列将完全中断。

解决方案是在更新“尾”指针之前先对最后一个节点的“下一步”指针进行CompareAndSet；如果“最后一个节点”‘S“下一个”指针“为非空指针，这意味着它不再是最后一个节点，必须遍历链接才能找到真正的最后一个节点，在其上重复CompareAndSet，并希望它仍然是最后一个节点。

Answer 3

虽然OP的解决方案对我来说是对的，但Ron的改进发明了一个竞赛条件：

线程1(在getObject()中)：

} while (!refHead.compareAndSet(head, next));

T value = next.value;

线程1在这里挂起，因此尚未执行。

next.value = null;

我们知道值！=null和refHead现在是下一个，所以refHead.get().value!=null

线程2(在getObject()中)：

    head = refHead.get();
    assert head.value == null;

在这里，断言咬咬，即使一切都会好起来后，线程1继续。