Rust in Everything
基于 crossbeam-deque 0.8.8

一个任务

主线位置:主线 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

Worker::push:

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

Stealer::steal:

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 之间需要一个 SeqCst fence(和主人 pop 里的那个配对);而 epoch::pin() 本来就要发一个 SeqCst fence(一块内存的回收)。所以只有当前线程已经 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):

  1. back 减一,Relaxed 写回——先「宣布」要拿走最后这个槽。
  2. fence(SeqCst)。
  3. 读 front,算新长度。
  4. 长度 < 0:队列本来就空,把 back 恢复。
  5. 长度 > 0:至少还剩一个,窃取者碰不到 back - 1 这个槽,直接读走。
  6. 长度 == 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 = 32Steal、Retry 与批量窃取
全局注入队列 InjectorInjector
pin、defer_unchecked、flush04 epoch
tokio 为什么在 2019 年换掉了 crossbeam 的 dequetokio 本地队列

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 → SeqCst fence(借 pin 的)→ 读 back → volatile 读任务 → 确认缓冲没换且 CAS front;失败返回 Retry,读出的值被丢弃。
  • LIFO pop 先减 back、fence、再读 front;只剩最后一个时和窃取者 CAS 同一个 front。

💬 关联讨论

发起讨论
加载中...