单队列单处理器的调度器

最简单的调度器，一个运行队列，不断的从队列中取task来执行，直到队列为空。

while let Some(task) = self.queue.pop() {
    task.run();
}

这种调度器没办法充分利用多核的能力，我们需要多个处理器并行的去处理task，这样才能充分利用现代硬件的多核。

单队列多处理器的调度器

一个multiple producers、multiple consumers的全局队列，多个Processor，一般和CPU的核心数一致。为了实现这样的一个队列，通常采用intrusive linked list算法来实现这样的一个队列，可以避免在push和pop的时候进行内存的分配，可以使用无锁的push操作，但是pop仍然需要一个mutext锁。(技术上可以实现无锁多消费者队列。但是，在实践中，正确避免锁定所需的开销比仅使用互斥锁要大。)，这种调度器相对来说会公平(先进先出)，实现相对简单。但是存在的问题就是所有的Processor都在队头抢占。对于通用线程池来说，这个方案足够了。处理器执行任务所花费的时间远远超过从运行队列中弹出任务所花费的时间。当任务执行时间较长时，队列争用会减少。然而，当从运行队列中弹出时，Rust 的异步任务预计只需要很少的时间执行。在这种情况下，队列竞争的开销变得很大。

多处理器多队列的调度器

每一个处理器都只处理自己的队列，这样就可以避免同步了，减少了竞争。但这种方法并非银弹，任务分配到各个队列并不是平均分布的，这会导致有的队列任务多，有的队列任务少，这会导致CPU资源利用不充分。因此我们需要实现Work-stealing调度。

Work-stealing的多处理器多队列的调度器

真实世界任务并非是统一分布的，这导致有的队列任务多，有的任务执行时间长，最终导致队列中的任务不平均，CPU利用率不高。因此需要让调度器支持Work-stealing，但是这种方法的缺点是要复杂得多。运行队列算法必须支持窃取操作，并且需要一些跨处理器同步以保持事情顺利运行。如果没有正确完成，实施工作窃取模型的开销可能会大于获得的收益。

下一代的Tokio调度器设计

基于std::task系统、自定义vtable、一个更好的Queue实现(基于固定大小的Queue，避免动态大小的Queue带来的管理复杂性，当Local Queue满的时候，task会push到Global Queue)，Tokio在处理Queue的时候，对于Local Queue做到少量的同步或者不同步来保证性能(weak ordering)。对于Task之间的Message Passing，假设Task A通过Channel发送一个消息给Task B，那么此时会将Task B设置成Running状态，放到Queue中，然后Processor开始处理Local Queue，直到遇到Task B，开始执行Task B，这导致消息从Channel发送出去到Task B运行，这期间存在延迟，并且消息属于热数据存在CPU缓存中，如果不是立刻运行Task B的话，会导致缓存失效，理想情况下，应该优先运行Task B，因此Tokio通过一个特殊的Next Task slot。 Tokio优先检查这个Slot中的Task。当消息发送给Task B后，会先将Task B放入到这个特殊的Slot中，Processor开始运行会优先处理这个Slot中的Task，从而解决了这个问题。