Thread-Safe and Lock-Free - Queue Implementation

I was 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?

(Cross-post from StackOverflow)

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue {
    private static class Node {
        final E value;
        volatile Node next;

        Node(E value) {
            this.value = value;
        }
    }

    private AtomicReference> head, tail;

    public LockFreeQueue() {
        // have both head and tail point to a dummy node
        Node dummyNode = new Node(null);
        head = new AtomicReference>(dummyNode);
        tail = new AtomicReference>(dummyNode);
    }

    /**
     * Puts an object at the end of the queue.
     */
    public void putObject(T value) {
        Node newNode = new Node(value);
        Node 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 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;
    }
}

Yes.

• The combination of volatile and compare-and-swap operations is enough to make sure that the Node objects are safely published.

• The compare-and-swap must be before the assignment to a volatile variable in both methods, so you're fine there. They do not need to happen atomically.

The queue exhibits odd behavior. Let's say thread 1 stops in putObject() after the CAS but before the last assignment. Next thread 2 executes putObject() in its entirety. Next thread three calls getObject(), and it cannot see either of the first two objects, even though thread 2 is completely done. There's a small chain being built up in-memory. Only after thread 1 completes putObject() are both objects visible on the queue, which is somewhat surprising, and has weaker semantics than most non-blocking data structures.

Another way of looking at the odd API is that it's nice to have a non-blocking put() but it's very strange to have a non-blocking get(). It means that the queue must be used with repeated polling and sleeping.

StackExchange Code Review Q#224, answer score: 21