🏆【算法数据结构专题】「线程锁算法专项」初探 CLH 队列锁机制原理分析

技术扩展

SMP（对称多处理器架构）

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

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

NUMA（非一致性内存访问）

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

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

自旋锁和互斥锁

CLH 锁是一种自旋锁，那么我们先来看看自旋锁是什么？

自旋锁

• 自旋锁说白了也是一种互斥锁，只不过没有抢到锁的线程会一直自旋等待锁的释放，处于 busy-waiting 的状态，此时等待锁的线程不会进入休眠状态，而是一直忙等待浪费 CPU 周期。

• 因此自旋锁适用于锁占用时间短的场合。

互斥锁

• 互斥锁说的是传统意义的互斥锁，就是多个线程并发竞争锁的时候，没有抢到锁的线程会进入休眠状态即【sleep-waiting】，当锁被释放时候，处于休眠状态的一个线程会再次获取到锁。

• 缺点：就是这一些列过程需要线程切换，需要执行很多 CPU 指令，同样需要时间。如果 CPU 执行线程切换的时间比锁占用的时间还长，那么可能还不如使用自旋锁。因此互斥锁适用于锁占用时间长的场合。

CLH 锁机制

CLH 锁其实就是一种是基于逻辑队列非线程饥饿的一种自旋公平锁，由于是 Craig、Landin 和 Hagersten 三位大佬的发明，因此命名为 CLH 锁，CLH 是一种基于单向链表的高性能、能确保无饥饿性，提供先来先服务公平性的自旋锁。

• 申请加锁的线程通过前驱节点的变量进行自旋。

• 前置节点解锁后，当前节点会结束自旋，并进行加锁。

CLH 节点模型

• CLH 队列中的结点 QNode 中含有一个 locked 字段，该字段若为 true 表示该线程需要获取锁，且不释放锁，为 false 表示线程释放了锁。

• 结点之间是通过隐形的链表相连，之所以叫隐形的链表是因为这些结点之间没有明显的 next 指针，而是通过 myPred 所指向的结点的变化情况来影响 myNode 的行为。

CLH 锁原理

• 首先有一个尾节点指针，通过这个尾结点指针来构建等待线程的逻辑队列，因此能确保线程线程先到先服务的公平性，因此尾指针可以说是构建逻辑队列的桥梁；

• 此外这个尾节点指针是原子引用类型，避免了多线程并发操作的线程安全性问题；

• 通过等待锁的每个线程在自己的某个变量上自旋等待，这个变量将由前一个线程写入。

• 由于某个线程获取锁操作时总是通过尾节点指针获取到前一线程写入的变量，而尾节点指针又是原子引用类型，因此确保了这个变量获取出来总是线程安全的。

CLH 锁分析

• 在 SMP 架构下，CLH 更具有优势。

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

加锁逻辑

1. 获取当前线程的锁节点，如果为空，则进行初始化；

2. sync 方法获取链表的尾节点，并将当前节点置为尾节点，此时原来的尾节点为当前节点的前置节点。

3. 如果尾节点为空，表示当前节点是第一个节点，直接加锁成功。

4. 如果尾节点不为空，则基于前置节点的锁值（locked==true）进行自旋，直到前置节点的锁值变为 false。

解锁逻辑

1. 获取当前线程对应的锁节点，如果节点为空或者锁值为 false，则无需解锁，直接返回；

2. 【sync 方法为尾节点赋空值，赋值不成功表示当前节点不是尾节点，则需要将当前节点的 locked=false 解锁节点】。如果当前节点是尾节点，则无需为该节点设置。

CLHLock 上还有一个尾指针，始终指向队列的最后一个结点。

CLHLock 的类图如下所示：

简易代码

// CLHLock.java
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() + "释放了锁！！！");        // 小伙伴们可以思考下，下面两句代码的作用是什么？？        CLHNode newCurNode = new CLHNode();        curNode.set(newCurNode);
        // 【优化】能提高GC效率和节省内存空间，请思考：这是为什么？        // curNode.set(predNode.get());    }}

代码流程

1. 当一个线程需要获取锁时，会创建一个新的 QNode，将其中的 locked 设置为 true 表示需要获取锁。

2. 然后线程对 tail 域调用 getAndSet 方法，使自己成为队列的尾部，同时获取一个指向其前趋的引用 myPred。

3. 然后该线程就在前趋结点的 locked 字段上旋转，直到前趋结点释放锁。

4. 当一个线程需要释放锁时，将当前结点的 locked 域设置为 false，同时回收前趋结点。

该算法也是空间有效的，如果有 n 个线程，L 个锁，每个线程每次只获取一个锁，那么需要的存储空间是 O（L+n），n 个线程有 n 个 myNode，L 个锁有 L 个 tail。

这种算法有一个缺点是在 NUMA 系统架构下性能表现很差，因为它自旋的 locked 是前驱线程的，如果内存位置较远，那么性能会受到损失。【但是在 SMP 这种 cache 一致性的系统架构上表现良好。】

流程说明

• 线程 A 需要获取锁，其 myNode 域为 true，些时 tail 指向线程 A 的结点，然后线程 B 也加入到线程 A 后面，tail 指向线程 B 的结点。

• 然后线程 A 和 B 都在它的 myPred 对象上旋转，一旦它的 myPred 结点的 locked 字段变为 false，它就可以获取锁进行继续执行业务方法。

• 明显线程 A 的 myPred locked 域为 false，此时线程 A 获取到了锁，如下图所示。

从代码中可以看出 lock 方法中有一个 while 循环，这 是在等待前趋结点的 locked 域变为 false，这是一个自旋等待的过程。unlock 方法很简单，只需要将自己的 locked 域设置为 false 即可。

CLH 优缺点

唯一的缺点是在 NUMA 系统结构下性能很差，在这种系统结构下，每个线程有自己的内存，如果前趋结点的内存位置比较远，自旋判断前趋结点的 locked 域，性能将大打折扣，但是在 SMP 系统结构下该法还是非常有效的。一种解决 NUMA 系统结构的思路是 MCS 队列锁。