How Does Java’s ConcurrentLinkedQueue Achieve Lock‑Free Thread Safety?

Overview

ConcurrentLinkedQueue is an unbounded, lock‑free FIFO queue introduced in JDK 7. It relies on compareAndSwapObject (CAS) operations on next and item fields of internal nodes to achieve thread‑safe offer (enqueue) and poll (dequeue) without blocking.

Key Invariants

The next reference of the last node is always null.

All nodes whose item is non‑null are reachable from the head node.

Logical removal clears item first; the node stays linked so that iterators can skip it. head and tail may temporarily lag behind the true first and last elements.

Node Structure

private static class Node<E> {
    /** element stored in the node */
    volatile E item;
    /** link to the next node */
    volatile Node<E> next;

    Node(E item) {
        UNSAFE.putObject(this, itemOffset, item);
    }
    boolean casItem(E cmp, E val) {
        return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
    }
    void lazySetNext(Node<E> val) {
        UNSAFE.putOrderedObject(this, nextOffset, val);
    }
    boolean casNext(Node<E> cmp, Node<E> val) {
        return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
    }
    // Unsafe mechanics (field offsets) omitted for brevity
    private static final sun.misc.Unsafe UNSAFE;
    private static final long itemOffset;
    private static final long nextOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> k = Node.class;
            itemOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("item"));
            nextOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("next"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}

Enqueue (offer) – Step‑by‑Step

The algorithm repeatedly reads the current tail ( t) and a candidate predecessor ( p). It tries to link a newly created node at p.next. If successful, it may advance tail to the new node. If another thread has already inserted a node, the algorithm helps advance tail or retries with a fresh snapshot.

public boolean offer(E e) {
    checkNotNull(e);
    final Node<E> newNode = new Node<>(e);
    for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {                     // 1. p is the last node
            if (p.casNext(null, newNode)) { // 2. link the new node
                if (p != t)                 // 3. tail may be behind
                    casTail(t, newNode);   // 4. advance tail
                return true;
            }
        } else if (p == q) {                // 5. p was removed (self‑link)
            p = (t != (t = tail)) ? t : head; // retry with fresh tail/head
        } else {
            // 6/7: help advance tail
            p = (p != t && t != (t = tail)) ? t : q;
        }
    }
}

Dequeue (poll) – Step‑by‑step

The outer loop restarts from the current head if the node being examined has been removed ( p == q). The inner loop scans forward, trying to atomically null out the item of the first node with a non‑null value. After a successful logical deletion, head is optionally advanced via updateHead, which performs a CAS on head and then lazily clears the old head's next reference to aid garbage collection.

public E poll() {
    restartFromHead:
    for (;;) {
        for (Node<E> h = head, p = h, q;;) {
            E item = p.item;
            if (item != null && p.casItem(item, null)) { // 1. logical delete
                if (p != h)                               // 2. head not at p
                    updateHead(h, (q = p.next) != null ? q : p); // 3
                return item;
            }
            if ((q = p.next) == null) { // queue appears empty
                updateHead(h, p);
                return null;            // 4
            } else if (p == q) {        // 5. p was removed by another thread
                continue restartFromHead;
            } else {
                p = q;                 // 6. advance p
            }
        }
    }
}

final void updateHead(Node<E> h, Node<E> p) {
    if (h != p && casHead(h, p))
        h.lazySetNext(h); // help GC by unlinking old head
}

Initialization

When a ConcurrentLinkedQueue is created, both head and tail reference a dummy sentinel node whose item is null. This sentinel simplifies the algorithms because the queue is never truly empty – the dummy node always exists.

Correctness Highlights

All modifications to next and item are performed with CAS, guaranteeing atomicity without locks.

Both offer and poll contain helping steps: a thread that discovers another thread's partial progress will assist by advancing tail or head, ensuring lock‑free progress.

Logical deletion (nulling item) preserves the node for ongoing traversals; physical removal is performed lazily by updateHead and by the self‑linking technique ( p == p.next) used when a node is removed.

The design tolerates temporary inconsistencies such as head or tail lagging behind the actual ends, which are resolved by the helping logic.

Understanding these invariants and the CAS‑based algorithms for offer, poll, and updateHead explains why ConcurrentLinkedQueue provides high‑throughput, non‑blocking FIFO semantics under heavy concurrency.