How Does Java’s AbstractQueuedSynchronizer Power Locks? A Deep Dive into AQS

Preface

AQS (AbstractQueuedSynchronizer) is a framework for building locks and synchronizers; understanding its implementation is crucial because many Java concurrency utilities (ReentrantLock, ReadWriteLock, CountDownLatch, Semaphore, CyclicBarrier) are based on it.

Lock Principles – Semaphore vs. Monitor

Semaphore

A semaphore is a OS-provided communication mechanism that coordinates access to shared resources. It consists of an integer S and two atomic operations P and V. P (acquire) decrements S; if S < 0 the thread waits. V (release) increments S; if S ≤ 0 it wakes a waiting thread.

While semaphores solve mutual exclusion and synchronization, they can lead to deadlocks if misused (e.g., producer‑consumer with reversed P/V).

Monitor

Proposed by Dijkstra in 1971, a monitor centralizes all synchronization operations for a particular critical resource into a “secretary” process. Threads must request the monitor to enter the critical section, which guarantees mutual exclusion. Monitors improve on semaphores by bundling the acquire/release pair and introducing condition variables.

A monitor consists of four parts: internal shared variables, condition variables, the threads that execute inside the monitor, and initialization statements for shared data.

In Java, most built‑in locks (e.g., synchronized) are implemented using monitors.

AQS Implementation Principles

AQS maintains a shared state variable and a FIFO wait queue (the monitor’s entry queue). It uses CAS to ensure atomic updates.

Lock acquisition (exclusive) works as follows: the state is initially 0. A thread attempts to set state to 1 via CAS; on success it records itself as the owner. If CAS fails, the thread enqueues itself using acquire(1), which eventually calls acquireQueued to block until it becomes the head.

public abstract class AbstractQueuedSynchronizer {
    private volatile Node head;
    private volatile Node tail;
    private volatile int state;
    protected final boolean compareAndSetState(int expect, int update) {
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }
    // ... other core methods ...
}

The FIFO queue is a doubly‑linked list of Node objects. Each node records its thread, wait status, and links to predecessor and successor.

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;
    // ... constructors and methods ...
}

When a thread fails to acquire the lock, it is added to the queue ( addWaiter(Node.EXCLUSIVE)) and may spin briefly before being parked. The method shouldParkAfterFailedAcquire decides whether the thread should block based on its predecessor’s wait status.

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

Parking uses LockSupport.park(this). When the lock is released, unparkSuccessor wakes the next eligible node.

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

Lock Release

Releasing a lock calls release(arg), which invokes the subclass’s tryRelease. If the state reaches zero, the owner is cleared and unparkSuccessor wakes the next thread.

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

ReentrantLock Example

ReentrantLock is a non‑fair exclusive lock by default. Its constructor creates a NonfairSync instance.

public ReentrantLock() {
    sync = new NonfairSync();
}
public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

Lock acquisition tries the fast‑path CAS; on failure it falls back to acquire which enqueues the thread.

private final boolean nonfairTryAcquire(int acquires) {
    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;
}

Custom Mutex Using AQS

A simple non‑reentrant mutex can be built by extending AQS and implementing tryAcquire, tryRelease, and isHeldExclusively:

public class Mutex {
    private final Sync sync = new Sync();
    public void lock() { sync.acquire(1); }
    public void unlock() { sync.release(1); }
    private static class Sync extends AbstractQueuedSynchronizer {
        protected boolean tryAcquire(int arg) {
            return compareAndSetState(0, 1);
        }
        protected boolean tryRelease(int arg) {
            setState(0);
            return true;
        }
        protected boolean isHeldExclusively() {
            return getState() == 1;
        }
    }
}

Conclusion

The article walks through AQS’s design, showing how semaphores and monitors relate to Java’s lock implementations, and demonstrates the core algorithms for acquiring, queuing, parking, and releasing locks. Understanding AQS clarifies the behavior of many Java concurrency utilities and helps developers build custom synchronizers.