Linux System Programming读书笔记之进程调度算法CFS

时间:2021-11-16 14:37:39

Unix(包括CFS问世之前的Linux)系统中,进程调度算法有两个核心概念:时间片(timeslice)和优先级(priority)。在传统的进程调度算法中,每个进程分配了一个时间片, 表示这个进程占用的CPU时间。进程可以一直运行,直到耗尽它的时间片。同样,每个进程分配了一个优先级,进程调度器先运行优先级高的进程,再运行优先级低的进程。这种调度算法简单高效,但是对于要求高交互性和公平性的系统,这种算法就显得效果不好了。

在CFS算法中就没有时间片这个概念了,CFS分配给进程的是处理器时间周期的一个比例(proportion)。CFS算法很简单:假如系统中有N个进程,那么CFS最初给每个进程1/N的处理器时间周期,即每个进程的proportion都是1/N。接下来,CFS根据每个进程的nice值来调节每个进程的权重,进而确定最后的proportion。系统的默认nice值是0,如果一个进程的nice值为0,那么它的权重为1,分配到的proportion不变。而高优先级的进程拥有较小的nice值和较高的权重值,会增加自己的proportion;低优先级的进程拥有较高的nice值和较低的权重值,降低自己的proportion。也就是说,如果进程A占用的处理器时间比例越小,其他进程可用的处理器时间就越多,那么可以看做A进程发扬了风格,对其他进程非常nice,所以就有更高的nice值。

现在,每个进程有了一个加权后的处理器时间周期的分配比例,接下来CFS要确定在每个处理器时间周期内,每个进程究竟运行多长时间。处理器时间周期也叫做目标延迟(target latency),因为它代表了系统的调度延迟。假如我们把目标延迟设为20ms,而系统中有两个优先级一样的进程,那么这两个进程也会拥有一样的权重和一样的proportion,它们在每个处理器时间周期内的运行时间都是10ms。因此,CFS会先运行一个进程10ms,再运行另一个进程10ms,如此反复循环。同样,如果系统中有5个优先级一样的进程,那么每个进程的运行时间是4ms。

这样问题就来了,如果我们有200个进程呢?如果目标延迟仍然是20ms,那么每个进程只有0.1毫秒的运行时间。由于进程不停地切换,减少了系统的时间局部性,会极大地降低系统性能。为了解决这个问题,CFS引入了第二个关键因素:最小粒度(minimum granularity)。最小粒度是每个进程最小的可运行时间,也就是说,不管一个进程被分配到的proportion有多么小,它在一个周期内至少会运行的时间为我们设置的最小粒度。这样就保障了为了达到目标延迟而造成的进程切换开销不会对系统造成太大负担。虽然说最小粒度降低了调度的公平性,但是大多数情况下,系统的目标延迟和进程数都在一个合理的范围内,最小粒度并不会被使用到,调度的公平性不会被影响,

在Unix系统中,每个进程分配到的时间片是固定的,但是调度延迟是不定的。而CFS中,进程的调度延迟是固定的,也就是目标延迟,进程分配到的是目标延迟的一个比例,计算出来时间片是动态变化的。CFS解决了很多传统进程调度算法不易解毒的交互密集型和IO密集型进程相关问题。