crossbeam-deque
工作窃取调度器的标准配置是：每个线程一个自己的双端队列，自己从一头放、一头取；闲下来的线程到别人的队列另一头去「偷」；另外有一个所有人共享的全局队列，接收从外面提交进来的任务。crossbeam-deque 提供的正是这三样：Worker（自己的队列）、Stealer（别人手里的窃取端）、Injector（全局队列），外加一个表示窃取结果的 Steal<T>。
rayon 的线程池就建在它上面（rayon-core 1.13.0 的 registry.rs 第 10 行：use crossbeam_deque::{Injector, Steal, Stealer, Worker};）。读完这一部分再读 rayon 卷，调度循环里的每一次 pop / steal 都能对上这里的源码。
flowchart LR
ext["外部线程 spawn"] -->|"push"| inj["Injector：64 槽一块的块链表"]
subgraph t1["工作线程 1"]
w1["Worker（push / pop）"]
end
subgraph t2["工作线程 2"]
w2["Worker（push / pop）"]
end
inj -->|"steal / steal_batch_and_pop"| w1
inj -->|"steal / steal_batch_and_pop"| w2
w1 -.->|"Stealer::steal：从对端偷"| w2
w2 -.->|"Stealer::steal：从对端偷"| w1
整个 crate 只有一个源文件 deque.rs，2261 行（含文档注释和例子），lib.rs 106 行是模块文档。按行号大致分成四块：
| 行 | 内容 | 章 |
|---|---|---|
| 1–163 | 索引类型、常量、Buffer、Inner | Chase-Lev 双端队列、扩容与回收 |
| 164–1209 | Flavor、Worker、Stealer 及全部窃取方法 | 同上，加 Steal、Retry 与批量窃取 |
| 1210–2078 | Slot、Block、Injector | Injector |
| 2079–2261 | Steal<T> 与 FromIterator | Steal、Retry 与批量窃取 |
四章：
- Chase-Lev 双端队列：任务主线的主体。
Inner{front, back, buffer}，单主人的Worker（!Sync）和可克隆的Stealer；FIFO 与 LIFO 两种 flavor；push、pop、steal逐行读，每个Ordering和 SeqCst fence 在和谁配对。实验 E5：用 loom 自写一个固定容量的版本，去掉任一处 SeqCst fence，loom 都报出同一个任务被取了两次。 - 扩容与回收：容量从 64 起翻倍、长度不到四分之一时减半；旧 buffer 交给 epoch，不小于 1 KiB 时立刻 flush；
Buffer::read/write用 volatile 访问，源码注释自认「技术上是 UB」。 - Steal、Retry 与批量窃取：
Retry为什么不能当Empty（实验 E4）；steal_batch一次最多 32 个；FIFO 与 LIFO 之间批量窃取时的顺序；rayon 怎么处理Retry。 - Injector：全局队列是 63 槽一块的无锁块链表，和
SegQueue、list channel 同构；HAS_NEXT位；批量窃取直接搬进Worker的 buffer。
和 tokio 本地队列对照
tokio 卷的本地队列里讲过：tokio 在 2019 年以前用的就是 crossbeam 的 Chase-Lev deque，#1657 换成了固定 256 槽的环形缓冲。两边的取舍在这一部分的几章里会反复出现，先列在这里：
crossbeam-deque Worker | tokio 本地队列 | |
|---|---|---|
| 容量 | 从 64 起按 2 的幂增长，可缩小 | 固定 256 |
| 满了 | 扩容，旧 buffer 交给 epoch 回收 | 把一半挪进全局注入队列 |
| 主人从哪头取 | FIFO 或 LIFO，构造时选 | 只从队头（FIFO），LIFO 效果靠外面的一个槽 |
| 窃取 | 一次一个，或一批（最多 32） | 一次偷一半，两次 CAS |
| 回收旧内存 | 需要 epoch（每次 steal 都 pin） | 不需要（buffer 不换） |
| 全局队列 | Injector：无锁块链表 | Mutex + 侵入式链表（全局注入队列） |
| 槽的读写 | volatile，非原子 | UnsafeCell + ptr::read，靠两段式认领避免并发读写同一槽 |
本部分的实验
| # | 目录 | 看什么 | 章 |
|---|---|---|---|
| E4 | exp-crossbeam/survey/（规划阶段）、exp-crossbeam/deque-retry/ | 窃取不丢不重；把 Retry 当 Empty 的后果；steal 与 steal_batch_and_pop 的调用次数、Retry 次数和耗时 | Steal、Retry 与批量窃取 |
| E5 | exp-crossbeam/loom-chase-lev/ | 用 loom 原子写一个固定容量的 Chase-Lev，完整版通过，去掉 pop 或 steal 的 SeqCst fence 都被抓到 | Chase-Lev 双端队列 |
crossbeam-deque 本身不能在 loom 下跑：它用的是 std::sync::atomic，没有 epoch 和 utils 那样的 crate::primitive 切换层。所以 E5 只能自写模型。实验机器 M2 Max（8P + 4E），macOS，rustc 1.99.1，--release。
发布之后
main 上的 deque.rs 和 0.8.8 有一百多行差异，逐行看都是写法上的：std:: 换成 core:: / alloc::、unsafe fn 里补显式 unsafe {}（unsafe_op_in_unsafe_fn）、(len + 1) / 2 换成 div_ceil(2)、Block::new 改走一个统一的分配辅助函数（0240f82d「Add helper for safer allocation」）。没有改动算法或内存序。上游仓库另有两条把 volatile 访问换成「按字节原子 memcpy」的分支，都没有合并进 main，见扩容与回收。