第5章 多线程 Scheduler 与工作窃取

"A good scheduler is an art gallery — each worker paints its own canvas, but steals color from its neighbors." —— 笔者

本章要点

• Tokio multi_thread scheduler 由三个核心 struct 支撑：Core（每 worker 独占的状态）、Shared（全体 worker 共享）、Worker（worker 线程的容器）
• Worker 主循环的"三条腿"：从本地队列取、从其他 worker 偷、park 等通知
• 本地队列是一个 256 大小的环形缓冲区，用一个 AtomicUsize 同时编码两个头指针（real head + steal head）——这个位打包是 Tokio 性能的关键之一
• 工作窃取的随机起点：避免所有 idle worker 同时盯着同一个繁忙 worker，用 fastrand 从随机位置开始扫描
• LIFO slot 是每 worker 一个的"最近一个 spawn"快照——刚 spawn 的 Task 立刻被同一个 worker 上运行的 poll 调走，省掉一次入队 / 出队
• global_queue_interval = 31 意味着 worker 每处理 31 个 Task 会强制从全局队列取一个——这是保证"全局 spawn 不被本地 spawn 饿死"的公平性机制
• park / transition_to_parked / transition_from_parked 三个状态转换是 worker 线程从"忙"到"空闲休眠"的完整协议

5.1 三个核心 struct：Core、Shared、Worker

打开 tokio/src/runtime/scheduler/multi_thread/worker.rs，Tokio 1.40 的多线程调度器主要由三个嵌套的 struct 构成。原样贴出（删除了非关键字段的注释）：

// 来源：tokio-rs/tokio · tokio/src/runtime/scheduler/multi_thread/worker.rs (tokio-1.40.0)

// 每个 worker 独占、不对外共享的状态
struct Core {
    tick: u32,                                       // 每 poll 一个 Task 自增 1，用于周期性检查
    lifo_slot: Option<Notified>,                     // LIFO slot：最近 spawn 的任务立刻被谁 poll
    lifo_enabled: bool,                              // 是否启用 LIFO 优化
    run_queue: queue::Local<Arc<Handle>>,            // 本地任务队列（256 容量）
    is_searching: bool,                              // "我现在在找活儿"的标志
    is_shutdown: bool,                               // shutdown 标志
    is_traced: bool,                                 // tracing 相关
    park: Option<Parker>,                            // park/unpark 器
    stats: Stats,                                    // 调度统计
    global_queue_interval: u32,                      // 多少次后强制去全局队列取
    rand: FastRand,                                  // 工作窃取的随机源
}

// 所有 worker 共享的状态
pub(crate) struct Shared {
    remotes: Box<[Remote]>,                          // 每个 worker 对应一个 Remote（里面是 Steal 句柄）
    pub(super) inject: inject::Shared<Arc<Handle>>,  // 全局注入队列
    idle: Idle,                                      // idle worker 管理
    pub(crate) owned: OwnedTasks<Arc<Handle>>,       // 所有 Task 的"全局名册"
    pub(super) synced: Mutex<Synced>,                // 需要互斥的共享状态
    shutdown_cores: Mutex<Vec<Box<Core>>>,           // shutdown 时暂存 Core 用
    pub(super) trace_status: TraceStatus,
    config: Config,
    pub(super) scheduler_metrics: SchedulerMetrics,
    pub(super) worker_metrics: Box<[WorkerMetrics]>, // 每 worker 的 metrics
    _counters: Counters,
}

// worker 线程持有的容器
pub(super) struct Worker {
    handle: Arc<Handle>,                             // 指回 runtime Handle（进而指回 Shared）
    index: usize,                                    // 这是第几个 worker
    core: AtomicCell<Core>,                          // 用 AtomicCell 让 Core 可以被偷走
}

这三个 struct 的关系：

为什么要把状态拆成独占 + 共享？

• Core 在 worker 内独占访问：tick、lifo_slot、run_queue 这些每个 worker 频繁读写，如果共享就需要锁——变成性能毒药
• Shared 跨 worker 共享：remotes（偷任务的句柄）、inject（全局队列）、owned（全局 Task 名册）必须对所有 worker 可见
• Core 用 AtomicCell 包装：平时 worker 独占，但 shutdown 时需要"把 Core 收回来"——用 AtomicCell::take 原子地"夺走"Core

这种"按访问模式分拆"的数据结构设计是高性能并发系统的通用做法。Linux scheduler 的 rq / task_struct 分拆、Go runtime 的 P / M / G 分拆，本质上都是同一种思路：把频繁访问的数据隔离到独占域、把偶尔共享的数据集中在共享域，用不同的同步原语保护。

---

5.2 Worker 主循环：run 函数的骨架

打开 worker.rs，run 函数是每个 worker 线程的入口点。原样：

// 来源：tokio/src/runtime/scheduler/multi_thread/worker.rs
fn run(worker: Arc<Worker>) {
    let core = match worker.core.take() {
        Some(core) => core,
        None => return,
    };

    worker.handle.shared.worker_metrics[worker.index]
        .set_thread_id(thread::current().id());

    let handle = scheduler::Handle::MultiThread(worker.handle.clone());

    crate::runtime::context::enter_runtime(&handle, true, |_| {
        let cx = scheduler::Context::MultiThread(Context {
            worker,
            core: RefCell::new(None),
            defer: Defer::new(),
        });

        context::set_scheduler(&cx, || {
            let cx = cx.expect_multi_thread();
            assert!(cx.run(core).is_err());        // ← run 永远返回 Err(shutdown)
            cx.defer.wake();
        });
    });
}

这 20 行代码做了 5 件事：

