Understanding Java’s CLH Sync Queue: How AQS Manages Threads

Background

In Java's AbstractQueuedSynchronizer (AQS), a CLH (Craig, Landin, and Hagersten) FIFO queue is used to manage thread synchronization. When a thread fails to acquire a lock, it creates a Node representing its wait status and inserts it into this queue.

Node Structure

static final class Node {
    static final Node SHARED = new Node();
    static final Node EXCLUSIVE = null;
    static final int CANCELLED = 1;
    static final int SIGNAL = -1;
    static final int CONDITION = -2;
    static final int PROPAGATE = -3;
    volatile int waitStatus;
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
    Node nextWaiter;
    final boolean isShared() { return nextWaiter == SHARED; }
    Node predecessor() throws NullPointerException {
        Node p = prev;
        if (p == null) throw new NullPointerException();
        return p;
    }
    Node() {}
    Node(Thread thread, Node mode) { this.nextWaiter = mode; this.thread = thread; }
    Node(Thread thread, int waitStatus) { this.waitStatus = waitStatus; this.thread = thread; }
}

1. Enqueueing a Thread (Add to Queue)

The addWaiter(Node mode) method creates a new node for the current thread and attempts a fast-path insertion at the tail. If the fast CAS fails, it falls back to the more robust enq(Node node) method.

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    Node pred = tail;
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    enq(node);
    return node;
}

The enq(Node node) method repeatedly attempts to link the new node at the tail using a CAS loop, initializing the queue head if it is absent.

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) {
            if (compareAndSetHead(new Node())) {
                tail = head;
            }
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

Both methods rely on compareAndSetTail to ensure thread‑safe insertion.

2. Dequeueing a Thread (Remove from Queue)

When the head node releases the synchronization state, AQS wakes its successor ( next) without using CAS, because only one thread can own the lock at a time. The successor then becomes the new head and attempts to acquire the lock.

Visually, the process follows a simple FIFO pattern: the head node is removed, its next node is unlinked, and the lock handoff proceeds.

Illustrations

Conclusion

The CLH queue provides a lock‑free, FIFO ordering mechanism for threads waiting on AQS. Understanding the Node fields, the enqueue logic in addWaiter and enq, and the simple handoff during dequeue helps developers grasp how Java implements fair and non‑fair locks under the hood.