What are spinlocks and mutex?

Since A CLH lock is a spin lock, let’s first look at what a spin lock is.

A spin lock is also a mutex, except that the thread that has not captured the lock spins and waits for the lock to be released. In this state, the thread that is waiting for the lock does not go to sleep, but is busy waiting for the lock to waste CPU cycles. Therefore, spin locks are suitable for short lock occupancy.

We talked about spin locks, but we also talked about mutex. The mutex here refers to the traditional mutex, that is, when multiple threads concurrently compete for the lock, the thread that does not grab the lock will enter the sleep state, namely sleep-waiting. When the lock is released, the thread in the sleep state will acquire the lock again. The downside is that these procedures require thread switching, many CPU instructions to execute, and also time. If the CPU takes longer to perform thread switches than the lock takes, it might be better to use a spin lock. Therefore, mutex is suitable for situations where the lock is held for a long time.

2 What is CLH lock?

CLH lock is actually a spin fair lock based on logical queue non-thread hunger, due to the invention of Craig, Landin and Hagersten, so named CLH lock.

CLH locking works as follows:

  1. First, there is a tail node pointer, through this tail node pointer to build the logical queue waiting for threads, so it can ensure the fairness of thread thread first-come-first-served, so the tail pointer can be said to be the bridge to build the logical queue; In addition, the tail node pointer is an atomic reference type, which avoids the thread-safety problem of multithreaded concurrent operations.
  2. By each thread waiting on the lock spinning waits on one of its own variables, which will be written by the previous thread. Since a thread always obtains a variable written by the previous thread through the tail node pointer, and the tail node pointer is of atomic reference type, this ensures that this variable is always thread-safe.

It’s ok. We can have a concept in our mind. Later we will thoroughly understand CLH lock step by step.

3 why learn CLH locking?

Ok, so now that we have an idea of CLH locking, why should we learn CLH locking?

Study AQS source partners should know that AQS is the core of JUC, and CLH lock is the basis of AQS, said that the core is not too much, because AQS is using a variant of CLH lock. If you want to learn Java concurrent programming, you must learn JUC; To learn JUC well, one must learn AQS well first. If you learn AQS well, you must learn CLH well first. So, that’s why we learn about CLH locking.

4 CLH lock details

So, let’s first look at the CLH lock implementation code, and then through a step-by-step diagram to explain the CLH lock.

// CLHLock.java

public class CLHLock {
    /** * CLH locks nodes */
    private static class CLHNode {
        // Lock status: The default value is false, indicating that the thread has not acquired the lock. True indicates that the thread has acquired the lock or is waiting
        To ensure that locked states are visible between threads, the volatile keyword is used
        volatile boolean locked = false;
    }
    // The last CLHNode
    // [note] We use Java's AtomicReference to ensure that the atom is updated
    private final AtomicReference<CLHNode> tailNode;
    // The successor of the current node
    private final ThreadLocal<CLHNode> predNode;
    // The current node
    private final ThreadLocal<CLHNode> curNode;

    // CLHLock constructor, used to do some initialization logic when creating a new CLH lock node
    public CLHLock(a) {
        // The endpoint points to an empty CLH node during initialization
        tailNode = new AtomicReference<>(new CLHNode());
        // Initialize the current CLH node
        curNode = new ThreadLocal() {
            @Override
            protected CLHNode initialValue(a) {
                return newCLHNode(); }};// Initialize the predecessor node. Note that the predecessor node does not store the CLHNode object, but stores null
        predNode = new ThreadLocal();
    }

    /** * get lock */
    public void lock(a) {
        // Fetch the current node stored by the current thread ThreadLocal. The initial value is always a new CLHNode, and the state is false.
        CLHNode currNode = curNode.get();
        // Set the lock state to true, indicating a valid state.
        // The lock has been acquired or is waiting for the lock
        currNode.locked = true;
        // When a thread arrives, the end node is always taken out and assigned to the successor node of the current thread;
        // Then assign the current node of the current thread to the tail node
        // [note] In the case of multi-threaded concurrency, the AtomicReference class can be used to prevent concurrency problems
        Prednode. set(preNode); Statement, so a logical thread wait chain is built
        // This chain prevents thread starvation
        CLHNode preNode = tailNode.getAndSet(currNode);
        // Pay the newly acquired tail (the current node of the previous thread) to the predecessor ThreadLocal of the current thread
        // [thinking] Can this code also be removed, if removed, will it affect?
        predNode.set(preNode);
        [1] If the precursor nodes are in locked state false, the lock is acquired, and spin wait is not required.
        [2] If the precursor node is in locked state true, the previous thread has acquired the lock or is waiting, spin waiting
        while (preNode.locked) {
            System.out.println("Thread" + Thread.currentThread().getName() + "Failed to acquire lock, spin wait...");
        }
        // The current thread has acquired the lock
        System.out.println("Thread" + Thread.currentThread().getName() + "Lock obtained!!");
    }

