Deep Dive into the Design and Implementation of Java's AbstractQueuedSynchronizer (AQS)

Content Overview

The article introduces the design philosophy of AbstractQueuedSynchronizer (AQS), the foundational component for many Java synchronizers such as ReentrantLock , Semaphore , and CountDownLatch .

Basic Concepts

AQS, abbreviated as AQS, defines a template for multithreaded access to shared resources, handling many low‑level details and reducing implementation effort. Although most developers rely on the JUC provided synchronizers, understanding AQS is valuable for architecture design and interview preparation.

AQS consists of three parts: a state variable, a CLH (Craig, Landin, and Hagersten) FIFO queue built from Node objects, and a ConditionObject that maintains a separate condition queue.

State Management

The state field stores the synchronization state. Methods such as getState() , setState(int) , and compareAndSetState(int,int) manipulate it. Different synchronizers give state different meanings (e.g., lock held, read‑write bits, semaphore permits, latch count).

CLH Queue

The CLH queue is a FIFO double‑linked list used to manage threads that failed to acquire the resource. Threads are wrapped in Node objects and inserted at the tail using CAS operations. The queue guarantees fairness and provides a non‑blocking, lock‑free insertion mechanism.

Node Internal Class

Each Node holds references to its predecessor and successor, a wait status, and the associated thread. The waitStatus indicates cancellation, signal, or condition status, while nextWaiter distinguishes shared versus exclusive modes.

Enqueue Process

The addWaiter(Node mode) method creates a node for the current thread and attempts to link it to the tail. If the tail is null, enq(Node) initializes a sentinel node and repeatedly CASes the tail until successful.

private Node addWaiter(Node mode) {
    // create node, set predecessor, CAS tail, etc.
}
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;
            }
        }
    }
}

Dequeue Process

When a thread releases the resource, the head of the CLH queue is advanced, and the successor node is unparked. The unparkSuccessor(Node) method clears the wait status and wakes the next thread, falling back to a tail‑to‑head scan if necessary.

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

Condition Variables

AQS provides ConditionObject which mimics the Object.wait/notify mechanism but can be associated with a single synchronizer multiple times. Threads awaiting a condition are placed in a separate condition queue and transferred back to the CLH queue when signal() is called.

Advanced Templates

AQS follows the Template Method pattern, offering exclusive ( acquire , release ) and shared ( acquireShared , releaseShared ) templates. The exclusive path uses tryAcquire and tryRelease implemented by subclasses; the shared path works similarly but may wake additional successors when permits remain.

Practical Example – Non‑Reentrant Lock

The article presents a complete implementation of a non‑reentrant exclusive lock using AQS. The inner Sync class extends AbstractQueuedSynchronizer and overrides isHeldExclusively() , tryAcquire(int) , and tryRelease(int) . The lock methods delegate to the AQS templates ( acquire , release , etc.). A test program creates two threads that each increment a shared counter 100 000 times under the custom lock, reliably producing the expected final value of 200 000.

public class NonReentrantLock implements Lock {
    private static final class Sync extends AbstractQueuedSynchronizer {
        protected boolean isHeldExclusively() {
            return getState() == 1;
        }
        protected boolean tryAcquire(int arg) {
            if (arg != 1) throw new RuntimeException("arg not is 1");
            if (compareAndSetState(0, arg)) {
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
            return false;
        }
        protected boolean tryRelease(int arg) {
            if (arg != 0) throw new RuntimeException("arg not is 0");
            setExclusiveOwnerThread(null);
            setState(arg);
            return true;
        }
        public ConditionObject createConditionObject() {
            return new ConditionObject();
        }
    }
    private final Sync sync = new Sync();
    public void lock() { sync.acquire(1); }
    public void unlock() { sync.release(0); }
    public Condition newCondition() { return sync.createConditionObject(); }
    // other Lock methods omitted for brevity
}

AQS Simplified Flowchart

The article concludes with a visual flowchart summarizing the AQS acquisition and release processes.