AQS Source Code Deep Dive: CLH Queue, CAS, and Exclusive/Shared Mode Design Philosophy

Overall Architecture

AQS (AbstractQueuedSynchronizer) is the foundation of the JUC package; ReentrantLock, CountDownLatch, Semaphore, and ReentrantReadWriteLock are all built on top of it. Its core structure consists of three pillars:

volatile int state — synchronization state; in exclusive mode it represents reentrancy count or lock ownership, in shared mode it represents remaining permits.

CLH variant queue — a FIFO doubly-linked list that serves as the vehicle for thread parking and unparking.

CAS — the atomic operation foundation for all state changes.

Node: The CLH Queue Unit

The Node class defines the queue elements:

static final class Node {
    // Shared mode
    static final Node SHARED = new Node();
    // Exclusive mode
    static final Node EXCLUSIVE = null;

    // Wait statuses
    static final int CANCELLED = 1;   // timeout/interrupt, dequeued
    static final int SIGNAL    = -1;  // successor needs wakeup
    static final int CONDITION = -2;  // in Condition queue
    static final int PROPAGATE = -3;  // shared-mode propagation

    volatile int waitStatus;
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
    Node nextWaiter; // Condition queue successor or shared-mode special list
}

Design highlights: waitStatus uses volatile per node (not a volatile int array) to avoid false sharing. prev and next are volatile for visibility of list mutations across threads. thread is volatile so interrupts can quickly locate the target thread. SHARED and EXCLUSIVE are distinguished by a Node instance vs. null — saving memory and comparison overhead.

CLH Variant vs. Original CLH Lock

Original CLH: each node spins waiting for predecessor to release
AQS CLH:     node parks (LockSupport.park), using waitStatus + park/unpark cooperation

Key modifications:

Added waitStatus to avoid spurious wakeups.

Replaced spinning with LockSupport.park() to save CPU.

Support timeout cancellation via CANCELLED state.

State CAS Operations: Atomicity Foundation

All core AQS methods rely on CAS to modify state via Unsafe:

private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long stateOffset;
static {
    try {
        stateOffset = unsafe.objectFieldOffset
            (AbstractQueuedSynchronizer.class.getDeclaredField("state"));
    } catch (Exception ex) { throw new Error(ex); }
}

protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

Why Unsafe instead of AtomicInteger? AtomicInteger also uses Unsafe.compareAndSwapInt underneath.

AQS needs finer-grained control (e.g., spin-retry logic after CAS failure).

Direct Unsafe removes one layer of indirection for more predictable performance.

CAS retry appears in acquireQueued — a spin loop that checks predecessor status before parking:

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed) cancelAcquire(node);
    }
}

Design philosophy: on CAS failure, don't park immediately; first check predecessor state. Only park when predecessor is SIGNAL or CANCELLED — reducing useless park/unpark cycles.

Exclusive Mode (ReentrantLock)

tryAcquire: Two Chances to Get the Lock

NonfairSync — non-fair version:

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    } else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

FairSync — fair version adds a queue check before CAS:

final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (!hasQueuedPredecessors() && compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    } else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

The sole difference: fair version calls hasQueuedPredecessors() before CAS:

static final boolean hasQueuedPredecessors() {
    Node h = head;
    Node t = tail;
    return h != t && (h.next == null || h.thread != Thread.currentThread());
}

release: Lock Release Propagation

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = (c == 0);
    if (free) setExclusiveOwnerThread(null);
    setState(c);
    return free;
}

unparkSuccessor

scans backward from tail to find the nearest non-cancelled node — one of the few reverse traversals in AQS:

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0) compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
        s = null;
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0) s = t;
    }
    if (s != null) LockSupport.unpark(s.thread);
}

Scanning from tail handles the case where node.next may be stale (cancelled nodes have their next nulled).

Shared Mode (Semaphore / CountDownLatch)

tryAcquireShared: Competing for Permits

protected int tryAcquireShared(int acquires) {
    for (;;) {
        int available = getState();
        int remaining = available - acquires;
        if (remaining < 0 || compareAndSetState(available, remaining))
            return remaining;
    }
}

Return value semantics: >= 0: success, returns remaining permits. < 0: failure, absolute value = permits needed to wait for.

doAcquireShared: Enqueue + Park

private void doAcquireShared(int arg) {
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head) {
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    setHeadAndPropagate(node, r);
                    p.next = null;
                    failed = false;
                    return;
                }
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed) cancelAcquire(node);
    }
}

setHeadAndPropagate: The Key Shared-Mode Propagation

private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head;
    setHead(node);
    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) {
        Node s = node.next;
        if (s == null || s.isShared())
            doReleaseShared();
    }
}

Propagation triggers when: propagate > 0 — permits remain, can wake successors. h.waitStatus < 0 — original head was SIGNAL, needs propagation.

Only wakes nodes where isShared() is true — avoids waking exclusive waiters unnecessarily.

Queue Operations: enq Details

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

Two CAS steps:

First CAS initializes head (only when tail is null).

Second CAS sets tail; only after success is t.next = node executed.

Why not set t.next before CAS? If CAS failed, t.next would already be modified while tail unchanged — other threads could see an inconsistent state. CAS-first guarantees atomicity. addWaiter is a fast-path wrapper around enq:

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

