CFS Scheduler（CFS调度器）

前面我们分享了O(n)和O(1)调度器的实现原理，同时也了解了各个调度器的缺陷和面临的问题。总的来说O(1)调度器的出现是为了解决O(n)调度器不能解决的问题，而O(1)调度器在Linux2.4内核的在服务器的变形是可行的，但是Linux2.4以后随着移动设备的逐渐普遍，面临的卡顿问题逐渐明晰，这才导致后来的CFS调度器的出现。

本节我们重点来关注下CFS调度器实现，在学习CFS代码之前，我们先看CFS的实现原理，搞清楚它的来龙去脉，以及为啥CFS调度器需要这样设计，基本就可以掌握CFS调度器了。

CFS引入

完全公平调度器(CFS)最早是在2017年merged进Linux2.6.23版本中的，一直到现在都是系统中默认的调度器。内核文章中的sched-design-CFS.txt文档对CFS调度器有一个简单的介绍。

80% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.

这句话的意思是CFS的80%的设计总结起来就一句话“在一个真实的硬件上，实现公平，精确的多任务CPU”

"理想的，精确的，多任务CPU"这句话是啥意思呢？ 到底怎么理解呢？我们来通过例子做下解释

"Ideal multi-tasking CPU" is a (non-existent :-)) CPU that has 100% physical power and which can run each task at precise equal speed, in parallel, each at 1/nr_running speed. For example: if there are 2 tasks running, then it runs each at 50% physical power --- i.e., actually in parallel.

内核文档是这样说的。"理想的，多任务CPU"是在同一时刻每个任务以1/nr_running_speed来运行，也就是同一时刻每个进程瓜分CPU的时间是相同的。例如如果有两个进程运行的话，每个进程占有50%的CPU时间。

举一个例子:

两个批处理进程，总共只能运行10ms。

实际情况：每个进程运行5ms，占有100%的CPU利用率

理想情况：每个进程运行10ms，占有50%的CPU利用率。

而所谓的理想情况就是CFS提到的"Ideal multi-tasking CPU"

上述的例子在一个单核CPU，只有一个处理核心的CPU上是完全不可能的，因为同一时刻只能运行一个进程，另外一个进程必须等待。而CFS就是为了的达到完全公平调度，它应该怎么做呢？

如何才能实现完全公平调度

在O(n)调度器和O(1)调度器中，我们知道都是通过优先级来分配对应的timeslice,也就是时间片。而这些时间片都是固定的。比如在O(n)调度器中nice0对应的时间片是60ms。而在CFS调度器中，不再有时间片的概念。而是根据当前系统中可运行进程的总数来计算出进程的可运行时间的。

在O(n)调度器和O(1)调度器中，普通进程都是通过nice值来获取对应时间片，nice值越大获取的时间片就越多，运行机会就越多。而在CFS调度器中引入了权重weight的概念，通过nice值转化为对应的权重，优先级越高的进程对应的权重就越大，意味着就可以获得更多的CPU时间。

则进程占用CPU的时间 =

进程的weight / 总的可运行进程weight

CFS是让进程通过运行一段时间来达到公平，进程占用的时间就是进程的weight占总的可运行进程的总权重的比值。

举例：总共10ms的时间，单核cpu

• 进程的优先级相同：

如果两个进程的优先级相同，则对应的权重相同，则每个进程占用5ms的CPU时间；如果有5个进程，每个进程占用2ms的CPU时间；如果共10个进程，每个进程占用1ms的CPU时间。

• 进程的优先级不同：

如果两个进程的优先级不同，比如A进程nice是0，B的nice值1，则A进程的优先级就高，weight就越大，对应B的优先级小，weight也小于A。假设A的权重是6，B的权重是4。则A占2/3的CPU时间，B占1/3的CPU时间。

这样一来就达到了公平性，每个进程在各子拥有的权重比例下，占用不同份额的CPU时间。

再结合生活举一例：

公司发年终奖，一般来说一个部门的总包（CPU时间）是固定的。而为了公平老板不会给每个人发同样的奖金的，这样反而不公平了。而是通过平时在公司的表现，工作的认真态度之类（进程的weight）来衡量，比如张XX很辛苦，经常加班，进程出差，年终奖（进程占用CPU的时间）就多发。刘XX经常迟到，下班就没人了，年终奖（进程占用CPU的时间）少发。这样就显得公平。

CFS调度器是如何选择进程的

CFS的目标是让各个进程在一段时间内实现公平，也就是根据进程的权重来瓜分CPU的时间。权重越大则瓜分的CPU时间就越多，分配的CPU时间多就等同于有更大的机会得到CPU。

CFS调度是通过进程的虚拟时间vruntime来选择要运行的进程。vruntime的计算公式如下：