1. 从 AtomicCell 里取出 Core——如果已经被别人取走（shutdown 发生），直接返回
2. 设置 worker 的 thread_id—— 用于 metrics 和 tracing
3. enter_runtime：把当前线程 thread-local 设置成"我是 Tokio 的 worker"
4. set_scheduler：再设一层 thread-local，标明"当前 scheduler 是 multi_thread"
5. 调 cx.run(core)—— 真正的调度主循环。assert!(...is_err()) 表示"它不应该 Ok 返回，要么 panic 要么 shutdown"

真正的干活在 cx.run(core) 里——这个函数在同一文件里，大致是：

// 简化自 worker.rs
impl Context {
    fn run(&self, mut core: Box<Core>) -> RunResult {
        while !core.is_shutdown {
            // 周期性的 maintenance（如 driver tick、trace）
            core.tick();

            // 三条腿找一个任务
            if let Some(task) = core.next_task(&self.worker) {
                core = self.run_task(task, core)?;
                continue;
            }
            if let Some(task) = core.steal_work(&self.worker) {
                core = self.run_task(task, core)?;
                continue;
            }

            // 没活了，park
            core = self.park(core);
        }

        // shutdown 路径
        core.shutdown(&self.worker);
        Err(())
    }
}

这就是 worker 主循环的骨架：

• 第一条腿：next_task —— 优先从本地队列取（偶尔从全局队列取一个）
• 第二条腿：steal_work —— 本地没了，去偷其他 worker 的
• 第三条腿：park —— 偷也偷不到，休眠等通知

三条腿的优先级是精心设计的——本地优先减少跨核访问的 cache miss；偷前先确认本地真空，避免无谓的跨核原子操作；只有彻底空才 park（park 涉及系统调用，代价高）。

tick 字段的玄机

注意 Core 里的 tick: u32 字段——每 poll 一个 Task 后自增 1。它是整个 scheduler 的"时间片秒表"：

• tick % global_queue_interval == 0 时检查全局队列（5.3 节讲过）
• tick % event_interval == 0 时调 driver.park_timeout(0) 非阻塞拉一次 I/O 事件——这让繁忙 worker 也会周期性处理 I/O，不会"只顾 CPU 忘了 I/O"
• 也用于周期性 metrics 提交

为什么用 u32？ 环绕一圈是 43 亿个 tick——按每 tick 一微秒算，70 分钟才环绕。而且这字段全是 % N 用途，环绕不影响正确性。省 4 字节，cache line 就多出位置。

这种"能用更小类型就用更小"的思考贯穿 Tokio 源码。现代 CPU cache line 是 64 字节——一个 struct 塞进单 cache line 比横跨两个 cache line 快 2-3 倍。Tokio hot struct 的字段排列全按这个原则。

---

5.3 next_task：本地队列 + 全局队列的配合

看 next_task 的原样代码：

// 来源：tokio/src/runtime/scheduler/multi_thread/worker.rs
fn next_task(&mut self, worker: &Worker) -> Option<Notified> {
    if self.tick % self.global_queue_interval == 0 {
        self.tune_global_queue_interval(worker);
        worker.handle.next_remote_task()
            .or_else(|| self.next_local_task())
    } else {
        let maybe_task = self.next_local_task();
        if maybe_task.is_some() {
            return maybe_task;
        }
        if worker.inject().is_empty() {
            return None;
        }
        let cap = usize::min(
            self.run_queue.remaining_slots(),
            self.run_queue.max_capacity() / 2,
        );
        let n = usize::min(
            worker.inject().len() / worker.handle.shared.remotes.len() + 1,
            cap,
        );
        let n = usize::max(1, n);
        let mut synced = worker.handle.shared.synced.lock();
        let mut tasks = unsafe { worker.inject().pop_n(&mut synced.inject, n) };
        let ret = tasks.next();
        self.run_queue.push_back(tasks);
        ret
    }
}

两条分支：

分支 A：tick % global_queue_interval == 0（每 31 次一次）

优先从全局队列取一个，取不到才 fallback 本地。这是反饥饿设计——如果只用本地队列，全局队列里的 Task（比如 Handle::current().spawn(...) 从外部线程塞进来的）可能永远被饿死。强制每 31 次拉一次全局，保证全局队列里的 Task 最多等 31 个 tick 就会被处理。

为什么是 31？ 再次回到第 4 章讲的"质数 + 基准测试最优解"：31 接近 32 但不是 2 的幂，避免与其他 2 的幂节奏同步。

分支 B：tick % global_queue_interval != 0（常态）

1. 先调 next_local_task 从本地队列 pop 一个——走 fast path
2. 本地没了，先看全局队列是不是真的空（is_empty 无锁检查）
3. 全局有 Task，一次性批量拉一些（pop_n）而不是一个一个拉——减少 mutex 争抢

批量拉的数量算法非常精细：

• 上限是"本地队列剩余槽位的一半"——不把本地队列塞满（给后续 spawn 留空间）
• 数量取 全局队列长度 / worker 数 + 1——每 worker 均摊一份

这是一个典型的"公平调度"工程细节：一个空的 worker 一次不会拉走所有全局任务（那样下次其他 worker 又会抢），而是拉自己那份。

---

5.4 steal_work：本地空了，去偷邻居的

当本地 + 全局都空，worker 就进入"搜索"模式，去其他 worker 那里偷任务。原样代码：

// 来源：tokio/src/runtime/scheduler/multi_thread/worker.rs
fn steal_work(&mut self, worker: &Worker) -> Option<Notified> {
    if !self.transition_to_searching(worker) {
        return None;
    }

    let num = worker.handle.shared.remotes.len();
    let start = self.rand.fastrand_n(num as u32) as usize;

    for i in 0..num {
        let i = (start + i) % num;
        if i == worker.index {
            continue;
        }

        let target = &worker.handle.shared.remotes[i];
        if let Some(task) = target
            .steal
            .steal_into(&mut self.run_queue, &mut self.stats)
        {
            return Some(task);
        }
    }

    worker.handle.next_remote_task()
}

四个关键点：

