JDK 21 · DUAL QUEUE · DUAL STACK · CAS · PARK / UNPARK · SLACK · JSR-166
一条链表,排着的要么全是货,要么全是等货的人
这两个类底层是同一个算法:双重队列(dual queue)。链表里的节点要么是数据(放进来的货),要么是请求(等着取货的空位)。来一个反方向的操作,就找到第一个还没配对的节点,用一次 CAS 改掉它的 item,交接当场完成,等着的那个线程被直接叫醒。SynchronousQueue 只做同步交接,默认按栈(后来的先配),公平模式按队列;LinkedTransferQueue 让放的人自己选:放下就走(put),还是等到被取走(transfer)。
假设场景面试时被追问:“Executors.newCachedThreadPool() 为什么用 SynchronousQueue?突发流量下线程为什么会暴涨?SynchronousQueue 容量是 0,那等着的线程排在哪?”上一页里 HikariCP 递交连接用的也是它。本页偏实现和面试,源码以 JDK 21.0.2 之后的新实现为准(JDK 22 引入,回移到了 21u),也对照 JDK 8~17 的老实现。标“实测”的数字在本机跑过:2 核 ARM 虚拟机,JDK 11.0.32 和 21.0.12。
①要解决的问题:把东西亲手交给另一个线程
有一类场景不想要缓冲区:线程池把任务交给一个闲着的工作线程,连接池把刚还回来的连接交给正在等的人。没人接就别放,有人接就当面交。
SynchronousQueue 的定义:每一次插入都必须等到另一个线程把它取走。它“容量为 0”,可等着的线程总得有个地方排,这正是本页要回答的问题。SynchronousQueue(true) 递交连接,在 ConcurrentBag 源码 讲过。这一页往下一层,看交接点内部长什么样。②朴素做法:一把锁、一个槽位、三个条件
用会的东西写一个“容量为 0”的交接点:一把 ReentrantLock 管一个槽位。put 放进槽位后还不能走,要一直等到对方真的取走。JDK 5 的 SynchronousQueue 就是用锁实现的,今天的源码里还为了兼容 1.5 的序列化格式,留着从来不用的 qlock、WaitQueue 字段。
final ReentrantLock lock = new ReentrantLock();
final Condition slotFree = lock.newCondition(),
hasItem = lock.newCondition(),
taken = lock.newCondition();
Object item; long putSeq, takeSeq;
void put(Object e) throws InterruptedException {
lock.lock();
try {
while (item != null) slotFree.await(); // 槽里有别人的
item = e; long my = ++putSeq;
hasItem.signal(); // ① 叫醒取的人
while (takeSeq < my) taken.await(); // 等对方取走
} finally { lock.unlock(); }
}
Object take() throws InterruptedException {
lock.lock();
try {
while (item == null) hasItem.await();
Object e = item; item = null; takeSeq++;
taken.signalAll(); // ② 叫醒放的人
slotFree.signal();
return e;
} finally { lock.unlock(); }
}
/proc/self/task/*/status 读出来。1 对时朴素做法每秒 10~12 万次、每次交接正好 2.01 次切换;SynchronousQueue 默认模式每秒 63~74 万次、0.24~0.26 次切换。放的人必须等“已取走”的回信,这就多出了一次唤醒。并发一高,抢锁失败的线程还要再睡再醒,4 对时每次交接要 2.9~3.0 次切换。
4 对同时交接,朴素做法反而比 1 对慢(每秒 7 万对 11 万);双重栈从 1 对到 4 对涨了约 4 倍:线程一多,总有人正好在自旋等着,交接时不用睡下再叫醒(每次只有 0.04~0.05 次切换)。
③几种思路:等的人排在哪,交接靠什么完成
“容量为 0”只是说不存元素,等着的线程总要有地方排。几种实现的区别就在这里。
| 思路 | 等的人排在哪 | 交接怎么完成 | 顺序 | 谁在用 |
|---|---|---|---|---|
| 一把锁 + 条件变量 | 条件变量的等待队列 | 拿锁放进槽位,signal 对方,再等回信 | 看锁 | JDK 5 的 SynchronousQueue |
| 双重栈 dual stack | 一个无锁栈(Treiber 栈)的栈顶 | 新来的和栈顶配对,CAS 栈顶节点 | 后到先得 | SynchronousQueue 默认模式:JDK 6~21.0.1 是 TransferStack,21.0.2 起是 xferLifo |
| 双重队列 dual queue | 一个无锁链表队列(Michael & Scott 队列) | 新来的和第一个没配对的节点配对,CAS 它的 item | 先到先得 | SynchronousQueue(true);LinkedTransferQueue(JDK 7 起) |
| 交换器 | 一个槽位,竞争大时换成一组槽位 | 两个线程互相换东西 | 不分先后 | Exchanger:两边都既给又拿,不分生产者和消费者 |
new SynchronousQueue<>()。线程池用它:最近闲下来的线程先接活,其余的闲久了被回收。
new SynchronousQueue<>(true)。HikariCP 递交连接就用这个。
LinkedTransferQueue:transfer 等到被取走,put 放下就走,取的一方不用区分。
选择规则:先问“放的人要不要等到被取走”,再问“要不要先来先得”。本页学双重队列和双重栈:从 JDK 21.0.2 起,SynchronousQueue 的两种模式和 LinkedTransferQueue 已经共用同一套节点和等待代码,学一个就懂三个。
④关键洞察:节点就是等着的人,CAS 就是交接
打个比方:一个交接柜台前排着一列人,要么全是拿着货等人接的,要么全是空着手等货的,不会两种人混着排。来了一个反方向的人,就直接走到队首那位面前完成交接。下面把比方换成真实的结构:每个人是一个 DualNode,“交接”是对它的 item 做一次 CAS。比方对不上的地方:真实的链表里还挂着已经交接完、还没被摘掉的节点,head 也不总指着队首(见 洞察 5)。
先知道这些
CAS
compareAndSet(期望值, 新值):是期望值才改,一条 CPU 指令完成,两个线程同时做只有一个成功。JDK 里用的是 compareAndExchange,失败时顺便返回当前值。上一页用过。
park / unpark
LockSupport.park() 让当前线程睡下,unpark(t) 叫醒 t。先 unpark 后 park 也行:会留一张“许可”,park 立刻返回,所以不怕叫早了。
无锁链表队列
Michael & Scott 队列:用 CAS 改队尾节点的 next 来追加,用 CAS 改 head 来出队。ConcurrentLinkedQueue 就是它。
无锁栈
Treiber 栈:只有一个 head(栈顶),压栈和弹栈都是对 head 做一次 CAS。
洞察 1一个节点两种身份,配对就是改 item
matched() = isData != (item != null)。数据节点有货就是活的,请求节点没货就是活的。CAS 成功的那一刻就是交接完成的那一刻;CAS 只有一个人能成功,所以一份货不会被两个人拿走,一个空位也不会被填两次。超时或中断的取消也走这条路:把 item 改成一个“不可能的值”(数据节点改成 null,请求节点改成指向自己),从此这个节点也算“已配对”,别人不会再和它配。洞察 2活着的节点永远是同一种
洞察 3所有方法都是同一个 xfer(e, ns)
e 是要放的东西,null 表示要取;ns 说明配不上时怎么办。两个类的十几个方法,全落在这四种 ns 上。
SQ.offer(e) SQ.poll() LTQ.poll() LTQ.tryTransfer(e)LTQ.put LTQ.offer LTQ.add(只有 LTQ 有)SQ.offer(e, t) SQ.poll(t) LTQ.poll(t) LTQ.tryTransfer(e, t)SQ.put SQ.take LTQ.take LTQ.transfer所以 SynchronousQueue 就是“放的一方只能选 0、T、MAX”的 LinkedTransferQueue;LinkedTransferQueue 多出来的只是 ns = -1:货可以先挂在链上,没人等它。
洞察 4等的人先自旋,再登记,再睡;配对的人负责叫醒
DualNode.await 的骨架。自旋是为了省掉线程切换:如果对方马上就来,转几十纳秒就能拿到,用不着睡下再被叫醒。可转多了浪费 CPU,所以有条件、有上限。这里和上一页的“先写自己的、再读对方的”是同一个套路。洞察 5head 和 tail 可以落后一步,被甩掉的旧 head 指向自己
next 指向自己的节点,就知道自己落后了,回到 head 重来。tail 甚至可以落后到 head 之前,指着一个已经被甩掉的节点,⑤ 最后一步就是这样。洞察 6公平是队列,不公平是栈,节点和等待完全一样
公平:xferSynchronousQueue(true)、LinkedTransferQueue
不公平:xferLifoSynchronousQueue() 默认
head 字段当栈顶用,tail 永远是 null;压栈、配对都只碰栈顶。源码注释说栈在竞争小时通常更快,而且更适合线程池这类“管资源”的场景(最近用过的线程还热着),但不适合消息传递。⑤ 和 ⑥ 都会实测这一点。为什么这样设计:把“会合”压成一次 CAS
被放弃的:锁 + 槽位 + 回信
- 放的人放进槽位后还得等回信,一次交接至少两次唤醒
- 所有交接共用一把锁,并发越高越挤
- 好写,好懂,用不着想内存可见性
双重队列:等的人就是节点
- 配对的人 CAS 成功,交接就完成了,只用叫醒对方一次,自己不等回信
- 不同的交接各 CAS 各的节点;head、tail 允许落后,热点竞争更少
- 代价是复杂:死节点的清理、超时取消、旧节点的垃圾链,源码里一大半在处理这些
决定胜负的约束:交接是两个线程的会合,最贵的是线程切换(微秒级),CAS 只要几十纳秒。锁的方案天生要两次唤醒;双重队列让等待者把“回信”写在自己的节点上,配对者一次 CAS 就同时完成了交货和回信。② 的实测:每次交接的线程切换从 2~3 次降到 1 次以内,吞吐高 2~40 倍。
JDK 21.0.2 之后还有一个设计取舍:原来 SynchronousQueue 自己有一套 TransferStack / TransferQueue,和 LinkedTransferQueue 各写各的。现在 SynchronousQueue 的内部类 Transferer 直接继承 LinkedTransferQueue:公平模式用父类的 xfer,不公平模式只加了一个 xferLifo,节点和等待逻辑共用。SynchronousQueue.java 从 1168 行(JDK 17)缩到 590 行。代价见 ⑥ 版本差异。
最少的 API
var sq = new SynchronousQueue<Task>(); // 默认不公平(栈);new SynchronousQueue<>(true) 是公平(队列)
sq.put(t); // 等到有人取走
boolean ok = sq.offer(t); // 现在就有人在等才成功,否则 false
Task x = sq.take(); // 等到有人放
Task y = sq.poll(1, SECONDS); // 最多等 1 秒,超时返回 null
var q = new LinkedTransferQueue<Task>(); // 无界,先来先得
q.put(t); // 放下就走,从不阻塞
q.transfer(t); // 等到有人取走(像 SQ.put)
boolean got = q.tryTransfer(t, 1, SECONDS); // 1 秒内没人取就撤回
boolean someone = q.hasWaitingConsumer(); // 有没有人停在 take/poll 上
超时取消后节点怎么摘、自旋的具体条件、各版本差在哪、哪些方法是 O(n),放到 第⑥步。
⑤手推一遍:10 个操作,看链表怎么变
下面的演示把 JDK 21u 的 LinkedTransferQueue.xfer 原样移植成了 JS,一次只走一个操作,所以每个 CAS 都会成功。节点编号、head、tail、谁指向自己,都和 JDK 里一模一样。
开始。
| 这 10 步里看到的 | 对应 ④ 的哪一条 |
|---|---|
| 第 3、4、7、9、10 步,来的人都是一次 CAS 就完成交接,不用排队 | 洞察 1 |
| 任何时刻,活着的节点要么全是请求(第 1~2 步),要么全是数据(第 5~8 步) | 洞察 2 |
put 放下就走(第 5、6 步),transfer 要等到第 10 步才返回 | 洞察 3 |
| 第 3、9 步配对的就是 head,head 不动;第 4、7、10 步 head 才前移,旧 head 指向自己 | 洞察 5 |
一段短实现:不到 60 行的双重队列
照 JDK 6~8 里 SynchronousQueue 公平模式(TransferQueue)的经典结构写的,只保留一直等的 put 和 take,不支持超时和中断,也不做 slack。有一个哑节点当 head,判断“排着的是不是同类”看的是 tail。
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.LockSupport;
// 极简双重队列(FIFO):只有 put(等到被取走才返回)和 take,不支持超时和中断
public class MiniDualQueue<E> {
static final class Node {
final boolean isData; // true:数据节点;false:请求节点
final AtomicReference<Object> item; // 数据节点 x→null、请求节点 null→x,就是“交接”
final AtomicReference<Node> next = new AtomicReference<>();
volatile Thread waiter;
Node(Object x, boolean isData) { this.item = new AtomicReference<>(x); this.isData = isData; }
}
private final AtomicReference<Node> head, tail;
public MiniDualQueue() {
Node dummy = new Node(null, true); // 哑节点:isData 却没数据,算“已配对”
head = new AtomicReference<>(dummy); tail = new AtomicReference<>(dummy);
}
public void put(E e) { xfer(e); }
@SuppressWarnings("unchecked") public E take() { return (E) xfer(null); }
private Object xfer(Object e) {
boolean haveData = (e != null);
Node s = null;
for (;;) {
Node t = tail.get(), h = head.get();
if (h == t || t.isData == haveData) { // 空,或者排着的是同类:排到队尾
Node tn = t.next.get();
if (t != tail.get()) continue;
if (tn != null) { tail.compareAndSet(t, tn); continue; } // tail 落后了,帮它往前推
if (s == null) s = new Node(e, haveData);
if (!t.next.compareAndSet(null, s)) continue; // 别人先追加了,重来
tail.compareAndSet(t, s);
Object x = await(s, e);
if (head.get() == t) head.compareAndSet(t, s); // 帮忙把 head 推过自己
return (x != null) ? x : e;
} else { // 排着的是异类:和第一个配对
Node m = h.next.get();
if (t != tail.get() || m == null || h != head.get()) continue; // 读到的不一致,重来
Object x = m.item.get();
boolean ok = (haveData == (x == null)) && m.item.compareAndSet(x, e);
head.compareAndSet(h, m); // 不管成没成功,m 都不再是活节点了
if (!ok) continue; // 被别人抢先配对了
LockSupport.unpark(m.waiter);
return (x != null) ? x : e;
}
}
}
private Object await(Node s, Object e) { // 先自旋,再挂起
for (int spins = 128;;) {
Object x = s.item.get();
if (x != e) return x;
if (spins > 0) { spins--; Thread.onSpinWait(); }
else if (s.waiter == null) s.waiter = Thread.currentThread(); // 先登记,再复查一遍 item
else LockSupport.park(this);
}
}
}
| P 放 / C 取 | 总个数 | 结果(JDK 21 和 11 各跑一次) | 每秒(JDK 21) |
|---|---|---|---|
| 1 / 1 | 200,000 | 全部取到,和对得上,没有重复 | 40 万 |
| 4 / 4 | 400,000 | 同上 | 77 万 |
| 16 / 16 | 320,000 | 同上 | 44 万 |
| 1 / 8、8 / 1、3 / 5 | 10~80 万 | 同上 | 28~57 万 |
和 JDK 21 的 SynchronousQueue(true)(同一台机器每秒 28~67 万次)在一个量级。JDK 的版本多出来的代码,几乎都花在超时取消、中断、摘掉死节点和防垃圾链上,见 ⑥ 第三圈。
在真 JDK 上对一遍
import java.util.*;
import java.util.concurrent.*;
// 看 SynchronousQueue 和 LinkedTransferQueue 的行为;JDK 11+ 直接 java SqPeek.java
public class SqPeek {
// 让 n 个线程按 A、B、C… 的先后顺序停在 take() 上,再依次放入 1..n,看谁拿到几
static String order(BlockingQueue<Integer> q, int n) throws Exception {
var got = new ConcurrentSkipListMap<Integer, String>();
var ts = new ArrayList<Thread>();
for (int i = 0; i < n; i++) {
String name = String.valueOf((char) ('A' + i));
Thread t = new Thread(() -> { try { got.put(q.take(), name); } catch (InterruptedException e) { } });
t.start(); ts.add(t);
while (t.getState() != Thread.State.WAITING) Thread.sleep(1); // 确认它已经停住
}
for (int v = 1; v <= n; v++) q.put(v);
for (Thread t : ts) t.join();
return got.toString();
}
public static void main(String[] args) throws Exception {
System.out.println("JDK " + Runtime.version());
var tr = Class.forName("java.util.concurrent.SynchronousQueue$Transferer");
System.out.println("① SynchronousQueue$Transferer 的父类:" + tr.getSuperclass().getName());
var sq = new SynchronousQueue<String>();
System.out.println("② 没人在取:offer(\"x\") = " + sq.offer("x") + ",poll() = " + sq.poll() + ",size() = " + sq.size());
Thread waiting = new Thread(() -> { try { sq.take(); } catch (InterruptedException e) { } });
waiting.start(); while (waiting.getState() != Thread.State.WAITING) Thread.sleep(1);
System.out.println(" 有人停在 take() 上:size() = " + sq.size() + ",isEmpty() = " + sq.isEmpty() + ",offer(\"x\") = " + sq.offer("x"));
waiting.join();
System.out.println("③ 默认(不公平):" + order(new SynchronousQueue<>(), 3) + " ← 值 → 拿到它的线程");
System.out.println(" 公平 true: " + order(new SynchronousQueue<>(true), 3));
var ltq = new LinkedTransferQueue<String>();
ltq.put("a"); ltq.put("b");
System.out.println("④ LTQ put 两次就返回:size() = " + ltq.size() + ";tryTransfer(\"c\") = " + ltq.tryTransfer("c") + "(没人在等)");
ltq.clear();
Thread consumer = new Thread(() -> { try { Thread.sleep(300); System.out.println(" 消费者 300 ms 后 take() = " + ltq.take()); } catch (InterruptedException e) { } });
consumer.start();
long t0 = System.nanoTime(); ltq.transfer("d");
System.out.println(" transfer(\"d\") 等了 " + (System.nanoTime() - t0) / 1_000_000 + " ms 才返回");
consumer.join();
Thread c2 = new Thread(() -> { try { ltq.take(); } catch (InterruptedException e) { } });
c2.start(); while (c2.getState() != Thread.State.WAITING) Thread.sleep(1);
System.out.println(" 有人在等:hasWaitingConsumer() = " + ltq.hasWaitingConsumer() + ",getWaitingConsumerCount() = " + ltq.getWaitingConsumerCount() + ",size() = " + ltq.size());
ltq.put("e"); c2.join();
}
}
$ java SqPeek.java
JDK 21.0.12.1+1-1-22.04.4-Ubuntu
① SynchronousQueue$Transferer 的父类:java.util.concurrent.LinkedTransferQueue
② 没人在取:offer("x") = false,poll() = null,size() = 0
有人停在 take() 上:size() = 0,isEmpty() = true,offer("x") = true
③ 默认(不公平):{1=C, 2=B, 3=A} ← 值 → 拿到它的线程
公平 true: {1=A, 2=B, 3=C}
④ LTQ put 两次就返回:size() = 2;tryTransfer("c") = false(没人在等)
消费者 300 ms 后 take() = d
transfer("d") 等了 300 ms 才返回
有人在等:hasWaitingConsumer() = true,getWaitingConsumerCount() = 1,size() = 0
JDK 11.0.32.1+1-post-1ubuntu1-22.04-Ubuntu
① SynchronousQueue$Transferer 的父类:java.lang.Object ← 老实现:自己的 TransferStack / TransferQueue
(②~④ 和上面一字不差)
offer 没人等就失败、为什么默认模式后到先得,面试里关于这两个类的大部分问题都答得上。⑥边界和变体:线程池里的后果、源码细节、版本差异
第一圈是用错就出事的边界,第二圈是团队里该怎么用,第三圈读源码、在沙盘里自己摆操作、对比 JDK 11 和 21。
注意事项
- 现象
- 1000 个任务一下子进来、每个跑 200 ms:线程池开了 1000 个线程,
getQueue().size()一直是 0。实测 - 根源
- 线程池提交任务用的是
offer,在 SynchronousQueue 上就是“立即”模式:此刻没有空闲线程停在poll上,就失败,线程池接着新建线程。newCachedThreadPool的上限是Integer.MAX_VALUE。 - 做法
- 自己 new
ThreadPoolExecutor,给maximumPoolSize一个上限,配上拒绝策略;或者换成有界队列,让任务排队。
- 现象
- 上限 50 个线程,同样 1000 个任务:开到 50 个线程,其余 950 个全抛
RejectedExecutionException。实测 - 根源
- 同上:SynchronousQueue 不存东西,线程到上限后
offer必然失败,只剩拒绝策略可走。 - 做法
- 想“满了先排一会儿”,就别用 SynchronousQueue;用它就要接受“满了立刻拒”,并用
CallerRunsPolicy之类的策略把压力推回给调用方。
- 现象
- 有线程停在
take()上时,size()仍是 0、isEmpty()仍是 true(⑤ 第 ② 段)。监控线程池的“队列长度”永远是 0。 - 根源
- 链表里挂着的是等待者,不是可以拿走的元素。源码直接把这些方法写死了:
size()返回 0、isEmpty()返回 true。 - 做法
- 监控线程池看
getActiveCount()、getPoolSize()、getLargestPoolSize()和拒绝次数。LinkedTransferQueue 能用getWaitingConsumerCount()看有几个人在等。
- 现象
- 拿它当“能交接的队列”,生产比消费快时一直
put,内存越涨越高,最后 OOM。remainingCapacity()永远是Integer.MAX_VALUE。 - 根源
- 异步模式配不上就追加一个数据节点,然后马上返回,没有任何上限。
- 做法
- 要背压,生产者用
transfer或tryTransfer(e, timeout);或者干脆用有界的ArrayBlockingQueue。
- 现象
- 做消息传递时,几个消费者都在
poll(timeout),新来的消费者总是先拿到,最早来的那个一直等到超时。放进线程池里却是好事:每 100 ms 来一个短任务,6 秒后不公平模式只剩 1 个线程,公平模式 10 个线程都还活着。实测 - 根源
- 不公平模式是栈,总是和栈顶(最后来的)配对。线程池里最后闲下来的线程一直接活,其他线程闲满 keepAlive 就被回收。
- 做法
- 线程池保持默认;做消息传递、要按先后服务时,用
new SynchronousQueue<>(true)或 LinkedTransferQueue。
- 现象
- 在高频路径上调
size()打日志或做判断,队列一长就明显变慢;并发修改时数出来的也只是个大概。 - 根源
- 链表里混着已配对的节点,没有计数器,
size()和getWaitingConsumerCount()都是countOfMode从 head 遍历一遍。javadoc 也写着它不是常数时间。 - 做法
- 判断空不空用
isEmpty()(找到第一个活数据节点就停);要计数就自己在外面维护一个LongAdder。
- 现象
- ① 21.0.2~21.0.4、JDK 22 上,不公平 SynchronousQueue 有内存泄漏(JDK-8332154),21.0.5 和 JDK 23 修复。② JDK 21.0.2 起到 JDK 25,
LinkedTransferQueue.poll()在极少数竞争下,队列不空也可能返回 null(JDK-8371740),JDK 26 修复。 - 根源
- ① 栈模式配对后没把节点的 item 改成指向自己,用户对象被留住了,修复就是补上那两行
selfLinkItem()。②xfer里 CAS 失败后没有重来,而是接着往后走,碰到链尾就当成“没有可配对的”。 - 做法
- 用 JDK 21 的至少升到 21.0.5。② 截至 2026-11,21u-dev 和 25u-dev 的这个文件里还没有回移,依赖
poll()结果做判断的代码要能容忍偶尔的假空。
使用规范
别直接用 Executors.newCachedThreadPool(),自己 new ThreadPoolExecutor。
突发流量把线程开到几千个(坑 1)
LinkedTransferQueue 的 put 只在“消费一定跟得上”时用。
无界堆积到 OOM(坑 4)
poll(timeout)、offer(e, timeout)、tryTransfer(e, timeout)。
对面的线程挂了,自己永远停在 take / put 上
new SynchronousQueue<>(true),代码里能看出是故意的。
最早来的等待者被一直插队(坑 5)
看线程池的活跃数、线程数、最大线程数、拒绝次数;LTQ 的 size() 不放热路径。
“队列长度 0”的假象,和 O(n) 的统计开销(坑 3、坑 6)
新实现是 21.0.2 回移进来的,21.0.2~21.0.4 有内存泄漏。
不公平 SynchronousQueue 留住已交接的对象(坑 7)
读源码:xfer、await、xferLifo
574 final Object xfer(Object e, long ns) {575 boolean haveData = (e != null);576 Object m; // the match or e if none577 DualNode s = null, p; // enqueued node and its predecessor578 restart: for (DualNode prevp = null;;) {579 DualNode h, t, q;580 if ((h = head) == null && // initialize unless immediate❶581 (ns == 0L ||582 (h = cmpExHead(null, s = new DualNode(e, haveData))) == null)) {583 p = null; // no predecessor584 break; // else lost init race585 }586 p = (t = tail) != null && t.isData == haveData && t != prevp ? t : h;❷587 prevp = p; // avoid known self-linked tail path588 do {589 m = p.item;590 q = p.next;591 if (p.isData != haveData && haveData != (m != null) &&❸592 p.cmpExItem(m, e) == m) {❹593 Thread w = p.waiter; // matched complementary node594 if (p != h && h == cmpExHead(h, (q == null) ? p : q))❺595 h.next = h; // advance head; self-link old596 LockSupport.unpark(w);❻597 return m;598 } else if (q == null) {599 if (ns == 0L) // try to append unless immediate❼600 break restart;601 if (s == null)602 s = new DualNode(e, haveData);603 if ((q = p.cmpExNext(null, s)) == null) {❽604 if (p != t)❾605 cmpExTail(t, s);606 break restart;607 }608 }609 } while (p != (p = q)); // restart if self-linked❿610 }611 if (s == null || ns <= 0L)612 m = e; // don't wait613 else if ((m = s.await(e, ns, this, // spin if at or near headundefined614 p == null || p.waiter == null)) == e)615 unsplice(p, s); // cancelled616 else if (m != null)617 s.selfLinkItem();618619 return m;620 }
- 1链表还没建(head 为 null):不是“立即”模式,就把自己的节点直接 CAS 成 head。tail 先不设,懒得设。
- 2从哪开始走:tail 和自己同类,说明大概率要追加,从 tail 走;否则大概率要配对,从 head 走。
prevp防止反复从一个已经自链接的 tail 出发。 - 3判断能不能配:节点和自己不同类(
p.isData != haveData),并且它还活着(haveData != (m != null),即数据节点有货、请求节点没货)。 - 4配对就是这一个 CAS:把 item 从
m换成e。取的人把货换成 null,放的人把 null 换成货。 - 5配对的不是 head 时,才把 head 推到下一个节点(没有下一个就推到 p),旧 head 的 next 改成指向自己。这就是 slack:配对的就是 head 时,head 不动。
- 6唤醒等在这个节点上的线程,返回对方的 item(取的人拿到货,放的人拿到 null 表示成功)。
- 7走到链尾也没配上:“立即”模式到此为止,返回失败。
- 8否则 CAS 链尾的
next,把自己挂上去。 - 9追加的地方不是 tail,才顺手把 tail 推过来;是 tail 就不改,又一处 slack。
- 10
p != (p = q):往后走一步;如果q == p(节点指向自己),说明自己落后了,从头重来。 - 11异步(
ns = -1)或立即模式不等;其余在自己的节点上await,只有前驱为空或前驱还没睡(p.waiter == null)时才允许自旋。等到的是自己的e,说明被取消了,去unsplice摘掉;等到的是货,就把 item 改成指向自己,不留住用户对象。
423 final Object await(Object e, long ns, Object blocker, boolean spin) {424 Object m; // the match or e if none425 boolean timed = (ns != Long.MAX_VALUE);426 long deadline = (timed) ? System.nanoTime() + ns : 0L;427 boolean upc = isUniprocessor; // don't spin but later recheck428 Thread w = Thread.currentThread();429 if (w.isVirtual()) // don't spin❶430 spin = false;431 int spins = (spin & !upc) ? SPINS : 0; // negative when may park❷432 while ((m = item) == e) {433 if (spins >= 0) {434 if (--spins >= 0)435 Thread.onSpinWait();❸436 else { // prepare to park437 if (spin) // occasionally recheck438 checkForUniprocessor(upc);439 LockSupport.setCurrentBlocker(blocker);440 waiter = w; // ensure ordering❹441 VarHandle.fullFence();442 }443 } else if (w.isInterrupted() ||444 (timed && // try to cancel with impossible match445 ((ns = deadline - System.nanoTime()) <= 0L))) {446 m = cmpExItem(e, (e == null) ? this : null);❺447 break;448 } else if (timed) {449 if (ns < SPIN_FOR_TIMEOUT_THRESHOLD)❻450 Thread.onSpinWait();451 else452 LockSupport.parkNanos(ns);453 } else if (w instanceof ForkJoinWorkerThread) {❼454 try {455 ForkJoinPool.managedBlock(this);456 } catch (InterruptedException cannotHappen) { }457 } else458 LockSupport.park();459 }460 if (spins < 0) {461 LockSupport.setCurrentBlocker(null);462 waiter = null;463 }464 return m;465 }
167 final Object xferLifo(Object e, long ns) {168 boolean haveData = (e != null);169 Object m; // the match or e if none170 outer: for (DualNode s = null, p = head;;) {171 while (p != null) {172 boolean isData; DualNode n, u; // help collapse173 if ((isData = p.isData) != ((m = p.item) != null))❶174 p = (p == (u = cmpExHead(p, (n = p.next)))) ? n : u;175 else if (isData == haveData) // same mode; push below❷176 break;177 else if (p.cmpExItem(m, e) != m)❸178 p = head; // missed; restart179 else { // matched complementary node180 Thread w = p.waiter;181 cmpExHead(p, p.next);❹182 LockSupport.unpark(w);183 break outer;184 }185 }186 if (ns == 0L) { // no match, no wait187 m = e;188 break;189 }190 if (s == null) // try to push node and wait191 s = new DualNode(e, haveData);192 s.next = p;193 if (p == (p = cmpExHead(p, s))) {❺194 if ((m = s.await(e, ns, this, // spin if (nearly) empty195 p == null || p.waiter == null)) == e)196 unspliceLifo(s); // cancelled197 else if (m != null)❻198 s.selfLinkItem();199 break;200 }201 }202 return m;203 }
- 1虚拟线程不自旋:它 park 只是把栈卸下来,不走操作系统的线程切换,比自旋划算。
- 2可以自旋、又不是单核时,最多转 128 圈;否则直接准备睡。
- 3每圈一次
Thread.onSpinWait(),提示 CPU“我在忙等”。 - 4转完了:登记
waiter = 自己,再来一道全屏障,然后回到循环开头复查 item。这就是 ④ 里“不会漏叫”的那一半。 - 5被中断或超时:用一个“不可能的值”CAS 掉自己的 item(请求节点改成指向自己,数据节点改成 null),算取消。
- 6限时等待剩下不到约 1 µs(1024 ns)时,转着等,不再 park。
- 7不限时等待时,ForkJoinPool 的工作线程用
managedBlock等,让池子有机会补一个线程;普通线程直接park。
- 1栈顶已经配对过(或取消了):帮忙弹掉,接着看下一个。
- 2栈顶和自己同类:压在它上面等。
- 3栈顶是反方向的活节点:直接 CAS 它的 item 完成配对,失败就从新栈顶重来。
- 4配对成功:弹掉栈顶,唤醒对方。老实现要先压一个“正在配对”的节点再去配,新实现不建节点。
- 5没人可配、也不是立即模式:新节点压到栈顶,等着。
- 6等到货就把 item 改成指向自己。JDK-8332154 的修复就是补上这里的两行。
沙盘:自己摆操作,先猜再看 上面三段代码的 JS 移植版
选一个剧本,先猜结果,再一步步点“按剧本走一步”。也可以随时用下面的按钮自己加操作,让等着的线程超时,看节点怎么被摘掉。每个操作在模拟里是一口气做完的,不会被别的线程打断。
版本差异:三代实现
| JDK | SynchronousQueue | LinkedTransferQueue | 等待策略 |
|---|---|---|---|
| 5 | 一把 ReentrantLock + 等待队列 | 没有 | 锁的条件变量 |
| 6 ~ 16 含 8、11 | 自己的 TransferStack(栈顶压“正在配对”节点)和 TransferQueue | JDK 7 加入,自己的 Node 和 xfer(e, haveData, how, nanos) | 固定次数自旋:SQ 限时 32 次、不限时 512 次(单核 0 次);LTQ 最多 128 + 64 次,期间随机 yield |
| 17 ~ 21.0.1 | 结构不变 | 结构不变 | JDK-8246677 改成:自己是唯一的等待者就 yield 一次,然后 park;ForkJoin 线程用 managedBlock |
| 21.0.2+、22+ | Transferer extends LinkedTransferQueue,公平用 xfer,不公平用 xferLifo | 重写成 DualNode + xfer(e, ns),head / tail 懒初始化 | JDK-8301341 统一成 DualNode.await:符合条件时自旋 ≤128 次;虚拟线程、单核不自旋 |
这几行对着 jdk8u、jdk11u、jdk17u、jdk21u、jdk25u 和主线的源码逐个核过;“21.0.2 起”是用 GitHub 上 jdk21u 的提交和 jdk-21.0.1-ga、jdk-21.0.2-ga 标签比出来的。主线在 2026-10 还把配对时读 waiter 改成了 volatile 读(JDK-8386428,Windows ARM64 关掉 LSE 时测试超时),我查看时它还不在任何已发布的版本里。
| 实现 | 1 对 · JDK 11 | 1 对 · JDK 21 | 4 对 · JDK 11 | 4 对 · JDK 21 | 16 对 · JDK 11 | 16 对 · JDK 21 |
|---|---|---|---|---|---|---|
| SynchronousQueue(默认) | 36~41 | 63~74 | 221~237 | 264~279 | 267~297 | 223~237 |
| SynchronousQueue(true) | 25~30 | 28~31 | 146~155 | 65~67 | 114~130 | 57~58 |
| LTQ.transfer / take | 215~239 | 22~32 | 90~92 | 69~70 | 67~69 | 57~59 |
| 朴素做法(一把锁) | 11~11 | 10~12 | 7~7 | 7~8 | 6~7 | 6~7 |
各跑两遍取范围。新实现不是全面更快:在这台 2 核 ARM 机器上,公平模式和 transfer 慢了,1 对 transfer 时 JDK 11 每次交接只有 0.04 次线程切换,JDK 21 有 0.73~0.86 次。老实现自旋更久、中间还会 yield 让对方先跑,对方往往在它睡下之前就来了;新实现最多 128 次 onSpinWait,在这台机器上大多等不到就睡了。换一台核多的 x86 机器结果可能不同,这里只说明“自旋多久”这个参数确实会左右结果。
await 里不自旋,直接 park;它的 park 只是把栈卸下来,载体线程接着跑别的虚拟线程,操作系统层面几乎没有线程切换。1 对时公平模式 112 万次/秒,平台线程只有 24 万次。所以新实现给虚拟线程关掉自旋是对的。再往深一点
为什么旧 head 要指向自己
- 节点之间只有
next单向链接。一个早就出队的旧节点如果还被谁引用着(比如一个停在半路的迭代器),它后面所有更新的节点都会顺着next被留住。 - 源码注释引用了 Boehm 的论文:GC 晚一点发现某个老节点是垃圾,后面一串都回收不了。把旧 head 的
next改成指向自己,链就在这里断开。 - 代价是所有遍历都要处理“读到自链接就从头重来”,迭代器、
size()、remove(o)里都有这段。
取消的节点怎么摘:unsplice 和 sweepVotes
- 超时的节点如果在链头附近,直接把 head 推过去;在中间,就 CAS 前驱的
next跳过它。 - 两种情况摘不掉:它是链尾(新节点还要往它后面挂),或者前驱自己也死了(前驱可能已经不在链上)。这时记一票
sweepVotes,攒够 16 票(SWEEP_THRESHOLD = 15,按位与判断)就从头扫一遍,统一摘掉。老实现的阈值是 32。 - 典型触发场景:队尾的人反复
poll(短超时)又超时,队首却有一个一直不超时的take()堵着。
自旋多少才合适
- 源码注释写得很直白:太少,对方马上就来时也白白切换了一次线程;太多,烧 CPU,还挡着对方上 CPU。最优值“不可知”,现在的 128 是在测试过的平台上取的折中。
- 只有自己是第一个等的人、或前一个等待者还没睡时才转:前面的人都睡了,说明对方一时半会儿来不了,转也白转。
- 上面 JDK 11 / 21 的对比就是这个折中在一台 2 核机器上的样子。
Exchanger 为什么不用双重队列
- 双重队列里两边身份不同:一边给、一边拿。
Exchanger两边都既给又拿,谁先到谁等,后到的把自己的东西放下、拿走对方的。 - 它用一个槽位,竞争大时改用一组槽位(arena),让不同的线程对在不同的槽位上配对,减少对同一个地址的 CAS。
- JDK-8338146 改进了 Exchanger 在虚拟线程下的性能,改动也落在 LinkedTransferQueue.java 里,可见这套节点和等待代码已经是 j.u.c 的公共件。
面试官会怎么问
SynchronousQueue 容量是 0,那等着的线程排在哪?
排在一个无锁链表里:每个等着的线程对应一个节点,节点上记着它要放的东西(数据节点)或者一个空位(请求节点)。“容量为 0”说的是没有可以被拿走、却没人等着交接的元素。默认模式这个链表当栈用,公平模式当队列用。
put 和 take 是怎么配对的?
来的人顺着链表找第一个反方向的活节点,对它的 item 做一次 CAS:取的人把货换成 null,放的人把 null 换成货。CAS 成功就算交接完成,然后 unpark 节点上等着的线程。找不到就把自己挂上去,先自旋一会儿再 park。
newCachedThreadPool 为什么用 SynchronousQueue?有什么风险?
它要的语义是“有闲线程就交给它,没有就新建”,SynchronousQueue 的 offer 正好是“此刻有人在 poll 才成功”。默认的栈模式让最近闲下来的线程先接活,其余的闲满 60 秒被回收。风险是线程上限为 Integer.MAX_VALUE,突发流量下线程数会暴涨。
LinkedTransferQueue 和 SynchronousQueue、LinkedBlockingQueue 有什么区别?
它和 SynchronousQueue 是同一个双重队列算法,多了异步模式:put 放下就走,像无界的 LinkedBlockingQueue;transfer 等到被取走,像 SynchronousQueue 的 put。和 LinkedBlockingQueue 比,它不用锁,取的人在等时来货可以直接交到手里。从 JDK 21.0.2 起,SynchronousQueue 的内部类直接继承了它。
下一圈
- ThreadPoolExecutor 的
execute:核心线程、队列、最大线程三段判断和Worker的生命周期(已写成下一页) - Michael & Scott 队列和
ConcurrentLinkedQueue:ABA、帮忙推 tail、为什么 Java 不怕 ABA - AQS:
ReentrantLock和Condition内部的 CLH 队列,和双重队列对比着看 Exchanger的 arena 和ForkJoinPool.managedBlock的补偿线程- 用 jcstress 验证并发数据结构:怎么写出能抓到 JDK-8371740 这类竞争的测试
- 虚拟线程的 park / unpark:continuation 怎么卸下和挂回载体线程
↺回到第⑤步:改 MiniDualQueue 和 SqPeek
每个练习都写了做对时会看到什么。
练习 1 · 改成栈
照 xferLifo 的思路,给 MiniDualQueue 加一个不公平模式:新节点压到 head 上,来的人只看栈顶。用 SqPeek 第 ③ 段的办法测顺序。
做对了会看到:三个先后停在 take 上的线程 A、B、C,依次放 1、2、3,拿到的是 C=1、B=2、A=3;压力测试仍然一个不多一个不少。
用到:④ 洞察 6,⑥ 坑 5
练习 2 · 加上 poll(timeout)
给 MiniDualQueue 的 await 加一个截止时间:到点就把自己的 item 从 null CAS 成节点自己。CAS 失败说明刚好被配上了,要把货收下。
做对了会看到:没人放时 poll(100ms) 约 100 ms 后返回 null;在第 99 ms 放进来的货不会丢,要么被这次 poll 拿到,要么留给下一个取的人。
用到:④ 洞察 1 的“取消也是 CAS”,⑥ await 第 5 条
练习 3 · 去掉自旋看看
把 MiniDualQueue 的 spins = 128 改成 0,再改成 4096,各跑一对生产者 / 消费者,同时读 /proc/self/task/*/status 数线程切换。
做对了会看到:本机 1 对时,0 圈每次交接约 1.06 次切换、每秒 19 万次;128 圈 0.24 次、65 万次;4096 圈几乎不切换、153 万次。一直有活时转得越久越快;代价要在“对方很久才来”时才显出来:每个等着的线程都要先空转完才睡,等的人一多就把 CPU 占满。
用到:④ 洞察 4,⑥ 版本差异
1. 用一句话说出双重队列的精华。
等着的线程自己就是链表里的一个节点,来配对的人对它的 item 做一次 CAS 就完成了交接,只需要叫醒对方一次。
← ② 精华
2. 用一把锁加条件变量做交接点,痛在哪?
放的人放下后还要等回信,一次交接至少两次唤醒;所有交接挤在一把锁上。实测每次交接 2~3 次线程切换,吞吐只有双重队列的几分之一到几十分之一。
← ② 实测
3. newCachedThreadPool 线程暴涨,根源是 ④ 里的哪一条?
线程池用 offer 提交,SynchronousQueue 的 offer 是 ns = 0 的立即模式:此刻没有空闲线程停在 poll 上就失败,线程池只能新建线程。
← ④ 洞察 3
4. 预测:一个 LinkedTransferQueue 里已经有 3 份 put 进来、没人取的货,这时来一个 transfer(x),它什么时候返回?
要等到 3 份旧货都被取走、x 也被取走之后。transfer 发现排着的全是同类(数据),只能追加到队尾,按先来先得,前面 3 份先被取。
← ④ 洞察 2 + 洞察 3
5. 预测:公平的 SynchronousQueue 上 A 在 take,B 调 poll()(不带超时),会怎样?
B 立刻拿到 null。B 也是请求,和 A 同类,没法配对;poll() 是立即模式,配不上就走,不会把自己挂到链上。A 继续等。
← ④ 洞察 2 + 洞察 3
6. 预测:线程池用 new SynchronousQueue<>(true) 代替默认的,每 100 ms 来一个很短的任务,keepAlive 2 秒,池里原本有 10 个空闲线程,过一会儿还剩几个?
10 个都在。公平模式按先来先得把任务交给等得最久的线程,10 个线程轮流接活,每个每秒都有活干,没有一个闲满 2 秒。默认的栈模式则总是交给最后闲下来的那个,其余 9 个会被回收。本机实测正是 10 和 1。
← ④ 洞察 6
7. 预测:如果去掉“旧 head 的 next 指向自己”这一步,功能会错吗?
功能不会错,配对和顺序都靠 item 的 CAS 和链表顺序保证。受影响的是内存:只要还有人引用某个很老的节点,它后面所有出过队的节点都回收不了。
← ④ 洞察 5