CLH锁队列

什么是CLH

CLH锁（Craig, Landin, and Hagersten Lock）是一种基于链表的可扩展、高性能、公平的自旋锁。

它的名字来源于三位发明者：Craig、Landin 和 Hagersten。

在 Java 的并发编程中，CLH 锁非常重要，因为它是 Java并发包（java.util.concurrent）核心组件 AQS (AbstractQueuedSynchronizer) 的基础实现原理。

以下是关于 CLH 锁队列的详细通俗解释：

1. 核心概念：隐式链表与"盯着前一个人"

CLH 锁并不是一个实际持有所有线程的物理队列，而是一个逻辑上的队列（或称为虚拟队列）。

• 排队机制：每个想要获取锁的线程，都会创建一个节点（Node），并将自己加入到队列的尾部。
• 自旋逻辑（关键点）：线程不检查具体的“锁”状态，而是只检查它前面的那个节点（前驱节点）的状态。
  • 就像在银行排队，你不需要一直问柜员“轮到我了吗？”，你只需要盯着排在你前面的那个人。如果他办完业务走了，你就知道轮到你了。

2. CLH 锁的数据结构与流程

假设有一个节点类 QNode，里面有一个布尔值 locked。

class QNode {
    volatile boolean locked = true; // 默认为 true，表示需要锁或持有锁
}

获取锁的过程：

1. 入队：线程 A 来了，生成一个 QNode，并试图通过 CAS 操作将自己设置为全局的 Tail（尾节点）。
2. 持有前驱引用：线程 A 获取原来的 Tail（即它前面的节点，假设是线程 B 的节点）。
3. 自旋等待：线程 A 开启一个 while 循环，不断检查前驱节点（线程 B） 的 locked 变量。
   • 如果 B 的 locked 是 true，说明 B 还在用锁，A 继续自旋（等待）。
4. 获取成功：当线程 B 释放锁，将自己的 locked 设为 false。线程 A 监测到这个变化，循环结束，A 成功拿到锁。

3. 为什么要这样设计？（CLH 的优势）

3.1 解决"惊群效应"与总线风暴

普通的自旋锁（如 AtomicInteger CAS 争抢）是所有线程都在盯着同一个变量。一旦锁释放，所有线程同时去抢，会导致 CPU 总线流量激增。

CLH 的优势：

• 本地自旋（Local Spinning）：每个线程只关心前一个节点的状态。
• 在多处理器架构（NUMA）中，如果前驱节点的内存恰好在本地 Cache 中，性能会极高，大大减少了处理器之间的缓存同步通信。

3.2 先来先服务（FIFO）

因为是入队排队，天然保证了公平性，不会出现“线程饥饿”的情况。

4. CLH 在 Java AQS 中的应用与改进

Java 的 ReentrantLock、CountDownLatch、Semaphore 背后都是 AQS，而 AQS 是基于 CLH 锁的变体 实现的。

AQS 对原始 CLH 做了哪些改造？

1. 显式的双向链表：原始 CLH 是单向的（只看前驱）。AQS 维护了 prev 和 next 指针，以便处理取消排队（如超时、中断）的情况。
2. 阻塞而非纯自旋：原始 CLH 是纯自旋锁（一直空转 CPU）。AQS 结合了 LockSupport.park()，如果长时间拿不到锁，会让线程挂起（阻塞），避免浪费 CPU。
3. 状态变量：AQS 使用 int state 来代表锁的状态（比如 0 是无锁，1 是有锁，>1 是重入），而不是简单的布尔值。

总结

CLH 锁队列就是一种让线程乖乖排队、只盯着前面的人、从而减少 CPU 竞争和缓存失效的高效锁算法。它是 Java 高并发编程大厦的地基之一。

AQS中的CLH使用

这段注释是对 AbstractQueuedSynchronizer (AQS) 中 Node 内部类的详细解释。Node 类是 AQS 的核心，它定义了等待队列（Wait Queue）中节点的数据结构。

这段文档主要解释了 AQS 为什么选择 CLH 队列变体，以及为了支持“阻塞”和“取消”特性做了哪些改造。以下是逐段翻译和核心原理解释：

1. 核心概念：CLH 队列的变体 (Variant of CLH Lock Queue)

The wait queue is a variant of a "CLH" ... lock queue. CLH locks are normally used for spinlocks. We instead use them for blocking synchronizers...