Condition Implementation: Wait/Notify in Exclusive Mode

ConditionObject

is an internal AQS class — essentially a separate CLH queue:

public class ConditionObject implements Condition, Serializable {
    private transient Node firstWaiter;
    private transient Node lastWaiter;

    public final void await() throws InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
        Node node = addConditionWaiter();
        int savedState = fullyRelease(node);
        int interruptMode = 0;
        while (!isOnSyncQueue(node)) {
            LockSupport.park(this);
            if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) break;
        }
        if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
            interruptMode = REINTERRUPT;
        if (node.nextWaiter != null) unlinkCancelledWaiters();
        if (interruptMode != 0) reportInterruptAfterWait(interruptMode);
    }

    private Node addConditionWaiter() {
        Node t = lastWaiter;
        if (t != null && t.waitStatus != Node.CONDITION) {
            unlinkCancelledWaiters();
            t = lastWaiter;
        }
        Node node = new Node(Thread.currentThread(), Node.CONDITION);
        if (t == null) firstWaiter = node;
        else t.nextWaiter = node;
        lastWaiter = node;
        return node;
    }

    public final void signal() {
        if (!isHeldExclusively()) throw new IllegalMonitorStateException();
        Node first = firstWaiter;
        if (first != null) doSignal(first);
    }

    private void doSignal(Node first) {
        do {
            if ((firstWaiter = first.nextWaiter) == null) lastWaiter = null;
            first.nextWaiter = null;
        } while (!transferForSignal(first) && (first = firstWaiter) != null);
    }

    final boolean transferForSignal(Node node) {
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0)) return false;
        Node p = enq(node);
        int ws = p.waitStatus;
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }
}

Key design points:

Condition queue nodes have waitStatus = CONDITION (-2), excluding them from the main queue's wakeup logic. await releases the lock fully ( fullyRelease) before parking — ensures the lock isn't held while waiting. signal moves a node from the Condition queue to the AQS main queue tail, then unparks it.

cancelAcquire: Cancelled Node Cleanup

private void cancelAcquire(Node node) {
    if (node == null) return;
    node.thread = null;
    Node pred = node.prev;
    if (pred == null) return;

    node.waitStatus = Node.CANCELLED;
    if (node.next == null || node.next.waitStatus > 0) {
        Node s = node.next;
        if (s == null)
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0) s = t;
        if (s != null) compareAndSetNext(pred, node, s);
    } else {
        if (pred != null && pred.waitStatus <= 0) {
            Node succ = node.next;
            if (succ != null && succ.waitStatus <= 0)
                compareAndSetNext(pred, node, succ);
        }
    }
}

Doubly-linked list deletion under concurrency uses CAS on each next pointer individually — not a single atomic unlink — to maintain thread safety.

shouldParkAfterFailedAcquire: Final Park Decision

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL) return true;
    if (ws > 0) {
        do { node.prev = pred = pred.prev; } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

Why not park immediately after marking SIGNAL? The CAS might fail (another thread could be changing the predecessor's status), so the loop retries — a "lazy marking" approach that avoids redundant work until the actual park point.

Summary of Design Choices

Why CLH over MCS?

Node storage : CLH uses thread-local (prev points to predecessor); MCS stores successor reference in each node.

Cache friendliness : CLH poor (prev may be on different cache line); MCS good (each node accesses only local fields).

Implementation complexity : CLH low (only prev needed); MCS high (requires a hint pointer).

AQS rationale : AQS needs fast backward scan from tail; prev suffices. MCS's hint mechanism offers no advantage here.

AQS chooses CLH because it frequently scans backward from tail to find valid nodes; the prev reference naturally supports this. MCS's hint mechanism offers no advantage here.

Why volatile + CAS instead of synchronized?

synchronized

involves kernel transitions under contention — high overhead. volatile + CAS is a single instruction when uncontended; under contention it spins with more predictable latency.

Trade-off: code complexity is very high — AQS is ~2000 lines of intricate detail.

Why int state instead of AtomicInteger?

int

+ CAS avoids an object header and one level of indirection vs. AtomicInteger.

AQS wraps its own compareAndSetState allowing custom spin-retry logic on failure.

In exclusive mode state represents reentrancy count (can be >1), which doesn't fit AtomicInteger 's single-value semantics.

Template Method Pattern Essence

public abstract class AbstractQueuedSynchronizer {
    protected boolean tryAcquire(int arg) { throw new UnsupportedOperationException(); }
    protected boolean tryRelease(int arg) { throw new UnsupportedOperationException(); }
    protected int tryAcquireShared(int arg) { throw new UnsupportedOperationException(); }
    protected boolean tryReleaseShared(int arg) { throw new UnsupportedOperationException(); }

    // Subclasses implement only the above four; everything else is reused
    public final void acquire(int arg) { ... }
    public final void release(int arg) { ... }
}

ReentrantLock

implements only tryAcquire and tryRelease; Semaphore implements only tryAcquireShared and tryReleaseShared. This is a classic combination of Strategy and Template Method — AQS handles queue management, park/unpark, and CAS; subclasses decide only when the lock can be granted.