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

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 предыдущего узла был установлен. Это происходит только в 3-м утверждении. Таким образом, есть окно, в котором next равно null; то есть состояние гонки.

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

• секунда более тонкая и не связана с параллелизмом: после возврата объекта в 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 упорядочены в соответствии с записью / чтением в поле volatile next.