1. 先 transition_to_searching

尝试把自己标记为"搜索中"。但 Tokio 限制并发搜索 worker 的数量——通常最多 worker_count / 2 个 worker 可以同时 searching。为什么？

搜索本身不免费：它要读其他 worker 的队列 head/tail——即使没偷到，也产生了 cross-core atomic load 的 cache-coherence 开销。如果所有 worker 都在搜索空队列，整个系统被"搜索开销"拖死。限制并发搜索是自我保护机制。

如果 transition_to_searching 失败，直接返回 None——worker 会走向 park。

2. fastrand_n 产生随机起点

注意这行：

let start = self.rand.fastrand_n(num as u32) as usize;

随机起点是工作窃取算法的灵魂。如果每个 worker 都从 0 开始扫描，那 worker 0 会被反复偷（所有 idle worker 都先问 worker 0），而 worker N-1 很少被偷——造成偷窃不均衡。

随机起点打破这个模式：每个 worker 每次搜索从一个随机位置开始扫描，统计上所有 worker 被偷的概率均匀。

这是一个被 20+ 年的调度器研究反复验证的算法。Go runtime 的 work-stealing、Cilk、OpenMP tasking、Folly CPUThreadPoolExecutor——都用随机起点。

随机 ≠ 真随机：fastrand 的伪随机就够用

这里的随机不需要密码学安全。实际上 Tokio 用一个极简的 xor-shift 伪随机生成器：

// 简化自 tokio/src/runtime/tests/loom_oneshot.rs（示意）
struct FastRand { state: u32 }
impl FastRand {
    fn fastrand_n(&mut self, n: u32) -> u32 {
        let s = self.state;
        self.state = s ^ (s << 13) ^ (s >> 17) ^ (s << 5);
        self.state % n
    }
}

几条指令就产生下一个数。对于"给偷窃起点选个位置"这个场景，统计分布够均匀就行。生产 Tokio 里每次工作窃取的随机起点，开销比一次 L1 cache miss 还小——完全免费。

把"选最优算法"的功夫花在值钱地方，把"够用就行"的地方放过——这是成熟系统的标志。本书后面你会看到 Tokio 还有类似的"够用即可"哲学出现在多处，比如时间轮的精度、metrics histogram 的桶数。

3. fastrand 而不是 rand

为什么不用标准的 rand crate？因为 fastrand 是极简的 xoshiro 变体——每次生成只需要几条指令。hot path 上用重度 RNG（比如 mersenne twister）会拖慢调度。Tokio 自带的 FastRand 是专门为此优化的。

4. 偷不到才 fallback 全局队列

所有 worker 都问过了还没偷到，调 next_remote_task 再查一次全局——可能这个时间窗里正好有新 Task 被 inject 进来。

如果最终依然 None，返回 None——worker 会 park。

---

5.5 queue.rs：本地队列的位打包魔法

Tokio 的本地队列是整个 scheduler 里最精巧的一段代码。它是一个 256 容量的环形缓冲区，但它的 head 指针用了双头打包技术：

// 来源：tokio/src/runtime/scheduler/multi_thread/queue.rs
#[cfg(not(loom))]
const LOCAL_QUEUE_CAPACITY: usize = 256;

pub(crate) struct Inner<T: 'static> {
    head: AtomicUnsignedLong,       // 一个 u32（或 u64）同时编码两个 u16
    tail: AtomicUnsignedShort,      // 只有生产者写、多消费者读
    buffer: Box<[UnsafeCell<MaybeUninit<task::Notified<T>>>; LOCAL_QUEUE_CAPACITY]>,
}

pub(crate) struct Local<T: 'static> {
    inner: Arc<Inner<T>>,
}

pub(crate) struct Steal<T: 'static>(Arc<Inner<T>>);

关键设计：

• Local：生产 + 本地消费接口。worker 自己通过 Local 推任务进、弹任务出
• Steal：窃取接口。其他 worker 通过 Steal 从这个队列"偷"任务
• head: AtomicUnsignedLong：一个 32 位 atomic（在大端架构可能 64 位），低 16 位是 "real head"，高 16 位是 "steal head"

双头打包解决什么问题

传统的 work-stealing 队列（Chase-Lev deque）需要两个独立的原子变量：

• top（消费端）由 thief 读写
• bottom（生产端）由 owner 读写

但"同时修改这两个字段"需要两次原子操作，难以保证原子性。Tokio 的做法：

• 把"real head"和"steal head"塞进同一个 atomic
• 一次 CAS 同时更新两者——原子性天然保证

具体含义：

• real head：真正"下一个要被消费的位置"
• steal head：如果有 thief 正在偷，它声明的"我打算消费的位置"
• 两者相等时，没人在偷；不相等时，区间 [steal_head, real_head) 是"有人正在偷走但还没完成"的任务

这个设计让 pop（owner 自己取）和 steal_into（thief 偷取）可以无锁并发执行——冲突在一次 CAS 的失败重试里自然解决。

pop：本地消费者的精巧路径

原样代码：

// 来源：tokio/src/runtime/scheduler/multi_thread/queue.rs
pub(crate) fn pop(&mut self) -> Option<task::Notified<T>> {
    let mut head = self.inner.head.load(Acquire);

    let idx = loop {
        let (steal, real) = unpack(head);
        let tail = unsafe { self.inner.tail.unsync_load() };

        if real == tail {
            return None;
        }

        let next_real = real.wrapping_add(1);
        let next = if steal == real {
            pack(next_real, next_real)
        } else {
            assert_ne!(steal, next_real);
            pack(steal, next_real)
        };

        let res = self
            .inner
            .head
            .compare_exchange(head, next, AcqRel, Acquire);

        match res {
            Ok(_) => break real as usize & MASK,
            Err(actual) => head = actual,
        }
    };

    Some(self.inner.buffer[idx].with(|ptr| unsafe { ptr::read(ptr).assume_init() }))
}