vruntime = (wall_time * NICE0_TO_weight) / weight

其中,wall_time代表的是进程实际运行的时间，NICE0_TO_Weight代表的是nice值等于0对应的权重，weight就是该进程对应的权重。可以看出vruntime的值其实是实际运行时间乘以nice0对应的weight除以进程的权重。

/*
 * Nice levels are multiplicative, with a gentle 10% change for every
 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 * nice 1, it will get ~10% less CPU time than another CPU-bound task
 * that remained on nice 0.
 *
 * The "10% effect" is relative and cumulative: from _any_ nice level,
 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 * If a task goes up by ~10% and another task goes down by ~10% then
 * the relative distance between them is ~25%.)
 */
const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

此表就是nice值和weight的转换变，此表已经计算好了，在代码中需要计算vruntime的时候，只需要根据nice值查表即可。

从注释上可以看出，当nice增大一个台阶，将会减少10%的CPU占用时间；当nice值减少一个台阶，将会获得10%的cpu时间。

从上面计算vruntime的公式可以得出，nice等于0的进程的虚拟时间等于物理时间。当一个进程的weight越大，则对应的进程的vruntime就越小；当一个进程的weight越小，则对应的vruntime就越大。

CFS每次调度原则是，总是选择vruntime最小的进程来调度，vruntime最小的进程weight越大，优先级越高，则就需要更高的获取CPU的时间。

举例说明：总共6ms的时间，有3个进程，一个进程A的权重是1024，另外一个进程B的权重是335，进程C的权重是3121

进程A vruntime = (2ms * 1024) / 1024 = 2ms， CPU占用率 = 1024/(1024+335+3121) = 22%

进程B vruntime = (2ms * 1024) / 335 = 6ms，CPU占用率 = 335/ (1024+335+3121) = 7%

进程C vruntime = (2ms * 1024) / 3121 = 0.65ms，CPU占用率 = 3121/ (1024+335+3121) = 70%

可以看出

1. 各个CPU利用率都是相差50%，因为nice值每增加一个台阶，CPU占用率有10%的差别
2. 进程的权重越大，分母也就越大，则vruntime则就越小，而在下一次选择进程时则高优先级选择它
3. nice0=1024权重的进程的虚拟时间和物理时间是一样的
4. 可以理解权重越大，虚拟时间越小，对应的虚拟时间轴跑的越快
5. 权重越小，虚拟时间越大，对应的虚拟时间轴跑的越慢

调度周期(sched_period)

之前说过一个进程占用的CPU时间是根据进程的weight和系统中总的可运行进程的权重的比值。

进程占用CPU的时间 =

进程的weight / 总的可运行进程weight

比如两个优先级相同进程，总共10ms的时间，每个进程占用5ms。当系统中可运行的进程数目逐渐增多，则每个进程占用的cpu的时间就会越来越小，趋近于0。这就会导致进程之前频繁的发生上下文切换，CPU的大多数时间是用来处理进程的上下文切换了，导致系统效率下降。

所以对于此问题再CFS中则引入了调度周期，调度周期的计算通过如下代码

/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
static u64 __sched_period(unsigned long nr_running)
{
	if (unlikely(nr_running > sched_nr_latency))
		return nr_running * sysctl_sched_min_granularity;
	else
		return sysctl_sched_latency;
}

static unsigned int sched_nr_latency = 8;
unsigned int sysctl_sched_latency			= 6000000ULL;
unsigned int sysctl_sched_min_granularity			= 750000ULL;

从注释上看，这个函数的目的是为了让每个进程都可以运行一次。当系统中的进程数目逐渐增大时，则需要增大调度周期。

当进程的数目小于8时，则调度周期等于调度延迟等于6ms。当系统的进程数目大于8时，则调度器周期等于进程的数目乘以0.75ms。sysctl_sched_min_granularity可以理解为在一个调度周期中一个进程至少保证执行0.75ms。

CFS总结：

• 在O(n)和O(1)调度器中都是通过nice值来分配固定的时间片，CFS中没有时间片的概念
• CFS调度器中通过进程的静态优先级来计算进程的权重，进程的权重就代表了此进程需要获取的CPU的时间比例
• 通过进程的weight和进程的实际运行时间来计算进程的vruntime虚拟时间。
• 当进程加入到运行队列，调度器会时刻来更新进程的vruntime，来达到公平
• 调度器每次调度的时候只选择运行队列中虚拟时间最小的进程，当此进程运行一段时间后，vruntime就会变大
• 这时候就需要调度时候就需要重新选择新的最小vruntime的进程来执行，上次被调度出去的进程则就需要根据vrumtime的值来选择自己在运行队列的位置