新版 Tokio 调度器性能提升10倍

调度器的优化围绕以下几个方面展开：

• 新的 std::future 任务系统
• 更好的队列算法
• 优化消息传递模式
• 改进的“任务窃取”算法
• 减少跨线程同步
• 减少内存分配
• 减少原子的引用计数

1 调度器如何工作

当涉及线程并发时，CPU 的缓存一致性机制会起作用，所以应尽可能避免跨线程同步。

• 单队列 多处理器
  • 优点：实现简单；任务被公平调度。
  • 缺点：所有处理器守着队头，真正执行任务消耗的时间远大于任务从队列中弹出的时间。rust 的异步任务是短耗时的，争用队列的开销大。
• 多处理器 多任务队列
  • 使用多个单线程调度器，每个处理器都有自己的任务队列，可完全避免同步问题。
  • rust 的任务模型中，任意线程都可以提交任务到队列，仍然需要线程安全。
    • 要么每个处理器的任务队列支持线程安全插入。
    • 要么每个处理器有两个队列：同步队列和非同步队列。
      • 优点：几乎完全避免了同步，性能较高。
      • 缺点：处理器可能出现严重的负载不均衡。
• “任务窃取”调度器
  • 每个处理器都有自己的任务队列。当一个处理器空闲时，可从同级的其它处理器窃取一些任务，窃取失败时会休眠。
    • 优点：避免同步开销；避免任务负载不均衡。
    • 缺点：复杂，任务队列必须支持“窃取”，且需要一些跨处理器同步操作。整个过程如果执行不正确，“窃取”的开销可能会超过收益。
• 总结
  • 尽量减少同步操作。
  • “任务窃取”是通用的调度器的首选算法。
  • 处理器见基本相互独立，但“窃取”操作需要一些同步操作。

2 新 Tokio 调度器

• 新的任务系统
  • std 中包含了新的 std::future 任务系统，比之前的版本更轻巧灵活。
  • Waker 结构更小，降低了复制开销，也允许将更多关键数据放入高速缓存行中。
• 更好的任务队列
  • 对每个队列使用固定大小。当队列已满时，任务将被推送到一个全局的、多使用者、多生产者队列中。处理器需检查该全局队列，但频率比本地队列低得多。
    • 优点：避免了扩容本地队列带来的开销。双端队列的扩容较为负载。
    • 细节：本地队列使用一个固定大小的单生产者、多消费者队列，只需要很少的同步便可正常工作。
• 优化消息传递模式
  • 当任务转换为可运行状态时，存储在“下一个任务”槽中，而不是添加到任务队列队尾。处理器在检查任务队列前会先检查该槽。
    • 优点：在消息传递的情况下，消息的接收者会被立马调度，较大概率会命中 CPU 高速缓存。
• 任务窃取
  • 当处理器的运行队列为空时，处理器将尝试随机从某个同级处理器中窃取任务，如果未找到，尝试下一个同级处理器。
    • 缺点：许多处理器大约同一时间完成运行队列的处理。将导致所有处理器同时尝试窃取，导致争用。虽然随机选择初始节点可减少争用，但仍然很糟。
    • 改善：限制并发执行窃取操作的处理器数量。试图窃取的处理器状态为“正在搜索”。通过使用原子计数器来控制并发数量：处理器开始搜索之前递增原子计数器，退出搜索状态时递减原子计数器。
• 减少跨线程同步
  • 任务窃取调度程序的另一个关键部分是同级通知。处理器在观察到新任务时通知同级处理器，收到通知的同级处理器如果处于休眠状态时会被唤醒并窃取任务。
    • 缺点：通知太多会导致惊群问题。
    • 改善：当没有任何处理器处于搜索状态时，才进行通知。当处于搜索状态的处理器找到新任务时，它会先退出搜索状态，然后通知下一个处理器。处于搜索状态的处理器是不会收到任何通知的。负责通知的处理器将窃取批处理中的一半任务，然后通知另一个处理器。第三个处理器被唤醒，从前两个处理器中查找任务并窃取其中的一半，从而快速达到负责均衡。
• 减少内存分配
  • 对每个任务只分配一次内存。
• 减少原子引用计数
  • 每个唤醒器都有一个对任务句柄的引用计数，唤醒任务后，将调用 task 的 clone 方法，增大原子计数，然后将引用放入运行队列。当处理器执行完任务时，它将删除引用，减少原子计数。这些原子操作虽然代价很低但是积少成多。
    • 改善：提供 weke 方法直接获取所有权，而非获取引用。调度程序需要维护未完成任务的列表。
      • 困难：需确保调度程序在任务结束前不会从其列表中删除任何任务。

3 使用 Loom 无畏并发

Loom 是一个用于测试并发代码的工具。Loom 会运行多次用例，同时会枚举在多线程环境下可能遇到的行为，并验证内存访问、内存分配和释放是否正确。

参考

https://tokio.rs/blog/2019-10-scheduler