AQS (AbstractQueuedSynchronizer) Core

AQS (AbstractQueuedSynchronizer) CoreAQS is the foundation of almost everything injava.util.concurrent. It provides: anint state a CLH wait queue. Subclasses just define whatstatemeans.What’s Built on AQSAQS ├── 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 EachSubclassAQS Modestate MeaningWhen to UseReentrantLockExclusiveHold count (reentrant depth)Need tryLock, timeout, fairness, or multiple conditions. Upgrade fromsynchronizedwhen its features aren’t enough. Seereentrant-lock.mdReentrantReadWriteLockShared (read) Exclusive (write)Upper 16 bits readers, lower 16 writer countRead-heavy workloads where multiple readers can proceed concurrently but writes must be exclusive. Seeread-write-lock.mdSemaphoreSharedAvailable permitsRate limiting, connection pools, bounding concurrent access to N threads. No ownership — any thread can release. Seesemaphore.mdCountDownLatchSharedRemaining countOne-shot “wait for N events” — workers count down, coordinator awaits zero. Cannot reset. Seecount-down-latch.mdFutureTaskCustomTask 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.mdThreadPoolExecutorExclusive (per worker)Worker run stateEach worker thread is an AQS-based exclusive lock.shutdown()interrupts idle workers by tryingtryLock()on each — if it succeeds, the worker is idle. Running workers hold their own lock sotryLock()fails → not interrupted. See../java-thread-internals.mdNote: CyclicBarrier is NOT built on AQS — it uses ReentrantLock Condition internally. Seecyclic-barrier.md.StampedLock is NOT built on AQS — it uses its own 64-bit state. Seestamped-lock.md.Inheritance ChainAbstractOwnableSynchronizer ← 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)exclusiveOwnerThreadis in the parent class because not all AQS subclasses need it —SemaphoreandCountDownLatchuse shared mode (no single owner).Core Structure// AbstractOwnableSynchronizerprivatetransientThreadexclusiveOwnerThread;// who holds the lock (exclusive mode only)// AbstractQueuedSynchronizervolatileintstate;// meaning depends on subclassvolatileNodehead;// head of CLH wait queue (dummy node) — null until first contentionvolatileNodetail;// tail of CLH wait queue — null until first contention// Subclasses override — define what acquire and release mean:protectedbooleantryAcquire(intarg){throwUOE;}protectedbooleantryRelease(intarg){throwUOE;}protectedinttryAcquireShared(intarg){throwUOE;}protectedbooleantryReleaseShared(intarg){throwUOE;}No Contention — Fast Path (No Queue)When no contention, the queue is never created. OnlystateandexclusiveOwnerThreadare used:// tryAcquire — no contentionif(state0CAS(state,0,1)){exclusiveOwnerThreadcurrentThread;// record ownerreturntrue;// 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 (whentryAcquirefails).CLH Queue (Craig, Landin, Hagersten)A doubly-linked FIFO queue.headandtailare the two endpoints. Each node holds a thread and a wait status:staticclassNode{volatileintwaitStatus;// SIGNAL(-1), CANCELLED(1), CONDITION(-2), PROPAGATE(-3), 0volatileNodeprev;volatileNodenext;volatileThreadthread;}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 withpark/unpark(no CPU waste) and addsprevpointers for node cancellation.Two key properties: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 conflictEach 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 wakeupsAQS maintains a dummy head so head and tail are separate nodes even with one entry. Queue is lazily initialized on first contention:privateNodeenq(Nodenode){for(;;){Nodettail;if(tnull){if(CAS(head,null,newNode()))// create dummy headtailhead;}else{node.prevt;if(CAS(tail,t,node)){// append to tailt.nextnode;returnt;}}}}Exclusive Acquire Flow (Full Code)// Entry point: ReentrantLock.lock() → AQS.acquire(1)publicfinalvoidacquire(intarg){if(!tryAcquire(arg)// fast path: try CASacquireQueued(addWaiter(Node.EXCLUSIVE),arg))// slow path: enqueue parkselfInterrupt();// restore interrupt flag if needed}staticvoidselfInterrupt(){Thread.currentThread().interrupt();// re-set the interrupt flag}addWaiter — Fast Path Slow PathprivateNodeaddWaiter(Nodemode){NodenodenewNode(Thread.currentThread(),mode);Nodepredtail;if(pred!null){// FAST PATH: queue existsnode.prevpred;// link prev BEFORE CASif(compareAndSetTail(pred,node)){// one CAS attemptpred.nextnode;// link next AFTER CASreturnnode;// done!}}enq(node);// SLOW PATH: queue empty or CAS failedreturnnode;}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:enqdoes NOT set predecessor’swaitStatus. SIGNAL is set later byshouldParkAfterFailedAcquire— only when the thread is actually about to park.acquireQueued — Spin/Park LoopfinalbooleanacquireQueued(finalNodenode,intarg){booleaninterruptedfalse;for(;;){finalNodepnode.predecessor();if(pheadtryAcquire(arg)){// am I next? can I get it?setHead(node);// become new dummy headp.nextnull;// help GC old dummyreturninterrupted;// tell caller: was I interrupted?}if(shouldParkAfterFailedAcquire(p,node))// set SIGNAL on predecessorinterrupted|parkAndCheckInterrupt();// park here, check interrupt on wake}}privatefinalbooleanparkAndCheckInterrupt(){LockSupport.park(this);// park (woken by unpark OR interrupt)returnThread.interrupted();// was I woken by interrupt? (clears flag)}voidsetHead(Nodenode){headnode;node.threadnull;// head is always a dummynode.prevnull;}interruptedtracks whether the thread was interrupted while parked.lock()doesn’t throw — it swallows the interrupt but remembers it. WhenacquireQueuedreturnstrue,acquire()callsselfInterrupt()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 lockOnly the thread right after head attemptstryAcquire(). 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 ParkprivatestaticbooleanshouldParkAfterFailedAcquire(Nodepred,Nodenode){intwspred.waitStatus;if(wsNode.SIGNAL)// Case 1: already SIGNALreturntrue;// → safe to parkif(ws0){// Case 2: CANCELLEDdo{node.prevpredpred.prev;}// skip cancelled nodeswhile(pred.waitStatus0);pred.nextnode;returnfalse;// → try acquire again}else{// Case 3: 0 or PROPAGATECAS(pred.waitStatus,ws,Node.SIGNAL);// set SIGNALreturnfalse;// → 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 extratryAcquirechance (lock might have been released).LockSupport Permit — Why unpark Before park Is SafeLockSupportuses a per-thread permit (0 or 1).unpark()beforepark()is NOT lost:unpark(thread): permit 1 park(): permit 1? → consume, return immediately (no sleep) permit 0? → sleep until unparkIf release happens betweenshouldParkreturning true andpark(), theunparksets the permit. Whenpark()is called, it sees the permit and returns immediately. No thread is ever lost.Exclusive Release Flowpublicfinalbooleanrelease(intarg){if(tryRelease(arg)){// state-- → state 0?Nodehhead;if(h!nullh.waitStatus!0)unparkSuccessor(h);// wake head.nextreturntrue;}returnfalse;// still held (reentrant)}tryReleaseSubclass-specific. Seereentrant-lock.mdfor ReentrantLock’s reentrant decrement logic.Theh.waitStatus ! 0check inrelease(): if 0, no successor has set SIGNAL yet — either queue is empty or successor hasn’t parked yet (it will trytryAcquireand succeed since state is now 0).unparkSuccessor — Find and Wake the Next ThreadvoidunparkSuccessor(Nodenode){CAS(node.waitStatus,SIGNAL,0);// reset for future useNodesnode.next;// fast path: head.nextif(snull||s.waitStatus0){// null or CANCELLED?snull;for(Nodettail;t!nullt!node;tt.prev)// walk backwardsif(t.waitStatus0)st;// find valid successor}if(s!null)LockSupport.unpark(s.thread);}Why walk backwards?previs always reliable (set before CAS).nextcan 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 → stopSeesemaphore.mdfor full shared acquire internals and PROPAGATE cascade details.tryAcquire() — Subclass-SpecificEach subclass defines what “acquire” means by overridingtryAcquire(exclusive) ortryAcquireShared(shared). AQS provides the queuing and parking — subclasses only define the CAS logic onstate. Seereentrant-lock.mdfor fair/unfair tryAcquire details.TheacquiresParameterForReentrantLock, always1. 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 1How Different Synchronizers Use AQSReentrantLock: 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, c1) → 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 QueueAQS supports two types of queues. The sync queue is built-in (one per AQS instance). Condition queues are created on demand vianewCondition()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 isnt met first → [Thread-3] → [Thread-4] → lastsignal()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 viaacquireQueuedwhen signaled.Seereentrant-lock.mdfor condition queue usage patterns (producer-consumer) andawait()/signal()internals.Lock Acquisition StrategiesAQS supports four waiting policies. The queue mechanics are the same — only the parking/cancellation behavior differs. Seereentrant-lock.mdfor usage details of each strategy (lock(),lockInterruptibly(),tryLock(),tryLock(timeout)).waitStatus Deep DivewaitStatustells 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) → Im in a condition queue, not the sync queue PROPAGATE (-3) → Shared release should propagate to next nodevolatilebecause 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 FlowCalled when a thread gives up waiting — fromlockInterruptibly()(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)privatevoidcancelAcquire(Nodenode){if(nodenull)return;// Step 1: Clear thread reference (this node is dead)node.threadnull;// Step 2: Skip cancelled predecessors (walk backwards)Nodeprednode.prev;while(pred.waitStatus0)node.prevpredpred.prev;NodepredNextpred.next;// Step 3: Mark as CANCELLEDnode.waitStatusNode.CANCELLED;// Step 4: Unlink — three casesif(nodetailcompareAndSetTail(node,pred)){// Case 1: tail → remove from endcompareAndSetNext(pred,predNext,null);}elseif(pred!head(pred.waitStatusNode.SIGNAL||compareAndSetWaitStatus(pred,pred.waitStatus,Node.SIGNAL))pred.thread!null){// Case 2: middle → link pred to my successor (skip me)Nodenextnode.next;if(next!nullnext.waitStatus0)compareAndSetNext(pred,predNext,next);}else{// Case 3: right after head → wake my successorunparkSuccessor(node);}// Step 5: Self-link for GCnode.nextnode;}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-parksCase 3 must callunparkSuccessor— if it just unlinked without waking, the successor would sleep forever (nobody to unpark it).The Big PictureAQS 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 cycleWhat Locks Actually ManageLocks 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 → safeAQS itself lives on the heap —state,head,tail, and allNodeobjects are heap-allocated. Unlikesynchronized’s lightweight lock (which uses a stack-based lock record as an optimization), AQS has no stack-resident structures.