返回文章列表

用 Rust 从零实现工作窃取调度器:为什么每个线程都要有自己的队列

625 字·5 分钟阅读
Rust从零造轮子并发

前面写过线程池,用的是 Arc<Mutex<Receiver>>。它在低并发下没问题,但有一个致命瓶颈:所有工作线程抢同一把锁。

锁竞争的代价随核数增加而非线性恶化。8 核时还能忍,64 核时大部分 CPU 都花在等锁上。这就是为什么所有高性能运行时(tokio、Rayon、Go runtime、Java ForkJoinPool)都用同一种结构:工作窃取(work-stealing)。


全局队列的问题在哪

先看清问题的形状:

        ┌─────────────────┐
生产者 ->│  全局任务队列    │<- 所有 worker 在这里抢
        └─────────────────┘
           ↑ ↑ ↑ ↑ ↑ ↑
          w w w w w w w w   (每个 worker 都要拿锁)

每次取任务都要:

  1. 拿锁
  2. 从队列弹出
  3. 释放锁

三个步骤都很快,但 8 个线程每秒各取 100 万次,就是 800 万次锁操作。锁本身的开销(cache line 争抢、上下文切换)会占掉相当一部分 CPU。

更糟的是"锁被某个线程长时间持有"时的** convoy effect**:其他所有线程排队等待,吞吐骤降。

工作窃取的核心:每线程一个队列

工作窃取的思路很直接:不共享队列,每个 worker 有自己的队列。

       ┌──────────┐  ┌──────────┐  ┌──────────┐
worker0│ 队列 [..] │  │ 队列 [..] │  │ 队列 [..] │worker2
       └──────────┘  └──────────┘  └──────────┘
            ↑              ↑              ↑
        本地 push/pop   本地 push/pop   本地 push/pop
          (无锁)         (无锁)          (无锁)
 
       偷不到 → 从别人的队列尾部拿

规则是:

  • 每个 worker 从自己队列的一端取任务(叫"头")
  • 空闲的 worker 从别人队列的另一端偷(叫"尾")
  • 本地操作占绝大多数,几乎不需要同步

为什么本地和窃取要用不同的端? 这是整个设计最关键的一点:

worker A 的队列:  [头 .......... 尾]
                   ↑            ↑
              A 自己在这里      别人从这里偷
              push / pop

如果两端都从同一端操作,本地线程和窃取线程会频繁争抢同一个位置。分两端之后,只有队列接近空或接近满时才会真正冲突。

工作窃取的本质是"用队列分离换取无锁",而两端分离是把冲突降到最低的关键技巧。

那个特殊的 deque

工作窃取需要的队列不是普通的 VecDeque,而是一个两端并发访问语义不同的 deque:

端 谁访问 并发度
头(本地) 只有 owner 无锁,但必须和"最后一个元素"的窃取处理竞争
尾(窃取) 任意其他 worker CAS 循环

这就是 Chase-Lev deque。它有一条非常精妙的规则:

当头尾只差一个元素时,本地取任务要用 CAS,而且要和其他窃取者竞争。

use std::sync::atomic::{AtomicIsize, Ordering};
 
pub struct Worker<T> {
    /// 环形缓冲区
    slots: Box<[std::cell::UnsafeCell<Option<T>>]>,
    /// 头指针:只有 owner 修改
    head: AtomicIsize,
    /// 尾指针:owner 和窃取者都可能修改
    tail: AtomicIsize,
    mask: isize,
    capacity: isize,
}

先实现那个"环形缓冲区 + 位掩码"的容量计算:

impl<T> Worker<T> {
    pub fn new(capacity: usize) -> Self {
        // 容量必须是 2 的幂,这样可以用 & 代替 %
        assert!(capacity.is_power_of_two());
 
        let slots = (0..capacity)
            .map(|_| std::cell::UnsafeCell::new(None))
            .collect::<Vec<_>>()
            .into_boxed_slice();
 
        Self {
            slots,
            head: AtomicIsize::new(0),
            tail: AtomicIsize::new(0),
            mask: (capacity - 1) as isize,
            capacity: capacity as isize,
        }
    }
 
    fn index(&self, pos: isize) -> usize {
        (pos as usize) & (self.mask as usize)
    }
}

容量必须是 2 的幂——这样就可以用位与代替取模。这是所有环形缓冲区的通用技巧。

本地 push:只有自己写

    /// 只有 owner 调用,不需要任何原子操作(除了 tail 的发布)
    pub fn push(&self, task: T) -> Result<(), T> {
        let head = self.head.load(Ordering::Relaxed);
        let tail = self.tail.load(Ordering::Relaxed);
 
        if head - tail >= self.capacity {
            return Err(task); // 满了
        }
 
        unsafe {
            *self.slots[self.index(head)].get() = Some(task);
        }
 
        // Release:让窃取者能看到刚写入的内容
        self.head.store(head + 1, Ordering::Release);
        Ok(())
    }

注意 head 用 Relaxed 读、Release 写。 读的时候只有自己写,不用同步;写的时候要发布给窃取者,必须 Release。

