Skip to content

CLH队列锁介绍

CLH锁是一种基于逻辑队列的、公平的自旋锁。它的名字来源于其三位发明者：Craig、Landin和Hagersten。

它的核心思想非常巧妙：当多个线程竞争一个锁时，它们会在一个隐式的链表队列中排队。每个线程不-再是去争抢一个全局的锁标记，而是各自在自己的节点上“自旋”（循环检查），并只关注其前一个节点的状态。 这种设计大大减少了锁竞争时的系统开销。

核心组件与结构

CLH锁的实现主要依赖于两个核心组件：

  1. 尾指针 (tail)：一个全局的、原子更新的指针，它永远指向队列中的最后一个节点（即最新加入的等待线程）。这是所有希望获取锁的线程进入队列的唯一入口。
  2. 节点 (Node)：每个希望获取锁的线程都会创建一个自己的节点。这个节点至少包含一个状态字段，通常是一个布尔类型的 locked 标志。这个标志的含义是：“我（当前节点）是否需要锁定状态？”或者“我的前驱节点是否已经释放了锁？”。

这个队列是一个隐式链表，因为节点之间没有显式的next指针，后继关系是通过每个节点持有其前驱节点的引用来确定的。

工作原理

我们可以通过“获取锁”和“释放锁”两个过程来理解其工作机制。

1. 获取锁 (Acquire Lock)

假设现在线程A持有锁，线程B正在等待。此时，队列的tail指针指向线程B的节点。现在线程C也想获取锁。

  1. 创建节点：线程C创建自己的节点 Node_C，并将其内部的 locked 状态设置为 true。这个true的含义是“我需要锁，但我还没拿到”。
  2. 入队：线程C通过一个原子操作（如getAndSet）来更新全局的tail指针。这个操作会做两件事：
    • 获取前驱：线程C得到tail指针之前的值，也就是Node_B。现在，Node_B就成了Node_C的前驱节点。
    • 成为队尾：将全局的tail指针设置为指向自己的Node_C。
  3. 自旋等待：线程C开始在一个循环中检查其前驱节点（Node_B）的locked状态。只要Node_B.locked为true，线程C就持续自旋（原地等待），消耗CPU。

这个过程就像排队买票：你（线程C）走到队尾，看着你前面那个人（线程B），只要他还没办完，你就一直等着。

2. 释放锁 (Release Lock)

当一个线程（比如线程B）完成了它的临界区代码，需要释放锁时，过程非常简单：

  1. 更新自身状态：线程B将自己的节点 Node_B 的 locked 状态设置为 false。
  2. 唤醒后继：这个状态改变会被正在自旋等待的线程C观察到。线程C的自旋循环检测到Node_B.locked变为false，循环立即终止。
  3. 获取成功：线程C成功获取到锁，可以进入临界区执行代码了。

这个过程就像办完业务的人（线程B）拍了拍后面人（线程C）的肩膀说“到你了”，然后自己就离开了。被释放的节点Node_B可以被垃圾回收，或者在某些实现中被Node_C复用，以减少内存分配。

CLH锁的优缺点

优点:

  • 公平性：严格遵循先来后到（FIFO）的原则，等待的线程不会被“插队”，避免了线程饥饿问题。
  • 高性能：等待的线程在不同的内存地址（各自前驱节点的locked字段）上自旋，而不是在同一个全局变量上争抢。 这在多处理器和缓存一致性（cache-coherent）架构下，极大地减少了缓存同步的开销和总线流量。
  • 实现简单：相对于其他一些复杂的锁，CLH的逻辑比较清晰。
  • 空间复杂度低：每个锁和线程只需要少量额外的固定空间。

缺点:

  • 仍然是自旋锁：如果锁被占用的时间很长，那么等待的线程会持续消耗CPU资源，这在某些场景下是不可接受的。
  • 在NUMA架构下性能不佳：NUMA（非统一内存访问）架构下，处理器访问本地内存和远程内存的速度差异很大。如果一个线程自旋等待的前驱节点位于一个物理距离很远的内存模块上，那么每次循环检查的延迟都会很高，导致性能下降。

与Java AQS的关系

Java并发包中的AbstractQueuedSynchronizer (AQS) 正是基于CLH队列锁的一个变体实现的。AQS对原始CLH锁做了关键性的优化和改造：

  • 从自旋到阻塞：AQS解决了CLH锁最大的缺点。它不会让线程无限地自旋，而是在短暂自旋失败后，利用LockSupport.park()将线程挂起，进入阻塞状态，从而释放CPU资源。
  • 显式双向链表：AQS使用了一个显式的双向链表结构，每个节点都有prev和next指针。这使得处理线程取消和超时等复杂场景变得更容易。
  • 复杂的状态：AQS的节点拥有更复杂的waitStatus字段，而不仅仅是一个布尔值，这使得节点之间可以进行更丰富的通信和协作。