AQS 为什么采用双向链表?

萧曵丶

978人浏览 · 2026-01-12 11:33:44

萧曵丶 · 2026-01-12 11:33:44 发布

前置认知：AQS（抽象队列同步器）的核心是同步队列，这个队列是用来存放「获取锁失败」的线程，而这个同步队列的底层实现，就是双向链表 + 虚拟头节点（哑节点） ，这是所有设计的基础。

一、先看基础：AQS 同步队列的「双向链表核心结构」+ 核心源码

✅ 1.1 AQS 的 Node 节点核心源码（JDK8）

AQS 的同步队列中，每一个等待锁的线程都会被封装成一个 Node 对象，双向链表的核心就体现在 Node 的两个指针属性，这是双向链表的根基，所有操作都基于此：

static final class Node {
    // 线程取消状态（超时/中断会进入此状态，核心！）
    static final int CANCELLED =  1;
    // 线程等待唤醒状态
    static final int SIGNAL    = -1;

    volatile int waitStatus;    // 节点的等待状态，volatile保证可见性
    volatile Node prev;         // 前驱节点指针 【双向链表核心】
    volatile Node next;         // 后继节点指针 【双向链表核心】
    volatile Thread thread;     // 当前节点绑定的等待线程
}

✅ 1.2 AQS 同步队列的静态结构图（必看）

AQS 的双向链表有 2 个关键设计 + 1 个核心特征：

链表是带头尾指针的：head（头节点）、tail（尾节点），可以直接定位首尾，无需遍历；
链表是虚拟头节点（dummy） 设计：头节点不绑定任何线程，是「占位节点」，真正的等待线程从 head.next 开始；
双向链表核心特征：每个节点都持有「前驱节点 prev」+「后继节点 next」的双向引用。

        【虚拟头节点】          线程1节点            线程2节点            线程3节点
head  →  Node(null)  ←→  Node(Thread-1)  ←→  Node(Thread-2)  ←→  Node(Thread-3)  ←→ tail
           prev=null        prev=head           prev=Thread-1       prev=Thread-2
           next=Thread-1    next=Thread-2       next=Thread-3       next=null

双向箭头 ←→ ：代表 prev/next 的双向引用，这是双向链表的核心标识

二、核心问题：AQS 为什么不用「单向链表」，非要用「双向链表」？

✅ 核心结论（先记死）：

AQS 选择双向链表，不是技术偏好，而是 并发场景下的「唯一最优解」，核心原因有 3 个，优先级从高到低，第一个原因是绝对核心（占 90%），后两个是强辅助、缺一不可：

🌟 最核心：处理「线程取消（超时 / 中断）」时，双向链表能 O (1) 高效删除任意位置的节点，单向链表做不到，这是 AQS 必须解决的核心痛点；
🌟 次核心：释放锁唤醒线程时（unparkSuccessor），能反向回溯找有效节点，清理无效节点，保证唤醒的绝对可靠性，避免锁死；
✅ 基础保障：双向链表 + CAS 原子操作，完美契合 AQS 的「无锁设计」初衷，所有队列操作都能无锁完成，单向链表会破坏这个设计。

三、原因一：【绝对核心】处理线程取消，O (1) 删除任意节点

3.1 线程取消的业务场景

当线程在队列中等待锁时，大概率会触发「放弃等待」的场景：

线程等待锁超时，主动放弃获取锁；
线程在等待时被中断 (interrupt)，响应中断后放弃等待；
线程发生异常，被动退出等待。

此时，该线程对应的 Node 节点需要被标记为「取消状态（CANCELLED=1）」，并从链表中删除该节点，让链表中只保留「有效等待的线程节点」。

3.2 双向链表 VS 单向链表：删除节点的天壤之别

✅ 情况 1：双向链表删除「取消节点」- 动态执行流程（核心！）

假设队列：虚拟头 → 线程A → 线程B → 线程C，此时线程 B 超时被取消，双向链表的删除过程是「O (1) 时间复杂度，无遍历，一步到位」，动态流程如下：

【步骤1】初始状态
虚拟头 ←→ A ←→ B(取消) ←→ C

