AQS为什么采用双向链表？

### **为什么 AQS 使用双向链表？** AQS (AbstractQueuedSynchronizer) 是 JDK 中用来构建锁和同步器的基础框架。AQS 内部使用一个 **FIFO 队列** 来管理线程排队逻辑，而这个队列实现为双向链表。双向链表的使用主要是基于以下几点原因： ### **单向链表 vs 双向链表** 1. **单向链表的特点：** - 每个节点只包含指向下一个节点的引用。 - 无法高效地访问前驱节点（需要从头遍历）。 - 节点的插入、删除操作依赖前驱节点的定位。 2. **双向链表的特点：** - 每个节点包含指向前一个和后一个节点的引用。 - 能够高效访问前驱节点。 - 插入和删除操作更高效，因为可以直接更新 `prev` 和 `next` 引用。 ### **AQS 为什么选择双向链表** 以下是 AQS 使用双向链表的具体优势和原因： #### 1. **高效的节点移除（中断支持）** - AQS 提供了中断支持：当线程被中断时，需要从队列中移除对应节点。 - 在双向链表中，移除节点的操作非常高效： - 只需要访问待移除节点的 `prev` 和 `next`，然后将 `prev.next` 指向 `next`，`next.prev` 指向 `prev` 即可。 - 如果使用单向链表，需要从头遍历整个链表找到前驱节点，效率较低。 **示例：移除中间节点 B** ```text 双向链表： A <-> B <-> C 移除 B： A <-> C ``` 仅需要操作： - `A.next = C` - `C.prev = A` #### 2. **高效的线程挂起判断** - 在线程获取锁失败后，AQS 判断当前线程是否需要挂起（`shouldParkAfterFailedAcquire`）。 - 判断依据是**当前节点的前驱节点状态**，如果前驱节点的状态允许挂起，则当前线程可安全挂起。 - 使用双向链表可以直接通过 `node.prev` 获取前驱节点的状态，避免从头开始遍历链表。 #### 3. **高效的遍历（支持从尾部向头部遍历）** - AQS 有一些方法需要从队列尾部向头部遍历，比如： - `getQueueLength()`：计算等待队列中的线程数。 - `getQueuedThreads()`：获取所有排队线程。 - 从尾部向头部遍历的好处： - 可能更快找到需要的节点，尤其是新加入的线程通常位于队列尾部。 - 避免频繁访问队列头部，减少对头部节点的竞争。 **示例代码：从尾部遍历** ```java public final int getQueueLength() { int count = 0; for (Node p = tail; p != null; p = p.prev) { if (p.thread != null) { count++; } } return count; } ``` 如果是单向链表，这种从尾部向头部遍历的逻辑无法实现。 #### 4. **支持条件队列** - AQS 的条件变量（`ConditionObject`）支持将线程在条件等待队列和同步队列之间移动。 - 双向链表使得从同步队列移动到条件队列、或从条件队列移动到同步队列更加高效和直接。 - 比如，条件队列中的节点需要根据条件被转移到同步队列时，直接通过 `prev` 和 `next` 引用调整即可。 #### 5. **减少并发竞争** - 在高并发场景中，队列的头部是最频繁访问的部分（释放同步状态时需要操作头部）。 - 一些非关键操作（如获取队列长度或遍历线程）可以从尾部开始遍历，减少对头部的竞争。 - 双向链表可以方便地实现从尾部开始的高效遍历，而单向链表无法支持。 ### **总结** **双向链表在 AQS 中的主要作用：** 1. **高效移除节点**：支持线程中断时快速移除队列中的节点。 2. **高效判断状态**：支持挂起线程时快速判断前驱节点状态。 3. **支持双向遍历**：从尾部遍历减少头部竞争，提升性能。 4. **灵活的数据操作**：方便在条件队列与同步队列之间移动节点。 尽管双向链表占用的内存稍多，但在多线程竞争和需要频繁操作的场景中，双向链表的优势远远超过单向链表。AQS 的设计充分体现了对性能和灵活性的追求，选择双向链表是实现这些目标的最佳方案。