AQS (AbstractQueuedSynchronizer) Core

AQS is the foundation of almost everything in java.util.concurrent. It provides: an int state + a CLH wait queue. Subclasses just define what state means.

What’s Built on AQS

AQS
├── ReentrantLock          (state = hold count)
├── ReentrantReadWriteLock (state = read count | write count)
├── Semaphore              (state = available permits)
├── CountDownLatch         (state = remaining count)
├── FutureTask             (state = task status)
└── ThreadPoolExecutor     (worker state via AQS)

When to Use Each

Subclass	AQS Mode	state Meaning	When to Use
ReentrantLock	Exclusive	Hold count (reentrant depth)	Need tryLock, timeout, fairness, or multiple conditions. Upgrade from synchronized when its features aren’t enough. See reentrant-lock.md
ReentrantReadWriteLock	Shared (read) + Exclusive (write)	Upper 16 bits = readers, lower 16 = writer count	Read-heavy workloads where multiple readers can proceed concurrently but writes must be exclusive. See read-write-lock.md
Semaphore	Shared	Available permits	Rate limiting, connection pools, bounding concurrent access to N threads. No ownership — any thread can release. See semaphore.md
CountDownLatch	Shared	Remaining count	One-shot “wait for N events” — workers count down, coordinator awaits zero. Cannot reset. See count-down-latch.md
FutureTask	Custom	Task status (NEW → COMPLETING → NORMAL/EXCEPTIONAL)	Wraps a Callable into a cancellable, awaitable task. get() parks via AQS until the task completes. Used internally by ExecutorService. See ../java-thread-internals.md
ThreadPoolExecutor	Exclusive (per worker)	Worker run state	Each worker thread is an AQS-based exclusive lock. shutdown() interrupts idle workers by trying tryLock() on each — if it succeeds, the worker is idle. Running workers hold their own lock so tryLock() fails → not interrupted. See ../java-thread-internals.md

Note: CyclicBarrier is NOT built on AQS — it uses ReentrantLock + Condition internally. See cyclic-barrier.md.
StampedLock is NOT built on AQS — it uses its own 64-bit state. See stamped-lock.md.

Inheritance Chain

AbstractOwnableSynchronizer     ← exclusiveOwnerThread (who holds the lock)
    │
AbstractQueuedSynchronizer      ← state, head, tail, CLH queue, acquire/release logic
    │
    ├── ReentrantLock.Sync      ← tryAcquire, tryRelease (see reentrant-lock.md)
    ├── Semaphore.Sync          ← tryAcquireShared, tryReleaseShared (see semaphore.md)
    ├── CountDownLatch.Sync     ← tryAcquireShared, tryReleaseShared (see count-down-latch.md)
    └── ReentrantReadWriteLock  ← packed state (see read-write-lock.md)

exclusiveOwnerThread is in the parent class because not all AQS subclasses need it — Semaphore and CountDownLatch use shared mode (no single owner).

Core Structure

// AbstractOwnableSynchronizer
private transient Thread exclusiveOwnerThread;  // who holds the lock (exclusive mode only)

// AbstractQueuedSynchronizer
volatile int state;          // meaning depends on subclass
volatile Node head;          // head of CLH wait queue (dummy node) — null until first contention
volatile Node tail;          // tail of CLH wait queue — null until first contention

// Subclasses override — define what "acquire" and "release" mean:
protected boolean tryAcquire(int arg)       { throw UOE; }
protected boolean tryRelease(int arg)       { throw UOE; }
protected int tryAcquireShared(int arg)     { throw UOE; }
protected boolean tryReleaseShared(int arg) { throw UOE; }

Serialization — Why head/tail Should Be transient

AQS implements Serializable (indirectly, through subclasses like ReentrantLock). This is for composability — if a class contains a lock field and is Serializable, the lock must be too. Otherwise NotSerializableException is thrown.

AQS has a custom readObject() that resets state on deserialization:

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    setState(0);  // reset to unlocked
}

The transient Keyword

transient tells Java serialization to skip a field. Fields like exclusiveOwnerThread are transient because they reference live Thread objects that are meaningless after deserialization (different JVM, different threads). After deserialization, transient fields default to null/0.

The Problem: head and tail Are NOT transient

head and tail are volatile but not transient. This means they get serialized and deserialized. If the lock was under contention at serialization time, the deserialized object has stale Node references with dead Thread pointers.

