CLH锁

在进行 Java 并发学习的时候发现关于锁这一涵盖性术语有太多的子概念，所以本篇博文首先对锁相关的概念进行一个简单的总结，然后讲解 AQS 的基石— CLH 锁。

术语表

• 独占锁: 确保同一时间只有一个线程可以访问共享资源，比如synchronized关键字和ReentrantLock类。
• 共享锁: 允许多个线程同时访问共享资源，以提高系统的并发性能。读写锁通常是一种共享锁，其中读锁是共享的，而写锁是独占的。
• 自旋锁: 在等待共享资源时，线程占用CPU来不停地检查共享资源是否可用，直到共享资源空闲为止。这是声称为忙等待，因为线程不会释放CPU。
• 互斥锁: 让不同的线程单独地访问共享资源。
• 读写锁: 允许多个线程同时读共享资源，但在写共享资源时只有一个线程可以执行。
• 悲观锁: 整个数据处理过程中，将数据处于锁定状态，只允许一个线程进行操作，其他线程需要等待。它基于独占锁机制，适用于对数据竞争的频率较高的情况，比如对大多数写操作的情况。使用悲观锁需要频繁的加锁和解锁，因此可能导致线程间的竞争和性能瓶颈。
• 乐观锁: 在整个数据处理过程中，不使用锁机制，甚至不考虑其他线程的存在，每个线程都可以对数据进行读写操作。在数据即将被提交时，再检查是否有其他线程修改过数据，如果没有，就将当前数据写回到数据源，如果有，则回滚事务。乐观锁可以提高并发性，减少线程的阻塞，适用于数据竞争较少的情况，比如对大多数读操作的情况。

在并发编程中，锁是一种常用的保证线程安全的方法。Java 中常用的锁主要有两类，一种是 Synchronized 修饰的锁，被称为 Java 内置锁或监视器锁。另一种就是在 J2SE 1.5版本之后的 java.util.concurrent包（下称j.u.c包）中的各类同步器，包括 ReentrantLock（可重入锁），ReentrantReadWriteLock（可重入读写锁），Semaphore（信号量），CountDownLatch 等。这些同步器都是基于 AbstractQueuedSynchronizer（下称 AQS）这个简单的框架来构建的，而 AQS 类的核心数据结构是一种名为 Craig, Landin, and Hagersten locks（下称 CLH 锁）的变体。本篇文章将详细讲解 CLH 锁这一数据结构以及 AQS 对 CLH 锁的改进。

CLH 锁是对自旋锁的一种改良。在介绍 CLH 锁前，我先简单介绍一下自旋锁。

1 自旋锁

1.1 什么是自旋锁

自旋锁是互斥锁的一种实现，Java 实现如下方所示。

public class SpinLock {
    private AtomicReference<Thread> owner = new AtomicReference<Thread>();

    public void lock() {
        Thread currentThread = Thread.currentThread();
        // 如果锁未被占用，则设置当前线程为锁的拥有者
        while (!owner.compareAndSet(null, currentThread)) {
        }
    }

    public void unlock() {
        Thread currentThread = Thread.currentThread();
        // 只有锁的拥有者才能释放锁
        owner.compareAndSet(currentThread, null);
    }
}

如代码所示，获取锁时，线程会对一个原子变量循环执行 compareAndSet 方法，直到该方法返回成功时即为成功获取锁。compareAndSet 方法底层是通用 compare-and-swap （下称 CAS）实现的。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。该操作是原子操作。原子性保证了根据最新信息计算出新值，如果与此同时值已由另一个线程更新，则写入将失败。因此，这段代码可以实现互斥锁的功能。

1.2 自旋锁缺点

自旋锁实现简单，同时避免了操作系统进程调度和线程上下文切换的开销，但他有两个缺点：