【步骤2】线程B通过自身的prev指针，直接拿到前驱节点A；通过next指针，直接拿到后继节点C
B.prev = A 、 B.next = C

【步骤3】CAS原子操作修改指针，完成删除
A.next = C  、  C.prev = A

【步骤4】最终状态（B节点被孤立，等待GC回收）
虚拟头 ←→ A ←→ C

👉 核心优势：不需要遍历链表，直接通过节点自身的 prev/next 找到前后节点，修改指针即可删除，无论节点在链表头部、中间、尾部，删除效率都是 O (1)。

❌ 情况 2：单向链表删除「取消节点」- 致命缺陷

单向链表的 Node 只有next指针，没有prev指针，当要删除中间的线程 B 节点时：

必须从头节点开始遍历整个链表，找到线程 B 的前驱节点 A，这个过程是O (n) 时间复杂度，并发场景下性能暴跌；
遍历过程中，为了保证线程安全，必须加锁，这直接违背了 AQS「无锁化设计」的初衷；
遍历 + 加锁会导致队列操作的并发安全问题，极端情况下会出现「链表死锁」，整个同步队列瘫痪。

3.3 对应 AQS 核心源码：取消节点的删除逻辑 `cancelAcquire(Node node)`

这是 JDK8 AQS 的原生核心源码，所有线程取消的逻辑都在这个方法里，完美印证「双向链表的删除逻辑」，源码做了精简（保留核心逻辑）+ 中文注释，看懂这个源码，就彻底懂了第一个核心原因：

// AQS核心方法：标记当前节点为取消状态，并从双向链表中删除该节点
private void cancelAcquire(Node node) {
    if (node == null) return;
    node.thread = null; // 解绑线程，标记为无效节点

    // 步骤1：通过node.prev拿到【前驱节点p】，双向链表的核心优势体现！
    Node p = node.prev;
    // 跳过所有已经被取消的前驱节点，找到第一个有效前驱
    while (p.waitStatus > 0) p = p.prev;
    Node pNext = p.next; // 前驱节点的后继指针

    // 步骤2：标记当前节点为【取消状态】
    node.waitStatus = Node.CANCELLED;

    // 步骤3：CAS原子操作修改指针，完成删除（双向链表核心操作）
    if (node == tail && compareAndSetTail(node, p)) {
        // 如果当前节点是尾节点，直接把前驱设为新的尾节点
        compareAndSetNext(p, pNext, null);
    } else {
        // 如果是中间节点，把前驱的next指向当前节点的后继
        compareAndSetNext(p, pNext, node.next);
        // 把后继的prev指向前驱，双向链表的反向绑定！
        if (node.next != null) node.next.prev = p;
    }
}

👉 源码核心亮点：全程没有任何遍历操作，所有节点的获取都是通过node.prev/node.next直接拿到，这就是双向链表的精髓！

四、原因二：【次核心】唤醒后继节点时，反向回溯 + 清理无效节点

4.1 唤醒线程的业务场景

AQS 的核心逻辑：持有锁的线程释放锁时，必须唤醒队列中第一个有效等待的线程，这个逻辑在unparkSuccessor(Node node)方法中实现，这是 AQS 的「解锁核心流程」。

这里有一个关键问题：队列中的后继节点可能是「取消状态」（比如超时、中断），如果直接唤醒这个无效节点，会导致「锁无人唤醒」，最终发生锁死！

4.2 双向链表的核心优势：反向回溯找有效节点，保证唤醒可靠性

✅ 双向链表唤醒节点 - 动态执行流程

释放锁时，当前节点是头节点，需要唤醒「第一个有效后继节点」，动态流程如下：

【步骤1】初始队列（存在无效节点）
虚拟头 ←→ A(取消) ←→ B(取消) ←→ C(有效等待) ←→ D(有效等待)

【步骤2】从头节点的next开始向后找，发现A、B都是取消状态
此时：双向链表可以通过「尾节点tail反向向前回溯」，从D→C，找到第一个有效节点C

【步骤3】清理无效节点A、B，修改指针让虚拟头直接指向C
虚拟头 ←→ C ←→ D

【步骤4】唤醒有效节点C对应的线程，获取锁

