如何通过 ConcurrentLinkedQueue 的 Michael-Scott 非阻塞算法理解高并发队列

轻墨大大_1475

轻墨大大_1475

2026-04-16

792人浏览

原创

concurrentlinkedqueue 的 head 指向哑节点、tail 可能滞后,是为在无锁下安全实现 offer/poll;它通过一次性节点避免 aba 问题,offer 性能优于 poll,无界且不阻塞,不适合需容量控制或等待语义的场景。

如何通过 concurrentlinkedqueue 的 michael-scott 非阻塞算法理解高并发队列

ConcurrentLinkedQueue 的 head/tail 指针为什么不是直接指向首尾元素?

因为 Michael-Scott 算法要求 head 始终指向一个“哑节点”(dummy node),而不是实际数据节点;tail 则可能指向最后一个节点,也可能指向倒数第二个节点。这种设计不是偷懒,而是为了在无锁前提下安全地完成出队(poll)和入队(offer)——避免 CAS 失败后无法判断当前结构是否已变更。

关键点在于:出队时先用 CAS 尝试把 head 从哑节点推进到下一个节点,再取该节点的 item;如果失败,说明其他线程刚完成了这步,那就重试读取新的 head。整个过程不依赖锁,也不阻塞。

  • head 和 tail 都是 volatile 字段,确保多核 CPU 上的可见性
  • 每次 CAS 前都重新读取一次最新值,构成“读-改-写”循环,这是非阻塞算法的典型模式
  • 不保证实时一致性:迭代器创建后看到的是快照,后续的 offer/poll 不会影响它

为什么 ConcurrentLinkedQueue 不怕 ABA 问题,而自己手写容易翻车?

ABA 问题本质是:某个线程读到地址 A,另一线程把 A 改成 B 再改回 A,第一个线程的 CAS 误判为“没变”,导致逻辑错误。ConcurrentLinkedQueue 用的是指针地址比较,不是值比较 —— 即使新节点的 item 和旧节点一样,只要内存地址不同,CAS 就不会成功。

但它真正绕过 ABA 的关键是:所有节点一旦被出队,就不再复用(不回收、不 reset、不放回对象池)。也就是说,Node 实例是“一次性”的,地址永远只用一次。这比用版本号或 epoch 更轻量,也避免了复杂内存回收机制。

  • 手写无锁队列时若尝试复用节点(比如用对象池),就必须引入 Hazard Pointer 或 EBR,否则大概率崩溃
  • ConcurrentLinkedQueue 的 Node 构造器是私有的,且内部不暴露引用,防止外部篡改或复用
  • 它的 CAS 调用全部基于 UNSAFE.compareAndSwapObject,操作目标是字段偏移量,不是值本身

offer() 和 poll() 的性能差异为什么比想象中大?

offer() 在绝大多数情况下是单次 CAS:更新 tail.next,再尝试推进 tail;而 poll() 可能触发两次 CAS:先推进 head,再清空原 head.next.item。更关键的是,poll() 还要处理 head == tail 的边界情况(比如队列只剩一个真实节点),这时需要额外校验并重置 tail。

实测表明,在高争用(大量线程同时 poll)场景下,poll() 的失败重试概率明显高于 offer()。这不是 bug,而是 Michael-Scott 算法对“出队优先级”更低的权衡结果 —— 它优先保障入队吞吐,出队则接受一定延迟。

  • 当队列长期为空又高频 poll(),会频繁触发 head == tail 分支,性能下降更明显
  • 没有 size() 的精确实现,是因为遍历链表算长度会破坏无锁性;isEmpty() 也只是检查 head == tail 是否成立,不保证绝对准确
  • 如果你的应用里消费速率远高于生产速率,得小心 poll() 成为瓶颈,考虑换用 LinkedBlockingQueue 配合合理阻塞策略

什么时候不该用 ConcurrentLinkedQueue?