本地 pop:从头部取

    /// owner 从头部取任务
    pub fn pop(&self) -> Option<T> {
        let head = self.head.load(Ordering::Relaxed) - 1;
        self.head.store(head, Ordering::Relaxed);
 
        // 关键:写完之后要 fence,保证和窃取者的 CAS 有序
        std::sync::atomic::fence(Ordering::SeqCst);
 
        let tail = self.tail.load(Ordering::Relaxed);
 
        if tail <= head {
            // 队列非空,且不是"最后一个元素"
            let task = unsafe { (*self.slots[self.index(head)].get()).take() };
            return task;
        }
 
        if tail == head + 1 {
            // 这是最后一个元素,可能正在被窃取者拿
            return self.pop_last(head, tail);
        }
 
        // 队列空,把 head 恢复
        self.head.store(head + 1, Ordering::Relaxed);
        None
    }
 
    /// 处理"最后一个元素"的竞争
    fn pop_last(&self, head: isize, _tail: isize) -> Option<T> {
        // 尝试把 tail 推进一格,标记"这个位置被你占了"
        let new_tail = head + 1;
 
        if self.tail
            .compare_exchange(new_tail, new_tail + 1, Ordering::SeqCst, Ordering::SeqCst)
            .is_ok()
        {
            // CAS 成功:窃取者没抢到,这个元素归我
            unsafe { (*self.slots[self.index(head)].get()).take() }
        } else {
            // CAS 失败:窃取者抢先了,队列已空
            self.head.store(head + 1, Ordering::Relaxed);
            None
        }
    }

pop_last 就是 Chase-Lev deque 的精髓。 当只剩一个元素时,本地 pop 和窃取者可能同时想拿:

  • 本地想"从头部取"
  • 窃取者想"从尾部取"
  • 但队里只有一个——它既是头也是尾

解法是让 tail 成为仲裁点:本地 pop 通过 CAS 争抢 tail 的所有权。抢到就归自己,抢输就说明被偷走了。

fence(SeqCst) 那一步不能省。 它的作用是保证"减小 head"和"读取 tail"之间有一个全序屏障——否则在某些架构上,窃取者可能看到旧的 tail 值而误判。

Chase-Lev deque 最反直觉的地方是:本地 pop 也需要 CAS,但只在"最后一个元素"时。 这是它比"全程加锁"快几个数量级的原因。

窃取:从尾部 CAS 抢

    /// 任意线程调用,从尾部偷一个
    pub fn steal(&self) -> Option<T> {
        loop {
            let tail = self.tail.load(Ordering::Acquire);
            let head = self.head.load(Ordering::Acquire);
 
            if tail >= head {
                return None; // 空
            }
 
            let task = unsafe { (*self.slots[self.index(tail)].get()).take() };
 
            // CAS:只有我能把这个尾位置"占掉"
            if self.tail
                .compare_exchange(tail, tail + 1, Ordering::SeqCst, Ordering::Relaxed)
                .is_ok()
            {
                return task;
            }
            // CAS 失败说明有人抢先了,重试
        }
    }

Acquire 读 head 是必需的:如果看到 head 已经推进,就要能看到 owner 写入的任务内容(push 里用的是 Release,两者配对)。

把 worker 和 stealer 分离

有个 Rust 类型系统上的细节需要注意:pop 和 steal 不能同时持有同一个 Worker 的可变引用。

标准做法是把它们拆成两个类型:

pub struct Worker<T> {
    inner: std::sync::Arc<Deque<T>>,
}
 
pub struct Stealer<T> {
    inner: std::sync::Arc<Deque<T>>,
}
 
impl<T> Worker<T> {
    /// 每个队列只能有一个 Worker
    pub fn new(capacity: usize) -> (Worker<T>, Stealer<T>) {
        let deque = std::sync::Arc::new(Deque::new(capacity));
        (Worker { inner: deque.clone() }, Stealer { inner: deque })
    }
}

Stealer 是 Clone + Send + Sync 的,可以分发给其他线程;Worker 不实现 Clone,保证"每个队列只有一个本地所有者"。

这是"用类型系统表达并发约束"的典型例子——不用文档说"每个队列只能一个 owner",编译器直接保证。

调度器主循环

pub struct Scheduler {
    workers: Vec<Worker<Job>>,
    stealers: Vec<Stealer<Job>>,
}
 
impl Scheduler {
    pub fn run(self, worker_id: usize) {
        let worker = &self.workers[worker_id];
 
        loop {
            // 1. 先看自己的队列
            if let Some(job) = worker.pop() {
                job();
                continue;
            }
 
            // 2. 自己空了,去做别的事(比如处理 IO、检查关闭信号)
            if let Some(job) = self.poll_external() {
                job();
                continue;
            }
 
            // 3. 还是没有,去偷
            let mut stolen = false;
            for i in 0..self.stealers.len() {
                let victim = (worker_id + i + 1) % self.stealers.len();
                if let Some(job) = self.stealers[victim].steal() {
                    job();
                    stolen = true;
                    break;
                }
            }
 
            // 4. 偷不到,短暂让出
            if !stolen {
                std::hint::spin_loop();
                std::thread::yield_now();
            }
        }
    }
}

