Understanding and Implementing the CLH Lock in Java (JDK 1.8 Source Code Analysis)

1 What are spin lock and mutex lock?

A spin lock is a type of mutex where a thread that fails to acquire the lock continuously spins (busy‑waiting) instead of sleeping, wasting CPU cycles; it is suitable for short lock hold times. A traditional mutex puts the thread to sleep (sleep‑waiting) when it cannot acquire the lock, which is better for longer lock hold times because it avoids costly context switches.

2 What is the CLH lock?

The CLH lock is a fair, queue‑based spin lock invented by Craig, Landin and Hagersten. It builds a logical queue of waiting threads, ensuring first‑come‑first‑served ordering.

The basic principle:

The tail node pointer constructs the waiting queue, guaranteeing fairness; the tail pointer is an atomic reference to ensure thread‑safety.

Each thread spins on a variable in its own node that is set by its predecessor, ensuring that only the immediate predecessor’s state is examined.

This abstract description will be clarified step‑by‑step later.

3 Why study the CLH lock?

The CLH lock underpins Java's AbstractQueuedSynchronizer (AQS), which is the core of the java.util.concurrent package. Mastering the CLH lock is essential for understanding AQS and, consequently, Java concurrency programming.

4 CLH lock detailed implementation

Below is the source code of the CLH lock with explanatory comments.

public class CLHLock {
    /** CLH lock node */
    private static class CLHNode {
        // lock state: false = not locked, true = locked or waiting
        volatile boolean locked = false;
    }
    // Tail node always points to the last CLHNode
    private final AtomicReference
tailNode;
    // Thread‑local references to predecessor and current nodes
    private final ThreadLocal
predNode;
    private final ThreadLocal
curNode;

    public CLHLock() {
        // Initialize tail to a dummy node
        tailNode = new AtomicReference<>(new CLHNode());
        // Initialize thread‑local current node
        curNode = new ThreadLocal
() {
            @Override
            protected CLHNode initialValue() {
                return new CLHNode();
            }
        };
        // Predecessor node starts as null
        predNode = new ThreadLocal<>();
    }

    /** Acquire lock */
    public void lock() {
        CLHNode currNode = curNode.get();
        currNode.locked = true; // mark as waiting/locked
        // Atomically swap tail and obtain predecessor
        CLHNode preNode = tailNode.getAndSet(currNode);
        predNode.set(preNode);
        // Spin while predecessor holds the lock
        while (preNode.locked) {
            try { Thread.sleep(1000); } catch (Exception e) {}
            System.out.println("Thread " + Thread.currentThread().getName() + " is spinning...");
        }
        System.out.println("Thread " + Thread.currentThread().getName() + " acquired the lock!");
    }

    /** Release lock */
    public void unLock() {
        CLHNode node = curNode.get();
        node.locked = false; // release
        System.out.println("Thread " + Thread.currentThread().getName() + " released the lock!");
        // Create a fresh node for the next lock acquisition
        CLHNode newCurNode = new CLHNode();
        curNode.set(newCurNode);
        // Optional optimization: curNode.set(predNode.get());
    }
}

4.1 Initialization logic

The constructor creates a dummy tail node and a thread‑local current node whose locked field is initially false . The predecessor node is initially null .

4.2 Lock acquisition process

When a thread calls lock() :

It obtains its thread‑local current node (initially unlocked).

Sets locked = true to indicate it is trying to acquire the lock.

Atomically swaps the tail pointer, receiving the previous node as its predecessor.

Spins on preNode.locked until the predecessor releases the lock.

Because each thread only watches its immediate predecessor, the lock is fair and avoids the thundering herd problem.

4.3 Unlock process

When unLock() is invoked, the thread sets its current node’s locked flag to false , allowing the next waiting thread to proceed. It then creates a fresh node and stores it in the thread‑local curNode to break the link with the old node, which helps garbage collection and prevents a thread from re‑entering the lock with a stale node.

4.4 Re‑acquiring the lock in the same thread

If the fresh node were not created, the same thread would see its predecessor’s locked flag still set to true on the next lock() call, causing an endless spin. The new node resets the state, allowing the thread to acquire the lock again.

4.5 Handling the edge case where the new node creation is omitted

Omitting the creation of a new CLHNode in unLock() leaves the thread’s current node linked as its own predecessor. On the subsequent lock() , the thread will spin forever because preNode.locked remains true . This demonstrates why the node reset is essential.

5 Testing the CLH lock

A simple demo spawns multiple threads that increment a shared counter under the CLH lock. The final counter value matches the expected total, confirming the lock’s correctness even with hundreds of concurrent threads.

public class CLHLockTest {
    private static int cnt = 0;
    public static void main(String[] args) throws Exception {
        final CLHLock lock = new CLHLock();
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                lock.lock();
                cnt++;
                lock.unLock();
            }).start();
        }
        Thread.sleep(10000); // wait for all threads
        System.out.println("cnt >>> " + cnt);
    }
}

The test shows no lost updates, proving that the CLH lock provides proper mutual exclusion.

6 Summary

Introduced spin locks and mutex locks and their trade‑offs.

Explained what a CLH lock is and why it matters for Java concurrency.

Walked through the CLH lock’s implementation, initialization, lock and unlock logic, and demonstrated its correctness with a multithreaded test, laying a solid foundation for studying AQS.