CLH锁

什么是CLH锁

CLH锁其实就是一种是基于逻辑队列非线程饥饿的一种自旋公平锁，由于是 Craig、Landin 和 Hagersten三位大佬的发明，因此命名为CLH锁。

AQS是JUC的核心，而CLH锁又是AQS的基础，说核心也不为过，因为AQS就是用了变种的CLH锁。如果要学好Java并发编程，那么必定要学好JUC；学好JUC，必定要先学好AQS；学好AQS，那么必定先学好CLH。

CLH锁详解

先看CLH锁实现代码，然后通过一步一图来详解CLH锁。

// 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

CLH锁的初始化逻辑

1，定义了一个CLHNode节点，里面有一个locked属性，表示线程线程是否获得锁，默认为false。false表示线程没有获取到锁或已经释放锁；true表示线程获取到了锁或者正在自旋等待。

注意，为了保证locked属性线程间可见，该属性被volatile修饰。

2，CLHLock有三个重要的成员变量尾节点指针tailNode,当前线程的前继节点preNode和当前节点curNode。其中tailNode是AtomicReference类型，目的是为了保证尾节点的线程安全性；此外，preNode和curNode都是ThreadLocal类型即线程本地变量类型，用来保存每个线程的前继CLHNode和当前CLHNode节点。

3，最重要的是我们新建一把CLHLock对象时，此时会执行构造函数里面的初始化逻辑。此时给尾指针tailNode和当前节点curNode初始化一个locked状态为false的CLHNode节点，此时前继节点preNode存储的是null。

CLH锁的加锁过程

我们再来看看CLH锁的加锁过程，下面再贴一遍加锁lock方法的代码：

// CLHLock.java

/**
 * 获取锁
 */
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) {
        try {
            Thread.sleep(1000);
        } catch (Exception e) {

        }
        System.out.println("线程" + Thread.currentThread().getName() + "没能获取到锁，进行自旋等待。。。");
    }
    // 能执行到这里，说明当前线程获取到了锁
    System.out.println("线程" + Thread.currentThread().getName() + "获取到了锁！！！");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

1，首先获得当前线程的当前节点curNode，这里每次获取的CLHNode节点的locked状态都为false；

2，然后将当前CLHNode节点的locked状态赋值为true，表示当前线程的一种有效状态，即获取到了锁或正在等待锁的状态；

3，因为尾指针tailNode的总是指向了前一个线程的CLHNode节点，因此这里利用尾指针tailNode取出前一个线程的CLHNode节点，然后赋值给当前线程的前继节点predNode，并且将尾指针重新指向最后一个节点即当前线程的当前CLHNode节点，以便下一个线程到来时使用；

4，根据前继节点（前一个线程）的locked状态判断，若locked为false，则说明前一个线程释放了锁，当前线程即可获得锁，不用自旋等待；若前继节点的locked状态为true，则表示前一线程获取到了锁或者正在等待，自旋等待。

场景举例

假如有这么一个场景：有四个并发线程同时启动执行lock操作，假如四个线程的实际执行顺序为：threadA<–threadB<–threadC<–threadD

第一步：线程A过来，执行了lock操作，获得了锁，此时locked状态为true，如下图：

第二步：线程B过来，执行了lock操作，由于线程A还未释放锁，此时自旋等待，locked状态也为true，如下图：

第三步：

线程C过来，执行了lock操作，由于线程B处于自旋等待，此时线程C也自旋等待（因此CLH锁是公平锁），locked状态也为true，如下图：

第四步，线程D过来，执行了lock操作，由于线程C处于自旋等待，此时线程D也自旋等待，locked状态也为true，如下图:

这就是多个线程并发加锁的一个过程图解，当前线程只要判断前一线程的locked状态如果是true，那么则说明前一线程要么拿到了锁，要么也处于自旋等待状态，所以自己也要自旋等待。而尾指针tailNode总是指向最后一个线程的CLHNode节点。

CLH锁的释放锁过程

前面用图解结合代码说明了CLH锁的加锁过程。同样，我们先贴下释放锁的代码：

// CLHLock.java

/**
 * 释放锁
 */
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

可以看到释放CLH锁的过程代码比加锁简单多了，下面同样缕一缕：

1，首先从当前线程的线程本地变量中获取出当前CLHNode节点，同时这个CLHNode节点被后面一个线程的preNode变量指向着；

2，然后将locked状态置为false即释放了锁；

注意：locked因为被volitile关键字修饰，此时后面自旋等待的线程的局部变量preNode.locked也为false，因此后面自旋等待的线程结束while循环即结束自旋等待，此时也获取到了锁。这一步骤也在异步进行着。

3，然后给当前线程的表示当前节点的线程本地变量重新赋值为一个新的CLHNode。

我们还是用一个图来说说明CLH锁释放锁的场景，接着前面四个线程加锁的场景，假如这四个线程加锁后，线程A开始释放锁，此时线程B获取到锁，结束自旋等待，然后线程C和线程D仍然自旋等待，如下图：

以此类推，线程B释放锁的过程也跟上图类似。

同个线程加锁释放锁再次正常获取锁

在前面讲到释放锁unLock方法中有下面两句代码：

CLHNode newCurNode = new CLHNode();
curNode.set(newCurNode);
1
2

这两句代码的作用是什么？这里先直接说结果：若没有这两句代码，若同个线程加锁释放锁后，然后再次执行加锁操作，这个线程就会陷入自旋等待的状态。

下面我们同样通过一步一图的形式来分析这两句代码的作用。假如有下面这样一个场景：线程A获取到了锁，然后释放锁，然后再次获取锁。

第一步： 线程A执行了lock操作，获取到了锁，如下图：

上图的加锁操作中，线程A的当前CLHNode节点的locked状态被置为true；然后tailNode指针指向了当前线程的当前节点；最后因为前继节点的locked状态为false，不用自旋等待，因此获得了锁。

第二步： 线程A执行了unLock操作，释放了锁，如下图：

上图的释放锁操作中，线程A的当前CLHNode节点的locked状态被置为false，表示释放了锁；然后新建了一个新的CLHNode节点newCurNode，线程A的当前节点线程本地变量值重新指向了newCurNode节点对象。