2.6.1 公平性
CFS的全称是Complete Fair Scheduler, 可见公平性是CFS的核心目标。所谓公平，就是调度器将CPU时间“按需分配”给每个进程。如何实现“按需分配”，以及如何简洁精炼地实现该逻辑，是CFS要考虑的首要问题。
在讨论调度器的演进历史时，我们看到不管是O(n)还是O(1)，实际上都在做这方面的工作：根据任务的优先级为其分配CPU时间。这是最直观也是最容易实现的策略，但他们判定交互式进程的逻辑过于复杂。CFS吸收了RSDL在公平性上的思想，放弃了“猜测”进程交互性的无谓尝试，根据任务的优先级来给任务分配时间，但与RSDL不同的是，CFS还放弃了“调度周期”这个概念，引入了“虚拟时间（vruntime）”来判断任务是否得到了公平对待。本章我们将深入分析CFS的算法思想，一探CFS设计者们是如何将复杂的问题抽象成一个简洁优雅的模型，并予以实现的！
理想模型
我们先来看在理想模型下，CFS如何有效地保证进程调度的公平性。这里我们首先明确两个概念：一是什么是理想模型；二是如何定义公平性。
理想模型：我们知道调度器的调度对象是进程（严格地说是调度实体），现实中进程有不同的种类，同一类进程也有不同的优先级，这些因素会造成进程对运行时间的需求存在差异性，从而影响调度器对公平性的定义。这里我们暂时忽略这些因素，将所有进程对时间的需求完全视为等价的。
公平性：对于理想模型而言，公平性就是每个进程得到同样多的CPU时间。即如果CPU运行的时间总量为T, 并且系统中有N个进程，那么最终每个进程得到的时间为T/N
但在实际情况下，系统是无法预先知道T的，此时调度器应该采用何种算法保证系统在任意时刻的公平性呢？在现实中，绝对的公平几乎是不可能实现的，也就是说，在任意时刻系统都存在着某种程度的不公平，即某些进程暂时获得了比其他进程更多的CPU时间。调度器要维持公平性，实际上就是要去除掉不公平性，那么每次调度时，调度器选择当前消耗CPU时间最少的进程即可。
这样我们抽象出了调度器的核心逻辑：以进程当前的实际运行时间为度量单位，记为runtime, 调度器每次调度时都选择runtime最小的进程。
该逻辑非常简单，因为此时我们只需要一个维度的指标（runtime）来度量当前系统的公平性。
优先级与权重
“理想模型”在现实情况中是不存在的！在现实世界中，我们必须考虑进程种类及优先级的不同所造成的对CPU时间需求的差异性。
前面章节我们已经详细讨论过了进程优先级的概念，这里我们只考虑CFS, 因此只讨论普通进程（Normal Process）的优先级给调度器带来的影响，即我们通常讨论的 nice 值。
CFS的公平性本质上是对CPU时间的公平分配，而优先级的加入并没有改变这一点，优先级本质上是为了区分不同进程的重要性，只要调度器能够根据每个进程的重要性的比例来分配时间，那么它就依然是公平的。例如我们有三个进程 A, B, C, 其中B与C的重要性相等，而A的重要性是他们的两倍，那么在公平的分配策略下，三个进程得到的CPU时间比例应该是：
A: 50%
B: 25%
C: 25%
不同的优先级实际上代表着不同的权重，Linux中普通进程的nice值为[-20, 19], Linux将nice值映射成了一个权重数组 sched_prio_to_weight ：
权重与nice值的关系是： weight = 1024 / 1.25^nice, 这样设计的目的是为了满足CFS的分配原则：进程的nice数值每变化1, 那么其获得的CPU时间将变化10%. 我们以任意两个相邻的权重来校验一下：
A: 88761 / (88761 + 71755) = 0.55
B: 71755 / (88761 + 71755) = 0.45
也就是说，如果进程A,B最初的nice值都是-20(此时两个进程各分配50%的时间)，那么当B变为-19后，它的CPU时间就会比A少了10%.
有了权重的概念之后，我们需要使用权重比例来刻画公平性。调度算法需要根据runtime计算出当前任务被分配到的实际比例，然后跟自己应该得到的比例相比较，差值最大的那个任务就是最应该被调度的任务。同样拿前文中A,B,C三个进程作为例子（三个任务的权重比重分别为：50%,25%,25%），假设系统已经运行了100ms, 三个任务均分了该时间片：
A: 33.3ms, 实际比例1/3, 期望比例为1/2, 差值为：1/6
B: 33.3ms, 实际比例1/3, 期望比例为1/4, 差值为：1/12
C: 33.3ms, 实际比例1/3, 期望比例为1/4, 差值为：1/12
此时A的比例差值最大，说明A所分配到的时间比例偏少，调度器应该选择A作为下一个任务来执行。整个过程略显复杂，需要每个任务都记录下自己的时间比例与权重比例，而前文我们讨论理想模型时，我们只需要知道每个任务的runtime即可。
有没有什么度量方式，让我们在引入权重差异性之后，依然保持理想模型下的调度简洁性呢？答案是“虚拟时间”！
虚拟时间
在上一节讨论权重时，我们自然地从权重比例想到了时间比例，导致了计算逻辑稍显复杂，但如果换一种思路：通过任务的权重比例对runtime进行伸缩（scale）的话，那么我们依然可以使用“伸缩后的时间”这一个维度来观察系统的公平性。
再次回到前文中的例子：A,B,C 三个任务的权重比分别为50%, 25%, 25%, 如果100ms的总时间按照公平的方式分配，那么他们将分别得到：
A: 50ms
B: 25ms
C: 25ms
我们将该时间称为墙上时间（wall time, 时钟挂在墙上，所以我们将物理时间叫着墙上时间），虽然三者的墙上时间不同，但只要将他们除以各自的权重比例，就可以得到一个归一化的数值：
A: 50 / 50% = 100
B: 25 / 25% = 100
C: 25 / 25% = 100
我们可以将该结果叫着虚拟时间（virtual runtime, 简称vruntime），如果任务的墙上时间分配是公平的，那么大家的vruntime就肯定是相等的。我们可以理解为每个任务有一个自己的虚拟时钟，该时钟的走速等于墙上时钟的走速除以任务的权重比例，也就是说任务的权重越低，其虚拟时钟就走得越快，权重越高就走得越慢，例如上例中，B与C的虚拟时钟走速就是A的两倍，但只要大家的虚拟时间在数值上相等，系统在时间分配上就是公平的。
有了虚拟时间这个概念，我们依然可以维持调度算法的简洁性：调度器要维持公平性，就是要维持所有任务的虚拟时间相同，也就是说每次选择虚拟时间最小的任务进行执行即可。
既然虚拟时间这么重要，那么系统如何计算呢？上一节我们给出了任务权重的计算公式： weight = 1024 / 1.25^nice, 当nice=0时，任务的权重值就是1024, 1024是权重的一个基准，内核中专门使用宏 NICE_0_LOAD 来记录该数值, 其他所有的权重都是在该基准上进行伸缩得到的。因此，在已知墙上时间之后，虚拟时间的计算就简单了： vruntime = wall_time * NICE_0_LOAD / weight, 可以看到 nice=0 的任务虚拟时间就是墙上时间。为了避免浮点数计算，程序中会将数字先放大再缩小，所以最终的计算公式为： vruntime = (wall_time * ((NICE_0_LOAD * 2^32) / weight)) >> 32, 其中 232/weight 也叫着 invweight, 其值预先计算好了存放在数组 sched_prio_to_wmult 中，所以可以得到最终的虚拟时间计算公式为： vruntime = (wall_time * NICE_0_LOAD * inv_weight) >> 32. 之所以优化做到了这种程度，是因为计算虚拟时间是调度器中非常高频次的操作，调度器需要将任务消耗掉的墙上时间计算成虚拟时间，然后累计起来。后续讨论CFS的runqueue时我们将看到Linux使用一颗红黑树来保存所有的任务，Key值就是任务的虚拟时间，因此红黑树最左侧节点的任务就是调度器应该选择的任务。
总结起来，虚拟时间就是CFS衡量系统公平性的唯一指标。可以发现CFS在公平性这方面的思路比O(n)和O(1)都简洁，到底CFS如何基于虚拟时间完成调度，我们将在后续章节中深入讨论。
Last updated