Case 1 — head == tail (same node or both null): This is the benign case. If no contention ever occurred, both are null — no problem. If contention happened but all waiters already acquired and left, head == tail points to the leftover dummy sentinel (its thread field is always null). Either way, no stale thread references, no corruption. The queue is effectively empty.

Case 2 — head != tail (multiple stale nodes — real contention at serialization time): Breaks. If threads were actively queued when serialization happened, the queue has head (dummy) → [waiter nodes] ← tail. The waiter nodes have dead Thread references. unparkSuccessor tries to unpark a dead thread — no-op. Real waiting threads appended after deserialization never get woken:

After deserialization: head = staleA, tail = staleC
Stale queue: staleA → staleB → staleC

Thread-B contends → appended after staleC:
  staleA → staleB → staleC → B's node

Thread-A releases: unparkSuccessor(staleA)
  → staleA.next = staleB
  → unpark(staleB.thread)  ← DEAD thread reference! No-op.
  → Thread-B is stuck forever.

Why It Works In Practice

readObject() resets state to 0. With state == 0, the first tryAcquire/tryAcquireShared succeeds immediately — no contention, no queue access on the first acquisition. If contention occurs later (second thread), addWaiter() reads tail and appends after the stale nodes. In the benign Case 1 (head == tail, empty sentinel), this works fine — the stale sentinel acts as the dummy head. In Case 2 (head != tail, active waiters), it breaks as shown above.

The real protection is that nobody serializes a lock while threads are actively queued (Case 2). In normal usage, serialization happens when the application is quiescent — no threads contending — so head/tail are either null or an empty sentinel (Case 1). But it’s still a minor JDK oversight — head and tail should be transient for correctness and clarity. A more thorough readObject() would also reset them:

// What readObject() should ideally do:
private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    setState(0);
    // head = null;  // should do this
    // tail = null;  // should do this
}

---

No Contention — Fast Path (No Queue)

When no contention, the queue is never created. Only state and exclusiveOwnerThread are used:

// tryAcquire — no contention
if (state == 0 && CAS(state, 0, 1)) {
    exclusiveOwnerThread = currentThread;  // record owner
    return true;                            // done — no queue touched
}

No contention:
┌──────────────────────────────────┐
│ state = 1                        │  ← "lock is held"
│ exclusiveOwnerThread = Thread-0  │  ← "held by whom"
│ head = null                      │  ← no queue (never needed)
│ tail = null                      │
└──────────────────────────────────┘

After release:
┌──────────────────────────────────┐
│ state = 0                        │  ← "lock is free"
│ exclusiveOwnerThread = null      │  ← "nobody owns it"
│ head = null                      │  ← still no queue
│ tail = null                      │
└──────────────────────────────────┘

The queue is lazily initialized only on first contention (when tryAcquire fails).

CLH Queue (Craig, Landin, Hagersten)

A doubly-linked FIFO queue. head and tail are the two endpoints. Each node holds a thread and a wait status:

static class Node {
    volatile int waitStatus;    // SIGNAL(-1), CANCELLED(1), CONDITION(-2), PROPAGATE(-3), 0
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
}

head (dummy) → [Node: T-1, SIGNAL] → [Node: T-2, SIGNAL] → [Node: T-3, 0] ← tail
                     (parked)              (parked)            (just enqueued)

Original CLH is a singly-linked spin lock. AQS replaces spinning with park/unpark (no CPU waste) and adds prev pointers for node cancellation.

Two key properties:

1. No contention between enqueue and dequeue (different ends):

Dequeue (head side):                Enqueue (tail side):
  head = head.next                    CAS(tail, old, new)
  touches: head pointer               touches: tail pointer
  → different memory locations → NO conflict

2. Each thread only interacts with predecessor (no thundering herd):

CLH — wake only successor:
  unlock() → unpark T-1 only (head.next)
  T-1 wakes → acquires → becomes head → unlocks → unpark T-2
  → one-to-one handoff, 0 wasted wakeups

AQS maintains a dummy head so head and tail are separate nodes even with one entry. Queue is lazily initialized on first contention:

private Node enq(Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) {
            if (CAS(head, null, new Node()))  // create dummy head
                tail = head;
        } else {
            node.prev = t;
            if (CAS(tail, t, node)) {         // append to tail
                t.next = node;
                return t;
            }
        }
    }
}