👉 核心优势：双向链表可以「双向遍历」，既可以从 head 向后找，也可以从 tail 向前找，当后继节点无效时，能反向回溯找到第一个有效节点，绝对不会出现「锁死」的情况。

❌ 单向链表的致命缺陷：只能单向遍历，必现锁死

单向链表只有next指针，只能从 head 向后找，当遇到连续的无效节点（A、B）时，会直接遍历到链表尾部，误以为队列中没有有效节点，最终没有线程被唤醒，锁永远无法被获取，发生锁死！

4.3 对应 AQS 核心源码：唤醒后继节点 `unparkSuccessor(Node node)`

这是 AQS 解锁时的核心源码，完美印证双向链表的反向回溯逻辑，源码精简 + 中文注释，核心逻辑一目了然：

// AQS核心方法：释放锁时，唤醒队列中第一个有效等待的线程
private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0) compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next; // 拿到当前节点的后继节点
    // 关键判断：如果后继节点是取消状态 或 为空
    if (s == null || s.waitStatus > 0) {
        s = null;
        // 双向链表核心：从【尾节点tail】反向向前遍历，找第一个有效节点！
        for (Node t = tail; t != null && t != node; t = t.prev) {
            if (t.waitStatus <= 0) s = t;
        }
    }
    // 唤醒找到的有效节点对应的线程
    if (s != null) LockSupport.unpark(s.thread);
}

👉 源码核心亮点：for (Node t = tail; t != null && t != node; t = t.prev) 这一行代码，就是双向链表的反向回溯逻辑，如果是单向链表，根本写不出这个逻辑！

五、原因三：【基础保障】双向链表完美契合 AQS 的「无锁化设计」

5.1 AQS 的设计初衷：无锁化的并发控制

AQS 是 Java 并发包的基石（ReentrantLock、CountDownLatch、Semaphore 等都基于 AQS），它的底层设计核心是：通过「CAS 原子操作 + 自旋」实现无锁化的队列维护，绝对不引入额外的锁，这是 AQS 高性能的核心原因。

5.2 双向链表如何支撑无锁设计？

双向链表的prev和next指针，让所有队列操作（入队、出队、删除、修改）都能通过CAS 原子操作完成：

入队：CAS 修改 tail 的 next 指针，把新节点加到队尾；
出队：CAS 修改 head 指针，把有效节点设为新的头节点；
删除：CAS 修改前驱的 next 和后继的 prev 指针，孤立取消节点；

所有操作都是原子性的、无遍历的、无锁的，时间复杂度都是 O (1)，这是双向链表的天然优势。

5.3 单向链表为什么会破坏无锁设计？

单向链表删除节点时，必须遍历找前驱节点，遍历过程中无法通过 CAS 保证原子性，只能引入额外的锁来保护链表，这会让 AQS 的性能暴跌，并且违背其设计初衷。

六、补充：AQS 双向链表的「额外优化设计」（锦上添花）

AQS 的双向链表还结合了两个优化设计，让队列的性能和安全性更上一层楼，这也是双向链表的配套优势：

✅ 6.1 虚拟头节点（dummy）

链表的头节点是「空节点」，不绑定任何线程，所有有效线程节点都从 head.next 开始，这样做的好处是：入队和出队的逻辑统一，不需要判断头节点是否为空，CAS 操作更简单。

✅ 6.2 尾节点指针（tail）

链表的尾节点直接通过 tail 指针定位，入队时不需要遍历链表找尾节点，直接 CAS 修改 tail 即可，入队效率 O (1)。

七、核心总结：单向链表 VS 双向链表（一张表看懂所有差异）

对比维度	单向链表	双向链表（AQS 选用）
取消节点删除效率	O (n)，需要遍历找前驱	O (1)，直接通过 prev/next 获取前后节点
唤醒后继节点	只能单向遍历，易锁死	双向遍历，反向回溯找有效节点，绝对可靠
并发安全实现	必须加锁，破坏无锁设计	CAS + 自旋，纯无锁，契合 AQS 初衷
时间复杂度	入队 O (1)，删除 O (n)，唤醒 O (n)	入队、删除、唤醒全是 O (1)
并发场景适配	完全不适合高并发	完美适配高并发、高竞争场景