What on Earth Is the AQS Everyone Keeps Talking About? (AbstractQueuedSynchronizer)

Surely you’ve heard plenty of experts talk about AQS. So what is AQS? From the name AbstractQueuedSynchronizer we can guess it’s an abstract queued synchronizer. Every character makes sense on its own; string them together and it stops making sense. Let’s break it apart.

Abstract

In “abstract queued synchronizer”, Abstract means it’s an abstract class, so AbstractQueuedSynchronizer doesn’t serve you directly. My personal take: an abstract class is a half-written class, so AQS is really a framework, a solution. The JDK authors wrote a solution following their own line of thought, and then we get to finish their class and implement our own synchronizer.

Queued

In “abstract queued synchronizer”, Queued means it relies on a queue data structure — a first-in-first-out (FIFO) queue, of course working together with related synchronizers (semaphores, events, and so on). That’s a lot of material; more on it later.

Synchronizer

And Synchronizer means… it’s a synchronizer. Hmm, that explains nothing. Let me write my own understanding here; it may not be strictly correct, so correct me if I’m wrong. In a multithreaded environment, threads get picked up by multiple CPUs and executed at random, so they run in near-arbitrary order. Some scenarios require threads to execute one after another in order — that’s when a synchronizer comes in, imposing order between threads. If your program is single-threaded, AQS means nothing to you at all.

What’s It For

First, it lets you show off — I mean, understand how the JDK authors think, learn from it, and worship them devoutly. You can basically find an AQS implemented internally in every Lock. In this novice’s view, whenever you need to coordinate thread execution order in a multithreaded program, that’s a synchronizer. Even though I rarely use AQS directly, knowing how the masters use it is still worthwhile.

If you want a custom synchronizer, extending AQS means implementing only how the shared resource state is acquired and released. All the queuing machinery (enqueueing on failed acquisition, waking up and dequeuing, etc.) is already implemented at the top level in AQS.

Inside AQS

That’s roughly what AQS is. Now let’s see what’s inside. There’s volatile everywhere — we’ll talk about that in the next article; AQS first.

volatile int state

The comment says: The synchronization state. What does it actually mean? That depends on the implementing class. In ReentrantLock, for example, state represents the lock count — being reentrant means it can be locked multiple times.

The final class Node Inner Class

This Node is the node class in the wait queue. Here we also need to mention the CLH (Craig, Landin, and Hagersten) lock, because this is a variant of it. CLH is a spin-based fair lock built on a logical queue that avoids thread starvation, named after its three inventors Craig, Landin, and Hagersten. AQS is the core of JUC, and CLH is the foundation of AQS. Let’s keep looking at what’s inside:

volatile int waitStatus, the node’s wait status, with 5 possible values:

• 0 — the default value when a Node is initialized

• CANCELLED = 1 — the thread’s request to acquire the lock has been cancelled

• CONDITION = -2 — the node is in a condition queue, its thread waiting to be woken

• PROPAGATE = -3 — only used when the current thread is in SHARED mode

• SIGNAL = -1 — the thread is ready, just waiting for the resource to be released

volatile Thread thread, the thread reference — this is the waiting thread it carries.

volatile Node prev, next, references to the node’s predecessor and successor, which is how the doubly-linked queue is formed.

Node nextWaiter, links to the next node waiting on a condition, or a special shared value. This is the Condition queue — let’s set it aside for now and cover condition queue / sync queue conversion later.

volatile Node head

Note we’ve stepped out of Node — this is the head node inside AQS.

volatile Node tail

And this is the tail node inside AQS.

That covers the structure. Now, how does it actually run? Remember AQS is just an abstract class; it only implements maintenance of the wait queue. So here I’ll only describe how the queue runs — operating the shared state depends on the concrete implementation.

acquire: Taking the Lock

Let’s look at the acquisition logic in code:

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

The execution order is tryAcquire(arg), addWaiter(Node.EXCLUSIVE), acquireQueued; if it enters the if, selfInterrupt() runs. Don’t rush — let’s look at what the masters did, one by one.