• 第一个是锁饥饿问题。在锁竞争激烈的情况下，可能存在一个线程一直被其他线程”插队“而一直获取不到锁的情况。
• 第二是性能问题。在实际的多处理上运行的自旋锁在锁竞争激烈时性能较差。

下图是引用自《多处理器编程的艺术》的 n 个线程固定地执行一段临界区所需的时间。

TASLock 和 TTASLock 与上文代码类似，都是针对一个原子状态变量轮询的自旋锁实现，最下面的曲线表示线程在没有干扰的情况下所需的时间。

显然，自旋锁的性能和理想情况相距甚远。这是因为自旋锁锁状态中心化，在竞争激烈的情况下，锁状态变更会导致多个 CPU 的高速缓存的频繁同步，从而拖慢 CPU 效率(这里涉及到 CPU 底层的一些知识，这里不再展开)。
因此自旋锁适用于锁竞争不激烈、锁持有时间短的场景。

2 CLH 锁

2.1 什么是 CLH 锁

CLH 锁是对自旋锁的一种改进，有效的解决了以上的两个缺点。首先它将线程组织成一个队列，保证先请求的线程先获得锁，避免了饥饿问题。其次锁状态去中心化，让每个线程在不同的状态变量中自旋，这样当一个线程释放它的锁时，只能使其后续线程的高速缓存失效，缩小了影响范围，从而减少了 CPU 的开销。

CLH 锁数据结构很简单，类似一个链表队列，所有请求获取锁的线程会排列在链表队列中，自旋访问队列中前一个节点的状态。当一个节点释放锁时，只有它的后一个节点才可以得到锁。CLH 锁本身有一个队尾指针 Tail，它是一个原子变量，指向队列最末端的 CLH 节点。每一个 CLH 节点有两个属性：所代表的线程和标识是否持有锁的状态变量。当一个线程要获取锁时，它会对 Tail 进行一个 getAndSet 的原子操作。该操作会返回 Tail 当前指向的节点，也就是当前队尾节点，然后使 Tail 指向这个线程对应的 CLH 节点，成为新的队尾节点。入队成功后，该线程会轮询上一个队尾节点的状态变量，当上一个节点释放锁后，它将得到这个锁。

下面用图来展示 CLH 锁从获取到释放锁的全过程。

1. CLH 锁初始化时会 Tail 会指向一个状态为 false 的空节点，如图1所示。
2. 当 Thread 1（下称 T1）请求获取锁时，Tail 节点指向 T1 对应的节点，同时返回空节点。T1 检查到上一个节点状态为 false，就成功获取到锁，可以执行相应的逻辑了，如图2所示。
3. 当 Thread 2（下称 T2）请求获取锁时，Tail 节点指向 T2 对应的节点，同时返回 T1 对应的节点。T2检查到上一个节点状态为 True，无法获取到锁，于是开始轮询上一个节点的状态，如图3所示。
4. 当 T1 释放锁时，会将状态变量置为 False，如图4所示。
5. T2 轮询到检查到上一个节点状态变为 False，则获取锁成功，如图5所示。

2.2 CLH 锁 Java 实现解析

通过上面的图形象的展示了 CLH 的数据结构以及初始化、获取、释放锁的全过程，便于大家理解 CLH 锁的原理。但是就算理解了原理，也不一定能够实现一个线程安全的 CLH 互斥锁。在并发编程领域，“细节是魔鬼”这一格言同样适用。下面将解读 CLH 锁 Java 实现源码并分享并发编程的一些细节。

代码如图所示，有三个地方需要关注，上图已用红框标记：

1、节点中的状态变量为什么用 volatile 修饰？可以不用 volatile 吗？
使用 volatile 修饰状态变量不是为了利用 volatile 的内存可见性，因为这个状态变量只会被持有该状态变量的线程写入，只会被队列中该线程的后驱节点对应的线程读，而且后者会轮询读取。因此，可见性问题不会影响锁的正确性。以上面的例子为例，T2 会不断轮询T1的状态变量，T1 将它的状态变更为 False 时 T2 没有立即感知也没有关系。该状态变量最终会写回内存并被 T2 终感知到变更后的值。

