Unlocking Java’s AQS: How AbstractQueuedSynchronizer Powers Locks and Synchronizers

Java's AbstractQueuedSynchronizer (AQS) class provides a FIFO queue framework for implementing locks and related synchronizers such as semaphores and events.

AQS has two main responsibilities: manipulating the state variable and implementing queuing and blocking mechanisms.

Note: AQS does not implement any synchronization interface itself; it only offers methods like acquireInterruptibly that concrete synchronizers call to implement locking behavior.

1 Monitor Model

Java uses the MESA monitor model to ensure thread‑safe access to class fields and methods. The model defines shared variables, condition variables, and a condition‑wait queue.

The diagram (not shown) illustrates three key points:

MESA encapsulates shared variables and their operations; a thread must acquire the lock before entering the monitor, otherwise it joins the entry‑wait queue.

Even after acquiring the lock, a thread may still wait on a condition variable if the condition is not satisfied.

When a thread is signaled from the condition‑wait queue, it must re‑enter the entry‑wait queue to try acquiring the lock again.

AJS’s monitor model relies on AQS’s FIFO queue for the entry‑wait queue, while ConditionObject implements a condition queue that can create multiple nodes.

2 Entry‑Wait Queue

2.1 Acquiring an Exclusive Lock

Exclusive lock acquisition (ignoring interrupts):

<code>public final void acquire(int arg) {<br/>    if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))<br/>        selfInterrupt();<br/>}</code>

Note: tryAcquire is abstract; subclasses provide the actual lock acquisition logic.

2.1.1 Enqueue

If lock acquisition fails, addWaiter adds the thread to the queue, and acquireQueued spins until the lock is obtained.

The enqueue logic is illustrated in the diagram (not shown): a node is added to the tail; if the queue is empty, a new head node is created.

2.1.2 After Enqueue – Lock Acquisition

acquireQueued spins and checks several details:

CANCELLED (1) : node cancelled due to timeout or interrupt.

SIGNAL (-1) : successor node waiting for current node to signal.

CONDITION (-2) : node waiting on a condition.

PROPAGATE (-3) : shared mode propagation.

0 : intermediate state where the node ahead has been signaled but the current thread has not finished.

2.1.3 Exclusive + Interruptible

Method acquireInterruptibly(int arg) checks the thread’s interrupt status before acquiring the lock and also during the spin; if interrupted, it throws InterruptedException .

2.1.4 Exclusive + Interruptible + Timeout

Method tryAcquireNanos(int arg, long nanosTimeout) adds timeout handling: each failed spin checks the remaining time, and before parking the thread it compares the timeout with a spin‑threshold (1 ns) and uses parkNanos for blocking.

2.2 Releasing an Exclusive Lock

Release consists of two steps: invoking the abstract tryRelease (implemented by subclasses) and waking up the successor node if the head is non‑null and its waitStatus is not zero. Two cases are illustrated: (1) successor’s waitStatus <= 0 – wake directly; (2) successor is null or waitStatus > 0 – search backwards for the nearest node to wake.

2.3 Acquiring a Shared Lock

Shared lock acquisition uses acquireShared(int arg) :

<code>public final void acquireShared(int arg) {<br/>    if (tryAcquireShared(arg) < 0)<br/>        doAcquireShared(arg);<br/>}</code>

tryAcquireShared returns an int indicating the result:

Negative – acquisition failed.

Zero – acquisition succeeded but further shared acquisitions will fail.

Positive – acquisition succeeded and further shared acquisitions may also succeed; the positive value is used to propagate wake‑ups.

If acquisition fails, the thread enqueues and spins via doAcquireShared . The wake‑up propagation requires one of four conditions, such as a positive return value, head node status, or presence of waiting successors.

2.4 Releasing a Shared Lock

<code>public final boolean releaseShared(int arg) {<br/>    if (tryReleaseShared(arg)) {<br/>        doReleaseShared();<br/>        return true;<br/>    }<br/>    return false;<br/>}</code>

