关于任务调度:Tokio解析之任务调度

简介

Tokio 是 Rust 世界里最驰名的异步执行框架，该框架包罗了简直所有异步执行的接口，包含但不限于文件、网络和文件系统治理。在这些方便使用的高层接口之下则是一些“基石”，他们并不存在于用户间接交互的接口中，而是藏于表层之下默默实现工作。这其中就包含了线程池，执行异步工作的根本单元，本文就来介绍一下 tokio 的线程池及其调度，尽可能阐明其中乏味的关键点。本文波及的代码次要在 tokio/src/runtime 下。

线程池

线程池的概念在许多语言中都有，个别大家应用线程池的起因是缩小创立和销毁线程带来的性能损失。在 tokio 中线程池被用作执行异步 task 的执行资源，例如下列代码其实就是创立了一个异步工作放到了 tokio 线程池中：

tokio::spawn(
    // This is an async task
    async {...}
);

至于如何寄存这些 task，有几种不言而喻的抉择（并非只有这几种）：

1. 将所有的待执行 task 都放到一个公共的队列中（即全局队列），每个线程都从这个队列中拿取信息。
2. 每个线程本人一个独立队列，只抓取本人队列中的 task 执行，队列中 task 空了就歇着。
3. 每个线程本人一个独立队列，首先抓取本人队列中的 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。如下图所示：

当没有人来偷取工作时，Tail 和 Head 相等，指向同一块地位。上面咱们剖析几种状况，看看该数据结构如何解决多人并发拜访的问题。

以后 Thread 拿取本地的 Task

1. 如果开始操作时还没有人来偷取工作，那么读取（应用 Atomic Load 办法读取，并 unpack）到的 Steal 和 Head 肯定相等，那么只须要将 Steal 和 Head 都加一，再利用 compare and swap (cmp-swp) 操作存入后果，胜利的话则阐明 task 拿取胜利。这里存在两个原子操作，第一个为 load，第二个为 cmp-swp，第二个操作有可能失败，失败的起因是此时凑巧其余线程来偷取工作，批改了该原子变量。如果 cmp-swp 操作失败，则头开始再尝试一次即可，直到胜利。
2. 如果开始操作时曾经有人正在偷取工作，那么读取到的 Steal 和 Head 肯定不相等，那么只须要将 Head 加一，Steal 放弃不变，再利用 cmp-swp 操作存入后果即可。同上，cmp-swp 如果胜利，阐明拿取本地 task 胜利，否则失败，反复上述操作直到胜利。

偷取其余 Thread 的工作

1. 如果开始操作时，曾经有其余 Thread 在偷取工作，那么 load 进去的后果中 Steal 和 Head 的值肯定不等，那么放弃本次偷取，间接完结操作。
2. 如果开始操作时，只有该 Thread 在偷取工作，那么 load 进去的后果 Steal 和 Head 肯定相等，那么 Steal 值不变，仅仅减少 Head，而后利用 cmp-swp 操作存入后果。此操作的外在含意为，提前预留一块区域为偷取区域。如果 cmp-swp 胜利则表明偷取工作能够持续，以后状态如下图所示。当偷取（将 Steal 到 Head 两头的工作挪动到偷窃者队列中）实现时，再将 Steal 变为和 Head 一样，最初利用 cmp-swp 操作存入后果。偷窃完结后的状态和开始前一样，Steal 和 Head 保持一致。这里值得注意的是，偷取包含三个原子操作，第一个为 load，第二个和第三个为 cmp-swp。第二个 cmp-swp 胜利表明能够开始偷窃工作，第二个 cmp-swp 失败表明还有其余线程在操作队列（可能是其余线程在做偷取，也有可能本地线程在拿本人的工作），则从头再试一次。第三个 cmp-swp 胜利表明没有线程在同步操作，失败则表明本地线程在拿取工作，这里重试将第一个 load 和 第三个 cmp-swp 再做一次即可。

总结一下，工作偷取的关键点：应用一个原子变量存储 Steal 和 Head 两个值。应用 cmp-swp 操作，保障操作过程中，没有其他人进行改变，如果有则重试。同一时间只有一个偷窃操作可能胜利。上述的办法就实现了仅仅应用一个原子变量也能保障并发平安的 ring buffer，十分奇妙。

Work Steal 的其余优化

除了上述的外围数据结构，还有一些其余的技巧，被用以进步工作偷取的效率，这里简略列出几项：

1. 限度同时施行工作偷取的线程数量。因为期待线程唤醒是一次性唤醒所有人，所以有可能产生大家都在偷其余线程的工作，竞争太强烈。为了防止上述情况的产生，Tokio 默认只容许一半的线程施行工作偷取，剩下的线程持续进入睡眠。
2. 偷取对象的公平性。所谓“薅羊毛不能盯着一头羊薅”，偷取指标的抉择也应该是随机的，因而初试偷窃指标是通过一个随机数生成器来决定，保障了公平性，让队列的工作更加均匀。
3. 偷取操作不应该太频繁，所以每次偷取工作的数量也不能太少，所以 Tokio 采取了“零售”的策略，每次都偷取以后队列一半数量的工作。

Work Steal 没有解决的问题

Work Steal 还有一些问题没有解决，例如当本地队列一下子涌入过多 task 的时候，这些 task 应该放在哪里？不限度长度的本地队列显然不是一个可选计划，这样会齐全突破上述的 ring buffer 设计。Tokio 的解决办法是，在本地队列之外依然保护了一个共有队列，本地放不下的工作能够放到共有队列中，因为本地队列的存在，拜访共有队列的机会不多，所以竞争不会太强烈，效率也就失去了保障。

即使如此依然存在后续问题，例如如果所有线程都优先思考本地队列，则会呈现一种可能状况——共有队列上的工作永远没有被调度起来的机会。为了防止这种不平衡的状况呈现，Tokio 规定了每个线程在拿取了 61 个本地队列的 task 后就须要去共有队列中看一看，通过这种机制保障了共有队列中的工作在无限的工夫内肯定会被调度起来。至于为何采纳了 61 这样奇怪的数字，代码中的解释如下，翻译过去就是“抄 golang 的，具体为啥问 golang 去”。

/// The number is fairly arbitrary. I believe this value was copied from golang.

总结

Tokio 为其多线程执行器实现了一个高效的工作偷取机制，保障了多线程可能高效并且平衡地调度工作。Tokio 的任务调度零碎是其余组件的“基石”，之后的文章会持续剖析 Tokio 的其余组件，肯定会提到这块“基石”在其中起到的作用。