Exclusive Acquire Flow (Full Code)

// Entry point: ReentrantLock.lock() → AQS.acquire(1)
public final void acquire(int arg) {
    if (!tryAcquire(arg) &&                            // fast path: try CAS
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))  // slow path: enqueue + park
        selfInterrupt();                                // restore interrupt flag if needed
}

static void selfInterrupt() {
    Thread.currentThread().interrupt();                 // re-set the interrupt flag
}

addWaiter — Fast Path + Slow Path

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    Node pred = tail;
    if (pred != null) {                          // FAST PATH: queue exists
        node.prev = pred;                        // link prev BEFORE CAS
        if (compareAndSetTail(pred, node)) {     // one CAS attempt
            pred.next = node;                    // link next AFTER CAS
            return node;                         // done!
        }
    }
    enq(node);                                   // SLOW PATH: queue empty or CAS failed
    return node;
}

Fast path: queue exists, one CAS succeeds → done (no loop). Slow path (enq): queue empty (create dummy head) or CAS race (retry in loop).

Note: enq does NOT set predecessor’s waitStatus. SIGNAL is set later by shouldParkAfterFailedAcquire — only when the thread is actually about to park.

acquireQueued — Spin/Park Loop

final boolean acquireQueued(final Node node, int arg) {
    boolean interrupted = false;
    for (;;) {
        final Node p = node.predecessor();
        if (p == head && tryAcquire(arg)) {              // am I next? can I get it?
            setHead(node);                                // become new dummy head
            p.next = null;                                // help GC old dummy
            return interrupted;                           // tell caller: was I interrupted?
        }
        if (shouldParkAfterFailedAcquire(p, node))       // set SIGNAL on predecessor
            interrupted |= parkAndCheckInterrupt();       // park here, check interrupt on wake
    }
}

private final boolean parkAndCheckInterrupt() {
    LockSupport.park(this);              // park (woken by unpark OR interrupt)
    return Thread.interrupted();          // was I woken by interrupt? (clears flag)
}

void setHead(Node node) {
    head = node;
    node.thread = null;                  // head is always a dummy
    node.prev = null;
}

interrupted tracks whether the thread was interrupted while parked. lock() doesn’t throw — it swallows the interrupt but remembers it. When acquireQueued returns true, acquire() calls selfInterrupt() to restore the flag so the caller can check it later.

lock():              interrupt → remember → keep waiting → got lock → restore flag
lockInterruptibly(): interrupt → cancel → throw InterruptedException → no lock

Only the thread right after head attempts tryAcquire(). Others stay parked.

Dequeue: the acquiring thread becomes the new dummy head. Old dummy is disconnected for GC. Nodes are removed one at a time — no bulk clear:

Before T-1 acquires:  head (dummy) → [T-1] → [T-2] ← tail
After T-1 acquires:   head (T-1, dummy) → [T-2] ← tail  (old dummy → GC)
After T-2 acquires:   head (T-2, dummy) ← tail            (queue "empty")

shouldParkAfterFailedAcquire — Set SIGNAL, Decide to Park

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)                               // Case 1: already SIGNAL
        return true;                                      // → safe to park
    if (ws > 0) {                                        // Case 2: CANCELLED
        do { node.prev = pred = pred.prev; }             // skip cancelled nodes
        while (pred.waitStatus > 0);
        pred.next = node;
        return false;                                     // → try acquire again
    } else {                                             // Case 3: 0 or PROPAGATE
        CAS(pred.waitStatus, ws, Node.SIGNAL);           // set SIGNAL
        return false;                                     // → try acquire one more time
    }
}

Always takes at least 2 loop iterations before parking — first to set SIGNAL, second to confirm and park. This gives one extra tryAcquire chance (lock might have been released).

LockSupport Permit — Why unpark Before park Is Safe

LockSupport uses a per-thread permit (0 or 1). unpark() before park() is NOT lost:

unpark(thread):  permit = 1
park():          permit == 1? → consume, return immediately (no sleep)
                 permit == 0? → sleep until unpark

If release happens between shouldPark returning true and park(), the unpark sets the permit. When park() is called, it sees the permit and returns immediately. No thread is ever lost.

Exclusive Release Flow

