Work-Stealing 调度器：本地队列与全局队列的工作窃取机制
在多核高并发系统中，如何将海量的微小异步任务（Task）均匀分发到各个 CPU 物理核心上，是决定异步运行时吞吐上限的核心难题。
如果采用最简单的**单全局共享队列（Single Global Queue）**架构：所有 Worker 线程在每次获取新任务时，都必须去抢占全局队列的互斥锁。当并发任务量达到数十万时，多核心之间的缓存一致性协议（MESI 广播）与锁争用，会直接把 CPU 算力全部消耗在自旋与总线锁上。
为了解决这一吞吐瓶颈，现代高性能异步运行时（如 Tokio、Go Runtime、Java ForkJoinPool）无一例外地采用了工作窃取算法（Work-Stealing Scheduling）。
理解 Tokio 中本地环形队列（Local Run Queue）、全局注射队列（Global Injection Queue）与窃取机制的协同设计，是排查高负载下任务调度倾斜与毛刺的关键。
+--------------------------------------------------------------------------+ | Tokio Work-Stealing 调度拓扑 | +--------------------------------------------------------------------------+ | 全局注射队列 (Global Injection Queue / MPMC 慢速保底) | | [ Task G1 ] -> [ Task G2 ] -> [ Task G3 ] ... | +--------------------------------------------------------------------------+ ^ ^ | 周期性轮询 (如每 61 次迭代) | 队列溢出溢出回退 v v +-----------------------------+ +-----------------------------+ | Worker 0 (CPU 核心 0) | 窃取 | Worker 1 (CPU 核心 1) | | 本地无锁环形队列 (Local 256) | <==== | 本地无锁环形队列 (Local 256) | | [T1] [T2] [T3] ... | 一半 | [ 空闲空转中... ] | +-----------------------------+ +-----------------------------+1. 本地队列设计：无锁单生产者-多消费者环形缓冲区
Tokio 为每个 Worker 线程分配了一个固定长度（默认 256 槽位）的本地运行队列（Local Run Queue）。
这个本地队列具有独特的并发访问模式：
- 本地 Worker 线程是唯一的生产者与主消费者：本地 Worker 从队列头部（Head）取任务执行，并将新生成的本地 Task 压入队列尾部（Tail）。在这个独占路径上，操作完全不需要加锁，通过无锁的原子游标更新即可在几个纳秒内完成；
- 其他空闲 Worker 是并发的偷取者（Stealers）：当其他 Worker 线程自身队列变空时，它们会扮演消费者从该队列中并发“偷取”任务。
巧妙的 256 容量限制与溢出处理
为什么本地队列的长度被固定为 256，而不是无限制动态扩容的数组？
- 防止单个 Worker 发生内存饥饿与倾斜：如果一个任务内部疯狂递归生成子任务，256 的容量上限能防止这些子任务全部积压在单个 Worker 核心上；
- 溢出回退到全局队列：当本地队列被填满 256 个任务时，Worker 会将本地队列中**一半的任务（128 个）打包一次性转移到全局注射队列（Global Queue）**中，主动让出给其他 Worker 分担。
2. 工作窃取流程：半数批量窃取（Steal Half）
当 Worker A 发现自己的本地队列变空时，它不会立刻陷入休眠（Sleep），而是进入窃取状态机：
- 随机挑选受害者（Victim Selection）：为了避免所有空闲 Worker 同时盯上同一个繁忙 Worker 造成二次争锁，Worker A 会随机选择一个目标 Worker B；
- 批量窃取一半任务（Steal Half）：
Worker A 不会只偷 1 个任务，而是通过 CAS 操作尝试一次性从 Worker B 的队列头部偷取其当前积攒任务总数的50%（最多 128 个），并直接搬迁到自己的本地队列中； - 消除颠簸（Anti-Thrashing）：一次性偷取一半任务，保证了 Worker A 在接下来的几百微秒内拥有充足的工作储备，不需要频繁触发昂贵的跨核心窃取。
// 伪代码：工作窃取核心逻辑 impl Worker { pub fn fetch_next_task(&mut self) -> Option<Task> { // 1. 优先消费本地最高优先级的 LifoSlot if let Some(task) = self.lifo_slot.take() { return Some(task); } // 2. 从本地无锁队列中弹出任务 if let Some(task) = self.local_queue.pop() { return Some(task); } // 3. 周期性（每 61 次迭代）主动检查全局队列，防止全局任务被饿死 if self.tick % 61 == 0 { if let Some(task) = self.global_queue.pop() { return Some(task); } } // 4. 本地为空，进入跨核心窃取逻辑 self.steal_from_peers() } fn steal_from_peers(&mut self) -> Option<Task> { let victims = self.get_randomized_peers(); for peer in victims { // 尝试从 peer 队列偷取一半任务 if let Some(stolen_task) = peer.local_queue.steal_half_into(&mut self.local_queue) { return Some(stolen_task); } } // 5. 最后兜底：检查全局队列 self.global_queue.pop() } }3. LIFO Slot 优化：极致的 CPU 缓存局部性
Tokio 还有一个极其精妙的微架构优化——LIFO Slot（后入先出单槽位）。
当一个正在执行的 Task A 通过tokio::spawn产生了一个新 Task B 时，调度器不会把 Task B 扔进队列尾部，而是将其暂存在一个名为lifo_slot的单任务寄存器式变量中。
当 Task A 执行完当前的这一轮 Poll 后，Worker 线程会优先取出lifo_slot中的 Task B 立即执行！
为什么这样做能大幅降低延迟？
因为 Task B 刚刚被 Task A 创建，Task B 所需的数据（包括请求结构体、张量切片）在 CPU 的 L1/L2 Cache 中处于完全温热（Hot Cache）状态！立即执行 Task B 可以实现极致的 CPU 缓存命中，避免了将任务推入队列尾部再由其他核心冷加载读取导致的 Cache Miss。
通过本地无锁环形队列、批量偷取一半策略以及 LIFO Cache 局部性插槽的三位一体配合，Work-Stealing 架构在多核心硬件上构建起了一套既能各自狂飙、又能自动动态削峰填谷的终极调度秩序。
