4.3.4 调度策略的活动

想象下面这样一个系统，他拥有两个可运行的进程：一个文字编辑程序和一个视频编码程序。文字编辑程序显然是I/O消耗型的，因为它大部分时间都在等待用户的键盘输入（无论用户的输入速度有多快，都不可能赶上处理的速度）。用户总是希望按下键系统就能马上响应。相反，视频编码程序是处理器消耗型的。除了最开始从磁盘上读出原始数据流和最后把处理好的视频输出外，程序所有的时间double用来对原始数据进行视频编码，处理器很轻易地被100%使用。它对什么时间开始运行没有太严格的要求——用户几乎分辨不出也并不关心它到底是立刻就运行还是半秒钟以后才开始。当然，它完成的越早越好，至于所花时间并不是我们关注的主要问题。

在这样的场景中，理想情况是调度器应该给予文本编辑程序相比视频编码程序更多的处理器时间，因为它属于交互式应用。对文本编辑器而言，我们有两个目标。第一是我们希望系统给它更多的处理器时间，这并非因为它需要更多的处理器时间（其实它不需要），是因为我们希望在它需要时总是能得到处理器；第二是我们希望文本编辑器能在其被唤醒时（也就是当用户打字时）抢占视频编码程序。这样才能确保文本编辑器具有很好的交互性能，以便能响应用户输入。在多数操作系统中，上述目标的达成是要依靠系统分配给文本编辑器比视频解码程序更高的优先级和更多的时间片。先进的操作系统可以自动发现文本编辑器是交互性程序，从而自动地完成上述分配动作。Linux操作系统同样需要追求上述目标，但是它采用不同的方法。它不再通过给文本编辑器分配给定的优先级和时间片，而是分配一个给定的处理器使用比。假如文本编辑器和视频解码程序是仅有的两个运行进程，并且又具有同样的nice值，那么处理器的使用比将都是50%——它们平分了处理器时间。但因为文本编辑器将更多的时间用于等待用户输入，因此它肯定不会用到处理器的50%。同时，视频解码程序无疑将能有机会用到超过50%的处理器时间，以便它能更快地完成解码任务。

这里的关键问题是：当文本编辑器程序被唤醒是将发生什么。我们首要目标是确保其能在用户输入发生时立刻运行。在上述场景中，一旦文本编辑器被唤醒，CFS注意到给它的处理器使用比是50%，但是其实它却用的少之又少。特别是，CFS发现文本编辑器比视频解码器运行的时间短得多。这种情况下，为了兑现让所有进程能公平分享处理器的承诺，他会立刻抢占视频解码程序，让文本编辑器投入运行。文本编辑器运行后，立即处理了用户的击键输入后，又一次进入睡眠等待用户下一次输入。因为文本编辑器并没有消费掉承诺给它的50%处理器使用比，因此情况依旧，CFS总是会毫不犹豫地让文本编辑器在需要时被投入运行，而让视频处理程序只能在剩下的时刻运行。

4.4.2 Unix系统中的进程调度

第一个问题，若要将nice值映射到时间片，就必然需要将nice单位值对应到处理器的绝对时间。但这样做将导致进程切换无法最优化进行。举例说明，假定我们将默认的nice值（0）分配给一个进程——对应的时间片是100ms；同时再分配一个最高nice值（+20，最低优先级）给另一个进程——对应的时间片是5ms。我们接着假定上述两个进程都处于可运行状态。那么默认优先级的进程将获得20/21(105ms中的100ms)的处理器时间，而低优先级的进程会获得1/21（105中的5）的处理时间。我们本可以选择任意数值用于本例子中，但这个分配值正好是最具有说服力的，所以我们选择它。现在，我们看看如果运行两个同等低优先级的进程情况会如何。我们是希望它们能各自获得一半的处理器时间，事实上也确实如此。但是任何一个进程么次仅仅只能获得5ms的处理器时间（10中各占一半）。也就是说，相比刚才的例子中105ms内进行一次上下文切换，现在则需要在10ms内继续进行两次上下文切换。类推，如果是两个具有普通优先级的进程，它们同样会每个获得50%处理器时间，但是是在100ms内各获得一半。显然，我们看到这些时间片的分配方式并不很理想：它们是给定nice值到时间片映射与进程运行优先级混合的共同作用结果。事实上，给定高nice值（低优先级）的进程往往是后台进程，且多是计算密集型；而普通优先级的进程则更多是前台用户任务。所以这种时间片分配方式显然适合初衷背道而驰的。

第二个问题涉及相对nice值，同时和前面的nice值到时间片映射关系也脱不了干系。假设我们有两个进程，分别具有不同的优先级。第一个假设nice值只是0，第一个假设是1。它们将被分别映射到时间片100ms和95ms（O(1)调度算法确实这么干了）。它们的时间片几乎一样，其差别微乎其微。但是如果我们的进程分别赋予18和19的nice值，那么它们则分别被映射为10ms和5ms的时间片。如果这样前者相比后者获得了两倍的处理器时间。不过nice值通常都使用相对值（nice系统调用是在原值上增加或减少，而不是在绝对值上操作），也就是说：“把进程的nice值减小1”所带来的效果极大地取决于其nice的初始值。

第三个问题，如果执行nice值到时间片的映射，我们需要能分配一个绝对时间片，而且这个绝对时间片必须能在内核的测试范围内。在多数操作系统中，上述要求意味着时间片必须是定时器节拍的整数倍。但是这么做必然会引发几个问题。首先，最小时间片必然是定时器节拍的整数倍，也就是10ms或1ms的倍数。其次，系统定时器限制了两个时间片的差异：连续的nice值映射到时间片，其差别范围多至10ms或者少则1ms。最后，时间片还会随着定时器节拍改变。

第四个问题（最后一个关于基于优先级的调度器为了优化交互任务而唤醒相关进程的问题）。这种系统中，你可能为了进程能够更快地投入运行，而去对新药唤醒的进程提升优先级，即便它们的时间片已经用尽了。虽然上述方法确实能提升不少交互性能，但是一些例外情况也有可能发生，因为它同时也给某些特殊的睡眠/唤醒用例一个玩弄调度器的后门，使得给定进程打破公平原则，获得更多处理器时间，损害系统中其他进程的利益。

Linux内核设计与实现详摘