public final boolean release(int arg) {
    if (tryRelease(arg)) {                               // state-- → state == 0?
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);                          // wake head.next
        return true;
    }
    return false;                                        // still held (reentrant)
}

tryRelease

Subclass-specific. See reentrant-lock.md for ReentrantLock’s reentrant decrement logic.

The h.waitStatus != 0 check in release(): if 0, no successor has set SIGNAL yet — either queue is empty or successor hasn’t parked yet (it will try tryAcquire and succeed since state is now 0).

unparkSuccessor — Find and Wake the Next Thread

void unparkSuccessor(Node node) {
    CAS(node.waitStatus, SIGNAL, 0);                     // reset for future use
    Node s = node.next;                                  // fast path: head.next
    if (s == null || s.waitStatus > 0) {                 // null or CANCELLED?
        s = null;
        for (Node t = tail; t != null && t != node; t = t.prev)  // walk backwards
            if (t.waitStatus <= 0) s = t;                // find valid successor
    }
    if (s != null) LockSupport.unpark(s.thread);
}

Why walk backwards? prev is always reliable (set before CAS). next can be null (enqueue window), self-link (cancelled), or stale.

Shared Acquire/Release (Semaphore, CountDownLatch)

Multiple threads can acquire simultaneously. Release propagates — waking cascades:

Semaphore(3) — 3 threads waiting, 3 permits released:
  releaseShared → wake T-1
  T-1 acquires → still permits → wake T-2 (PROPAGATE)
  T-2 acquires → still permits → wake T-3 (PROPAGATE)
  T-3 acquires → no more → stop

See semaphore.md for full shared acquire internals and PROPAGATE cascade details.

tryAcquire() — Subclass-Specific

Each subclass defines what “acquire” means by overriding tryAcquire (exclusive) or tryAcquireShared (shared). AQS provides the queuing and parking — subclasses only define the CAS logic on state. See reentrant-lock.md for fair/unfair tryAcquire details.

The acquires Parameter

For ReentrantLock, always 1. Exists because AQS is a general framework:

ReentrantLock:    state = reentrant count     tryAcquire(1)  → state += 1
Semaphore(3):     state = available permits   tryAcquire(1)  → state -= 1
                                              tryAcquire(2)  → state -= 2
CountDownLatch:   state = remaining count     tryRelease(1)  → state -= 1
ReadWriteLock:    state = packed 32 bits
                  upper 16 = read count       tryAcquireShared(1) → upper += 1
                  lower 16 = write count      tryAcquire(1)       → lower += 1

How Different Synchronizers Use AQS

ReentrantLock:
  tryAcquire(1):  state == 0? CAS(0,1), owner = me. owner == me? state++
  tryRelease(1):  state-- → state == 0? owner = null → wake successor

Semaphore(3):
  tryAcquireShared(1):  avail = state; CAS(state, avail, avail-1)
  tryReleaseShared(1):  CAS(state, c, c+1) → propagate

CountDownLatch(5):
  tryAcquireShared(1):  state == 0 ? 1 : -1  (only "acquire" when count is 0)
  tryReleaseShared(1):  CAS(state, c, c-1) → c-1 == 0? wake all

ReadWriteLock:
  state upper 16 bits = shared read count
  state lower 16 bits = exclusive write count
  tryAcquire(1):       write lock (lower bits)
  tryAcquireShared(1): read lock (upper bits)

Sync Queue vs Condition Queue

AQS supports two types of queues. The sync queue is built-in (one per AQS instance). Condition queues are created on demand via newCondition() and are only available for exclusive-mode subclasses (e.g., ReentrantLock).

Sync Queue (lock waiters):
  "I want the lock but someone else has it"
  head → [Thread-1] → [Thread-2] → tail

Condition Queue (condition waiters):
  "I have the lock but a business condition isn't met"
  first → [Thread-3] → [Thread-4] → last

signal() moves a thread from condition queue to sync queue (still needs to re-acquire lock). await() fully releases the lock, parks in the condition queue, then re-acquires via acquireQueued when signaled.

See reentrant-lock.md for condition queue usage patterns (producer-consumer) and await()/signal() internals.

Lock Acquisition Strategies

AQS supports four waiting policies. The queue mechanics are the same — only the parking/cancellation behavior differs. See reentrant-lock.md for usage details of each strategy (lock(), lockInterruptibly(), tryLock(), tryLock(timeout)).

waitStatus Deep Dive

