2.3.7 RSDL
设计调度器是个很复杂的工作，特别是要设计出一款通用调度器，其面临的挑战更大，因为不同的应用场景有不同的需求，交互式任务希望响应速度更快，批处理任务希望吞吐量更大，多核架构下，又需要在高效利用所有CPU的前提下，尽量保证高速缓存与TLB的命中率。尽管O(1)调度器针对O(n)的问题做了很多优化，在大多数情况下也工作得很好，但依然有用户抱怨在特定场景下存在各种问题。
识别与奖励交互式任务本质上是在追求时间分配的公平性，而仅仅通过进程行为来判断其是否是交互式任务实际上是没有理论依据的，尽管O(1)在算法上做了很多改进，包括考量进程在CPU 上的运行时间、在runqueue中的等待时间、睡眠时间以及进程睡眠时的状态等，但这些努力也只是能够提升“猜中”的概率而已，总有用户举出在特殊场景下交互式任务响应太慢的例子，反而导致代码变得非常复杂。同时不管是O(n)还是O(1), 其对交互式任务的奖励方式都会造成任务的调度延迟是不确定的，我们无法通过有效的手段得到某个任务的延迟响应时间。
后来，大家尝试着抛弃“评估任务的交互性”这种思路来寻找解决办法，RSDL(Rotating Staircase Deadline Scheduler)便是这样的一种方案。该方案由Con Kolivas提出，我们在这里简单讨论一下其设计思路。
同O(1)一样，在每个调度周期内，RSDL会根据任务的优先级为其分配固定的CPU时间，并且为每一个优先级维护一个任务列表。但在任务运行过程中，任务不会始终呆在自己优先级所对应的任务列表中，而是随着时间的消耗顺着优先级的任务阶梯逐级下降，直到所有任务的运行时间耗尽，调度器再开启下一轮调度。下图展示了4个任务分别在4个优先级中的调度流程：
不同的优先级任务队列形成一个阶梯 - Staircase, 每当一个任务在当前优先级的运行时间耗尽后，就会发生一次轮转 - Rotating. RSDL的核心思想体现在对任务运行时间的管理上，其本质上是将任务的运行时间逐级下降地分配到了每个优先级上，这种设计简化了调度逻辑：调度器只需要从高到底地遍历优先级任务队列，然后运行每个任务即可。
当然，上图只体现了RSDL的核心思想，具体实现中还要考虑很多其他因素，例如如何避免某个优先级的任务列表中堆积了太多任务，导致更低优先级的任务等待时间过长。详细的设计可以参见作者的这篇文章
虽然RSDL最终没有并入Linux的内核中，但它在公平调度这方面的想法启发了后来的CFS, 因此对其加以了解也是有益的。更多资料可以参考：
Last updated