1. What?
Craig, Landin, and Hagersten 简称 CLH，CLH锁是一个自旋锁，以自旋的方式确保无饥饿性，提供先来先服务的公平性，即公平锁。
CLH锁也是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程仅仅在本地变量上自旋，它不断轮询前驱的状态，假设发现前驱释放了锁就结束自旋。
2. Why?
CLH队列锁的优点是空间复杂度低，如果有n个线程去竞争一把锁，那么空间复杂度是O(n+1)，n个线程有n个node，一个tail。
CLH的升级版本应用在Java并发框架中，如AQS。
3. How?
3.1 代码实现
public class CLHLock implements Lock {
private AtomicReference<Node> tail;
/**
* 当前节点
*/
private ThreadLocal<Node> cur;
/**
* 前置节点
*/
private ThreadLocal<Node> prev;
public CLHLock(){
// 初始化尾节点
tail = new AtomicReference<>(new Node());
// 初始化节点
cur = ThreadLocal.withInitial(Node::new);
// 初始化前置节点，值为空
prev = ThreadLocal.withInitial(() -> null);
}
@Override
public void lock() {
// 加锁过程
// get():若Node为空，则新建Node；再锁定
cur.get().locked=true;
// getAndSet()方法修改尾节点，返回tail修改前的值
Node prev = tail.getAndSet(cur.get());
// 设置前置
this.prev.set(prev);
// 当前线程自旋(堵塞)，依赖前置线程的cur，一直到前置线程解锁，才跳出自旋
for (;prev.locked;);
}
@Override
public void unlock() {
// 解锁
cur.get().locked=false;
// 前置赋值给当前节点
cur.set(prev.get());
// help gc prev node
prev.remove();
}
class Node{
volatile boolean locked;
}
}
3.2 图解代码
CLH node 之间没有直接的指向关系，通过上一线程的cur和当前线程的prev保持联系
- 数据结构图
线程A、线程B、线程C进入同步代码块，竞争锁资源，当前线程A获取锁资源，线程B/C，添加到CLH中，并自旋
具体分析初始化CLH，加锁，多线程加锁，解锁的过程
- 初始化CLH
a. 初始化尾节点; b. 初始化线程的cur为新节点; c. 初始化线程的prev为null
- 加锁
tail指向Node1，且ThreadA.prev指向Node2(原tail节点)
- 多线程竞争锁
ThreadB进入，会新建节点Node3，并Node3.locked=true，尾节点重新指向如下图
tail指向Node3,并ThreadB.prev指向Node1(原tail)
- 解锁
ThreadA 执行完同步代码块后，先修改cur.get().locked=flase，即Node1.locked=false，修改完后，ThreadB.prev.locked=false，跳出自旋，ThreadB再执行同步代码块
3.2 测试
public class CLHLockTest {
private final CLHLock clhLock = new CLHLock();
private int i = 0;
private void testLock() {
// 加锁
clhLock.lock();
try {
// 自增
i++;
// 打印线程名和i
System.out.println(Thread.currentThread().getName() + ":" + i);
} finally {
// 解锁
clhLock.unlock();
}
}
public static void main(String[] args) {
CLHLockTest instance = new CLHLockTest();
// 启动100线程做自增操作
IntStream.range(0, 100).forEach(e -> new Thread(instance::testLock).start());
}
}
测试过程中发现CLH锁存在性能问题，当启动过多线程时，cpu飙高，原因是同步代码块执行时间过长，导致CLH中没有获取锁资源的线程自旋时间过长，非常吃资源；还有个问题就是每个线程进入时都会新建Node，占用大量内存，所以Java中的AQS采用了升级版的CLH。