• 原文含义：AQS 的等待队列是 CLH 锁队列的一个变体。CLH 锁通常用于自旋锁（Spinlocks），但 AQS 将其用于阻塞式同步器。
• 核心思想：
  • 控制信息在前驱节点：AQS 沿用了 CLH 的核心策略，即当前线程的阻塞状态由其前驱节点（Predecessor）决定。
  • status 字段：每个节点有一个 status 字段，用来标记该线程是否应该阻塞。
  • 唤醒机制：当一个前驱节点释放锁时，它会负责唤醒（Signal）它的后继节点（Successor）。
  • 非强制拥有权：即使你是队列中的第一个节点，也不代表你一定能拿到锁，你只是获得了去竞争锁的权利。如果竞争失败，你可能需要再次等待。

2. 入队与出队 (Enqueue & Dequeue)

To enqueue into a CLH lock, you atomically splice it in as new tail. To dequeue, you just set the head field.

• 结构示意：

       +------+  prev +-----+       +-----+
  head |      | <---- |     | <---- |     |  tail
       +------+       +-----+       +-----+

• 操作：
  • 入队：通过原子操作（CAS）更新 tail 指针，将新节点拼接到队尾。这是一个简单的原子分界点。
  • 出队：只需要更新 head 指针。

3. prev 指针的作用：处理取消 (Cancellation)

The "prev" links (not used in original CLH locks), are mainly needed to handle cancellation.

• 原文含义：原始的 CLH 锁是不需要 prev（前驱）指针的，但在 AQS 中引入 prev 主要是为了处理取消（Cancellation）。
• 为什么需要？：如果一个节点因超时或中断被取消了，它的后继节点需要跳过这个取消的节点，重新连接到一个未取消的前驱节点上。prev 指针让这种向前遍历和重连成为可能。

4. next 指针的作用：实现阻塞唤醒 (Blocking Mechanics)

We also use "next" links to implement blocking mechanics...

• 原文含义：引入 next 指针是为了实现阻塞机制。
• 唤醒流程：前驱节点需要知道唤醒谁。它通过 next 指针找到后继节点，读取其中的线程 ID 并进行唤醒。
• 竞争条件处理：新节点入队时，tail 更新和 next 指针赋值不是原子的。
  • 问题：可能出现 prev 已经连上，但前驱的 next 还没指过来的瞬间状态。
  • 解决：如果通过 next 找不到后继节点（看似为 null），AQS 会从 tail 开始向前遍历（Backward Scan）来找到正确的后继节点。这解释了源码中为什么经常能看到 LockSupport.unpark 前有一个从尾部向前的循环。
  • 定位：next 指针主要是一种优化，为了避免频繁的从尾部向前扫描。

5. 取消带来的保守策略 (Conservatism via Cancellation)

Cancellation introduces some conservatism...

• 因为需要处理节点取消，算法变得相对保守。在某些取消场景下，为了确保不再丢失唤醒信号，可能会采取“宁可多唤醒，不可漏唤醒”的策略（Always unparking successors upon cancellation）。

6. 虚拟头节点 (Dummy Header Node)

CLH queues need a dummy header node to get started...

• 延迟初始化：CLH 队列需要一个虚拟的头节点（Sentinel/Dummy Node）。AQS 不会在构造时立即创建它（为了省资源），而是在发生第一次锁竞争时才延迟初始化这个头节点。

7. 条件队列 (Condition Support)

Threads waiting on Conditions use the same nodes, but use an additional link.

• 复用 Node：Condition 等待队列复用了同一个 Node 类。
• nextWaiter：条件队列使用一个额外的链接（通常是 nextWaiter）来维护一个单向链表。
• 转移机制：
  • Await：节点放入 Condition 队列。
  • Signal：节点从 Condition 队列转移（Transfer）到 AQS 的主等待队列（CLH 队列）中去竞争锁。

总结

这段注释解释了 AQS 队列模型 的设计哲学：

1. 基于 CLH：利用前驱节点状态管理阻塞。
2. 双向链表：引入 prev 处理取消，引入 next 优化唤醒。
3. 从尾部遍历：为了解决原子性问题，在特定情况下依靠 prev 从尾部向前查找节点是可靠的兜底方案。
4. 复用：同一个 Node 结构既用于锁等待队列，也用于 Condition 条件队列。

为什么CLH队列是双向的，Condition队列是单向的

这是一个非常经典且深入的并发源码问题。AQS 中存在两种队列：

1. 同步队列（CLH 队列）：用于抢锁的，双向链表。
2. 条件队列（Condition 队列）：用于 await/signal 的，单向链表。

之所以设计成不同的结构，核心原因在于并发环境和使用场景的不同。

以下是详细的对比解释：

---

1. 为什么 CLH 同步队列必须是“双向”的？

CLH 队列是线程争抢锁的“战场”，面临着极其复杂的并发环境。