这段代码的精华：

• unsync_load() 读 tail：因为 tail 只能由 owner（本地 worker）写，所以在 owner 自己 pop 时可以用 unsynchronized load（比 atomic load 更快）
• CAS 更新 head：如果没有 thief 介入（steal == real），一并推进两个 head；有 thief 介入则只推 real head
• real as usize & MASK：MASK = LOCAL_QUEUE_CAPACITY - 1 = 255，环形缓冲用位与代替取模

几十纳秒级别的性能就是从这种对每一个字段的极致利用中攒出来的。

steal_into：偷取者的批量策略

原样（简化）：

// 来源：tokio/src/runtime/scheduler/multi_thread/queue.rs
pub(crate) fn steal_into(
    &self,
    dst: &mut Local<T>,
    dst_stats: &mut Stats,
) -> Option<task::Notified<T>> {
    let dst_tail = unsafe { dst.inner.tail.unsync_load() };
    let (steal, _) = unpack(dst.inner.head.load(Acquire));

    if dst_tail.wrapping_sub(steal) > LOCAL_QUEUE_CAPACITY as UnsignedShort / 2 {
        return None;          // 目标自己队列已经半满，不要再偷
    }

    let mut n = self.steal_into2(dst, dst_tail);
    if n == 0 { return None; }

    // 统计 + 把偷来的 n 个里的第一个直接返回，剩下的放进 dst 队列
    // ...
    Some(ret)
}

关键决策：

• 预检查 dst 队列容量：如果我（thief worker）自己队列已经半满，不去偷。因为偷来放不下、偷少了不划算
• 一次偷 n 个而不是 1 个：steal_into2 内部会偷被偷者队列现有任务数的一半（截断到目标容量）。理论依据是工作窃取的**"half-steal"策略**——偷走一半让两边负载均衡

这就是 Tokio 为什么高效：不是单纯的"本地没就偷一个"，而是每次偷一把，减少未来的偷窃频率。

偷不回头：被偷走的 Task 会再被偷吗？

一个精细问题：worker A 偷走了 worker B 的一批 Task 放进 A 的本地队列。这些 Task 会不会再被 worker C 偷走？

可以。一旦任务到了 A 的本地队列，它就是 A 队列的一部分——worker C 偷 A 时可能偷到它。但实际极少发生——worker 刚偷完任务就去跑了，很快就会 pop 掉放队列前头的任务。到 C 有机会偷时，这些 Task 可能已经被 A 跑完了。

这种"偷的级联"理论上会发生但实际罕见——工作窃取的自然流动是从忙到闲，很少发生"A 偷完 B，C 又偷完 A" 的链式偷窃。就算真发生了，系统也不会错，只是会多几次 cache miss、性能稍差。

罕见路径不优化但也不出错——这是 Tokio 源码的常见哲学，也是性能敏感系统的工程美学之一。

push_back：生产者端

看 owner 把新任务塞进本地队列的代码：

// 来源：tokio/src/runtime/scheduler/multi_thread/queue.rs
pub(crate) fn push_back(&mut self, tasks: impl ExactSizeIterator<Item = task::Notified<T>>) {
    let len = tasks.len();
    assert!(len <= LOCAL_QUEUE_CAPACITY);

    if len == 0 {
        return;
    }

    let head = self.inner.head.load(Acquire);
    let (steal, _) = unpack(head);
    let mut tail = unsafe { self.inner.tail.unsync_load() };

    if tail.wrapping_sub(steal) <= (LOCAL_QUEUE_CAPACITY - len) as UnsignedShort {
        // 有空间
    } else {
        panic!()   // 实际 Tokio 里这里会 overflow 到全局队列，不是 panic
    }

    for task in tasks {
        let idx = tail as usize & MASK;
        self.inner.buffer[idx].with_mut(|ptr| {
            unsafe {
                ptr::write((*ptr).as_mut_ptr(), task);
            }
        });
        tail = tail.wrapping_add(1);
    }

    self.inner.tail.store(tail, Release);
}

三个技术细节值得驻足：

1. tail.wrapping_sub(steal)：用 wrapping（环绕）减法算队列当前长度。tail 和 steal 都是 u16，但它们可以自然 wrap——环绕减法恰好计算出循环距离
2. unsync_load 读 tail：owner 自己就是唯一写 tail 的人，无需 atomic load——省一条屏障
3. store(tail, Release) 最后一步：所有任务写完后用 Release 发布新 tail——保证其他 worker（thief）看到新 tail 时，被索引的槽位已经可读

这个 release store 是唯一一次同步开销——一次 push 批量 N 个任务，只付一次 release。批量越大，平摊的同步开销越小。这就是为什么 5.3 节的 next_task 批量拉取全局队列——不是一次一个，是一次一批，就是在榨干这个 release 的价值。

容量溢出怎么办？

LOCAL_QUEUE_CAPACITY = 256。如果 worker 一直在 spawn 而没来得及消费，本地队列满了怎么办？

Tokio 的实际处理（简化版，不在我们上面的代码片段里）：

• 检查本地队列是否能装下
• 装不下 → overflow 到全局队列——从本地队列pop 一半到全局队列，腾出空间后 push 新任务
• 这意味着 spawn 的最坏情况是"遇到本地队列满了，触发一次全局队列的 mutex lock"——而不是 panic 或丢任务

这是 Tokio 对"突发 spawn 密度"的天然保护。你可以安心在一个 async fn 里 spawn 几千个子任务，Tokio 会在本地 256 容量用完时自动 overflow 到全局，其他 worker 就能偷走全局的任务分担负载。不需要任何显式流控。

---

5.6 LIFO slot：给 spawn → .await 这个模式开绿灯

Core 里有一个字段 lifo_slot: Option<Notified>。这是一个只能装一个 Task 的槽位，用途是给刚刚 spawn 的任务开绿灯。

