06-完全公平调度器

6.2　完全公平调度器

完全公平调度器和传统的UNIX进程调度器有很大区别。在大多数UNIX系统中，包括引入CFS之前的Linux系统，在进程调度中存在两个基本的基于进程的因素：优先级和时间片。正如在前面的章节中所提到的，在传统的进程调度器中，会给每个就绪进程分配一个时间片，表示分配给该进程的处理器“分片”。进程可能会一直运行到消耗完其分配到的时间片。此外，还给每个进程分配优先级。进程调度器会先调度运行优先级高的进程，然后再运行优先级低的进程。这个调度算法非常简单，而且对于早期的基于时间片共享的UNIX系统效果良好。但是，需要交互和公平性的系统而言，比如现代计算机的桌面和移动设备，该算法就有些差强人意了。

完全公平调度器引入了一种非常不同的算法，称为公平调度，它消除了时间片作为处理器访问分配单元，相反地，它给每个进程分配了处理器的时间比例。算法很简单：CFS在最初给N个进程分别分配1/N的处理器时间。然后，CFS通过优先级（nice value）权衡每个进程的比例，调整分配。默认的优先级是0，权值是1，则比例不变。优先级的值设置越小（优先级越高），权值就越高，就增加分配给该进程的处理器的比例值；优先级的值设置越高（优先级越低），权值越低，就减少分配给该进程的处理器的比例值。

通过这种方式，完全公平调度器就给每个进程分配了基于权值的处理器比例。要确定每个进程真正的执行时间，完全公平调度器需要把比例划分成一个固定的周期。该周期称为“目标延迟（target latency）”，它表示系统的调度延迟。下面我们举个例子，可以帮助理解“目标延迟”这个概念。假设“目标延迟”设置为20ms，存在两个优先级相同的可运行进程。每个进程有相同的权值，并被分配相同的处理器比例，每个进程占用10ms。这样，完全公平调度器就会先执行一个进程，运行10ms，然后执行另一个进程，也运行10ms，这样不断重复。如果系统中有五个可运行的进程，完全公平调度器会每个运行4ms。

目前来看一切都不错，没什么问题。但是，当有200个可运行进程时，怎么办？如果目标延迟是20ms，完全公平调度器会给每个进程仅分配100微妙。由于从一个进程到另一个进程的上下文切换会带来开销（该开销称为“切换开销”），以及无法更好地利用时间局部性，基于以上问题，完全公平调度器引入了另一个关键因素：最小粒度。

“最小粒度”是指任一进程所运行的时间长的基准值。所有进程，不管其分配到的处理器比例是多少，都至少会运行最小粒度的时间（除非被阻塞了）。这种机制可以保证切换代价不会因为目标延迟值很小，而占用过大比例的系统总时间。也就是说，如果在最小粒度内切换进程，就破坏了公平性。设置了目标延迟和最小粒度后，在可运行进程数合理的情况下，不需要应用最小粒度，只需要满足目标延迟，就可以保证公平性。

通过给进程分配处理器资源比例，而不是固定的时间片，完全公平调度可以实现公平性：每个进程都获得了处理器资源的“公平份额”。此外，完全公平调度器还可以支持可配置的调度延迟，因为目标延迟是用户可设置的。在传统的UNIX调度器中，进程运行几个固定的时间片，称为“priori（先验值）”，但调度延迟（运行频率）是未知的。在完全公平调度器中，进程按“配额”运行，其延迟称为“priori”，时间片是根据系统上可运行的进程数而动态变化的。完全公平调度器是完全不同的处理进程调度方案，解决了传统进程调度器对于交互进程和I/O约束型进程所面临的很多问题。