它不适合需要强一致语义或容量控制的场景。比如你希望队列最多存 1000 个任务,满了就拒绝新任务 —— ConcurrentLinkedQueue 是无界的,offer() 永远返回 true,不会拒绝。这时候必须靠上层加限流(如 Semaphore)或换用 ArrayBlockingQueue。

另一个常被忽略的点:它不提供任何等待能力。如果业务逻辑依赖“队列空时等新任务来”,你就得自己包装一层轮询 + Thread.sleep(),或者干脆用阻塞队列。别试图用 while (queue.isEmpty()) {} 自旋,那只会吃满 CPU。

  • 秒杀系统里用它做任务缓冲没问题,但订单去重、库存扣减这类需原子事务的操作,不能只靠它保证一致性
  • 日志收集场景常用它,但要注意:如果下游写磁盘慢,队列会无限增长,最终 OOM —— 必须配监控+告警+降级开关
  • 它和 ConcurrentLinkedDeque 共享同一套底层逻辑,但后者支持双端操作,代价是更复杂的 CAS 序列,别为了“看起来更通用”而误选
真正难的不是看懂 CAS 循环,而是理解 Michael-Scott 算法在“正确性”“性能”“实现复杂度”三者之间的取舍点 —— 比如为什么宁可让 tail 滞后两步,也不用额外锁同步;为什么宁愿放弃 size() 精确值,也要保住 wait-free 特性。这些设计选择,往往比代码本身更值得细读。
PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
java
java

Java是一个通用术语,用于表示Java软件及其组件,包括“Java运行时环境 (JRE)”、“Java虚拟机 (JVM)”以及“插件”。php中文网还为大家带了Java相关下载资源、相关课程以及相关文章等内容,供大家免费下载使用。

2023.06.15

10977

6

java正则表达式语法
java正则表达式语法

java正则表达式语法是一种模式匹配工具,它非常有用,可以在处理文本和字符串时快速地查找、替换、验证和提取特定的模式和数据。本专题提供java正则表达式语法的相关文章、下载和专题,供大家免费下载体验。

2023.07.05

8082

9

java自学难吗
java自学难吗

Java自学并不难。Java语言相对于其他一些编程语言而言,有着较为简洁和易读的语法,本专题为大家提供java自学难吗相关的文章,大家可以免费体验。

2023.07.31

7012

8

java配置jdk环境变量
java配置jdk环境变量

Java是一种广泛使用的高级编程语言,用于开发各种类型的应用程序。为了能够在计算机上正确运行和编译Java代码,需要正确配置Java Development Kit(JDK)环境变量。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

2023.08.01

1184

3

java保留两位小数
java保留两位小数

Java是一种广泛应用于编程领域的高级编程语言。在Java中,保留两位小数是指在进行数值计算或输出时,限制小数部分只有两位有效数字,并将多余的位数进行四舍五入或截取。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

2023.08.02

968

3

java基本数据类型
java基本数据类型

java基本数据类型有:1、byte;2、short;3、int;4、long;5、float;6、double;7、char;8、boolean。本专题为大家提供java基本数据类型的相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.02

1416

5

java有什么用
java有什么用

java可以开发应用程序、移动应用、Web应用、企业级应用、嵌入式系统等方面。本专题为大家提供java有什么用的相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.02

2889

5

java在线网站
java在线网站

Java在线网站是指提供Java编程学习、实践和交流平台的网络服务。近年来,随着Java语言在软件开发领域的广泛应用,越来越多的人对Java编程感兴趣,并希望能够通过在线网站来学习和提高自己的Java编程技能。php中文网给大家带来了相关的视频、教程以及文章,欢迎大家前来学习阅读和下载。

2023.08.03

20171

3

配置java环境变量
配置java环境变量

配置Java环境变量是为了让操作系统能够识别和使用Java的相关命令和功能。本专题为大家提供配置java环境变量相关文章,帮助大家解决问题。

2023.08.03

1275

8

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 133.9万人学习