但要实现一个可以在多线程程序中正确执行的锁，还需要解决重排序问题。在《Java 并发编程实战》一书对于重排序问题是这么描述的：在没有同步的情况下，编译器、处理器以及运行时等都可能对操作的执行顺序进行一些意想不到的调整。在缺乏足够同步的多线程程序中，要想对内存操作的执行顺序进行判断，几乎无法得到正确的结论。对于 Java synchronized 关键字提供的内置锁(又叫监视器)，Java Memory Model（下称 JMM）规范中有一条 Happens-Before（先行发生）规则：“一个监视器锁上的解锁发生在该监视器锁的后续锁定之前”，因此 JVM 会保证这条规则成立。

而自定义互斥锁就需要自己保证这一规则的成立，因此上述代码通过 volatile 的 Happens-Before（先行发生）规则来解决重排序问题。JMM 的 Happens-Before（先行发生）规则有一条针对 volatile 关键字的规则：“volatile 变量的写操作发生在该变量的后续读之前”。

2、CLH 锁是一个链表队列，为什么 Node 节点没有指向前驱或后继指针呢？

CLH 锁是一种隐式的链表队列，没有显式的维护前驱或后继指针。因为每个等待获取锁的线程只需要轮询前一个节点的状态就够了，而不需要遍历整个队列。在这种情况下，只需要使用一个局部变量保存前驱节点，而不需要显式的维护前驱或后继指针。

3、this.node.set(new Node()) 这行代码有何意义？

如果没有这行代码，Node 可能被复用，导致死锁，如下图所示：

1. 一开始，T1 持有锁，T2 自旋等待，如图1开始。
2. 当 T1 释放锁（设置为 false），但此时 T2 尚未抢占到锁，如图2所示。
3. 此时如果 T1 再次调用 lock()请求获取锁，会将状态设为 True，同时自旋等待 T2 释放锁。而T2也自旋等待前驱节点状态变为 False，这样就造成了死锁，如图3所示。

因此需要这行代码生成新的 Node 节点，避免 Node 节点复用带来的死锁。

2.3 CLH 优缺点分析

CLH 锁作为自旋锁的改进，有以下几个优点：

1. 性能优异，获取和释放锁开销小。CLH 的锁状态不再是单一的原子变量，而是分散在每个节点的状态中，降低了自旋锁在竞争激烈时频繁同步的开销。在释放锁的开销也因为不需要使用 CAS 指令而降低了。
2. 公平锁。先入队的线程会先得到锁。
3. 实现简单，易于理解。
4. 扩展性强。下面会提到 AQS 如何扩展 CLH 锁实现了 j.u.c 包下各类丰富的同步器。

当然，它也有两个缺点：第一是因为有自旋操作，当锁持有时间长时会带来较大的 CPU 开销。第二是基本的 CLH 锁功能单一，不改造不能支持复杂的功能。

3.处理器架构下的CLH

3.1 SMP（对称多处理器架构）

• SMP(Symmetric Multi-Processor)，即对称多处理器结构，指服务器中多个CPU对称工作，每个CPU访问内存地址所需时间相同。其主要特征是共享，包含对CPU，内存，I/O等进行共享。

• SMP优点是能够保证内存一致性，缺点是这些共享的资源很可能成为性能瓶颈，随着CPU数量的增加，每个CPU都要访问相同的内存资源，可能导致内存访问冲突，可能会导致CPU资源的浪费。常用的PC机就属于这种。

3.2 NUMA（非一致性内存访问）

• NUMA(Non-Uniform Memory Access)非一致存储访问， 将CPU分为CPU模块，每个CPU模块由多个CPU组成， 并且具有独立的本地内存、 I/O 槽口等，模块之间可以通过互联模块相互访问 ，访问本地内存的速度将远远高于访问远地内存 ( 系统内其它节点的内存 ) 的速度，这也是非一致存储访问 NUMA 的由来。

