Tokio 解析之任务调度 _Tokio

文章插图

简介Tokio 是 Rust 世界里最著名的异步执行框架，该框架包罗了几乎所有异步执行的接口，包括但不限于文件、网络和文件系统管理。在这些方便使用的高层接口之下则是一些“基石”，他们并不存在于用户直接交互的接口中，而是藏于表层之下默默完成任务。这其中就包括了线程池，执行异步任务的基本单元，本文就来介绍一下tokio 的线程池及其调度，尽可能说明其中有趣的关键点。本文涉及的代码主要在 tokio/src/runtime 下。

线程池线程池的概念在许多语言中都有，一般大家使用线程池的原因是减少创建和销毁线程带来的性能损失。在 tokio 中线程池被用作执行异步 task 的执行资源，例如下列代码其实就是创建了一个异步任务放到了 tokio 线程池中：
tokio::spawn(// This is an async taskasync { ... });至于如何存放这些 task，有几种显而易见的选择（并非只有这几种）：

将所有的待执行 task 都放到一个公共的队列中（即全局队列），每个线程都从这个队列中拿取信息。
每个线程自己一个独立队列，只抓取自己队列中的 task 执行，队列中 task 空了就歇着。
每个线程自己一个独立队列，首先抓取自己队列中的 task 执行，如果自己的队列为空，则从其他线程的队列中偷取。

第一种实现很糟糕，无论如何优化那个公共队列——用锁或者原子操作——竞争带来的性能下降是无法避免的。这里需要指明一点，用原子操作并不是没有竞争，原子操作是将竞争放到了硬件，竞争多了效率仍然不好。
第二种实现也不太好，当一个线程堆满任务时，他的任务来不及执行，而其他空闲线程“无事可做”，造成线程间的不平等。这种不平等也会使得多线程并行执行的优势发挥不出来。
第三种实现则是现在常用的“任务偷取（Work Stealing）”方式，该方法避免了上述两种方法的问题，但在实现细节上仍然有许多值得优化的地方。

Work Steal 如何才能高效Work Steal 的实现方法虽然很直接，但是有个问题仍然无法避免，存在两个或者多个线程同时从一个队列中拿取 task 。想要线程安全，要么采用锁，要么采用无锁数据结构。Tokio 在早期版本中采用了基于 crossbeam 的无锁队列，但是 Tokio 作者认为这种实现仍然太重了（epoch-based gc 仍然效率不高，此为 Tokio 作者观点，本文作者未实验论证），因此之后采用了现在的实现方法。
现在 Tokio 任务队列实现仍然是无锁的，采用的是环形队列数据结构，即ring buffer 。该数据结构为了能够知道哪些 slot 已经被使用，一般会使用两个 index —— head 和 tail，从 tail 初放入 item，从 head 处拿出 item，如下图所示：

文章插图

但是这样的数据结构如果不做修改，仍然无法满足并行访问的需求，因此 tokio 对数据结构进行了一些调整。其将 head 这个 index 变成了两部分，一部分为 head，另一外一部分为 steal 。原来的 head index 为 u32，修改后前面 16 bits 是 steal, 后面 16 bits 为 head，组合一下变成了 AtomicU32 。如下图所示：