Trying to grab the resource directly:

protected boolean tryAcquire(int arg) {
    throw new UnsupportedOperationException();
}

The very first tryAcquire is baffling. Where’s the master’s implementation? Throwing an exception — what? Remember what I said above: AQS is only a framework, a half-written class. This part is up to the subclass extending AQS. Whether it’s reentrant, whether barging is allowed — the subclass decides. So nothing to see here; moving on.

Appending this thread to the tail of the wait queue:

The addWaiter(Node) method appends the current thread to the tail of the wait queue and returns the node holding it:

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    Node pred = tail;
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    enq(node);
    return node;
}

It wraps the current thread into a Node, checks that the tail isn’t null, sets this node as the tail, and if that fails, runs enq(node) to enqueue.

enq(node): Enqueueing

It joins the tail via a CAS spin. We’ll cover CAS spinning in a later article; let’s stay on AQS logic:

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

acquireQueued: Waiting in Line

After tryAcquire tries to grab the lock and addWaiter appends us to the tail, what next? We’re at the tail now, so queue up obediently and wait to be called and woken. Here’s roughly how it flows:

First it uses try to handle thread interruption, then spins in a for loop retrying, grabbing the node’s predecessor;

It checks whether the predecessor is the head node; if so it tries tryAcquire, and on success sets itself as head via setHead and nulls the predecessor’s successor reference to help GC;

If the predecessor isn’t the head, it can go rest — entering the waiting state via park() until unpark(). If interrupted while uninterruptible, it wakes from park(), spins, finds the resource unavailable, and goes back into park() to wait.

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

shouldParkAfterFailedAcquire checks the status: it reads the predecessor’s waitStatus to see whether the person ahead in line gave up. If the predecessor cancelled, it moves up the line, then goes to rest.

parkAndCheckInterrupt rests via LockSupport.park(). LockSupport.park() goes in a later article too. Patience.

That completes the AQS queuing flow for acquiring; now the release flow.

release: Letting Go of the Lock

First the logic in code:

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

It runs tryRelease first, then unparkSuccessor to wake the next node in the wait queue.

tryRelease, like acquisition above, is left to subclasses.

unparkSuccessor wakes the next thread in the wait queue. It mainly looks for the next node; if that node already cancelled, it scans from the tail forward to find the frontmost node in the queue, then wakes it.

Why scan backward rather than forward? Because scanning forward can break. Imagine this:

A node is calling addWaiter to enqueue itself, setting itself as the tail. It executes compareAndSetTail(pred, node) and then gets kicked off the CPU and suspended. Now if you scan from the front, you reach the end and find next is null — because pred.next = node; hasn’t executed yet!

That was exclusive mode. There’s also shared mode, but I’m out of energy for that — I’ll describe it in words rather than walking every line of code.

In exclusive mode only one thread works. Shared mode is much the same, with one extra step: the thread that gets the resource checks whether any is left, and if so it wakes the brothers behind it to work together. The resource count comes from the return value of tryAcquireShared, again implemented by the subclass. I’ll just sketch the call chain here:

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

tryAcquireShared is left to subclasses, but AQS fixes the semantics of its return value: negative means acquisition failed; 0 means success with no resources left; positive means success with resources remaining.

doAcquireShared sends the current thread to the tail of the wait queue to rest:

private void doAcquireShared(int arg) {
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head) {
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

Very similar to exclusive mode; the main difference is calling setHeadAndPropagate. Let’s look at that too:

private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head; // Record old head for check below
    setHead(node);
    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) {
        Node s = node.next;
        if (s == null || s.isShared())
            doReleaseShared();
    }
}

Which in turn calls doReleaseShared. What does that mean? If there’s anything left, keep waking the next neighbor thread, so your brothers can work too. That’s the biggest difference from exclusive mode.

I’ll stop here on AQS. Once you expand it, there’s knowledge everywhere, and a novice like me can’t contain it. Next article I’ll write about CAS — stay tuned.