典型场景

// 生产者模式：spawn 子任务后立刻 await 它
async fn producer_consumer() {
    let handle = tokio::spawn(async { compute() });
    let result = handle.await;    // 立刻等 handle
    use_result(result);
}

这段代码的调用序列：

1. 调用 tokio::spawn——一个新 Task 被 push 到当前 worker 的本地队列
2. handle.await——当前 Task yield（返回 Pending）
3. Worker 需要找下一个 Task

没有 LIFO slot 时：Worker 从本地队列 pop——拿到的是队列里最老的那个 Task（FIFO），不一定是刚 spawn 的 handle——于是要等一会儿。

有 LIFO slot 时：tokio::spawn 把新 Task 先放进 LIFO slot，slot 满了再推入本地队列。Worker 下次取任务时优先从 LIFO slot 取——刚 spawn 的任务立刻被执行。

为什么这是关键优化

spawn 子任务 + await 它这个模式极其常见——几乎所有 "fan-out" 并发代码都有这个形态。Tokio 的 LIFO slot 把这种模式的延迟从"好几个 poll 周期"压缩到"下一次 poll"。

Discord 在从 Go 迁移到 Rust 时遇到的一个经典问题就是没有 LIFO slot 导致的调度延迟高——他们给 Tokio 提了 PR 加了这个特性（2021 年），现在是默认行为。如果需要关闭 LIFO slot（某些反直觉场景下有用），用 Builder::disable_lifo_slot()。

LIFO slot 和 work-stealing 的互动

LIFO slot 的任务不能被其他 worker 偷——它是本 worker 独占的。这保证"刚 spawn 的任务不会被远程 worker 意外拿走"。但如果 worker 自己 park 了，LIFO slot 里的 Task 会被"转交"到本地队列，让其他 worker 有机会偷——这是 park_timeout 里的一段 maintenance 逻辑。

disable_lifo_slot 什么时候用

绝大多数时候别关——LIFO slot 是净收益。但极少数场景你可能想关：

1. 严格公平的 round-robin 需求：任务严格按 spawn 顺序执行时（某些队列系统），LIFO 会打乱——关掉它回到 FIFO
2. 压测对调度公平性敏感：基准测试里想排除 LIFO 影响
3. 任务间优先级反转：A spawn 了 B 但 A 优先级更低，LIFO 会让 B 先跑

生产服务几乎没有关它的理由——默认最优，不要瞎调。

---

5.7 park / unpark：worker 的休眠协议

当 worker 三条腿都走不通（本地空、全局空、偷不到），它就 park。原样代码：

// 来源：tokio/src/runtime/scheduler/multi_thread/worker.rs
fn park(&self, mut core: Box<Core>) -> Box<Core> {
    if let Some(f) = &self.worker.handle.shared.config.before_park {
        f();
    }

    if core.transition_to_parked(&self.worker) {
        while !core.is_shutdown && !core.is_traced {
            core.stats.about_to_park();
            core.stats.submit(
                &self.worker.handle.shared.worker_metrics[self.worker.index]
            );
            core = self.park_timeout(core, None);
            core.stats.unparked();
            core.maintenance(&self.worker);
            if core.transition_from_parked(&self.worker) {
                break;
            }
        }
    }

    if let Some(f) = &self.worker.handle.shared.config.after_unpark {
        f();
    }
    core
}

四步：

1. before_park 回调（第 4 章说的 Builder 字段）
2. transition_to_parked：尝试把状态从 "Searching" 转到 "Parked"——这一步可能失败（有新任务进来），失败就直接回主循环
3. 循环 park/unpark：
   • park_timeout(None) 阻塞等待 unpark 信号（None = 无超时）
   • 醒来 maintenance 做一轮杂事：driver tick、stats 提交
   • transition_from_parked 判断"真的该起床了吗"——比如spurious wake（虚假唤醒）就继续睡
4. after_unpark 回调

transition_to_parked 的"最后检查"

这个函数不仅仅是"标记成 parked"——它还会再扫一眼本地 / 全局 / 偷窃队列，确认真的没任务了才 park。这是避免 park-wakeup 竞态的关键：

• 如果不做最后检查，可能发生："worker 决定 park → 另一个 spawn 进来（并尝试 unpark）→ worker park"
• unpark 信号必须在 park 之后才生效。如果 spawn 的 unpark 在 park 之前，信号就丢了，worker 会永远睡

Tokio 的做法：transition_to_parked 用原子操作同时做两件事：标记 parked + 再次确认无任务。如果任何一步发现任务，放弃 park、回主循环。

这一段状态机是整个 scheduler 最容易出 race 的地方，也是 Loom（Tokio 的并发测试工具）反复穷举的重点。

Loom 是什么 —— 简短介绍

Loom 是 Tokio 团队做的Rust 并发正确性测试框架。它会穷举所有可能的线程交错，让并发 bug 几乎不可能逃过测试。

具体做法：

• 把 std::sync::atomic / std::thread 等标准并发原语替换成 Loom 自己的等价物
• 运行测试时，Loom 模拟每种可能的 memory ordering 和线程调度顺序
• 一个简单的"两线程原子 CAS"测试在 Loom 下会跑上千种交错组合

Tokio 的 scheduler、queue、state 这些核心模块都有 cfg(loom) 下的 Loom 专用测试版本。每次 PR 合并前要跑过 Loom——这是 Tokio 稳定性的最大保证。

你看到 queue.rs 里 LOCAL_QUEUE_CAPACITY = 4 在 cfg(loom) 下的定义就是为了 Loom 测试——把容量缩到 4 让 Loom 更快穷举所有状态。生产是 256，测试是 4，同一份代码两种行为。

Loom 的详细讲解超出本章范围，但你应该知道它存在——这类"穷举模型检查"工具在系统编程里是你信任复杂并发代码的唯一理性依据。