• NUMA优点是可以较好地解决原来SMP系统的扩展问题，缺点是由于访问远程内存的延时远远超过本地内存，因此当CPU数量增加时，系统性能无法线性增加。

3.3 CLH锁分析

• 在SMP架构下，CLH更具有优势。
• 在NUMA架构下，如果当前节点与前驱节点不在同一CPU模块下，跨CPU模块会带来额外的系统开销，而MCS锁更适用于NUMA架构。

4 AQS 对 CLH 队列锁的改造

针对 CLH 的缺点，AQS 对 CLH 队列锁进行了一定的改造。

• 针对第一个缺点，AQS 将自旋操作改为阻塞线程操作

• 针对第二个缺点，AQS 对 CLH 锁进行改造和扩展，原作者 Doug Lea 称之为“CLH 锁的变体”。下面将详细讲 AQS 底层细节以及对 CLH 锁的改进。AQS 中的对 CLH 锁数据结构的改进主要包括三方面：扩展每个节点的状态、显式的维护前驱节点和后继节点以及诸如出队节点显式设为 null 等辅助 GC 的优化。正是这些改进使 AQS 可以支撑 j.u.c 丰富多彩的同步器实现。

4.1 扩展每个节点的状态

AQS 每个节点的状态如下所示，在源码中如下所示：

volatile int waitStatus;

AQS 同样提供了该状态变量的原子读写操作，但和同步器状态不同的是，节点状态在 AQS 中被清晰的定义，如下表所示：

状态名	描述
SIGNAL	表示该节点正常等待
PROPAGATE	应将 releaseShared 传播到其他节点
CONDITION	该节点位于条件队列，不能用于同步队列节点
CANCELLED	由于超时、中断或其他原因，该节点被取消

4.2 显式的维护前驱节点和后继节点

上文我们提到在原始版本的 CLH 锁中，节点间甚至都没有互相链接。但是，通过在节点中显式地维护前驱节点，CLH 锁就可以处理“超时”和各种形式的“取消”：如果一个节点的前驱节点取消了，这个节点就可以滑动去使用前面一个节点的状态字段。对于通过自旋获取锁的 CLH 锁来说，只需要显式的维护前驱节点就可以实现取消功能，如下图所示：

但是在 AQS 的实现稍有不同。因为 AQS 用阻塞等待替换了自旋操作，线程会阻塞等待锁的释放，不能主动感知到前驱节点状态变化的信息。AQS 中显式的维护前驱节点和后继节点，需要释放锁的节点会显式通知下一个节点解除阻塞，如下图所示，T1 释放锁后主动唤醒 T2，使 T2 检测到锁已释放，获取锁成功。

其中需要关注的一个细节是：由于没有针对双向链表节点的类似 compareAndSet 的原子性无锁插入指令，因此后驱节点的设置并非作为原子性插入操作的一部分，而仅是在节点被插入后简单地赋值。在释放锁时，如果当前节点的后驱节点不可用时，将从利用队尾指针 Tail 从尾部遍历到直到找到当前节点正确的后驱节点。

4.3 辅助 GC

JVM 的垃圾回收机制使开发者无需手动释放对象。但在 AQS 中需要在释放锁时显式的设置为 null，避免引用的残留，辅助垃圾回收。

5 CLH锁参考代码注释

// CLHLock.java

import java.util.concurrent.atomic.AtomicReference;

public class CLHLock {
    /**
     * CLH锁节点
     */
    private static class CLHNode {
        // 锁状态：默认为false，表示线程没有获取到锁；true表示线程获取到锁或正在等待
        // 为了保证locked状态是线程间可见的，因此用volatile关键字修饰
        volatile boolean locked = false;
    }
    // 尾结点，总是指向最后一个CLHNode节点
    // 【注意】这里用了java的原子系列之AtomicReference，能保证原子更新
    private final AtomicReference<CLHNode> tailNode;
    // 当前节点的前继节点
    private final ThreadLocal<CLHNode> predNode;
    // 当前节点
    private final ThreadLocal<CLHNode> curNode;

