1. synchronzied vs. Lock

1.1 Where synchronized falls short

The built-in monitor (synchronized) provides mutual exclusion and automatic release when a block exits. However, it has notable constraints:

• Acquisition is blocking-only; there is no non-blocking attempt to acquire (no try semantics).
• Waiting threads cannot be selected fairly; ordering is not guaranteed.
• Threads blocked entering a monitor cannot be interrupted while acquiring the monitor.
• One condition queue per monitor limits flexibility when modeling complex wait/notify patterns.

1.2 A brief look at Lock

The java.util.concurrent.locks.Lock abstraction adds richer control:

• lock()
• lockInterruptibly()
• tryLock()
• tryLock(long timeout, TimeUnit unit)
• unlock()
• newCondition()

Typical usage ensures the lock is released in a finally block.

private final Lock gate = new ReentrantLock();

public void execute() {
    gate.lock();
    try {
        runCriticalSection();
    } finally {
        gate.unlock();
    }
}

2. AQS in a nutshell

AbstractQueuedSynchronizer (AQS) supplies the queuing and state-management mechanics used by many synchronizers (ReentrantLock, Semaphore, CountDownLatch, ReentrantReadWriteLock, FutureTask, etc.).

Core ideas:

• A single volatile integer state encodes the synchronizer’s permit or hold count (e.g., ReentrantLock hold count, Semaphore permits, FutureTask status).
• A FIFO CLH-style queue holds contending threads as nodes. The dummy head node has no associated thread; subsequent nodes represent waiting threads.
• CAS (compare-and-set) is used to mutate head/tail links and the state atomically.
• AQS extends AbstractOwnableSynchronizer, tracking the exclusive owner thread for diagnostic and correctness purposes.

Understanding AQS clarifies the behavior of most java.util.concurrent lock implementations.

3. How ReentrantLock acquires and releases

3.1 Terminology

• Reentrancy: the current owner can acquire the same lock repeatedly; the hold count increases.
• Interruptible acquisition: a waiting thread can be interrupted while attempting to acquire.
• Fairness: a fair lock honors first-in-first-out acquisition for queued threads; a nonfair lock allows barge-in by newly arriving threads.
• CAS: atomic compare-and-set that updates a value only if it still equals an expected value.

3.2 Structure

ReentrantLock selects a fairness policy by constructing a specific AQS subclass:

public ReentrantLock() {
    sync = new NonfairSync();
}

public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

The lock and unlock methods delegate to this sync instance.

3.3 Nonfair lock path

Nonfair mode prioritizes fast, uncontended acquisition and allows barge-in when the lock becomes free.

3.3.1 lock()

Fast path first, then fall back to AQS queuing:

final void lock() {
    // Attempt a 0→1 transition without queueing
    if (casStateTo(0, 1)) {
        markOwner(Thread.currentThread());
        return;
    }
    // Contended path
    acquire(1);
}

private boolean casStateTo(int expect, int update) {
    // CAS on AQS.state; placeholder for Unsafe.compareAndSwapInt
    return compareAndSetState(expect, update);
}

private void markOwner(Thread t) {
    setExclusiveOwnerThread(t);
}

The "unfair" aspect: if the lock becomes free and a new thread arrives before queued threads are unparked, the newcomer may acquire immediately.

The acquire path coordinates trying, enqueueing, and parking:

public final void acquire(int permits) {
    if (tryAcquire(permits)) {
        return;
    }
    final Node n = enqueueExclusive();
    if (awaitOnQueue(n, permits)) {
        // Reassert interrupt status if we were interrupted while parked
        selfInterrupt();
    }
}

Try-acquire for nonfair reentrant locks:

final boolean tryAcquire(int acquires) {
    final Thread me = Thread.currentThread();
    int s = getState();
    if (s == 0) {
        // No owner: attempt to grab it
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(me);
            return true;
        }
        return false; // lost the race
    }
    // Reentrant acquisition
    if (me == getExclusiveOwnerThread()) {
        int next = s + acquires;
        if (next < 0) throw new Error("Hold count overflow");
        setState(next);
        return true;
    }
    return false;
}

Enqueue the current thread when the fast path fails:

private Node enqueueExclusive() {
    Node node = new Node(Thread.currentThread(), Node.EXCLUSIVE);
    for (;;) {
        Node t = tail;
        if (t == null) {
            // Initialize the queue with a dummy head
            if (casHead(new Node())) {
                tail = head;
            }
            continue;
        }
        node.prev = t;
        if (casTail(t, node)) {
            t.next = node;
            return node;
        }
    }
}

private boolean casHead(Node h) { return compareAndSetHead(h); }
private boolean casTail(Node expect, Node update) { return compareAndSetTail(expect, update); }

Wait on the queue untill the lock can be acquired:

final boolean awaitOnQueue(final Node node, int permits) {
    boolean interrupted = false;
    try {
        for (;;) {
            final Node prev = node.predecessor();
            // Only the node right after head is eligible to try acquiring
            if (prev == head && tryAcquire(permits)) {
                setHead(node);
                prev.next = null; // help GC
                return interrupted; // done; propagate interrupt status
            }
            if (readyToPark(prev, node) && parkAndFlagInterrupt()) {
                interrupted = true;
            }
        }
    } catch (Throwable t) {
        cancelAcquire(node);
        throw t;
    }
}

Parking policy and park primitive:

private static boolean readyToPark(Node pred, Node node) {
    int ps = pred.waitStatus;
    if (ps == Node.SIGNAL) return true;

    if (ps > 0) { // CANCELLED
        // Skip cancelled predecessors
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
        return false;
    }
    // Ask predecessor to signal us when it releases
    compareAndSetWaitStatus(pred, ps, Node.SIGNAL);
    return false;
}

private boolean parkAndFlagInterrupt() {
    LockSupport.park(this);
    return Thread.interrupted();
}

Only when a node’s predecessor is in SIGNAL state is it considered safe to park. Otherwise, the thread helps repair the queue’s links and retries, minimizing missed signals.

3.3.2 unlock()

Release reduces the hold count and unparks the next in line when the count reaches zero.

public void unlock() {
    sync.release(1);
}

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

tryRelease updates state and clears ownership when fully released:

protected final boolean tryRelease(int releases) {
    int s = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread()) {
        throw new IllegalMonitorStateException();
    }
    boolean free = false;
    if (s == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(s);
    return free;
}

Wake-up policy targets the successor of head (if any):

private void unparkNext(Node h) {
    // Find the first non-cancelled successor
    Node s = h.next;
    while (s != null && s.waitStatus > 0) {
        s = s.next;
    }
    if (s != null) {
        LockSupport.unpark(s.thread);
    }
}

3.3.3 Notes on nonfair acquisition

• A fast 0→1 state CAS allows new arrivals to win immediate when the lock opens, even if there are waiters.
• Only the node immediately following head competes for the lock, preserving queue discipline once contended.
• Reentrancy increments state; only when the count returns to zero does ownership clear and a successor get signaled.

3.4 FairSync

Fair mode differs at the entry point: it does not perform the initial 0→1 barge-in. Instead, it goes directly through the queued acquisition path and ensures that only the first queued thread can acquire next, preserving FIFO ordering among contenders.

4. Timed acquisition

ReentrantLock supports bounded waiting via tryLock(long, TimeUnit). Semantics: acquire with in the given time window or return false.

public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
    return sync.tryAcquireNanos(1, unit.toNanos(time));
}

Implementation sketch:

public final boolean tryAcquireNanos(int permits, long nanosTimeout)
        throws InterruptedException {
    if (Thread.interrupted()) throw new InterruptedException();
    return tryAcquire(permits) || doTimedAcquire(permits, nanosTimeout);
}

private boolean doTimedAcquire(int permits, long nanosTimeout)
        throws InterruptedException {
    long deadline = System.nanoTime() + nanosTimeout;
    final Node node = enqueueExclusive();
    boolean failed = true;
    try {
        for (;;) {
            final Node prev = node.predecessor();
            if (prev == head && tryAcquire(permits)) {
                setHead(node);
                prev.next = null;
                failed = false;
                return true;
            }
            long remaining = deadline - System.nanoTime();
            if (remaining <= 0L) return false;

            if (readyToPark(prev, node) && remaining > spinForTimeoutThreshold) {
                LockSupport.parkNanos(this, remaining);
            }
            if (Thread.interrupted()) throw new InterruptedException();
        }
    } finally {
        if (failed) cancelAcquire(node);
    }
}

The loop retries because a predecessor may not yet be in SIGNAL state, and the thread must ensure a safe parking point before sleeping for up to the remaining timeout.