    /** * release lock */
    public void unLock(a) {
        // Get the current node of the current thread
        CLHNode node = curNode.get();
        // Perform the unlocking operation
        // This will be locked to false, and subsequent nodes that have performed the lock method and are waiting on spin will acquire the lock
        // Instead of all spinning waiting threads competing for the lock concurrently
        node.locked = false;
        System.out.println("Thread" + Thread.currentThread().getName() + "Lock released!!");
        // What is the function of the following two lines of code?
        CLHNode newCurNode = new CLHNode();
        curNode.set(newCurNode);

        // [optimization] can improve GC efficiency and save memory space, please consider: why?
        // curNode.set(predNode.get());}}Copy the code

4.1 Initialization logic of CLH lock

CLH lock initialization logic:

  1. Defines aCLHNodeNode, there’s one in therelockedProperty indicating whether the thread has acquired the lock. The default isfalse.falseThe thread does not acquire the lock or has released the lock.trueIndicates that the thread has acquired the lock or is waiting at spin.

Note that to ensure that the locked attribute is visible between threads, it is decorated with volatile.

  1. CLHLockThere are three important Pointers to the tail node of the member variabletailNode, the predecessor node of the current threadpreNodeAnd the current nodecurNode. Among themtailNodeisAtomicReferenceType to ensure thread-safety of the tail node; In addition,preNodeandcurNodeAre allThreadLocalType is the thread-local variable type used to hold the precursor of each threadCLHNodeAnd the currentCLHNodeNode.
  2. The important thing is that we build a new oneCLHLockObject, at which point the initialization logic in the constructor is executed. The tail pointer is given at this pointtailNodeAnd the current nodecurNodeInitialize onelockedThe status offalsetheCLHNodeNode, at this time the predecessor nodepreNodeThe store isnull.

4.2 CLH lock locking process

CLH lock (CLH) lock (CLH) lock (CLH)

// CLHLock.java

/** * get lock */
public void lock(a) {
    // Fetch the current node stored by the current thread ThreadLocal. The initial value is always a new CLHNode, and the state is false.
    CLHNode currNode = curNode.get();
    // Set the lock state to true, indicating a valid state.
    // The lock has been acquired or is waiting for the lock
    currNode.locked = true;
    // When a thread arrives, the end node is always taken out and assigned to the successor node of the current thread;
    // Then assign the current node of the current thread to the tail node
    // [note] In the case of multi-threaded concurrency, the AtomicReference class can be used to prevent concurrency problems
    Prednode. set(preNode); Statement, so a logical thread wait chain is built
    // This chain prevents thread starvation
    CLHNode preNode = tailNode.getAndSet(currNode);
    // Pay the newly acquired tail (the current node of the previous thread) to the predecessor ThreadLocal of the current thread
    // [thinking] Can this code also be removed, if removed, will it affect?
    predNode.set(preNode);
    [1] If the precursor nodes are in locked state false, the lock is acquired, and spin wait is not required.
    [2] If the precursor node is in locked state true, the previous thread has acquired the lock or is waiting, spin waiting
    while (preNode.locked) {
        try {
            Thread.sleep(1000);
        } catch (Exception e) {

        }
        System.out.println("Thread" + Thread.currentThread().getName() + "Failed to acquire lock, spin wait...");
    }
    // The current thread has acquired the lock
    System.out.println("Thread" + Thread.currentThread().getName() + "Lock obtained!!");
}
Copy the code

Although the code has been commented in detail, we can still trace the thread locking process:

  1. First get the current node of the current threadcurNodeI get it every timeCLHNodeThe node’slockedState isfalse;
  2. And then put the currentCLHNodeThe node’slockedThe state is assigned totrue, represents a valid state of the current thread, that is, the state that has acquired the lock or is waiting for the lock;
  3. Because the tail pointertailNodeIs always pointing to the previous threadCLHNodeNode, so we use the tail pointer heretailNodeFetch the value of the previous threadCLHNodeNode, which is then assigned to the predecessor node of the current threadpredNodeAnd repoints the tail pointer to the last node, the current of the current threadCLHNodeNode to be used when the next thread arrives;
  4. According to the preceding node (the previous thread)lockedState judgment, iflockedforfalse, it means that the previous thread released the lock, the current thread can obtain the lock, no spin wait; If the precursor node is in locked state true, the previous thread has acquired the lock or is waiting, spin waiting.

To make it easier to understand, let’s use an illustration.

ThreadA <–threadB<–threadC<–threadD if there are four concurrent threads executing the lock operation at the same time

In the first step, thread A comes in, performs the lock operation, obtains the lock, and the locked state is true, as shown below:

The second stepThread B comes and performs the lock operation. Since thread A has not released the lock, the spin waits.lockedState fortrue, as shown below: The third step, thread C comes and performs the lock operation. Since thread B is in spin wait, thread C is also in spin wait (so CLH lock is fair lock).lockedState fortrue, as shown below: The fourth step, thread D comes and performs the lock operation. Since thread C is in spin wait, thread D is also in spin wait.lockedState fortrue, as shown below:

If the current thread determines that the previous thread is in locked state (true), then the previous thread is either holding the lock or is in spin wait, and therefore must spin wait itself. The tailNode always points to the CLHNode node of the last thread.

4.3 CLH lock release process

CLH lock locking process, so, what is the process of CLH lock release? Again, let’s first post the lock release code:

// CLHLock.java

/** * release lock */
public void unLock(a) {
    // Get the current node of the current thread
    CLHNode node = curNode.get();
    // Perform the unlocking operation
    // This will be locked to false, and subsequent nodes that have performed the lock method and are waiting on spin will acquire the lock
    // Instead of all spinning waiting threads competing for the lock concurrently
    node.locked = false;
    System.out.println("Thread" + Thread.currentThread().getName() + "Lock released!!");
    // What is the function of the following two lines of code?
    CLHNode newCurNode = new CLHNode();
    curNode.set(newCurNode);

    // [optimization] can improve GC efficiency and save memory space, please consider: why?
    // curNode.set(predNode.get());
}
Copy the code

CLH lock release code is much simpler than CLH lock release code.

  1. The current is first fetched from the thread-local variable of the current threadCLHNodeNode, and thisCLHNodeThe node is followed by a threadpreNodeThe variable points to;
  2. thenlockedState tofalseThe lock is released;

Note that while locked, which is modified by the volitile keyword, is false for the local variables preNode.locked for the subsequent spin waiting threads, the spin waiting threads end the while loop and acquire the lock. This process also happens asynchronously.

  1. The thread-local variable representing the current node of the current thread is then reassigned to a new oneCLHNode.

Think: This step may seem redundant, but it’s not. Why do you do that? We’ll talk more about that later.

Let’s still use A diagram to illustrate the CLH lock release scenario, followed by the previous four threads lock scenario, suppose that after the four threads lock, thread A starts to release the lock, at this time thread B obtains the lock, ends the spin wait, then thread C and thread D still spin wait, as shown below:Similarly, thread B releases the lock in a similar way, which is not described here.

4.4 Consider the situation that the same thread locks and releases the lock and obtains the lock normally again

In the previous section 4.3, there are two lines of code in the unLock method:

  CLHNode newCurNode = new CLHNode();
  curNode.set(newCurNode);
Copy the code

What do these two lines of code do? Without these two lines of code, if the same thread locks, releases the lock, and then performs the lock again, the thread would fall into a spin wait state. This is why, may be some of the partners did not understand, the strength is also made quite a long time to figure out, hey hey.

Let’s also analyze the functions of these two lines of code in the form of a step by step diagram. Consider A scenario where thread A acquires the lock, releases the lock, and acquires the lock again.

The first step:Thread A performs the lock operation and obtains the lock, as shown below:

In the lock operation above, thread A’s current CLHNode is set to True. The tailNode pointer then points to the current node of the current thread; Finally, because the precursor node is in locked false, no spin wait is required, so the lock is acquired.

The second step:Thread A has performed an unLock operation to release the lock, as shown below:

In the lock release operation, thread A’s current CLHNode status is set to False, indicating that the lock is released. A new CLHNode node, newCurNode, is created, and the thread local variable value of the current node of thread A is redirected to the newCurNode node object.

Step 3: Thread A performs the lock operation again to regain the lock, as shown below:

In this example, thread A’s CLHNode is locked to True. The tailNode pointer is used to retrieve the ancestor node (the curNode object in step 1 and step 2), and the value of the local variable of the ancestor node thread of thread A is redirected to the curNode object. The tailNode tail pointer then repoints to the newly created CLHNode newCurNode object. Finally, because the precursor node is in locked false, no spin wait is required, so the lock is acquired.

Extension: Notice that the preNode object in the above image has no references at this time, so it will be removed by GC next time. This is done by creating A new CLHNode object, newCurNode, each time you unLock, and then repointing the thread local variable value of the current node of thread A to newCurNode. Curnode.set (prednode.get ()); This code is optimized to improve GC efficiency and save memory space.

4.5 Consider the case that the same thread adds the lock and releases the lock again

Now let’s call CLHNode newCurNode = new CLHNode(); And curNode. Set (newCurNode); The two lines of code are commented out to look like this:

// CLHLock.java

public void unLock(a) {
    CLHNode node = curNode.get();
    node.locked = false;
    System.out.println("Thread" + Thread.currentThread().getName() + "Lock released!!");
    /*CLHNode newCurNode = new CLHNode(); curNode.set(newCurNode); * /
}
Copy the code

So the result is that thread A gets the lock, releases the lock, and then gets the lock again and then goes into spin wait. Why is that? Let’s break it down.

The first step:Thread A performs the lock operation and obtains the lock, as shown below:

In the lock operation above, thread A’s current CLHNode is set to True. The tailNode pointer then points to the current node of the current thread; Finally, because the precursor node is in locked false, no spin wait is required, so the lock is acquired. There is nothing unusual about this step.

Step 2: Thread A performs an unLock operation and releases the lock.

And now we haveunLockmethodsCLHNode newCurNode = new CLHNode();andcurNode.set(newCurNode);These two lines of code are commented out, so the change above is the current thread ACLHNodeThe node’slockedState tofalseThat is! Can be.

Step 3:Thread A performs the lock operation again, and then falls into A state of constant spin waiting, as shown below:The lock is acquired again by thread A in the figure abovelockMethod each line of code is analyzed, knowing that while the second step will be thread A’s currentCLHNodethelockedState tofalseBut in the third step, thread A acquires the lock againCLHNodethelockedThe state is set to zero againtrueAnd tail pointertailNodeIt’s still pointing to the current current of thread ACLHNodeNode. And because it’s always going to be the tail pointertailNodePoint to theCLHNodeThe node is pulled out to predispose the current threadCLHNodeNode, and then executewhile(predNode.locked) {}Statement, at this time becausepredNode.locked = true, so thread A spins and waits forever.

5 Test CLH locks

Here’s a Demo to test the CLH lock implemented in the previous code:

// CLHLockTest.java

/** * to test that CLHLocke does not work ** define a static member variable CNT, and then start 10 threads to run to see if there are thread safety issues */
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();
        }
        // Let the main thread sleep for 10 seconds to ensure that all other threads have finished executing
        Thread.sleep(10000);
        System.out.println();
        System.out.println("cnt----------->>>"+ cnt); }}Copy the code

Screenshots of the running results are attached below:

PS: Only 10 threads are open here to capture the full picture. After the strength of the test, open 100 threads, 1000 threads will not exist thread safety problems.

6 summary

CLH lock: CLH lock: CLH lock: CLH lock: CLH lock

  1. First we learned the concept and difference between spin locks and mutex;
  2. Then we learned what CLH locks are and why;
  3. Finally, we learn the principle of CLH lock by way of graphic + code implementation, so as to lay a solid foundation for learning the AQS behind.