• 原因一：为了处理“取消”（Cancellation）

  • 在锁的竞争中，线程可能会因为超时（tryLock 带超时）或中断（lockInterruptibly）而放弃竞争。
  • 当一个节点需要从队列中间被移除时，它需要把自己从链表中“抠”出来。
  • 如果是单向链表，节点只知道后面是谁，不知道前面是谁，很难高效地把前驱节点的 next 指向后继节点。
  • 双向链表使得节点可以轻松获取 prev（前驱），从而完成断链重连的操作。

• 原因二：为了“唤醒”时的可靠性（解决尾部并发竞争）

  • 在 AQS 的入队逻辑中，是先设置 prev，再通过 CAS 修改 tail，最后才设置前驱的 next。
  • 这意味着在极端并发下，next 指针可能是断开的或不一致的（即 node.next 为 null，但实际上后面有节点）。
  • 为了保证唤醒操作绝对可靠，当通过 next 找不到后继节点时，AQS 会选择从 tail 指针利用 prev 向前遍历来找到最靠近当前节点的等待线程。只有双向链表才能支持从后向前遍历。

---

2. 为什么 Condition 条件队列只需要是“单向”的？

Condition 队列是线程已经拿到了锁，但因为某些条件不满足而主动挂起的“休息室”。

• 原因一：天然的线程安全（不需要复杂的并发控制）

  • 前提条件：调用 await() 或 signal() 的前提是当前线程必须持有独占锁。
  • 这意味着，操作 Condition 队列时，即使没有 CAS 也是线程安全的。
  • 在一个已经加锁的临界区内，维护一个简单的 FIFO 队列，单向链表（利用 nextWaiter 指针）就足够了，不需要双向链表带来的额外开销。

• 原因二：操作逻辑简单（入队和出队）

  • 入队（Await）：直接把节点拼接到链表尾部（不需要像 CLH 那样考虑并发入队的 CAS 失败重试）。
  • 出队（Signal）：直接把链表头部的第一个节点拿出来（FIFO）。
  • 这里不需要从队列中间移除节点（除非是取消，但 Condition 的取消逻辑是直接将节点状态改为 CANCELLED，在后续遍历中剔除，或者直接转移到 CLH 队列处理），也不需要从后向前遍历。

• 原因三：复用 Node 对象，节省内存

  • AQS 的 Node 类为了复用，设计了 nextWaiter 字段用于 Condition 队列，而 prev 和 next 用于 CLH 队列。
  • 当节点被 signal 唤醒时，它会从 Condition 队列（单向）被转移（Transfer）到 CLH 队列（双向）。在这个转移过程中，会把 nextWaiter 置空，并初始化 prev 和 next，完成身份的转换。

---

总结

特性	CLH 同步队列	Condition 条件队列
结构	双向链表 (prev, next)	单向链表 (nextWaiter)
并发环境	高并发，多线程同时入队竞争	无并发，操作时必须持有独占锁
入队方式	CAS 自旋入队	直接追加到队尾
主要难点	处理节点取消、保证唤醒的可靠性	简单的 FIFO 等待
遍历方向	常用从尾向头 (prev)	从头向尾 (nextWaiter)

一句话总结：CLH 队列双向是因为要处理复杂的并发竞争和中断取消，需要回溯；Condition 队列单向是因为它在独占锁的保护下运行，场景简单，单向链表效率更高且够用。

Condition队列的唤醒逻辑

Condition 队列的唤醒逻辑（即 signal 或 signalAll）的核心本质是：将节点从 Condition 队列（等待区）搬运到 CLH 同步队列（竞争区）。

被唤醒并不意味着线程立刻执行，而是意味着它重新具备了竞争锁的资格。

以下是详细的唤醒流程解析：

1. 前置检查

调用 condition.signal() 的线程必须持有锁（Lock.lock()）。

• 如果未持有锁，会抛出 IllegalMonitorStateException。
• 这一点保证了操作 Condition 队列时是线程安全的。

2. 选取目标节点

AQS 会检查 Condition 队列的头节点（firstWaiter）。

• 如果是 signal()，则选取队列中的第一个节点。
• 如果是 signalAll()，则会遍历整个队列，选取所有节点。
• 注意：如果在选取过程中发现节点已经取消（Cancelled），会跳过该节点找下一个。

3. 核心步骤：节点转移 (Transfer)

这是最关键的一步，源码对应 transferForSignal(Node node) 方法。

1. 修改状态 (CAS)：

   • 将节点的状态从 CONDITION (-2) 修改为 0 (初始状态)。
   • 如果 CAS 失败，说明该节点在排队期间已经被取消了（比如被中断），则放弃该节点，继续找下一个。