tryReleaseShared is implemented by subclasses; if it succeeds, doReleaseShared performs a spin to wake up waiting nodes. Three cases of head node waitStatus are shown (‑1, 0, ‑3) with corresponding diagrams.

2.5 Abstract Methods to Implement

Subclasses must provide concrete implementations for:

tryAcquire(int arg) – exclusive lock acquisition.

tryRelease(int arg) – exclusive lock release.

tryAcquireShared(int arg) – shared lock acquisition.

tryReleaseShared(int arg) – shared lock release.

Optionally they can override isHeldExclusively() to test exclusive ownership.

3 Concurrency Locks Built on AQS

3.1 ReentrantLock

UML shows ReentrantLock using an internal Sync class that implements AQS methods, providing both fair and non‑fair locks. Core methods are tryAcquire , tryRelease , and isHeldExclusively . The lock is exclusive; the acquisition code is the same as in section 2.1.

3.1.1 Fair Lock

If state == 0 and there is no predecessor, CAS sets state to 1 and the thread becomes owner.

3.1.2 Non‑Fair Lock

If state == 0 , the thread attempts CAS without checking for a predecessor, making it more efficient but potentially starving later threads.

3.1.3 Unlock

Both fair and non‑fair unlock logic are identical: they clear the owner and wake a successor. The lock is re‑entrant, so state can exceed 1.

3.2 ReentrantReadWriteLock

Uses the same Sync base but implements both exclusive and shared modes. Core abstract methods include tryAcquire , tryRelease , tryAcquireShared , tryReleaseShared , and isHeldExclusively . The lock state packs shared count in the high 16 bits and exclusive count in the low 16 bits.

3.2.1 Read Lock

Acquisition calls acquireShared(1) . tryAcquireShared checks that no exclusive lock is held and that the shared count is below the maximum, then CAS adds SHARED_UNIT (65536) to state and increments the thread’s hold count.

3.2.2 Write Lock

Acquisition calls acquire(1) . If state is zero, the thread acquires the lock; otherwise it checks exclusive count and fairness policy before succeeding.

3.3 CountDownLatch

Internally a subclass of AQS uses the state field as the countdown. The constructor sets state = count . await calls acquireSharedInterruptibly(1) and spins until state == 0 . countDown calls releaseShared(1) , decrementing state and waking the waiting thread when it reaches zero.

3.4 Semaphore

Also a subclass of AQS; the constructor initializes state with the number of permits. acquire uses acquireSharedInterruptibly(1) (fair or non‑fair) and release uses releaseShared(1) to increment permits and wake waiters.

3.5 ThreadPoolExecutor

Its internal Worker uses a private AQS to protect interruption of threads. tryAcquire CASes state from 0 to 1 and records the owner; tryRelease clears the owner and resets state to 0. The worker is initially created with state = -1 so it cannot be interrupted until runWorker releases the lock.

4 Condition‑Variable Wait Queues

Condition queues are built on the Condition interface and its ConditionObject implementation. They are single‑linked (using nextWaiter ) and store nodes with waitStatus == -2 .

4.1 await

When a thread calls await , it is added to the condition queue via addConditionWaiter , releases the lock (saving the current state ), and then blocks until signaled.

4.2 signal

Signal moves the first waiting node whose waitStatus == -2 to the entry‑wait queue, updates its status to 0, and may unpark it directly if the tail’s status is unsuitable.

4.3 signalAll

Transfers all waiting nodes from the condition queue to the entry‑wait queue, waking every blocked thread.

4.4 Example – CyclicBarrier

CyclicBarrier creates a Condition with a count. Each thread calls await , which decrements the count and waits on the condition. When the last thread arrives, the barrier signals all waiting threads, allowing them to proceed.

5 Summary

AQS uses a FIFO queue to implement a generic synchronizer template, enabling the construction of exclusive locks, shared locks, semaphores, latches, barriers, and thread‑pool coordination. The core waitStatus field determines node behavior, while ConditionObject provides condition‑variable queues that integrate with the entry‑wait queue.