窃取的顺序:轮询而不是随机

上面用的是 (worker_id + i + 1) % n——从自己的下一个开始,依次轮询。

为什么不随机?因为局部性好。相邻的 worker 通常在同一个 NUMA 节点上,偷它们的任务,数据更可能还在缓存里。

窃取顺序的选择对大规模系统影响不小:

策略 优点 缺点
随机 简单,负载分散快 缓存局部性差
轮询(顺序) 局部性好 可能导致"互相偷"
优先偷"最忙的" 平衡快 需要额外维护负载信息

Go runtime 用的是"随机起点 + 遍历",tokio 用的是 worker 之间的直接 steal 循环。 顺序遍历自己的邻居通常是更好的默认选择。

一个容易忽略的点:任务本地性

工作窃取有个隐含的假设:任务最好在被提交的那个 worker 上执行。

这带来的一个重要性质是"亲和性":如果任务 A 创建了任务 B,B 会被 push 到 A 所在 worker 的队列头部,下一次就优先执行。

这个性质对"任务树"特别有用:

任务 A 拆分成 B、C、D
├── B 执行完,可能会再拆出 B1、B2
└── 这些都在同一个 worker 的队列里,LIFO 顺序

用 LIFO(后进先出,从头部取)而不是 FIFO,能保证"深度优先"的遍历顺序,从而让相关任务在同一个 worker 上连续执行,缓存友好。

这也是为什么工作窃取的本地端是"栈",窃取端是"队列"——本地 LIFO 保证局部性,窃取 FIFO 保证最早提交的任务先被执行。

背压与有界队列

前面实现里 push 返回 Result<(), T>,满了就失败。真实调度器怎么处理?

方案一:让 push 阻塞。 但阻塞会卡住整个 worker 线程,而在工作窃取里,worker 阻塞是灾难——它会让所有想偷它任务的线程也拿不到东西。

方案二:溢出到全局队列。 本地队列满了,把新任务放进共享的全局队列,由空闲 worker 去取。

    pub fn spawn(&self, job: Job) {
        // 1. 优先放本地
        if self.local.push(job.clone()).is_ok() {
            return;
        }
        // 2. 本地满,放全局
        self.global_queue.lock().unwrap().push_back(job);
    }

方案三:让提交方感知背压。 返回失败,由调用方决定重试还是降级。这是最可控的做法,适合已有背压机制的系统。

关键原则:worker 线程本身永远不能因为队列满而阻塞。 因为工作窃取的调度依赖"其他 worker 主动来偷",一个卡住的 worker 会拖累整个池。

在工作窃取模型里,阻塞是"传染"的。 这也是为什么 tokio 明确区分了"异步任务"和"阻塞任务"(spawn_blocking 会放进完全独立的线程池)。

和全局队列的实测差异

用一个简单的对比来感受差距(8 核,每任务极短):

结构 吞吐 说明
Mutex<VecDeque> 1× 基准
分片(N 个 Mutex 队列) 3-4× 锁竞争降低
工作窃取 5-8× 几乎无锁

差距的来源很明确:全局队列时,每次取任务都要经过一次 cache line 的争抢(锁变量所在的缓存行会在多个核之间来回弹跳)。工作窃取时,本地操作只碰自己的缓存行。

什么时候不该用工作窃取

工作窃取不是万能的:

1. 任务粒度太粗时没收益。 如果每个任务要跑 100ms,任务队列的同步开销占比微乎其微,全局队列完全够用。工作窃取是为"百万级/秒的细粒度任务"准备的。

2. 任务是 IO 密集时会被浪费。 工作窃取假设"任务都是 CPU 密集",被偷走的任务能在别的核上真正并行跑。如果任务是阻塞 IO,偷来也只是换个线程挂起——这时应该用异步 IO,而不是加更多线程。

3. 调试难度显著上升。 任务在哪执行变得不确定,任务顺序也不确定。追踪一个"偶发只在某台机器上出现"的任务顺序 bug,成本很高。

结论

工作窃取把"避免锁竞争"这个目标推到了极致:

每线程一个队列 → 本地操作无锁 → 只在空闲时跨线程偷 → 用两端分离(本地头、窃取尾)把冲突降到最低 → 用 Chase-Lev 的 CAS 处理"最后一个元素"的竞争。

它的三个设计要点值得记住:

  1. 本地 LIFO,窃取 FIFO:前者保证缓存局部性(深度优先),后者保证任务大致按提交顺序执行
  2. 本地 pop 只在"最后一个元素"时用 CAS:这是它无锁的前提
  3. worker 永远不能阻塞:否则会传染整个池

理解了这些,你再看 rayon 的 join、tokio 的 work-stealing runtime、Go 的 GMP 调度——它们都是在 Chase-Lev deque 这个底座上,各自加上了自己的任务类型和窃取策略。 下一篇我们看一个更底层的问题:如果没有操作系统线程的帮助,怎么在自己的用户态实现"协程"。