这个（无锁）队列实现线程安全吗？ [英] Is this (Lock-Free) Queue Implementation Thread-Safe?

问题描述

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

I am trying to create a lock-free queue implementation in Java, mainly for personal learning. The queue should be a general one, allowing any number of readers and/or writers concurrently.

请您查看它，并建议您找到的任何改进/问题？

Would you please review it, and suggest any improvements/issues you find?

谢谢。

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

推荐答案

代码不是线程 - 安全。考虑 putObject（...）：

The code is not thread-safe. Consider 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 ;即竞争条件。

The 2nd statement adds the new node before the previous node's next pointer has been set. That only happens in the 3rd statement. Thus, there is a window in which the next is null; i.e. a race condition.

即使你修正了这个问题，也存在一个更加隐蔽的问题。读取Node对象的 next 字段的线程不会必须看到第二个线程刚写入的值。这是Java内存模型的结果。在这种情况下，确保以下读取总是看到先前写入的值的方式是：

Even if you fixed that, there is a more insidious problem. A thread reading the next field for an Node object won't necessarily see the value that a second thread has just written. That's a consequence of the Java memory model. In this case, the way to ensure that the following read always sees the earlier written value is to either:

• 声明下一步为 volatile ，或


• 同时阅读和在原始互斥体上写入同一个对象。

• declare next to be volatile, or
• do both the reading and writing in a primitive mutex on the same object.

编辑：在读取的代码时getObject（）和 putObject（）更详细一点，我可以看到没有任何东西强制的非空值在 putObject 中刷新到内存，并且没有任何强制 getObject 读取下一步来自主内存。所以 getObject 代码可能会看到 next 的错误值，导致它返回 null 当队列中确实有一个元素时。

on reading the code for getObject() and putObject() in more detail, I can see that nothing forces the non-null value of next to be flushed to memory in putObject, and nothing forces getObject to read next from main memory. So the getObject code could see the wrong value of next, causing it to return null when there is really an element in the queue.

这篇关于这个（无锁）队列实现线程安全吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！