深入剖析AQS：为什么并发大师选择了双向链表

大家好，我是你们的技术老友科威舟，今天给大家分享一下为什么AQS选择了双向链表。

同步器设计的精髓，就藏在线程排队的数据结构里

在Java并发编程的世界里，AbstractQueuedSynchronizer（AQS）堪称是同步器设计的"脊柱"。它隐藏在ReentrantLock、Semaphore、CountDownLatch等强大工具的背后，默默协调着线程间的协作。而AQS核心中的核心，就是那个神秘的等待队列。

今天，我们就来解开AQS选择双向链表而非单向链表背后的设计智慧。

一、AQS的排队哲学：线程如何优雅等待

想象一下医院挂号的场景：病人（线程）需要获取挂号资源（state变量）。如果资源充足，病人直接获取；如果号源紧张，新来的病人就需要排队等待。

AQS的等待队列就是管理这些"排队线程"的机制。它需要解决几个核心问题：

• 如何高效管理大量等待线程？
• 当有线程放弃等待时，如何快速移除？
• 资源释放时，如何准确唤醒下一个等待者？

AQS的解决方案是维护一个FIFO双向队列，每个等待线程被封装成一个Node节点，包含前驱（prev）和后继（next）指针。

staticfinalclassNode{volatileNodeprev;volatileNodenext;volatileThreadthread;volatileintwaitStatus;// ...}

但为什么是双向链表？单向链表不够简单高效吗？

二、双向链表：AQS的高效秘诀

1. 高效处理"中途离场"：线程取消的优雅解决方案

在并发世界中，线程等待可能被中断或超时，这就需要它能中途离开队列。

假设我们使用单向链表（如CLH锁的原版实现），要删除中间节点会遇到大问题：要删除节点B，必须知道它的前驱节点A，但在单向链表中，节点B并不知道谁指向自己。

双向链表的优势：每个节点都有前驱指针，删除任意节点只需修改相邻节点的指针：

// 简化版的节点删除逻辑node.prev.next=node.next;if(node.next!=null){node.next.prev=node.prev;}

这种操作的时间复杂度是O(1)，而单向链表需要从头遍历，时间复杂度为O(n)。

现实比喻：想象超市结账队伍中有人突然接到电话要离开。如果是单向排队（每个人只记得前面是谁），离开的人需要大喊"我是谁前面的人"，让队伍重新整理。而双向排队（每个人记得前后是谁），离开只需与前后的人沟通即可，不影响其他人。

2. 从"轮询"到"唤醒"：性能的巨大飞跃

原始CLH锁通过线程不断轮询前驱状态来判断是否轮到自己。这种忙等待在竞争激烈时会导致大量CPU资源浪费。

AQS的创新在于：线程经过短暂尝试后，如果未能获取锁，就会主动进入休眠，等待被唤醒。这就需要一个机制来确保释放锁的线程能准确找到下一个应该运行的线程。

双向链表中的next指针正是实现"精准唤醒"的关键：

// 释放锁时唤醒后继节点的核心逻辑Nodes=node.next;if(s!=null&&s.thread!=null){LockSupport.unpark(s.thread);}

通过next指针，释放锁的线程可以直接找到后继节点并唤醒它，实现了从"被动轮询"到"主动唤醒"的进化。

3. 状态的高效传播：共享模式的精髓

在共享模式（如Semaphore、CountDownLatch）下，资源释放可能需要连续唤醒多个等待线程。

当第一个共享节点被唤醒并获取资源后，如果还有剩余资源，它会通过next指针找到并唤醒后继节点，形成"唤醒传播链"。

// 共享模式下唤醒传播的简化逻辑if(propagate>0||h==null||h.waitStatus<0){Nodes=node.next;if(s==null||s.isShared()){doReleaseShared();// 继续唤醒后继节点}}

这种连锁反应依赖于next指针的高效遍历，是共享同步器高性能的关键。

三、实战分析：ReentrantLock中的双向链表应用

让我们看一个ReentrantLock的典型场景，了解双向链表如何工作：

ReentrantLocklock=newReentrantLock();// 线程Alock.lock();try{// 临界区操作}finally{lock.unlock();}// 同时，线程B、C、D也尝试获取锁

1. 线程A首先获取锁，state变为1
2. 线程B尝试获取失败，被加入队列：head → B（tail）
3. 线程C也获取失败，加入队尾：head → B → C（tail）
4. 线程D同样加入：head → B → C → D（tail）

此时，如果线程C因中断取消等待，双向链表的优势就体现出来了：

• 通过C的prev指针找到B，将B的next指向D
• 通过C的next指针找到D，将D的prev指向B
• C被成功移除：head → B → D（tail）

这个过程中，不需要遍历整个队列，即使队列有1000个节点，删除操作也是常量时间。

四、设计哲学的思考：空间换时间的经典权衡

AQS选择双向链表而非单向链表，体现了经典的空间换时间权衡：

• 空间开销：每个节点增加一个prev指针（8字节），在大多数场景下可忽略不计
• 时间收益：节点删除操作从O(n)提升到O(1)，唤醒操作更加精准高效

在并发编程中，减少竞争通常比优化单线程速度更重要。双向链表通过减少全局竞争，显著提升了高并发下的吞吐量。

就像城市交通规划：增加一些立体交叉桥（空间投入）可以避免主要路口的拥堵（时间收益），整体通行效率反而提升。

五、总结

AQS选择双向链表不是随意之举，而是基于以下深思熟虑：

1. 高效取消：线程中断或超时时，能快速移除节点，避免遍历开销
2. 精准唤醒：通过next指针直接定位后继节点，实现主动唤醒而非忙等待
3. 状态传播：共享模式下支持连续唤醒，提高资源利用率
4. 设计平衡：以微小空间代价换取显著性能提升

双向链表在AQS中的应用，体现了并发大师Doug Lea对实际应用需求的深刻理解。它不是理论上的最优解，而是工程实践中的最佳平衡。

下次使用ReentrantLock或CountDownLatch时，不妨想想背后那个默默工作的双向链表，正是这个看似简单的数据结构，支撑起了Java并发编程的半壁江山。

参考文档

1. https://blog.csdn.net/u012503481/article/details/108185186
2. https://blog.csdn.net/hlqionga/article/details/148868791
3. https://segmentfault.com/a/1190000046120153
4. https://blog.csdn.net/weixin_58316280/article/details/145604477
5. https://blog.csdn.net/Cobbyer/article/details/106316582
6. http://www.cnblogs.com/hanease/p/14897445.html
7. https://blog.csdn.net/weixin_48302711/article/details/126793986

本文由Java并发技术爱好者撰写，欢迎关注公众号"后端技术精粹"获取更多深度技术解析。

---

更多技术干货欢迎关注微信公众号科威舟的AI笔记~

【转载须知】：转载请注明原文出处及作者信息