waitStatus tells the system what to do with a node and its successor:

 0          → Initial state (just enqueued)
SIGNAL (-1) → "When I release, I MUST unpark my successor"
CANCELLED (1) → "I gave up waiting (timeout/interrupt), skip me"
CONDITION (-2) → "I'm in a condition queue, not the sync queue"
PROPAGATE (-3) → "Shared release should propagate to next node"

volatile because it’s read by one thread (predecessor) and written by another (successor setting SIGNAL, or node itself setting CANCELLED).

SIGNAL is set by the successor, not the node itself — Thread-2 arrives, sets predecessor.waitStatus = SIGNAL, then parks safely knowing predecessor will wake it.

cancelAcquire() — Full Cancel Flow

Called when a thread gives up waiting — from lockInterruptibly() (interrupt), tryLock(timeout) (timeout), or any exception:

park()  → give up CPU, stay in queue
unpark  → get CPU back, still in queue
tryAcquire success → get CPU + get lock → become head (normal path)
tryAcquire fail + timeout/interrupt → get CPU, no lock → cancelAcquire (cleanup)

private void cancelAcquire(Node node) {
    if (node == null) return;

    // Step 1: Clear thread reference (this node is dead)
    node.thread = null;

    // Step 2: Skip cancelled predecessors (walk backwards)
    Node pred = node.prev;
    while (pred.waitStatus > 0)
        node.prev = pred = pred.prev;
    Node predNext = pred.next;

    // Step 3: Mark as CANCELLED
    node.waitStatus = Node.CANCELLED;

    // Step 4: Unlink — three cases
    if (node == tail && compareAndSetTail(node, pred)) {
        // Case 1: tail → remove from end
        compareAndSetNext(pred, predNext, null);
    } else if (pred != head
               && (pred.waitStatus == Node.SIGNAL
                   || compareAndSetWaitStatus(pred, pred.waitStatus, Node.SIGNAL))
               && pred.thread != null) {
        // Case 2: middle → link pred to my successor (skip me)
        Node next = node.next;
        if (next != null && next.waitStatus <= 0)
            compareAndSetNext(pred, predNext, next);
    } else {
        // Case 3: right after head → wake my successor
        unparkSuccessor(node);
    }

    // Step 5: Self-link for GC
    node.next = node;
}

The three cases:

Case 1: node is tail
  Before: head → [pred] → [node] ← tail
  After:  head → [pred] ← tail

Case 2: node is in the middle
  Before: head → [pred SIGNAL] → [node] → [T-3]
  After:  head → [pred SIGNAL] ────────→ [T-3]  (skip node)

Case 3: node is right after head
  Before: head → [node] → [T-3 parked]
  After:  unparkSuccessor(node) → wake T-3
          T-3 wakes → shouldPark skips cancelled nodes → acquires or re-parks

Case 3 must call unparkSuccessor — if it just unlinked without waking, the successor would sleep forever (nobody to unpark it).

The Big Picture

AQS = state (int) + CLH sync queue + park/unpark

Exclusive (ReentrantLock):
  acquire: tryAcquire → fail → enqueue → park → wake → tryAcquire → success
  release: tryRelease → state == 0 → unpark successor

Shared (Semaphore, CountDownLatch):
  acquire: tryAcquireShared → fail → enqueue → park → wake → propagate
  release: tryReleaseShared → unpark + propagate

Condition:
  await:  condition queue → fully release → park
  signal: condition queue → sync queue → normal acquire cycle

What Locks Actually Manage

Locks manage access to shared heap memory — not the stack. Each thread has its own private stack (local variables, method frames). The shared heap is where contention happens:

Thread-0 stack (private):          Thread-1 stack (private):
┌──────────────────┐               ┌──────────────────┐
│ local var x = 10 │               │ local var y = 20 │
└──────────────────┘               └──────────────────┘
         │                                  │
         ▼                                  ▼
┌─────────────────────────────────────────────────┐
│              Shared Heap Memory                  │
│  counter = 42  ← BOTH threads read/write this   │
└─────────────────────────────────────────────────┘

Without lock: both do counter++ → race condition
With lock:    one at a time → safe

AQS itself lives on the heap — state, head, tail, and all Node objects are heap-allocated. Unlike synchronized’s lightweight lock (which uses a stack-based lock record as an optimization), AQS has no stack-resident structures.