    // CLHLock构造函数，用于新建CLH锁节点时做一些初始化逻辑
    public CLHLock() {
        // 初始化时尾结点指向一个空的CLH节点
        tailNode = new AtomicReference<>(new CLHNode());
        // 初始化当前的CLH节点
        curNode = new ThreadLocal() {
            @Override
            protected CLHNode initialValue() {
                return new CLHNode();
            }
        };
        // 初始化前继节点，注意此时前继节点没有存储CLHNode对象，存储的是null
        predNode = new ThreadLocal();
    }

    /**
     * 获取锁
     */
    public void lock() {
        // 取出当前线程ThreadLocal存储的当前节点，初始化值总是一个新建的CLHNode，locked状态为false。
        CLHNode currNode = curNode.get();
        // 此时把lock状态置为true，表示一个有效状态，
        // 即获取到了锁或正在等待锁的状态
        currNode.locked = true;
        // 当一个线程到来时，总是将尾结点取出来赋值给当前线程的前继节点；
        // 然后再把当前线程的当前节点赋值给尾节点
        // 【注意】在多线程并发情况下，这里通过AtomicReference类能防止并发问题
        // 【注意】哪个线程先执行到这里就会先执行predNode.set(preNode);语句，因此构建了一条逻辑线程等待链
        // 这条链避免了线程饥饿现象发生
        CLHNode preNode = tailNode.getAndSet(currNode);
        // 将刚获取的尾结点（前一线程的当前节点）付给当前线程的前继节点ThreadLocal
        // 【思考】这句代码也可以去掉吗，如果去掉有影响吗？
        predNode.set(preNode);
        // 【1】若前继节点的locked状态为false，则表示获取到了锁，不用自旋等待；
        // 【2】若前继节点的locked状态为true，则表示前一线程获取到了锁或者正在等待，自旋等待
        while (preNode.locked) {
            System.out.println("线程" + Thread.currentThread().getName() + "没能获取到锁，进行自旋等待。。。");
        }
        // 能执行到这里，说明当前线程获取到了锁
        System.out.println("线程" + Thread.currentThread().getName() + "获取到了锁！！！");
    }

    /**
     * 释放锁
     */
    public void unLock() {
        // 获取当前线程的当前节点
        CLHNode node = curNode.get();
        // 进行解锁操作
        // 这里将locked至为false，此时执行了lock方法正在自旋等待的后继节点将会获取到锁
        // 【注意】而不是所有正在自旋等待的线程去并发竞争锁
        node.locked = false;
        System.out.println("线程" + Thread.currentThread().getName() + "释放了锁！！！");
        // 如果没有这行代码，Node 可能被复用，导致死锁
        CLHNode newCurNode = new CLHNode();
        curNode.set(newCurNode);

        // 【优化】能提高GC效率和节省内存空间
        // curNode.set(predNode.get());
    }
}

6 小结

Java AQS 是 Java 并发中重要的一部分，但作为一个抽象的并发同步框架，源代码比较晦涩，不利于阅读和学习。本篇文章从自旋锁出发，详细介绍了 CLH 锁及 AQS 对 CLH 的改造，尽量使用丰富的图展示相关的数据结构，避免引用晦涩难懂的 Java 源码，希望对大家理解 AQS 原理和正确使用 j.u.c 下各类同步器有帮助。

参考

• https://mp.weixin.qq.com/s/jEx-4XhNGOFdCo4Nou5tqg
• https://juejin.cn/post/6981431787746492447
• https://juejin.cn/post/6981431787746492447
• https://blog.csdn.net/weixin_47184173/article/details/115340014