在并发编程中，锁是一种常用的保证线程安全的方法。Java 中常用的锁主要有两类，一种是 Synchronized 修饰的锁，被称为 Java 内置锁或监视器锁。另一种就是在 J2SE 1.5版本之后的 java.util.concurrent包（下称JUC包）中的各类同步器，包括 ReentrantLock（可重入锁），ReentrantReadWriteLock（可重入读写锁），Semaphore（信号量），CountDownLatch 等。这些同步器都是基于 AbstractQueuedSynchronizer（下称 AQS）这个简单的框架来构建的，而 AQS 类的核心数据结构是一种名为 Craig, Landin, and Hagersten locks（下称 CLH 锁）的变体。
CLH 锁是对自旋锁的一种改良
自旋锁
自旋锁是互斥锁的一种实现，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）实现的。该操作是原子操作。原子性保证了根据最新信息计算出新值，如果与此同时值已由另一个线程更新，则写入将失败。因此，这段代码可以实现互斥锁的功能
自旋锁实现简单，同时避免了操作系统进程调度和线程上下文切换的开销，但他有两个缺点：
-
第一个是锁饥饿问题。在锁竞争激烈的情况下，可能存在一个线程一直被其他线程”插队“而一直获取不到锁的情况。
-
第二是性能问题。在实际的多处理上运行的自旋锁在锁竞争激烈时性能较差。
自旋锁的性能和理想情况相距甚远。这是因为自旋锁锁状态中心化，在竞争激烈的情况下，锁状态变更会导致多个 CPU 的高速缓存的频繁同步，从而拖慢 CPU 效率
因此自旋锁适用于锁竞争不激烈、锁持有时间短的场景
CLH原理
CLH 锁是对自旋锁的一种改进，有效的解决了以上的两个缺点。首先它将线程组织成一个队列，保证先请求的线程先获得锁，避免了饥饿问题。其次锁状态去中心化，让每个线程在不同的状态变量中自旋，这样当一个线程释放它的锁时，只能使其后续线程的高速缓存失效，缩小了影响范围，从而减少了 CPU 的开销。
CLH 锁数据结构很简单，类似一个链表队列，所有请求获取锁的线程会排列在链表队列中，自旋访问队列中前一个节点的状态。当一个节点释放锁时，只有它的后一个节点才可以得到锁。CLH 锁本身有一个队尾指针 Tail，它是一个原子变量，指向队列最末端的 CLH 节点。
每一个 CLH 节点有两个属性：所代表的线程和标识是否持有锁的状态变量。当一个线程要获取锁时，它会对 Tail 进行一个 getAndSet 的原子操作。该操作会返回 Tail 当前指向的节点，也就是当前队尾节点，然后使 Tail 指向这个线程对应的 CLH 节点，成为新的队尾节点。入队成功后，该线程会轮询上一个队尾节点的状态变量，当上一个节点释放锁后，它将得到这个锁。
CLH 锁 Java 实现
public class CLHLock {private static class CLHNode {// 锁状态：默认为false，表示线程没有获取到锁；true表示线程获取到锁volatile boolean locked = false;}private final AtomicReference<CLHNode> tailNode;private final ThreadLocal<CLHNode> preNode;private final ThreadLocal<CLHNode> curNode;public CLHLock() {// 初始化前继节点，注意此时前继节点没有存储CLHNode对象，存储的是null// 在加锁时，会将 tailNode 赋值给 preNodethis.preNode = new ThreadLocal<>();this.curNode = ThreadLocal.withInitial(CLHNode::new);this.tailNode = new AtomicReference<>(new CLHNode());}public void lock() {CLHNode currNode = curNode.get();currNode.locked = true;// 当前节点赋值给尾节点, 就尾节点变为当前节点的前节点CLHNode oldTail = tailNode.getAndSet(currNode);preNode.set(oldTail);// 循环监控前节点while (oldTail.locked) {try {TimeUnit.MILLISECONDS.sleep(10);} catch (InterruptedException e) {throw new RuntimeException(e);}System.out.println(Thread.currentThread().getName() + "未获取到锁");}System.out.println(Thread.currentThread().getName() + "获取到锁了");}public void unlock() {CLHNode currNode = curNode.get();currNode.locked = false;System.out.println(Thread.currentThread().getName() + "释放锁了");// 防止当前节点重新执行lock()导致死锁curNode.set(new CLHNode());// curNode.set(preNode.get());}
} private static int count = 0;public static void main(String[] args) throws InterruptedException {CLHLock lock = new CLHLock();for (int i = 0; i < 100; i++) {new Thread(() -> {lock.lock();count++;lock.unlock();}).start();}TimeUnit.SECONDS.sleep(2);System.out.println("count: " + count);}加锁流程分析
假如有这么一个场景：有四个并发线程同时启动执行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节点
释放锁流程
假如这四个线程加锁后，线程A开始释放锁，此时线程B获取到锁，结束自旋等待，然后线程C和线程D仍然自旋等待
以此类推，线程B释放锁的过程也跟上图类似，这里不再赘述。
CLH 优缺点分析
CLH 锁作为自旋锁的改进，有以下几个优点：
-
性能优异，获取和释放锁开销小。CLH 的锁状态不再是单一的原子变量，而是分散在每个节点的状态中，降低了自旋锁在竞争激烈时频繁同步的开销。在释放锁的开销也因为不需要使用 CAS 指令而降低了。
-
公平锁。先入队的线程会先得到锁。
-
实现简单，易于理解。
-
扩展性强。下面会提到 AQS 如何扩展 CLH 锁实现了 j.u.c 包下各类丰富的同步器。
当然，它也有两个缺点：第一是因为有自旋操作，当锁持有时间长时会带来较大的 CPU 开销。第二是基本的 CLH 锁功能单一，不改造不能支持复杂的功能。
死锁
在 unlock() 中有如下代码
curNode.set(new CLHNode());若没有这两句代码，若同个线程加锁释放锁后，然后再次执行加锁操作，可能会发生死锁
出现的根本原因应该是tailNode和curNode的引用一致，当修改tailNode的值为true时，curNode也会被改为true
第一种情况：
A线程拿到锁，B线程正在等待。A线程执行完unlock()后（locked = false），（在B线程 while循环中发现A线程释放锁之前）此时A线程再次加锁，会把 locked 改为 true，此时B线程在循环中看到A线程还是没有释放锁
第二种情况：
有且只有A线程。A线程执行完unlock()后（locked = false），A线程再次加锁，这样 tail 和 cur 都是同一个引用，且tail 在加锁是把 locked 改为 true
https://zhuanlan.zhihu.com/p/197840259
Java AQS 核心数据结构-CLH 锁