在O(n)和O(1)调度器中，时间片是一个很重要的概念，它决定了一个任务能够运行多长时间而不被抢占。对于内核，时间片的机制是这样的，每当系统时钟中断来临，调度器从当前任务的时间片中减去一个时钟周期，直至时间片耗完，这个时候当前任务返回用户空间会，换成其他任务执行，所以时间片的划分是调度器设计上重要的问题。
为了解决上面问题，以往的调度器把动态优先级和时间片绑定在一起，高优先级的进程获得长的时间片，而低优先级的进程获得短的时间片，调度器优先调度具有时间片长的任务。但是这样分配不合理，时间片长的进程并不一定是当下最需要CPU时间的任务。但是这样的算法还是存在一定的问题
-
高优先级任务的应用会比低优先级任务获得更多的资源，这样会导致一个调度周期内，低优先级的任务可能一直无法得以响应，直到高优先级任务接收。在实际使用的过程中，发现，当一个CPU消耗性任务启动后，那些用户交互程序都可以感觉到明显的延迟。
-
高优先级的进程将获得更多的执行机会，这是CPU消耗性的任务的期望的，但是，实际上，CPU消耗性进程往往是后台执行，优先级都比较低。例如，我们使用用户交互进程，并设定它的优先级很高，以便它能有更好的用户体验，给它分配一个很大的时间片。实际中，我们发现，这个进程多半是处于阻塞状态的，等待用户的输入。
针对以上问题，linux2.6.23版本引入了CFS(Complete Fair Scheduler)，引入了公平性的概念。本章主要是学习CFS调度器的相关原理性内容。
1. CFS调度器基本思想
CFS调度器核心原理很简单，就是使得每个进程都尽可能“公平”地获得运行时间，因此每次都选择过去运行得最少的进程运行，也就是在真实的硬件上实现理想的、精准、完全公平的多任务调度。引入公平性的概念：CFS假设一个理想化的CPU，同时可以运行所有的任务，以动态优先级为权重，那么CFS调度器如何理想化呢?
• CFS调度器和以往得调度器不同之处在于没有时间片得概念，而是分配CPU使用时间的比例
• CFS为了实现公平，必须惩罚当前正在运行的进程，以使得哪些正在等待的进程下次被调度
CFS引入了虚拟运行时间(vruntime)，每个调度实体的运行时间，任务的虚拟运行时间越小，意味着任务被访问的时间越短，其对处理器的需求就越高，其核心的思想表现如下：
- 进程的运行时间相等
- 对睡眠的进程进行补偿
所以CFS调度器本质上是改进了Round Robin的真是运行时间片的基础上实现了一个虚拟的运行的时间的概念，每个进程都有要给vruntime值，根据不同的权重，vruntime就是该进程的实际运行时间。得到这个vruntime之后，系统将会根据进程的vruntime的排序，基于红黑树，vruntime最小进程会最早得到调度。
2. 关于公平
CFS与以往的调度器不同之处在于没有时间片的概念，而是公平分配CPU使用时间。例如：2个相同优先级的进程在一个CPU上运行，那么每个进程将会分配50%的CPU运行时间，这就是要实现的公平。但是现实是残酷的，必然是有的进程优先级高，有的进程优先级。
针对该问题，CFS调度器引入了权重的概念，有权重代表进程的优先级，各个进程按照权重的比例分配CPU的时间，因此CFS调度器的公平就是保证所有的可运行状态的进程按照权重分配其CPU资源。例如
2个进程A和B，A进程的权重是1024，B进程的权重是2048，那么
A获得CPU的时间比例是1024/(1024+2048) = 33.3%
B获得CPU的时间比例是2048/(1024+2048) = 66.7%
实际运行时间 = 调度周期 * 进程权重 / 所有进程权重之和
CFS调度器用nice值来表示优先级，取值范围是[-20,19]，nice值和权重是一一对应的关系。数字越小代表优先级越大，同时意味着权重值越大，而内核本身，选择范围[0,139]在内部表示优先级，同样是数值越低优先级越高。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b130pgXl-1641641082356)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/be1bd92f-ddfc-43a4-8964-5fa9ad07edab/Untitled.png)]
对于普通的进程，可以认为优先级不会发生变化，而实时进程则不然：
static int effective_prio(struct task_struct *p)
{
p->normal_prio = normal_prio(p);
//如果不是实时进程，返回前面normal_prio的计算结果
if (!rt_prio(p->prio))
return p->normal_prio;
return p->prio;
}
nice值与权重之间是一对一的关系，为了实现普通进程的nice值到CPU时间权重的快速计算，内核预计算好了一个映射数组。对于linux内核的nice和权重之间的转换关系如下所示
- 进程每降低一个nice级别，优先级则提高一个级别，相应的进程多获得10%的CPU时间
- 进程每提升一个nice级别，优先级则降低一个级别，相应的进程减小得10%的CPU时间
内核预定nice值为0的进程权重为1024，其他nice值对应的权重值可以通过查上述表来获得。同时对于10%的影响也是相对的，累加的。例如一个进程增加10%的CPU时间，则另外一个进程减小10%，因此差距大约是20%，这里使用一个系数1.25来计算。
• 如果进程A和进程B的nice值都为0，那么权重值就是1024，那么它们将获得50%的CPU时间，计算公式为
1024/(1024+1024) = 50%
• 假设进程A增加nice值，此时变成nice = 1，那么进程B理论上将获得55%的CPU时间，而进程A应该获得45%的CPU时间
• 我们利用prio_to_weight表来计算，对于进程A，其获得CPU时间为820/(820+1024)=44.5%
对于进程B，其获得CPU时间为1024/(820+1024)=55.5%
3. 虚拟运行时间
有了进程在CPU运行的权重之后，内核就可以根据权重值计算出进程的虚拟运行时间（virtual runtime）。
什么是“虚拟运行时间”，就是内核根据进程运行的实际时间和权重计算出来的一个时间，CFS调度器只需要保证在同一个CPU上面运行的进程，其虚拟运行时间一致即可。
假设一个CPU调度的周期是6ms，进程A和进程B的权重分别是1024(nice值为0)和820(nice值为1)，
• 那么进程A获得的运行时间是6*1024/(1024+820)=3.3ms，进程A的CPU使用比例是3.3/6=55%
• 进程B获得的运行时间是 6 * 1024/(1024+820) = 2.7ms，进程B的CPU使用比例是2.7/6=45%
符合上面说的“进程每降低一个nice值，将多获得10%的CPU时间。
很明显，2个进程的实际执行时间是不相等，但是CFS想保证每个进程运行时间相等。因此CFS引入了虚拟时间的概念。也就是说上面的2.7ms和3.3ms经过一个公式的转换可以得到一个一样的值，这个转换后的值就被称作为虚拟时间。对于CFS只需要保证每个进程运行的虚拟时间是相等的即可，虚拟时间vriture_runtime和时间的时间(wall time)转换公式如下：
virture_runtime = wall_time * NICE_0_LOAD / weight
按照这样的公式，对于上图例子中的进程A和进程B，我们可以看出其虚拟运行时间是相同的
• 进程A的虚拟运行时间：3.3 * 1024 / 1024 = 3.3ms
• 进程B的虚拟运行时间：2.7 * 1024/820 =3.3ms
我们可以看出，尽管A和B进程的权重值不一样，但是计算得到的虚拟时间是一样的。因此CFS就可以保证每个进程获得执行的虚拟时间一致即可。在选择下一个即将运行的进程的时候，只需要找到虚拟时间最小的进程即可，为避免浮点数运算，因此我们采用先放大再缩小的方式以保证计算精度，内核又对公式做了如下转换
对于权重的值，已经计算保存在sched_prio_to_weight数组中，所以这个很容易计算出inv_weight，通过后面的公式计算，对于内核使用sched_prio_to_wmult[40]，它也是预先计算好的
- 例如当nice值为0的进程，其inv_weight就为： 232/NICE_0_LOAD=232/1024=4194304，符合预期
3. vruntime计算
内核使用0139的数值表示进程的优先级，数值越低，优先级越高。优先级099给实时进程使用，100~139给普通进程使用，内核使用load_weight数据结构来记录调度实体的权重信息
struct load_weight {
unsigned long weight; /* 存储了权重的信息 */
u32 inv_weight; /* 存储了权重值用于重除的结果 weight * inv_weight = 2^32 */
};
由上面的可以知道，weight代表进程的权重，而Inv_weight等于上面公式计算的值。内核提供了一个函数来查询上面的两个表，然后把这个值放在p->se.load数据结构中，级load_weight数据结构中，详细的代码见
//set_load_weight负责根据非实时进程类型极其静态优先级计算符合权重
//实时进程不需要CFS调度, 因此无需计算其负荷权重值
static void set_load_weight(struct task_struct *p)
{
//由于数组中的下标是0~39, 普通进程的优先级是[100~139]，将静态优先级转换成为数组下标
//权重值取决于static_prio，减去100而不是120，对应了下面数组下标
int prio = p->static_prio - MAX_RT_PRIO;
//task_statuct->se.load获取负荷权重的信息
struct load_weight *load = &p->se.load;
/*
* SCHED_IDLE tasks get minimal weight:
* 必须保证SCHED_IDLE进程的负荷权重最小
* 其权重weight就是WEIGHT_IDLEPRIO
* 而权重的重除结果就是WMULT_IDLEPRIO
*/
if (idle_policy(p->policy)) {
load->weight = scale_load(WEIGHT_IDLEPRIO); //IDLE调度策略进程使用固定优先级权重，取最低普通优先级权重的1/5
load->inv_weight = WMULT_IDLEPRIO; //取最低普通优先级反转权重的5倍
return;
}
/* 设置进程的负荷权重weight和权重的重除值inv_weight */
load->weight = scale_load(sched_prio_to_weight[prio]);
load->inv_weight = sched_prio_to_wmult[prio];
}
有了前面的铺垫，来看内核中对应的实现，内核中使用函数__calc_delta来将实际时间转换为虚拟时间，算法原理就是前面介绍到的公式
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD))
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
return delta;
}
按照之前的理论，nice值为0(权重为NICE_0_LOAD)的进程的虚拟时间和实际的时间是相等的，那么此进程对应的虚拟时间就不用计算了，如果不为0，就需要调用__calc_delta计算虚拟时间。
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
u64 fact = scale_load_down(weight); /*fact等于weight*/
int shift = WMULT_SHIFT; /*WMULT_SHIFT为32*/
__update_inv_weight(lw); /*更新load_weight->inv_weight，一般情况下已经设置，不需要进行操作 */
if (unlikely(fact >> 32)) { /*一般fact>>32为0，所以跳过*/
while (fact >> 32) {
fact >>= 1;
shift--;
}
}
/* hint to use a 32x32->64 mul */
fact = (u64)(u32)fact * lw->inv_weight;
while (fact >> 32) {
fact >>= 1;
shift--;
}
return mul_u64_u32_shr(delta_exec, fact, shift);
}
这里主要考虑两种极限的情况：
- 当
lw->weight特别小，比如为1时，__update_inv_weight(lw)会把lw->inv_weight置为WMULT_CONST（即0x ff ff ff ff）,NICE_0_LOAD等于1024相当于将0x ff ff ff ff再右移10位。因此，第二个while循环后shift的值会变为22。mul_u64_u32_shr(delta_exec, fact, shift)相当于delta_exec * (2^32-1) / 2^22变换成delta_exec * (2^10 - 1/2^22)，算下来应该与delta_exec * 1024的值差不多。 - 当
lw->weight特别大，甚至超过WMULT_CONST（即0x ff ff ff ff）时，__update_inv_weight(lw)会把lw->inv_weight置为 1 ，两次while循环都不会产生fact右移的情况。fact仍然是NICE_0_LOAD，而shift还是32，故mul_u64_u32_shr(delta_exec, fact, shift)相当于delta_exec >> 22（2^22 = 4,194,304）。
以下将前面的nice值、权重、虚拟运行时间的关系总结如下图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OvMdncim-1641641082358)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7cce8ff8-87db-4b05-8bcd-8f3c0f77a162/Untitled.png)]
对于上面的vruntime该如何理解呢？这里面有一个真实事件和虚拟事件的概念，如下图，假设系统中有3个进程A、B、C，
- 假设它们的nice值都为0，也就是权重值都是1024，它们分配到运行时间相同，即虚拟时间过得跟真实的时间是一样的
- 假设进程的nice值不为0，并且nice值小的进程优先级高，那么虚拟时间比真实的时间过得慢
- 假设进程的nice值不为0，并且nice值大的进程优先级低，那么虚拟时间比真实的时间过得快
所有CFS调度器抛弃了以前固定时间片和固定调度周期的算法，而是采用进程权重比重来量化和计算实际运行时间。另外引入了虚拟时钟的概念，每个进程的虚拟时间是虚拟运行时间相对nice值为0的权重的比例。
- nice值越小的进程，优先级高且权重越大，vruntime值越小，其虚拟时钟比真实时钟跑的慢，也就可以获得比较多的运行时间
- nice值越大的进程，优先级低且权重越低，vruntime值越大，其虚拟时钟比真实时钟跑的快，反而获得比较少的运行时间。
CFS调度器 总是选择 虚拟时钟跑得慢 的进程，它像一个 多级变速箱 ， NICE为0 的进程是 基准齿轮 ，其他各个进程在不同的变速比下相互追赶，从而达到公正公平
4 调度延迟
传统的调度器无法保证调度延迟，调度的延迟是和系统的负载相关，当负载增加的时候，用户更容易观察到卡顿的现象。
假设CPU的就绪队列上由两个nice value等于0的进程A和B，传统调度器会为每一个进程分配一个固定的时间片100ms，这个时候A先运行，直到100ms的时间耗尽，然后B进行。这两个进程会交替运行，那么调度的延迟是100ms。
但是随着系统的负担越来越重，假如又有两个nice值为0的进程C和D挂到就绪队列，这个时候A→B→C→D交替运行，调度延时就变成了300ms
所以调度延迟就是保证每一个可运行进程都至少运行一次的时间间隔，如果保持调度延时不变，例如固定是6ms，那么系统中如果有两个进程，那么每个进程的运行时间为3ms；但是如果系统中有100个进程，那么每个CPU分配到时间片就为0.06ms，将会导致系统的进程调度太过于频繁，上下文切换时间开销就变大。所以CFS调度器的调度延迟的设定并不是固定的。
当系统就绪态进程个数超过这个值时，我们保证每个进程至少运行一定的时间才让出cpu。这个“至少一定的时间”被称为最小粒度时间。在CFS默认设置中，最小粒度时间是0.75ms。用变量sysctl_sched_min_granularity记录。因此，调度周期是一个动态变化的值。调度周期计算函数是__sched_period()。
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;
}
5 总结
CFS（完全公平调度器）是Linux内核2.6.23版本开始采用的进程调度器，它的基本原理是这样的：设定一个调度周期（sched_latency_ns），目标是让每个进程在这个周期内至少有机会运行一次，换一种说法就是每个进程等待CPU的时间最长不超过这个调度周期；然后根据进程的数量，大家平分这个调度周期内的CPU使用权，由于进程的优先级即nice值不同，分割调度周期的时候要加权；每个进程的累计运行时间保存在自己的vruntime字段里，哪个进程的vruntime最小就获得本轮运行的权利。