2. 入队 CLH (enq)：

   • 调用 enq(node) 方法，将该节点尾插入到 CLH 同步队列中。
   • 这一步成功后，该节点就正式从“条件等待队列”转移到了“锁同步队列”。
   • enq 方法会返回该节点在 CLH 队列中的前驱节点 (predecessor)。

3. 尝试唤醒 (Unpark - 可选)：

   • 获取刚返回的前驱节点 p。
   • 判断前驱节点 p 的状态：
     • 如果前驱节点已经取消 (ws > 0)；
     • 或者尝试将前驱节点的状态改为 SIGNAL (-1) 失败；
   • 只有在上述异常情况下，AQS 才会立即调用 LockSupport.unpark(node.thread) 唤醒当前线程，让它自己去修正前驱状态。
   • 正常情况下，signal 不会立即唤醒线程。线程依然在 await() 方法的 while 循环中阻塞，直到持有锁的线程释放锁（unlock），触发 CLH 队列的正常唤醒流程。

4. 唤醒后的行为 (Wait 结束)

当线程最终被唤醒（通常是持有锁的线程执行完 unlock 后）：

1. 线程从 LockSupport.park 中醒来。
2. 检查 isOnSyncQueue(node)：发现自己已经成功在 CLH 队列中了。
3. 跳出 await() 内部的 while 循环。
4. 调用 acquireQueued(node, savedState)：
   • 这里会尝试像普通抢锁线程一样去竞争锁。
   • 如果竞争成功，await() 方法返回，代码继续往下执行。
   • 如果竞争失败，再次挂起（Park），等待下一次 CLH 队列的唤醒。

总结流程图

graph TD
    A["调用 condition.signal()"] --> B{"持有锁?"}
    B -->|No| C["抛异常 IllegalMonitorStateException"]
    B -->|Yes| D["获取 Condition 队列首节点 first"]
    D --> E{"节点有效?"}
    E -->|No Cancelled| F["找下一个节点"]
    E -->|Yes| G["CAS修改状态: CONDITION -> 0"]
    G -->|成功| H["入队 CLH: enq(node)"]
    H --> I["获取前驱节点 prev"]
    I --> J{"prev有效 且 CAS设为SIGNAL成功?"}
    J -->|Yes 正常情况| K["结束 signal, 线程仍在阻塞中"]
    J -->|No 前驱异常| L["立刻 Unpark 线程让其自救"]
    K --> M["等待持有锁线程 unlock"]
    M --> N["CLH 队列机制唤醒线程"]
    N --> O["线程在 await() 中醒来"]
    O --> P["竞争锁 acquireQueued"]
    P -->|成功| Q["await() 返回, 继续执行业务"]

一句话概括

signal 的本质不是“唤醒”，而是“晋升”。它把线程从“等待冷板凳”（Condition 队列）提拔到了“候选人名单”（CLH 队列），真正的执行机会要等到当前持锁人退位（unlock）后，它才有资格去争抢。

3. 运作流程：线程的“迁移”之旅

假设线程 A 持有锁，但在执行过程中发现条件不满足（比如队列满了），它调用 condition.await()。

第一阶段：调用 await()（入队与阻塞）

1. 完全释放锁：线程 A 释放持有的锁（无论重入多少次，state 清零），并保存当前的锁状态（以便后续恢复）。

2. 进入等待队列：AQS 将当前线程包装成一个 Node，加入到该 Condition 的等待队列队尾。

3. 阻塞：线程 A 被 LockSupport.park() 挂起，进入休眠状态。

第二阶段：调用 signal()（通知与迁移）

此时，线程 B 获取了锁，执行某些操作让条件满足了（比如消费了一个数据），调用 condition.signal()。

1. 取出队头：检查当前线程是否持有锁，然后从等待队列头部取出一个 Node（比如线程 A）。

2. 迁移队列：将这个 Node 从等待队列移除，并加入到 AQS 的同步队列（Sync Queue）尾部。

• 注意：此时线程 A 还没醒，它只是从“等待被叫号”变成了“等待抢锁”。

1. 唤醒（视情况）：通常情况下，线程 B 释放锁（unlock）时，AQS 会唤醒同步队列头部的线程（此时轮到 A 了）。

第三阶段：被唤醒（抢锁与恢复）

1. 竞争锁：线程 A 在同步队列中醒来，开始尝试获取锁（和其他竞争者一样）。

2. 恢复状态：一旦获取锁成功，它将 state 恢复到 await 之前的数值（处理重入）。

3. 方法返回：await() 方法执行结束，线程 A 继续执行后续代码。