Действительно ли эта (Свободная от блокировок) Реализация Очереди ориентирована на многопотоковое исполнение?

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

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.

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:

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

EDIT: 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.

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

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

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

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

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

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

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

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

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

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

Удаленные объекты упорядочиваются в соответствии с успешными операциями compareAndSet в getObject .

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

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

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

Удаленные объекты упорядочиваются в соответствии с успешными операциями compareAndSet в getObject .

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

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

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

Удаленные объекты упорядочиваются в соответствии с успешными операциями compareAndSet в getObject .

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

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