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就为：2^{32/NICE_0_LOAD=2}32/1024=4194304，符合预期 
3. vruntime计算
 
内核使用0_{139的数值表示进程的优先级，数值越低，优先级越高。优先级0}99给实时进程使用，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;
		return sysctl_sched_latency;
CFS（完全公平调度器）是Linux内核2.6.23版本开始采用的进程调度器，它的基本原理是这样的：设定一个调度周期（sched_latency_ns），目标是让每个进程在这个周期内至少有机会运行一次，换一种说法就是每个进程等待CPU的时间最长不超过这个调度周期；然后根据进程的数量，大家平分这个调度周期内的CPU使用权，由于进程的优先级即nice值不同，分割调度周期的时候要加权；每个进程的累计运行时间保存在自己的vruntime字段里，哪个进程的vruntime最小就获得本轮运行的权利。
                    在O(n)和O(1)调度器中，时间片是一个很重要的概念，它决定了一个任务能够运行多长时间而不被抢占。对于内核，时间片的机制是这样的，每当系统时钟中断来临，调度器从当前任务的时间片中减去一个时钟周期，直至时间片耗完，这个时候当前任务返回用户空间会，换成其他任务执行，所以时间片的划分是调度器设计上重要的问题。为了解决上面问题，以往的调度器把动态优先级和时间片绑定在一起，高优先级的进程获得长的时间片，而低优先级的进程获得短的时间片，调度器优先调度具有时间片长的任务。但是这样分配不合理，时间片长的进程并不一定是当
				首先需要思考的问题是：什么是调度器（scheduler）？调度器的作用是什么？调度器是一个操作系统的核心部分。可以比作是CPU时间的管理员。调度器主要负责选择某些就绪的进程来执行。不同的调度器根据不同的方法挑选出最适合运行的进程。目前Linux支持的调度器就有RT scheduler、Deadline scheduler、CFS scheduler及Idle scheduler等。我想用一系列文章呈现Linux 调度器的设计原理。
注：文章代码分析基于Linux-4.18.0。
什么是调度类
				CFS(Completely Fair Schduler), 首次出现于Linux2.6.23。
CFS区别于其他调度算法的最突出一点是CFS保证每个任务分配到公平的运行时间。
经典抢占式调度通常包括多个调度队列，每个进程优先级一个：高优先级队列中的每个进程在低优先级队列中的任何进程之前被调度。例如，VAX/VMS 使用 32 个优先级队列进行调度。CFS 省去了固定的时间片和明确的优先级。处理器上给定任务的时间量是随着调度上下文在系统生命周期中的变化而动态计算的。
CFS的一些概念
目标延迟（targ
				CFS（Complete Fair Schedule）调度算法的思想是为每一个task维护一个虚拟的运行时间vruntime
调度程序优先选择vruntime值最小的任务执行，之所以引入vruntime的概念，是为了支持优先级调度。vruntime其实是基于task的实际运行时间及优先级权重计算出来的值，其计算公式如下：vruntime += delta_exec * NICE_0_LOAD / weightvruntime：虚拟运行时间
delta_exec: 实际的执行时间
NICE_0_LOAD：进程
				一、CFS 调度器概念 ( 完全公平调度器 )、
二、CFS 调度器虚拟时钟概念 ( Virtual Runtime )、
三、进程优先级 ( 调度优先级 | 静态优先级 | 正常优先级 | 实时优先级 )、
四、调度类 ( 停机调度类 | 限期调度类 | 实时调度类 | 公平调度类 | 空闲调度类 )
				进程的状态转换
 系统中的进程在调度程序schedule()的协调下按既定规则运转，保证每个进程尽可能公平地获得CPU运行时间。在单处理器系统中，同一时刻只能有一个进程占用CPU，由于CPU的运行速度很快，加上有调度程序的协调，肉眼看到所有进程在同时运行的假象。在多处理器系统中，同一时刻可以有多个进程在运行，具体由处理器个数决定。
				CFS是内核使用的一种调度器或调度类，它主要负责处理三种调度策略：SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE。调度器的核心在挑选下一个运行的进程时有可能会遍历所有的调度类别。实际上系统大多数进程通常都是CFS调度类负责处理的，因此为了优化下一个进程的挑选调度器核心会先判断当前进程是否采用了CFS调度策略，若是，则直接调用CFS代码来挑选下一个进程，若不是或CFS代码未能挑选到一个合适的进程，则会调用各个调度类的挑选函数来寻找一个合适的进程。若CFS代码寻找到了合适的下一个运行的进
				linux的完全公平调度算法类中，CFS是其中一种，目前默认的。
CFS公式就不贴了，自己搜。CFS引入了虚拟时间的概念。
CFS所谓的“完全公平”指的是虚拟时间的完全公平，而不是指的实际的CPU占用时间公平。
所以它的“完全公平”是建立在虚拟时间的完全公平上的。用了套算法把实际霸占cpu的时间转换成了虚拟时间，而这个转换nice
值很决定这个权重，nice值越大转换的虚拟时间越大，那么很短的cpu霸占时间就能达到很大的虚拟时间，也就是nice值控制虚拟时间的增长率。
这就造成了，用nice值来调整各tas