ReentrantLock and AQS: CAS on state, park waiters in a queue

The idea: one int and a queue

java.util.concurrent.locks.ReentrantLock keeps almost no code of its own. Inside it is a small class Sync that extends AbstractQueuedSynchronizer (AQS), written by Doug Lea. AQS holds one volatile int state, the exclusiveOwnerThread, and a wait queue of sleeping threads. For a lock, state is 0 when it is free and n when the owner has locked it n times.

The page shows four threads sharing one lock. Pick a thread and press lock() or unlock(). The code panels follow the JDK 8 source of ReentrantLock and AbstractQueuedSynchronizer line by line.

The fast path: one CAS

A free lock is taken with one compare-and-swap: compareAndSetState(0, 1). If it succeeds, the thread writes itself into exclusiveOwnerThread and returns. There is no system call and no queue, so an uncontended lock() and unlock() cost about as much as two atomic writes. (Demo 1: no contention, one CAS.) See Compare-and-Swap for how the CAS itself works.

Reentrant: state counts the holds

If the owner calls lock() again, tryAcquire sees that exclusiveOwnerThread is the current thread and just writes state + 1. No CAS is needed, because only the owner can change state while it is held. Each unlock() subtracts 1, and the lock is free only when state is back to 0. So every lock() needs its own unlock(), which is why the pattern is always lock(); try { ... } finally { unlock(); }. (Demo 2: reentrant, state counts holds.)

The wait queue and park

A thread that finds the lock taken calls acquire(1), the AQS template method:

1. tryAcquire fails.
2. addWaiter wraps the thread in a Node and appends it to the queue with a CAS on tail. The first time anyone waits, AQS creates a dummy head node first.
3. acquireQueued: if the node's predecessor is the head, the thread is next in line and tries once more.
4. shouldParkAfterFailedAcquire sets the predecessor's waitStatus to SIGNAL (-1): "wake my successor when you are done".
5. LockSupport.park(this): the thread sleeps in state WAITING. On Linux this is a futex wait (see How a Mutex Works: the Futex), so a waiting thread uses no CPU.

The queue is a variant of the CLH lock queue (Craig, Landin and Hagersten). Appending only needs a CAS on tail, so many threads can join it at once without a lock of their own.

unlock and the hand-off

unlock() calls release(1). tryRelease subtracts 1 from state; at 0 it clears the owner. If the head's waitStatus is SIGNAL, someone is sleeping, so unparkSuccessor resets it to 0 and calls LockSupport.unpark on the thread of head.next. The woken thread is still inside acquireQueued. It retries tryAcquire, wins, and its node becomes the new dummy head (setHead clears node.thread). (Demo 3: two waiters park, then hand-off.)

Only the owner may unlock. Any other thread gets an IllegalMonitorStateException, and the lock does not change. (Demo 6: unlock by a non-owner throws.)

Because state is volatile, the release is a volatile write and the next CAS is a volatile read. That gives the same happens-before edge as leaving and entering synchronized: everything the old owner wrote is visible to the next one (see Java Memory Model).

Nonfair vs fair

Waking a parked thread takes time: the scheduler has to put it back on a core. In between, the lock is free. A nonfair lock (the default) lets any thread that arrives just then take it with the fast-path CAS. This is called barging. The woken thread fails, sets SIGNAL again and parks. A fair lock (new ReentrantLock(true)) has no fast path, and its tryAcquire refuses a free lock while hasQueuedPredecessors() is true, so the newcomer joins the tail. (Demo 4: nonfair, T4 barges in; Demo 5: fair lock, T4 must queue.)

	nonfair (default)	fair
new thread, lock free, queue not empty	takes it with a CAS	joins the tail and parks
order of service	mostly FIFO, newcomers can cut in	FIFO
throughput	higher: the lock is not idle while a thread wakes	lower: every hand-off waits for a wake-up
risk	a waiter can be passed over many times	more context switches

tryLock() with no timeout always barges, even on a fair lock.

One AQS, many synchronizers

AQS does the hard part: the queue, parking, waking, timeouts and interrupts. A class built on it only writes tryAcquire / tryRelease (exclusive mode) or tryAcquireShared / tryReleaseShared (shared mode), and decides what state means.

In shared mode one release can wake several waiters in a row (it "propagates"), which is how countDown() to 0 lets every await() through. See Semaphore for the idea in general.

ReentrantLock vs synchronized

Both are reentrant and give the same memory guarantees. synchronized is built into the JVM (the object header and monitors) and is released automatically at the end of the block. ReentrantLock is plain Java on top of AQS and adds tryLock, timeouts, lockInterruptibly, a fairness option and several Condition queues. With virtual threads, a thread parked in AQS unmounts from its carrier; before JDK 24 a thread blocked in synchronized pinned it.

What the page leaves out

The page follows JDK 8. JDK 14 rewrote AQS (status bits instead of waitStatus, spinning a little before parking, ConditionNode) but kept the same design. It leaves out the extra loop in shouldParkAfterFailedAcquire before parking, cancelled nodes (waitStatus 1) from timeouts and interrupts, Condition objects and their second queue, shared-mode propagation, AbstractQueuedLongSynchronizer, and how park maps to the OS. Real threads run at the same time; here each call runs to the end before the next one starts, except for the barging thread in demos 4 and 5.

References

AbstractQueuedSynchronizer, Java SE 21 API documentation

ReentrantLock, Java SE 21 API documentation

Doug Lea: The java.util.concurrent Synchronizer Framework (2004)

OpenJDK 8 source: AbstractQueuedSynchronizer.java