How to Hand‑Write a Simple AbstractQueuedSynchronizer (AQS) for High‑Pay Java Interviews

Core concepts of AQS and related queues

Locks and queues are tightly coupled in Java concurrency. Both intra‑process locks (e.g., ReentrantLock) and distributed locks (e.g., ZooKeeper) use a FIFO queue to reduce contention.

CLH lock internal queue

CLH lock uses a single‑direction FIFO queue where the head node holds the lock and new threads are appended to the tail.

Distributed lock queue (ZooKeeper example)

Distributed locks also maintain a waiting queue similar to CLH. The waiting queue structure is shown in the diagram.

AQS internal queue

AbstractQueuedSynchronizer (AQS) provides a FIFO doubly‑linked list; each node represents a waiting thread.

Node structure

private static class Node {
    final Thread thread;
    Node next;
    Node prev;
    Node(Thread thread) { this.thread = thread; }
}

The original AQS node also contains a waitStatus field with values CANCELLED (1), SIGNAL (-1), CONDITION (-2), PROPAGATE (-3), and 0. The simplified version omits waitStatus but its purpose is explained.

State management

AQS holds a volatile int state representing the synchronization state.

// Get the current state
protected final int getState() { return state; }

// Set a new state (non‑atomic)
protected final void setState(int newState) { state = newState; }

// CAS update of the state
protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

Template design

AQS follows the template‑method pattern: concrete synchronizers implement tryAcquire and tryRelease while AQS provides queuing and blocking logic.

Key simplified AQS methods

acquire(int arg)

Attempts to acquire the lock; if it fails, the current thread is wrapped in a node and added to the queue, then it enters the spin‑wait loop.

public final void acquire(int arg) {
    if (!tryAcquire(arg)) {
        Node node = addWaiter();
        acquireQueued(node, arg);
    }
}

addWaiter()

Creates a node for the current thread and appends it to the tail. If the queue is empty, a dummy head node is created first.

private Node addWaiter() {
    Node node = new Node(Thread.currentThread());
    for (;;) {
        Node t = tail;
        if (t == null) {
            Node dummy = new Node(null); // dummy head
            dummy.next = node;
            node.prev = dummy;
            head = dummy;
            tail = node;
            return node;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return node;
            }
        }
    }
}

acquireQueued(Node node, int arg)

Spins while the node is not at the head. When the predecessor becomes the dummy head, it retries tryAcquire. If acquisition fails, the thread may be parked.

private void acquireQueued(Node node, int arg) {
    boolean interrupted = false;
    try {
        for (;;) {
            Node p = node.prev;
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                return;
            }
            if (shouldParkAfterFailedAcquire()) {
                LockSupport.park(this);
                if (Thread.interrupted()) {
                    interrupted = true;
                }
            }
        }
    } finally {
        if (interrupted) selfInterrupt();
    }
}

shouldParkAfterFailedAcquire()

Determines whether the current thread should block. The simplified version checks that the queue is not empty.

private final boolean shouldParkAfterFailedAcquire() {
    Node p = head;
    return p != null && p != tail;
}

release(int arg)

Calls tryRelease. If successful, it wakes up the successor node.

public final void release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h != tail) {
            unparkSuccessor(h);
        }
    }
}

private void unparkSuccessor(Node node) {
    Node next = node.next;
    if (next != null) {
        LockSupport.unpark(next.thread);
    }
}

Simple exclusive lock example

The following class extends the simplified AQS to implement an exclusive lock.

public class SimpleExclusiveLock extends SimpleAQS {
    @Override
    protected boolean tryAcquire(int arg) {
        if (compareAndSetState(0, 1)) {
            setExclusiveOwnerThread(Thread.currentThread());
            return true;
        }
        return false;
    }

    @Override
    protected boolean tryRelease(int arg) {
        setState(0);
        setExclusiveOwnerThread(null);
        return true;
    }

    private void setExclusiveOwnerThread(Thread thread) {
        // Simplified: not storing the thread reference
    }

    private boolean compareAndSetState(int expect, int update) {
        return getState() == expect && setState(update);
    }

    public void lock() { acquire(1); }
    public void unlock() { release(1); }

    public static void main(String[] args) {
        SimpleExclusiveLock lock = new SimpleExclusiveLock();
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                lock.lock();
                try {
                    System.out.println(Thread.currentThread().getName() + " acquired the lock");
                    Thread.sleep(1000);
                } catch (InterruptedException e) { e.printStackTrace(); }
                finally {
                    System.out.println(Thread.currentThread().getName() + " released the lock");
                    lock.unlock();
                }
            }).start();
        }
    }
}

Running the program shows threads acquiring and releasing the lock one after another, confirming the exclusive nature of the lock.

Dummy head node

A dummy head node simplifies queue handling by avoiding null checks for the first waiting thread and ensures that only the node whose predecessor is the head can attempt to acquire the lock.

waitStatus field (omitted in the simplified version)

CANCELLED (1) – node cancelled.

SIGNAL (-1) – predecessor must wake this node.

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

PROPAGATE (-3) – used in shared mode.

0 – initial state.

In the full AQS implementation, a node sets its predecessor’s waitStatus to SIGNAL before parking so that the predecessor knows to wake it.

Original AQS snippets for reference

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;
}

private final boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)
        return true;
    if (ws > 0) {
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

Summary

The dummy head node eliminates special‑case handling for the first waiting thread.

State management, queue insertion, and proper wake‑up logic are the core of AQS‑based synchronizers.

Understanding these mechanisms enables implementation of custom synchronizers and answers high‑level interview questions.