AbstractQueuedSynchronizer (AQS)

AbstractQueuedSynchronizer (AQS) is the framework upon which almost all synchronizers in java.util.concurrent are built.

Source Code #

View Source on GitHub

The Core Mechanics #

AQS revolves around three fundamental components:

1. The State: A single volatile int that represents the synchronization status.
2. The Wait Queue: A FIFO queue based on a variant of the CLH lock queue.
3. Acquire/Release Operations: Atomic updates to the state using CAS (Compare-And-Swap).

// The core state variable
private volatile int state;

protected final int getState() { return state; }
protected final boolean compareAndSetState(int expect, int update) {
    return U.compareAndSetInt(this, STATE, expect, update);
}

Implementation Details #

Node Structure #

The wait queue is composed of Node objects, each representing a waiting thread:

abstract static class Node {
    volatile Node prev;       // initially attached via casTail
    volatile Node next;       // visibly nonnull when signallable
    Thread waiter;            // visibly nonnull when enqueued
    volatile int status;      // WAITING, CANCELLED, or COND
}

Node status values:

• WAITING = 1: Thread is waiting to acquire
• CANCELLED = 0x80000000: Thread cancelled while waiting
• COND = 2: Thread is waiting on a Condition

Queue Management #

The queue uses lazy initialization with a dummy head node:

/** Head of the wait queue, lazily initialized. */
private transient volatile Node head;

/** Tail of the wait queue. After initialization, modified only via casTail. */
private transient volatile Node tail;

The tryInitializeHead() method creates the initial dummy head node:

private Node tryInitializeHead() {
    for (Node h = null, t;;) {
        if ((t = tail) != null)
            return t;
        else if (head != null)
            Thread.onSpinWait();
        else {
            if (h == null) {
                try {
                    h = new ExclusiveNode();
                } catch (OutOfMemoryError oome) {
                    return null;
                }
            }
            if (U.compareAndSetReference(this, HEAD, null, h))
                return tail = h;
        }
    }
}

CLH Queue Algorithm #

AQS uses a variant of the CLH (Craig, Landin, and Hagersten) lock queue algorithm:

1. Enqueue: Atomically splice new node as new tail using casTail()
2. Dequeue: Set head field to make next waiter the first eligible
3. Signaling: Predecessor nodes signal successors when releasing

// Insertion into CLH queue
private boolean casTail(Node c, Node v) {
    return U.compareAndSetReference(this, TAIL, c, v);
}

Barging and Fairness #

AQS allows barging - incoming threads can acquire the synchronizer while enqueuing, potentially jumping ahead of queued threads. This improves throughput but reduces fairness.

For fair synchronizers, override tryAcquire() to check hasQueuedPredecessors():

protected final boolean hasQueuedPredecessors() {
    Node t = tail; // Read fields in reverse initialization order
    Node h = head;
    Node s;
    return h != t && 
        ((s = h.next) == null || s.thread != Thread.currentThread());
}

Exclusive vs Shared Mode #

Exclusive Mode (e.g., ReentrantLock):

• Only one thread can hold the synchronizer
• Uses tryAcquire(int) and tryRelease(int)
• Node type: ExclusiveNode

Shared Mode (e.g., Semaphore, CountDownLatch):

• Multiple threads may acquire simultaneously
• Uses tryAcquireShared(int) and tryReleaseShared(int)
• Node type: SharedNode
• Acquires propagate to successors

Condition Support #

AQS includes ConditionObject for condition variables:

static final class ConditionNode extends Node 
    implements ForkJoinPool.ManagedBlocker {
    ConditionNode nextWaiter;  // link to next waiting node
    
    public final boolean isReleasable() {
        return status <= 1 || Thread.currentThread().isInterrupted();
    }
    
    public final boolean block() {
        while (!isReleasable()) LockSupport.park();
        return true;
    }
}

Memory Management #

Fields are nulled aggressively to improve garbage collectibility:

• Node fields are null when not on list
• Fields coming off list are nulled immediately
• This requires fallback traversal from tail when determining first waiter

OOME Handling #

AQS handles OutOfMemoryError gracefully:

• Acquire methods resort to spin-waits with backoff if nodes cannot be allocated
• Condition waits release and reacquire locks at fixed rate (OOME_COND_WAIT_DELAY)
• Methods may throw OOME when creating IllegalMonitorStateException or InterruptedException

Exclusive vs. Shared Mode #

• Exclusive Mode: Only one thread can hold the synchronizer at a time (e.g., ReentrantLock).
• Shared Mode: Multiple threads may acquire the synchronizer simultaneously (e.g., Semaphore).

Canonical Usage #

When to use: You rarely use AQS directly. Instead, you use it when building a custom synchronizer. It requires defining a private inner class that extends AQS.

class Mutex extends AbstractQueuedSynchronizer {
    protected boolean tryAcquire(int ignored) {
        if (compareAndSetState(0, 1)) {
            setExclusiveOwnerThread(Thread.currentThread());
            return true;
        }
        return false;
    }

    protected boolean tryRelease(int ignored) {
        setExclusiveOwnerThread(null);
        setState(0);
        return true;
    }
}