# 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` ： ``` /* file: kernel/sched/core.c */ 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 = 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如何基于虚拟时间完成调度，我们将在后续章节中深入讨论。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://s3.shizhz.me/linux-sched/cfs-sched/fairness.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.