Park 如何跨线程唤醒

park_timeout 底层调的是 std::thread::park / std::thread::park_timeout——Rust 标准库的线程休眠原语。unpark 通过 std::thread::Thread::unpark() 发出。

这不是 condvar 而是 atomic flag：unpark 设置一个标志位，park 看到标志位就不睡。所以多次 unpark 只等于一次——这是 OS 层的幂等，和我们第 3 章讲的 wake 幂等正好对应。

---

5.7½ 搜索者计数：Tokio 限流机制的又一例

前面提到 transition_to_searching 会限制同时 searching 的 worker 数——这是通过 Shared 里一个 atomic 计数器实现的。具体机制：

• Shared.idle 内部维护一个 num_searching 原子计数
• 任何 worker 进入 searching 前，先 num_searching += 1，并检查"当前 searching 数是否超过 worker 总数的一半"
• 超过就拒绝，worker 直接去 park
• worker 偷到任务（或放弃搜索去 park）时，num_searching -= 1
• 偷到任务后额外做一件事：如果 num_searching 变成 0 了，唤醒另一个 worker 继续 searching——避免"最后一个 searching worker 拿到任务，整个系统进入误以为都空闲的 idle 状态"

这一套协议完整的原子操作序列只有几行代码，但它保证：

• 系统永远有 searching worker（只要有任务流动）——避免"任务堆积但 worker 全 park"
• searching 数量有上限——避免所有 worker 都在偷空队列，拖累 cache coherence
• transition 本身是原子的——无论多少 worker 同时做决策，不会出现"all park"或"all search"的悬崖状态

这种"搜索者计数 + 自唤醒协议"是工作窃取调度器的标志性设计。如果你读其他工作窃取实现（Go / Folly / rayon），会发现同样的三件套：num_searching counter、"entering search" gate、"last one out wakes another" 协议。

Tokio 的实现在 tokio/src/runtime/scheduler/multi_thread/idle.rs——这个文件专门负责这套协议，代码精细到每一个 atomic ordering 都有特定理由。读源码的乐趣之一就是，这种看似琐碎的协议居然能让一个庞大的并发系统稳如磐石。

---

5.8 一次典型调度事件的完整路径

把前面所有东西拼起来，看一次典型调度在 Tokio 里的走位：

场景：worker 0 正 poll 一个 async fn，它内部 tokio::spawn 了一个子任务。

1. spawn 发生：

   • 新 Task 创建，通过 LIFO slot 机制，先看 worker 0 的 lifo_slot
   • lifo_slot 为空 → 新 Task 占 lifo_slot
   • 原 lifo_slot 里的 Task（如果有）被挤到本地队列

2. 当前 async fn 继续执行：

   • 遇到 .await → 如果子任务还没完成，当前 Task 返回 Pending
   • Worker 0 的 poll 循环结束

3. Worker 0 主循环取下一个 Task：

   • next_task：tick % 31 != 0 → 先看本地
   • 本地队列可能非空 → 返回一个 Task
   • 但实际上 Worker 0 应该先处理 lifo_slot——next_task 的具体实现里会先看 lifo_slot（上面的代码没展示全，实际 next_task 有 lifo_slot 优先逻辑）
   • 拿到刚 spawn 的子任务，开始 poll

4. 子任务执行完返回 Ready：

   • handle.await 的 handle 被唤醒（通过 JoinHandle 内部的 oneshot-like 机制）
   • 父 Task 被 wake → 入某个 worker 的队列
   • Worker 继续循环

这整条路径的 hot 部分都是当前 worker 独占的访问——没有跨 worker 的原子操作。这就是 Tokio 高性能的秘密：90% 的调度事件不跨核。

跨 worker 的场景什么时候发生

那哪些场景会触发跨核？主要四类：

1. 从非 worker 线程 spawn：Handle::current().spawn(fut) 在 std thread 里调 —— Task 进全局 inject 队列，worker 从那里取（跨核）
2. I/O Driver 在独立线程：I/O Driver 可能在 worker-0 线程跑 epoll，如果唤醒的 Task 属于 worker-3，就是跨核 wake
3. Worker 工作窃取：每次偷都是跨核
4. channel 跨 worker 发消息：sender 在 worker-1，receiver 的 Task 在 worker-3，wake 时跨核

这四类是 Tokio 无法避免的跨核场景。Tokio 的设计是这些场景里原子操作和 cache miss 最小化——偷任务偷一把、wake 幂等、remote 入队尽量批量。把不可避免的跨核成本压到最低，而不是假装它不存在，这是工程现实主义。

---

5.9 和其他语言调度器的对比

维度	Tokio multi_thread	Go GMP	Erlang BEAM	Node.js libuv
调度单位	Task（async state machine）	Goroutine（独立栈）	Process（ErlVM process）	Callback
每 worker 本地队列	256 容量环形	256 容量数组	每 scheduler 独立	无
工作窃取	✅ 随机起点	✅ 随机起点	✅ 主动调度	❌（单线程 event loop）
LIFO 优化	✅ 有 lifo_slot	✅ 有 runnext	❌	N/A
全局队列	✅ inject	✅ global runq	✅ migration	N/A
公平性	global_queue_interval	类似机制	reduction counting	N/A

结论：Tokio 的多线程调度器和 Go runtime 的 GMP 非常接近——两者都是"每 P 一个本地队列 + 全局队列 + 工作窃取 + LIFO 优化"。主要差异是：

• Go 的 Goroutine 有独立栈（2 KB 起），Tokio 的 Task 是 state machine（常常几十字节）
• Go 的调度器更主动（协作抢占+ 时间片），Tokio 依赖 .await 自然让出
• Go 有 GC，Tokio 无

Tokio 借鉴了 Go 的很多调度经验。这是 Carl Lerche 在多次演讲里公开说过的——站在巨人肩膀上没什么不好意思的。

