一个任务
主线位置:主线 2 的全程,也是 rayon 卷的前置。本页只画时序和关键行,细节在 05 部分:Chase-Lev 双端队列、扩容与回收、Steal、Retry 与批量窃取。
工作窃取的形状:每个工作线程有一个自己的双端队列,自己往一端放任务、从一端取;别的线程闲下来时从另一端「偷」。crossbeam-deque 用 Worker<T> 表示主人那一侧(只能有一个,!Sync),Stealer<T> 表示窃取者那一侧(可克隆、可跨线程)。两者共享一个 Arc<CachePadded<Inner<T>>>:
struct Inner<T> {
/// The front index.
front: AtomicWorkerIndex,
/// The back index.
back: AtomicWorkerIndex,
/// The underlying buffer.
buffer: CachePadded<Atomic<Buffer<T>>>,
}
(deque.rs:132。有 64 位原子的平台上 AtomicWorkerIndex 是 AtomicI64,0.8.8 起如此,deque.rs:19-34。)任务在 [front, back) 之间;主人在 back 端 push,窃取者从 front 端偷。buffer 是一个 epoch::Atomic,因为它会被换掉,而旧的那块要等所有可能还在读它的窃取者都走开才能释放:这就是 deque 依赖 epoch 的原因。
sequenceDiagram participant O as 主人 Worker participant I as Inner front back buffer participant E as epoch participant T as 窃取者 Stealer O->>I: push:写 buffer[back],fence(Release),back+1 T->>I: steal:front.load(Acquire) T->>E: pin(自带 SeqCst fence) T->>I: back.load(Acquire),buffer.load(Acquire) T->>I: volatile 读 buffer[front] T->>I: buffer 没换且 CAS front 成功则 Success,否则 Retry O->>I: 满了:resize,复制,swap buffer(Release) O->>E: defer_unchecked 释放旧 buffer,大于 1 KiB 则 flush O->>I: LIFO pop:back-1,fence(SeqCst),读 front O->>I: 只剩一个:CAS front,和窃取者抢
push:写槽,再发布 back
pub fn push(&self, task: T) {
// Load the back index, front index, and buffer.
let b = self.inner.back.load(Ordering::Relaxed);
let f = self.inner.front.load(Ordering::Acquire);
let mut buffer = self.buffer.get();
// Calculate the length of the queue.
let len = b.wrapping_sub(f);
// Is the queue full?
if len >= buffer.cap as WorkerIndex {
// Yes. Grow the underlying buffer.
unsafe {
self.resize(2 * buffer.cap);
}
buffer = self.buffer.get();
}
// Write `task` into the slot.
unsafe {
buffer.write(b, MaybeUninit::new(task));
}
// ThreadSanitizer does not understand fences, so we omit fence and do store with Release ordering.
#[cfg(not(crossbeam_sanitize_thread))]
atomic::fence(Ordering::Release);
let store_order = if cfg!(crossbeam_sanitize_thread) {
Ordering::Release
} else {
Ordering::Relaxed
};
// Increment the back index.
self.inner.back.store(b.wrapping_add(1), store_order);
}
back只有主人写,所以Relaxed读自己的值就够了;front会被窃取者改,用Acquire。- 主人在
Worker里还缓存了一份buffer: Cell<Buffer<T>>,不用每次都去读epoch::Atomic。 - 写槽是
ptr::write_volatile,不是原子写。随后fence(Release)+Relaxed写back,等同于一次Release写:窃取者Acquire读到新的back,就一定看得到槽里的任务(本库里的内存序 第 ① 类)。 - 新建的
Worker缓冲是MIN_CAP = 64个槽。
resize:换缓冲,旧的交给 epoch
满了就 resize(2 * cap):分配新缓冲,把 [front, back) 逐个复制过去,然后
let guard = &epoch::pin();
// Replace the old buffer with the new one.
self.buffer.replace(new);
let old =
self.inner
.buffer
.swap(Owned::new(new).into_shared(guard), Ordering::Release, guard);
// Destroy the old buffer later.
guard.defer_unchecked(move || old.into_owned().into_box().dealloc());
// If the buffer is very large, then flush the thread-local garbage in order to deallocate
// it as soon as possible.
if mem::size_of::<T>() * new_cap >= FLUSH_THRESHOLD_BYTES {
guard.flush();
}
旧缓冲不能立刻释放:某个窃取者可能刚 load 到它,正要读。defer_unchecked 把释放推迟到所有当时 pin 着的线程都离开之后(这一段就是 一块内存的回收 的入口)。FLUSH_THRESHOLD_BYTES 是 1 KiB:新缓冲按字节算不小于 1 KiB 时,马上把本线程攒的垃圾推到全局队列,让大块内存早点回来。pop 在长度降到容量的 1/4 以下、且容量大于 64 时会减半,走的是同一个 resize。
steal:读 front,pin,读 back,读任务,CAS
pub fn steal(&self) -> Steal<T> {
// Load the front index.
let f = self.inner.front.load(Ordering::Acquire);
// A SeqCst fence is needed here.
//
// If the current thread is already pinned (reentrantly), we must manually issue the
// fence. Otherwise, the following pinning will issue the fence anyway, so we don't
// have to.
if epoch::is_pinned() {
atomic::fence(Ordering::SeqCst);
}
let guard = &epoch::pin();
// Load the back index.
let b = self.inner.back.load(Ordering::Acquire);
// Is the queue empty?
if b.wrapping_sub(f) <= 0 {
return Steal::Empty;
}
// Load the buffer and read the task at the front.
let buffer = self.inner.buffer.load(Ordering::Acquire, guard);
let task = unsafe { buffer.deref().read(f) };
// Try incrementing the front index to steal the task.
// If the buffer has been swapped or the increment fails, we retry.
if self.inner.buffer.load(Ordering::Acquire, guard) != buffer
|| self
.inner
.front
.compare_exchange(f, f.wrapping_add(1), Ordering::SeqCst, Ordering::Relaxed)
.is_err()
{
// We didn't steal this task, forget it.
return Steal::Retry;
}
// Return the stolen task.
Steal::Success(unsafe { task.assume_init() })
}
- 两件事共用一个 fence。 读
front和读back之间需要一个SeqCstfence(和主人pop里的那个配对);而epoch::pin()本来就要发一个SeqCstfence(一块内存的回收)。所以只有当前线程已经 pin 着(pin()是重入的,不会再发 fence)时才手动补一个。 - 先读后抢。 任务是在 CAS 之前用
read_volatile读出来的,放在MaybeUninit<T>里。CAS 成功才assume_init交出去;失败就「忘掉」它:不析构,因为它仍然属于队列,或者已经被别人拿走。读的那一刻主人可能正在往同一个槽写(缓冲绕了一圈),这是一次数据竞争;源码和 TSan 抑制文件都承认这一点,理由是读到的值只要 CAS 失败就不会被使用(怎么验证并发代码)。 - Retry 不是 Empty。 返回
Steal::Retry的意思是「队列里有东西,但这次和别人撞了」:别的窃取者先 CAS 了front,或者主人刚好换了缓冲。调用方应该再试,而不是当作队列空了。
rayon 就是这么用的:WorkerThread::steal 从随机位置开始轮询其他线程的 Stealer,碰到 Retry 记一个 retry = true,一圈下来没偷到但有过 Retry,就再来一圈。
pop:主人和窃取者抢最后一个
LIFO 的 pop 从 back 端取(deque.rs:505-563):
back减一,Relaxed写回——先「宣布」要拿走最后这个槽。fence(SeqCst)。- 读
front,算新长度。 - 长度 < 0:队列本来就空,把
back恢复。 - 长度 > 0:至少还剩一个,窃取者碰不到
back - 1这个槽,直接读走。 - 长度 == 0:这是最后一个,窃取者可能也盯着它。用
compare_exchange(front, front + 1, SeqCst)和窃取者抢front;输了就当没拿到。最后把back恢复成原值(front已经加一,队列为空)。
第 1 到 3 步和窃取者「读 front → fence → 读 back」是一对:两边都是「写或读一个,fence,再读另一个」,SeqCst fence 保证不会出现「主人看到旧的 front、窃取者看到旧的 back」,两边都以为自己独占了那个槽。真正的仲裁落在第 6 步的 CAS 和 steal 的 CAS 抢同一个 front。
FIFO 的 pop 从 front 端取,直接 front.fetch_add(1, SeqCst),和窃取者在同一端竞争。rayon 默认用 new_lifo(),breadth_first 配置下才用 new_fifo()(registry.rs:248-262)。
每一步在哪一章
| 步 | 本卷 |
|---|---|
Inner、Worker / Stealer、FIFO 与 LIFO、push / pop / steal 的完整论证 | Chase-Lev 双端队列 |
resize、volatile 读写与「技术上的 UB」 | 扩容与回收 |
Steal 三态、steal_batch、MAX_BATCH = 32 | Steal、Retry 与批量窃取 |
全局注入队列 Injector | Injector |
pin、defer_unchecked、flush | 04 epoch |
| tokio 为什么在 2019 年换掉了 crossbeam 的 deque | tokio 本地队列 |
rayon 的调度器建在这四个类型上,rayon 卷会从 registry.rs 一侧再走一遍。
小结
Worker(唯一主人)在back端 push / pop,Stealer(可克隆)从front端偷;共享Inner{front, back, buffer},buffer是epoch::Atomic。push:volatile 写槽,fence(Release)后发布back;满了resize加倍,旧缓冲defer_unchecked给 epoch,新缓冲 ≥ 1 KiB 时立即flush。steal:读front→SeqCstfence(借pin的)→ 读back→ volatile 读任务 → 确认缓冲没换且 CASfront;失败返回Retry,读出的值被丢弃。- LIFO
pop先减back、fence、再读front;只剩最后一个时和窃取者 CAS 同一个front。