LKD（Linux内核设计与实现） Chapter 4 Process Scheduling

以往在调度器的设计中，时间片（timeslice）是一个很重要的概念，它决定了一个任务能够运行多长时间而不被抢占。其机制是这样的，每当系统时钟中断来临时，调度器从当前任务的时间片中减去一个时钟周期，直至时间片耗光，这时候当前任务就会被抢占，换成其他任务执行。所以如何划分和分配时间片成了调度器设计上最重要的问题。

为了解决上面的问题，以往的调度器把动态优先级（nice值）和时间片绑定在一起，高优先级获得长时间片，低优先级获得短时间片，调度器优先调度具有时间片长的任务。但是，如果分配不合理，时间片长的任务并不一定是当下最需要CPU时间的任务。

2.6.23版本引入了CFS（Complete Fair Scheduler），引入了公平性的概念。 CFS假设一个理想化的CPU，可以同时运行所有任务。以动态优先级作为权重，这些同时运行的任务获得其应得的CPU计算能力的一部分。

现实中CPU（的一个核）单次只能运行一个任务，那么CFS调度器如何模拟这个理想化的CPU呢？

  • 计算每个任务的应得运行时间，也就是CPU计算能力份额。计算时以动态优先级为权重，将当前所有可运行任务纳入考量，得出单个任务的应得运行时间。
  • 以任务实际运行时间和应得运行时间差距为调度依据，差距大的优先运行。

上述的原则大大简化了调度决策过程，保证了公平性，顺利解决了以往以时间片长短作为调度依据而导致的时间片分配不均的问题。

同时还创新性地解决了交互性问题，如果一个任务长时间处于I/O等待状态，那么这个任务的实际运行时间和应得运行时间差距就会加大，当被唤醒的时候，它就会被优先调度。以往，交互性问题只能在I/O任务被唤醒的时候分配更多时间片来提升它的优先级。

模拟理想化CPU的最大阻碍来自于切换任务的代价。切换不仅会花费时间，还有可能影响cache的性能，是一个不得不考虑的问题。为此CFS设了一个最小粒度，即一个任务至少能够运行1ms而不被强占。

CFS替代了之前的O（1）调度器，成为SCHED_OTHER（偏向交互性）策略下的默认调度器。

  • 文章中涉及的任何代码都参考Linux v4.4。
  • Documentation/scheduler/sched-design-CFS.txt
  • 为了改进O（1），内核开发者做了许多尝试，其中最引人注目的是RSDL（Rotating Staircase Deadline Scheduler），它引入了排队理论中的公平性调度原则，CFS正是借鉴了这一设计。