代码之家 › 专栏 › 技术社区 › Hosam Aly

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

thread-safety locking multithreading java

Hosam Aly · 技术社区 · 16 年前

我试图用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;
}

4 回复 | 直到 16 年前

Stephen C 16 年前

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

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

next 是 null

即使你解决了这个问题,还有一个更隐秘的问题。读节点对象的字段不会 必要地 查看第二个线程刚刚写入的值。这是Java内存模型的结果。在这种情况下确保下面的读数总是看到之前写入的值,即:

声明 下一个 volatile ,或
在同一个对象上用一个基本互斥体进行读写操作。

编辑:在阅读 getObject() 和 putObject() 更详细地说,我可以看到没有任何东西强制冲入记忆 putObject 没有什么力量 getObject 下一个 从主存储器。所以 获取对象 下一个 ,导致它返回 无效的

jpalecek 16 年前

我看到你的代码只有两个问题:

通过声明Stephen的操作可以解决内存排序问题 next value volatile )(节点:value也有同样的问题)
第二个是更微妙的一个,与并发无关:在 getObject 从它的头上留下你的参考。这可能导致内存泄漏。

否则算法正常。一个模糊的演示(假设上面的内容是固定的):

一年级: tail 无法从队列中删除。这是因为当某些东西被储存在 尾 next == null . 另外,当你分配一些东西给 xxx.next (仅限于 putObject ),不可能 ,因为getAndSet的原子性以及volatile write和后续read之间的顺序-假设您读取的是非null tail.next putObject公司 因此 发生在 发生在 .

putObject公司 最终可以从 head . 那是因为我们在 ,并且只有在我们将新节点的引用写入其 ,这意味着可以从访问新节点 头 .

添加的对象由 getAndSet putObject公司 .

compareAndSet 经营范围 获取对象

这个 获取对象 根据对易失性字段的写入/读取顺序 .

Andrzej Doyle 16 年前

new LockFreeQueue<?>().getObject();

valueNode 在那里,尽管在上面有防范。

Yuval Rimar 16 年前

你应该看看java.util.concurrent.ConcurrentLinkedQueue http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html 它几乎可以实现你想要达到的目标