bigywater.tech
Java · 171

ConcurrentLinkedQueue:无锁队列如何入队出队

无锁队列是怎么入队出队的?什么时候不如带锁队列?这篇不画 CAS 的示意图,而是直接测它的弱一致性、size 的代价、顺序保证和线程数增加时的吞吐(BlockingQueue 的阻塞语义见前一篇)。

2,099 → 2,648,479 ns
ConcurrentLinkedQueue.size():1000 个 → 100 万个元素
0 次乱序
4 个生产者并发入队后,每个生产者自己元素的出队乱序次数
88.4 → 8.7
ConcurrentLinkedQueue 1 → 8 线程的吞吐(百万次/秒)

弱一致

实测 · 本机执行输出 
  队列 [1,2,3] 先创建迭代器,之后 add(4)、remove(2)、add(5):迭代器看到 [1, 3, 4, 5](弱一致:不抛 ConcurrentModificationException,看到的是创建迭代器之后又发生的部分变化)
  add(null) → NullPointerException(不允许 null 元素)
  空队列 poll() = null,peek() = null(不阻塞)

size 的代价

实测 · 本机执行输出 
      1,000 个元素:ConcurrentLinkedQueue.size() 2,099 ns;LinkedBlockingQueue.size() 16 ns;ConcurrentLinkedQueue.isEmpty() 44 ns
    100,000 个元素:ConcurrentLinkedQueue.size() 229,068 ns;LinkedBlockingQueue.size() 4 ns;ConcurrentLinkedQueue.isEmpty() 21 ns
  1,000,000 个元素:ConcurrentLinkedQueue.size() 2,648,479 ns;LinkedBlockingQueue.size() 0 ns;ConcurrentLinkedQueue.isEmpty() 10 ns

顺序

实测 · 本机执行输出 
  4 个生产者各并发入队 200000 个元素,单线程依次出队:共 800000 个,每个生产者自己的元素出队顺序乱序的次数 = 0(每个生产者内部保持先进先出);不同生产者的元素在队列里交错了 382735 次

吞吐

实测 · 本机执行输出 
  ConcurrentLinkedQueue  1 个线程各自反复 offer+poll:88.4 百万次操作/秒
  ConcurrentLinkedQueue  2 个线程各自反复 offer+poll:22.4 百万次操作/秒
  ConcurrentLinkedQueue  4 个线程各自反复 offer+poll:9.7 百万次操作/秒
  ConcurrentLinkedQueue  8 个线程各自反复 offer+poll:8.7 百万次操作/秒
  LinkedBlockingQueue    1 个线程各自反复 offer+poll:57.1 百万次操作/秒
  LinkedBlockingQueue    2 个线程各自反复 offer+poll:13.2 百万次操作/秒
  LinkedBlockingQueue    4 个线程各自反复 offer+poll:29.5 百万次操作/秒
  LinkedBlockingQueue    8 个线程各自反复 offer+poll:34.9 百万次操作/秒

分步演示

ConcurrentLinkedQueue
本步的对象

    本文用到的工具与边界

    • 本机 macOS 27 arm64 / OpenJDK(Temurin 17.0.20、Homebrew 21.0.12 与 27,每篇注明实际用的版本);用 javac 编译、java 直接运行,需要第三方库时用 Maven 解析依赖;计时用 System.nanoTime,数字每次运行会有小幅抖动。JDK 21.0.12,10 核
    • 没有验证:CAS 失败重试的具体次数、head/tail 懒更新的内部细节、ConcurrentLinkedDeque、不同负载形态(生产者与消费者分开、队列很长)下的吞吐对比、JDK 17 与 27;吞吐是自写循环的一次运行
    京ICP备2026067502号-1京公网安备11010502063487号