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

传统的调度器设计，一个任务能够运行多长时间而不被抢占，是根据分配给这个任务的时间片决定的。优先级高的任务分配的时间片就长，优先级低的任务分配的时间就短。

系统根据每个进程的nice值来决定如何分配时间片。但nice值的范围只有-20到+19，共40个离散的值。如何用这40个值来给那么多运行中的任务定优先级、分时间片？能保证每个任务得到应得的运行时间吗？

上面问题的答案显然是不行的。现在计算机的性能越来越好，同时运行的任务越来越多，不同的任务对CPU时间有不同的需求，40个nice值已经不能满足需求了。

按nice值分配时间片的方法有以下几个缺点：

  • 考虑到CPU切换任务需要花费一定的代价（消耗CPU时间，影响Cache性能），优先级最低的nice值（+19）对应的时间片就无法设的太小。假设nice+19的时间片设为5ms，如果系统当前只有两个nice+19的任务同时运行，这两个任务就会每5ms切换一次，这种情况下本不需要如此快切换。
  • 优先级最高的nice值（-20）对应的时间片不能设置的太大。假设nice-20的时间片是100ms，当某个nice-20的任务运行时，突然一个交互性任务需要运行（比如响应键盘输入），这个交互性任务可能最长需要等待100ms才能获得CPU时间。
  • 无法使用比较优先级。假设任务A、B的nice值是0、1，它们获得的时间片可能是100ms，95ms；如何任务A、B的nice值是18，19，它们获得的时间片可能是10ms，5ms。虽然两种情况下时间片的差别都是5ms，但是第二种情况下任务A获得的CPU时间远超过第一种情况（A的10ms对B的5ms）。
  • 时间片依赖于系统时钟的精度（系统时钟可以是1ms~10ms）。假设系统时钟是10ms，那么时间片的最小值只能是10ms，而且时间片之间的差距最小值也只能是10ms。如果一个任务的应得运行时间是1ms或11ms，但实际得到的则是10ms或20ms。对一个任务分配超过应得的运行时间，就会对系统中其他任务造成不公平。
  • 另外一种不公平现象会发生在交互性任务的调度上。为了保证系统的交互性（例如让大家敲键盘的时候不感觉到延迟），调度器一般会偏向交互性任务，在调度的时候优先保持它们的低延迟。这回造成一种情况，当一个交互性任务刚用完它的应得时间片后，突然来了一个交互请求（一个键盘输入），调度器很可能重新给这个任务分配新的时间片。对一个任务太好，就是对其他任务不太好，公平性就无法保证。

在2.6.23之前，Linux使用的是O（1）调度器。为了缓和上面的问题，O（1）调度器的代码变得异常复杂。虽然修修补补改进了O（1）的性能，但是根本的问题没有解决，即按优先级来分配时间片既会把任务可以选择的时间片限定在某一范围，又会导致对单一任务分配超过应得的时间片，从而影响总体的公平性。

这篇到此为止，以后会介绍2.6.23引入了CFS调度器，不再把nice值直接映射到时间片了，一举解决了上述问题。

  • 文章中涉及的任何代码都参考Linux v4.4。
  • Documentation/scheduler/sched-nice-design.txt