CLH队列（Craig-Landin-Hagersten队列）是一种基于链表的自旋锁等待队列，是Java并发包中AQS（AbstractQueuedSynchronizer）框架的核心实现机制。

核心原理

CLH队列是一种**FIFO（先进先出）**的双向链表结构，每个节点代表一个等待锁的线程。其核心思想是：每个线程只监视前一个线程的状态，而不是竞争共享变量。具体工作流程如下：

  1. 节点结构：每个节点包含以下关键属性

    • waitStatus：节点等待状态（如CANCELLED=1、SIGNAL=-1、CONDITION=-2等）
    • prev：前驱节点引用
    • next：后继节点引用
    • thread：等待的线程
    • nextWaiter：条件队列中的后继节点

  2. 入队机制：

    • 当线程尝试获取锁失败时，会将当前线程构造成一个Node节点
    • 通过CAS操作原子性地将节点添加到队列尾部（尾插法）
    • 随后将前驱节点状态设置为SIGNAL（-1），表示"后继节点需要被唤醒"

  3. 自旋等待：

    • 线程在获取锁失败后，会自旋检查前驱节点的waitStatus状态
    • 如果前驱节点状态为SIGNAL（-1），表示前驱节点正在等待释放锁，当前线程继续自旋等待
    • 一旦前驱节点释放锁（状态变为CANCELLED），当前线程即可获取锁

  4. 出队机制：

    • 当线程释放锁时，会唤醒队列中第一个等待的线程（即head的后继节点）
    • 被唤醒的线程会尝试获取锁，成功后将自己设置为新的head节点
    • 旧head节点被废弃，等待垃圾回收

AQS中的CLH队列实现特点

  1. 虚拟头节点：AQS使用一个虚拟的head节点（不存储实际线程），简化队列操作

  2. 状态管理：

    • SIGNAL(-1)：前驱节点已释放锁，当前节点需要被唤醒
    • CANCELLED(1)：线程已取消等待（超时或中断）
    • CONDITION(-2)：线程在Condition队列中等待
    • PROPAGATE(-3)：共享模式下可传播的状态

  3. 性能优化：

    • AQS对CLH队列进行了变种实现，避免所有线程都自旋
    • 在插入尾节点时，会将前置节点设置为SIGNAL状态并通过LockSupport.park()阻塞当前线程
    • 通过这种方式避免了所有线程一直自旋导致的CPU 100%占用问题

优势与特点

  • 公平性：保证线程按照先来先服务的顺序获取锁，避免线程饥饿
  • 高效性：每个线程只需关注前驱节点状态，降低线程间通信开销
  • 可扩展性：通过动态调整队列长度，适应不同并发场景
  • 内存效率：相比MCS锁，CLH只需维护tail指针的原子更新，减少50%的CAS操作

与MCS锁的对比

特性CLH队列MCS锁
队列结构单向链表（看前驱）单向链表（看自己）
自旋位置前驱节点自己的节点
空间重用是（通过前驱复用）否（每次新建）
实现复杂度较低较高
缓存局部性高（本地自旋）一般

CLH队列作为Java并发框架的核心机制，通过简单的链表结构和自旋等待机制，实现了高效的线程同步和协作，是ReentrantLock、Semaphore等同步组件底层实现的基础。