Is this (Lock-Free) Queue Implementation Thread-Safe?

Question

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?

Thank you.

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

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.

Answer 2

I see only two problems with your code:

• one is the problem with memory operations ordering Stephen C mentioned (can be solved by declaring next and value volatile) (Node: value has the same problem)

• second is a more subtle one, and not concurrency related: after you return an object in getObject, you still retain its reference from head. This could lead to a memory leak.

Otherwise the algorithm is OK. A vague demonstration (assume the above are fixed):

L1: tail can never be deleted from the queue. This holds because when something is stored in tail, it has next == null. Also, when you assign something to xxx.next (only in putObject), it cannot be tail, because of the getAndSet's atomicity and the ordering between volatile write and subsequent read - assume you read a non-null tail.next, this value must have been written by putObject and therefore happens-after the last line of it. This means it happens-after the previous line, which means the value we are reading is not from tail.

A consequent of it is that every object in putObject will eventually be reachable from head. That's because we are connecting after tail, and this node can be deleted only after we write the new node's reference to its next, which means the new node is reachable from head.

The added objects are trivially ordered by the getAndSet operation in putObject.

The dequeued objects are ordered according successful compareAndSet operations in getObject.

The getObject/putObject are ordered according to write/read to volatile field next.

Answer 3

I believe you'd get an NPE when you try to "release the value..." if you call

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

since you don't perform any nullity checks on valueNode there, despite guarding against it above.

Answer 4

You should take a look at the implementation of java.util.concurrent.ConcurrentLinkedQueue http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html It does pretty much what you are trying to achieve