和 Go GMP 的具体差异，以及为什么 Tokio 有独特取舍

Go GMP 里 M 是 OS 线程、P 是逻辑处理器、G 是 goroutine。Tokio 的对应：Worker = M + P 合一（一个 OS 线程绑一个 Core），Task = G。但几个关键差异值得单独说：

**差一：**Go 的 G 有独立栈，可以在任意点让出（运行时会在函数调用处插入抢占点）。Tokio 的 Task 没有独立栈，让出只在显式 .await 处。意味着：一个 Tokio Task 如果写成纯 CPU 循环（没有 await），它会占住 worker 直到跑完。这就是第 16 章要讲"CPU 密集代码必须 spawn_blocking"的根源。

差二：Go 的调度器有"sysmon" 后台线程定期检查"是否有 G 占了 P 太久"，会抢占。Tokio 没有这个——完全靠协作。这让 Tokio 更轻量（省一个监控线程），但要求用户代码遵守协作契约。

差三：Go 的 M 可以动态创建（sysmon 发现 P 都阻塞就 new M），数量可达几千。Tokio 的 worker 数量固定（build 时决定），绝对不动态增加。这让 Tokio 的资源占用可预测，但也意味着"所有 worker 都阻塞 = 系统停滞"。

这些差异不是"Tokio 不如 Go"，是"两种不同的取舍"。Go 做的是"对用户尽可能透明，牺牲一点运行时复杂度"；Tokio 做的是"保持运行时极简，让用户按契约协作"。Rust 生态的典型美学：显式 > 隐式。

---

5.10 和这个系列的其他书的关联

本章的"状态机 + 原子位打包"设计，和 《Vue 3 设计与实现》第 12 章（生命周期与调度） 里 Vue 的 queueJob + flushJobs 调度机制有同型结构——都是"push 进队列 + 批量 flush + 去重"。但 Vue 在浏览器单线程里不需要 work-stealing，Tokio 在多线程服务端必须。同一问题（异步任务调度）在不同运行时环境下的不同解是非常有启发性的对比。

**《Rust 编译器与运行时揭秘》第 15 章（MIR 优化 Pass）**里讲的 rustc 工作窃取分派 pass 编译任务，也是类似的工作窃取架构——你会看到 Rust 生态里工作窃取不止 Tokio 用，编译器自己也用。

---

5.10½ 对比 Cilk：学术世界的 work-stealing 起源

最后给调度的工作窃取算法一个历史维度。Tokio 的工作窃取可以追溯到 1994 年 MIT 的 Cilk 项目——该项目第一次系统地研究并论证了"分布式工作窃取调度器"的性能上界。

Cilk 的核心定理：N 核上的工作窃取调度器，对于一个有 W 个任务、关键路径 S 的并行程序，期望运行时间是 W/N + O(S)。这个定理表明：

• 工作窃取接近理论最优并行加速
• 关键路径 S 是根本瓶颈——序列化不可避免的部分
• 随机起点的选择不影响渐近性能，只影响常数因子

Tokio 的设计师当然读过这些论文。LIFO slot、随机起点、批量偷窃——这些不是凭空发明的，是 30 年学术研究的工程化落地。Carl Lerche 在 Tokio 博客里明确引用过 Cilk 和 Chase-Lev 论文。

如果你想深入学术侧，读 Cilk 的论文 "Cilk: An Efficient Multithreaded Runtime System"（Blumofe et al., 1995）。读完你会发现 Tokio 2019 年的调度器改造在概念上和 Cilk 基本相同——30 年历史的成熟技术终于在 Rust 生态落地。

---

5.11 本章小结

读完这章你会发现：Tokio 的调度器没有奇迹，只有对细节的狂热打磨。每一个字段、每一个位、每一个 ordering 都有解释。你现在有了看懂任何调度器代码的基础——Go、Erlang、rayon、Java ForkJoinPool——你都能用同一套词汇（work-stealing、LIFO、fairness、searching、park/unpark）解码它们。

带走三件事：

1. Tokio multi_thread scheduler 由三个 struct 支撑：Core（每 worker 独占，含 lifo_slot + 本地队列）、Shared（跨 worker 共享，含 inject 全局队列）、Worker（容器）
2. Worker 主循环的三条腿：next_task（本地 + 偶尔全局）→ steal_work（随机起点扫其他 worker）→ park（真的没活了才休眠）
3. 本地队列用一个 AtomicUnsignedLong 打包两个头指针（real head + steal head），使 owner 的 pop 和 thief 的 steal 可以无锁并发，这是 Tokio 性能的核心秘密之一

5.11½ Tokio 调度器的演化史：从 0.1 到 1.40

Tokio 的多线程调度器经历过几次大重构，每次都有明确的性能或正确性目标。简要时间线：

2017-2019：Tokio 0.1 / 0.2 —— 基于 futures 0.1

最早的调度器是一个非常简单的 "每线程一个 MPSC channel" 设计。tokio::spawn 往 channel 里 push 任务，worker 线程从 channel pop。没有 work-stealing，没有 LIFO slot。

性能瓶颈：不均衡——某个 worker 忙到爆，其他 worker 空转。基准上最高吞吐只有现在的 20%。

2019：Tokio 0.2 中期 —— 引入 work-stealing

Carl Lerche 做了第一轮大改造。参考 Go GMP 模型，引入每 worker 本地队列 + 工作窃取。性能瞬间提升 3-5 倍。这一轮的博客《Making the Tokio scheduler 10x faster》是必读文档——现代工作窃取调度器的中文参考材料里，这篇实用度最高。

2020-2021：Tokio 1.0 / 1.6 —— LIFO slot 加入

