Tokio 解析之任务调度( 二 ) _Tokio

偷取其他 Thread 的任务

如果开始操作时，已经有其他 Thread 在偷取任务，那么 load 出来的结果中 Steal 和 Head 的值一定不等，那么放弃本次偷取，直接结束操作。
如果开始操作时，只有该 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 的其他优化除了上述的核心数据结构，还有一些其他的技巧，被用以提高任务偷取的效率，这里简单列出几项：

限制同时实施任务偷取的线程数量。由于等待线程唤醒是一次性唤醒所有人，所以有可能发生大家都在偷其他线程的任务，竞争太激烈。为了避免上述情况的发生，Tokio 默认只允许一半的线程实施任务偷取，剩下的线程继续进入睡眠。
偷取对象的公平性。所谓“薅羊毛不能盯着一头羊薅”，偷取目标的选择也应该是随机的，因此初试偷窃目标是通过一个随机数生成器来决定，保证了公平性，让队列的任务更加平均。
偷取操作不应该太频繁，所以每次偷取任务的数量也不能太少，所以 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 的其他组件，一定会提到这块 “基石” 在其中起到的作用。

【Tokio 解析之任务调度】