Является ли эта (без блокировки) реализация очереди поточно-ориентированной?

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

2-й оператор добавляет новый узел перед предыдущим узлом next указатель был установлен. Это происходит только в третьем утверждении. Таким образом, есть окно, в котором next является null; то есть состояние гонки.

Даже если вы исправили это, есть более коварная проблема. Поток, читающий next Поле для объекта Node не обязательно будет видеть значение, которое только что записал второй поток. Это следствие модели памяти Java. В этом случае, способ гарантировать, что следующее чтение всегда видит ранее записанное значение:

• объявлять next быть volatile, или же
• выполнять чтение и запись в примитивном мьютексе для одного и того же объекта.

РЕДАКТИРОВАТЬ: при чтении кода для getObject() а также putObject() более подробно, я вижу, что ничто не заставляет ненулевое значение next быть в памяти в putObjectи ничего не заставляет getObject читать next из основной памяти. Итак getObject код мог видеть неправильное значение next, заставляя его вернуться null когда действительно есть элемент в очереди.

Answer 2

Я полагаю, что вы получите NPE, когда попытаетесь "освободить значение...", если вы позвоните

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

так как вы не выполняете никаких проверок недействительности valueNode там, несмотря на защиту от этого выше.

Answer 3

Я вижу только две проблемы с вашим кодом:

• одна проблема связана с упорядочением операций с памятью, упомянутым Стивеном С (может быть решен путем объявления next а также valuevolatile) (Узел: значение имеет ту же проблему)

• второй - более тонкий, не связанный с параллелизмом: после возврата объекта в getObjectВы по-прежнему сохраняете свою ссылку из головы. Это может привести к утечке памяти.

В противном случае алгоритм в порядке. Неопределенная демонстрация (предположим, что выше исправлено):

L1: tail никогда не может быть удален из очереди. Это верно, потому что когда что-то хранится в tail, она имеет next == null, Кроме того, когда вы назначаете что-то xxx.next (только в putObject), не может быть tailиз-за атомарности getAndSet и порядка между volatile-записью и последующим чтением - предположим, что вы читаете ненулевое значение tail.nextэто значение должно быть написано putObject и, следовательно, происходит - после последней строки. Это означает, что это происходит после предыдущей строки, что означает, что значение, которое мы читаем, не из tail,

Следствием этого является то, что каждый объект в putObject в конечном итоге будет достигнуто из head, Это потому, что мы подключаемся после tail, и этот узел может быть удален только после того, как мы запишем ссылку на новый узел в его next, что означает, что новый узел доступен из head,

Добавленные объекты тривиально упорядочены getAndSet операция в putObject,

Снятые объекты упорядочены в соответствии с успешным compareAndSet операции в getObject,

getObject/putObject упорядочены в соответствии с записью / чтением в энергозависимое поле next,

Answer 4

Вы должны взглянуть на реализацию java.util.concurrent.ConcurrentLinkedQueue http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html ты пытаешься достичь