Discord 工程师在真实服务里发现"spawn + await 立刻" 模式的延迟问题，提 PR 加了 LIFO slot。这一轮改进让tail latency（尾延迟）显著改善——从 p99 几毫秒降到亚毫秒。

2022-2023：Tokio 1.15+ —— 本地队列扩容和 idle 协议改进

本地队列容量从 128 改到 256（更少 overflow）、idle worker 的 num_searching 协议细化、新增 runtime metrics API。

2024-2026：Tokio 1.30-1.40 —— MultiThreadAlt 实验

Carl 在 tokio_unstable feature 下做了一个完全不同架构的多线程调度器原型（MultiThreadAlt）。核心差异：

• 本地队列用锁而不是 atomic（某些场景下锁反而便宜）
• 全局队列用 per-worker inject 而不是单一 inject
• 不同的公平性策略

MultiThreadAlt 的目标是在特定工作负载下（比如大量短 Task）拿到更高吞吐。尚未稳定，生产不推荐用。

这段历史给你的启示

1. 调度器没有"一次写对"——行业头部项目也在持续迭代 5-10 年
2. 每次改动都要有具体的性能数据支撑——不要靠直觉优化
3. 抽象的正确性测试（Loom）是头等公民——Tokio 调度器用 Loom 跑了成千上万种线程交错组合，这是它稳定性的基石

你读本章时看到的所有"看似最优"的设计，都是这 10 年里大量真实生产 bug 积累出来的答案。不要觉得这些设计理所当然——它们背后每一个都是血泪史。

---

5.11½ 一些容易被忽略的细节

在告别本章之前，把几个容易被读者忽略但值得记住的小细节串一下：

细节一：Worker 启动不是并行的

build_threaded_runtime 里 spawn N 个 worker 时，并不是 N 个线程同时启动——是按索引顺序 spawn。这意味着在 runtime 刚启动的前几毫秒，一些 worker 可能还没准备好、它们的 Core 还没被 take。如果这时有 Task 被 spawn，可能会先进全局队列，等 worker 就绪后被偷/拉走。这是启动窗口的微妙行为，极少影响生产。

细节二：Arc<Handle> 的引用计数是每 worker 独立维护一份

每个 worker 持有 Arc<Handle> 的一份 clone——意味着 runtime drop 时必须等所有 worker 都释放这个 Arc。这就是为什么 shutdown 必须 join 所有 worker 线程——不是因为它们"干活"没停，而是因为它们持有 Arc 会让 Handle 不能 drop。

细节三：Remote 结构体

Shared.remotes: Box<[Remote]> —— 每个 worker 对应一个 Remote。Remote 里主要是该 worker 队列的 Steal<T> 句柄（让别的 worker 偷）和一个 unpark 句柄（让别的地方唤醒这个 worker）。Remote 是"其他人对这个 worker 的访问入口"——每 worker 本地的 Core 私有，Remote 公开。

细节四：调度决策是完全本地化的

worker A 决定下一步做什么，不会询问 worker B 的意见。没有中央协调。这让 Tokio 的 scheduler 可以 scale 到几十核而不出现锁竞争——中央协调是调度器的最大扩展性杀手。

把这四个细节合起来，你就理解了 Tokio scheduler 的设计精髓：无中央、最小共享、最大并发。

---

5.11¾ 实战：如何从 tokio-console 看调度问题

光讲理论没用，来看真实场景怎么调试调度问题。

工具：tokio-console —— Tokio 官方的可视化调试工具。启动你的应用时加上 tokio_unstable 和 RUSTFLAGS="--cfg tokio_unstable"，再用 tokio-console 命令连接。

场景 1：某 worker 长时间繁忙，其他 worker 空 症状：tokio-console 里看 WorkerMetrics，某个 worker 的 busy 指标 100%，其他接近 0。

• 可能原因：任务没有走 spawn（都是 block_on 同一个任务链）
• 或：某个 Task 持有了只能在本 worker 跑的资源（罕见，但存在）
• 排查：看这个 busy worker 上在跑什么 Task

场景 2：所有 worker 都 busy 但吞吐上不去 症状：busy_duration 接近 100%、poll_count 很高、但用户吞吐一般。

• 可能原因：Task 里有大量同步阻塞（文件 I/O 没走 spawn_blocking、CPU 密集计算），worker 在跑不能让出的代码
• 排查：flamegraph + tokio-console 的 poll_duration 分布——如果某个 Task 的单次 poll 超过几百微秒，就是阻塞了
• 修法：第 16 章（spawn_blocking 与 block_in_place）

场景 3：某 Task 永久 pending 症状：tokio-console 显示某 Task 有 idle_duration 但 poll_count 很低。

• 就是第 3 章的 BrokenCounter / stale Waker 问题
• 排查：查 Task 注册 Waker 的位置，看有没有人 wake 它

这三类症状对应调度器的三种常见病。掌握 tokio-console 的读图能力是生产调优的入门技能——第 17 章会专门讲这个工具的使用细节。

---

下一章我们钻进 Task 这个数据结构本身。你会看到 Task 是如何用一次堆分配存下 Header + Future、Header 前 64 字节塞了什么、spawn 到底创建了什么、JoinHandle 如何从 Task 拿到 Output。理解了 Task 结构，你就完全拼出了 Tokio 运行时的图。

---

延伸阅读

• Tokio 源码：tokio/src/runtime/scheduler/multi_thread/worker.rs —— Core / Worker / run / next_task / steal_work / park
• Tokio 源码：tokio/src/runtime/scheduler/multi_thread/queue.rs —— 本地队列的双头打包实现
• Chase, D. & Lev, Y. 的论文 "Dynamic Circular Work-Stealing Deque"（2005）—— 工作窃取队列的理论基础
• Tokio blog: "Making the Tokio scheduler 10x faster" —— Carl Lerche 写的调度器改造历史
• 《Rust 编译器与运行时揭秘》第 15 章：rustc 的工作窃取架构对比