玻尔百科在现代操作系统的复杂世界里，管理对 CPU 的访问是一项至关重要且永无止境的挑战。早期的简单方法常常导致令人沮丧的“护航效应”，即一个长时间运行的任务可能会阻塞那些简短的交互式任务，使系统感觉响应迟钝。理论上的理想状态是一个“完全公平”的处理器，能够同时运行所有任务，但物理硬件的限制使之成为不可能。那么，一个系统如何才能创造出令人信服的公平假象，确保每个进程都能获得其应有的执行机会，而不损害性能呢？
本文深入探讨了完全公平调度器（CFS）的架构，这是 Linux 内核中为解决这一问题而设计的巧妙方案。通过探索其核心概念，您将深入了解我们的计算机是如何以卓越的效率和公平性处理数十甚至数千个任务的。
第一章“原理与机制”将剖析 CFS 背后的核心理论。我们将探讨虚拟运行时间（vruntime）这一革命性概念、允许设置优先级的加权公平性机制，以及使其在现实世界中得以实现的高效数据结构。随后，“应用与跨学科联系”一章将展示这些原理如何应用于解决实际挑战，从管理单台桌面电脑的资源到在云端协调大规模工作负载，揭示 CFS 对现代计算的深远影响。
要理解完全公平调度器（CFS）的精妙之处，让我们先想象一个没有它的世界。想象一条单车道公路，一辆缓慢的长卡车恰好在十几辆跑车之前上了路。无论这些跑车有多快，它们都陷入了“护航”之中，以卡车的速度缓慢前行。早期的简单调度器，如先来先服务（FCFS），其行为与此完全相同。一个繁重的、长时间运行的计算任务（卡车）可能恰好在一个系列简短的交互式任务（如鼠标移动或按键操作，即跑车）之前到达。结果呢？一个响应迟钝得令人沮丧的系统，成为了护航效应的受害者。
我们如何设计一条“更公平”的道路呢？如果，通过某种魔力，这条路可以瞬间变得足够宽，让每辆车都能以一小部分限速同时行驶，会怎么样？卡车仍然会很慢，但跑车可以在自己的车道上飞驰而过。这个理想状态就是操作系统设计者所称的处理器共享（PS）。如果有 个任务，每个任务都能即时获得 的 CPU 算力。一个仅需 毫秒 CPU 时间的短任务，无论旁边是否有长任务在运行，都将在 毫秒内完成。这是调度的理论乌托邦：完美、瞬时的公平。但这当然只是一种幻想。一个真实的 CPU 核心在任何一个时间点上只能执行来自一个任务的一条指令。
完全公平调度器的核心使命就是将这种幻想变为实际可行的现实——或者至少，创造出最令人信服的假象。
如果你无法改变物理定律，那就改变游戏规则。CFS 建立在一个简单而深刻的理念之上：既然 CPU 无法在真实时间里无处不在，我们可以发明一种新的时间，用以追踪每个任务已获得的“公平份额”。这项发明被称为虚拟运行时间，即 vruntime。
想象每个正在运行的任务都有一个测量其个人虚拟时间的秒表。调度器的唯一指导原则简单得惊人：永远运行其虚拟秒表显示时间最短的任务。
让我们看看这是如何运作的。当一个任务被选中运行时，它的虚拟秒表开始计时。当它运行时，所有其他等待任务的秒表都会暂停。在它运行了一小段真实时间后，调度器会再次查看所有的秒表。刚刚运行过的任务现在的 vruntime 更高了，因此另一个任务很可能拥有“最短的时间”，从而获得下一次运行的机会。
这单一机制优雅地解决了饥饿问题。一个等待运行的任务，其 vruntime 是不会增加的。迟早，它的 vruntime 将不可避免地成为所有任务中最低的，从而保证它能获得在 CPU 上的执行机会。这是一个隐性的老化系统，一个内置的承诺，保证没有任务会被遗忘。
给予每个任务同等的执行机会总是正确的“公平”吗？或许不是。你的视频会议肯定比一个在后台索引文件的任务更重要。我们需要一种方法来告知调度器这些优先级。CFS 通过权重来实现这一点。权重较高的任务更重要，应该获得更大比例的 CPU 关注。
但是，在坚持“永远运行 vruntime 最低的任务”这一简单规则的同时，你如何给一个任务更多的时间呢？答案非常巧妙：你让重要任务的虚拟秒表走得更慢。
一个任务的 vruntime 累积速率与其权重成反比。让我们将任务实际运行的时间表示为 ，其权重为 。其虚拟运行时间的变化量 由一个可以归结为如下的公式给出：
让我们来建立对此的直观理解。一个高权重的任务就像一个“沉重”的赛跑者。它需要花费很大的力气（真实的 CPU 时间）才能在虚拟时间的赛跑中前进一小步。它的 vruntime 计数器缓慢攀升，这意味着它可以在其 vruntime 值不再是最小值之前，运行很长一段真实时间。相反，一个低权重的任务则是一个“轻量”的赛跑者。它的 vruntime 计数器会迅速飙升。它只能运行很短的一段时间，另一个任务的 vruntime 就会变得更低。
其美妙的结果是，随着时间的推移，调度器在不懈地追求使所有 vruntime 大致相等的过程中，被迫将更多的真实时间分配给高权重的任务。加权公平性从一个简单的局部规则中自然而然地浮现出来。在一个真实的 Linux 系统中，这个权重源自于你在任务管理器中可能看到的熟悉的 niceness 值。较低的 niceness 值意味着较高的优先级，CFS 会将其转换为较大的权重，导致其 vruntime 累积得更慢。
一个真实的系统可能有成百上千个可运行的任务。调度器如何能几乎瞬时地找到 vruntime 最小的那个任务呢？搜索一个列表会太慢。这时，一个巧妙的计算机科学技巧就派上用场了。CFS 将所有可运行的任务组织起来，不是放在一个简单的队列中，而是放在一个名为红黑树的复杂数据结构中。
可以把它想象成一种特殊的家谱，其中个体（任务）按年龄（vruntime）排列。调度器的任务是找到最年轻的人。在这棵树中，vruntime 最小的任务永远是最左侧的节点。找到它就像从根节点开始，一直向左转直到不能再转一样简单。这个操作非常快，其时间复杂度相对于任务数量呈对数关系，记为 。正是这种效率使得整个 vruntime 概念变得切实可行。
当然，现实世界也施加了其他限制。任务之间的切换不是没有成本的；它会消耗少量 CPU 时间。为了避免过于频繁地切换，CFS 不会每纳秒都重新评估其决策。相反，它的目标是让每个可运行的任务在一个称为目标延迟的时间窗口内至少运行一次。一个任务的实际时间片是其基于权重在此延迟中所占的比例份额。 此外，为防止过高的切换成本占据主导地位，还设有一个最小粒度——即任务一旦被调度，所能被赋予的最短时间下限。这种实际的权衡在病态情况下可能导致一个权重非常低的任务等待，而一个由高权重任务组成的“队伍”各自轮流占据它们的最小执行时间，这说明了完美的、瞬时的公平性总是与现实世界的开销处于紧张关系之中。
在现代多核处理器上，故事变得更加有趣。为提高效率，每个 CPU 核心通常维护其自己私有的任务运行队列。
这就引入了一个新的挑战：vruntime 漂移。想象一下两个任务，一个在一个非常繁忙的核心上运行，另一个在一个基本空闲的核心上运行。在空闲核心上的任务获得了大量的 CPU 时间，其 vruntime 会飙升。而在繁忙核心上的任务只获得很少的时间，其 vruntime 几乎不会变动。它们的虚拟时钟已经相差甚远。如果我们把任务从繁忙的核心迁移到空闲的核心，它那微小的 vruntime 会让它看起来拥有至高无上的权利，并会不公平地独占新核心。为了解决这个问题，操作系统必须执行周期性的负载均衡，在核心之间迁移任务以均衡负载，并在任务移动时对其 vruntime 进行归一化，以防止此类不公。
在具有非统一内存访问（NUMA）架构的大型服务器中，全局公平性与局部效率之间的这种紧张关系甚至更为明显。在 NUMA 机器中，每个 CPU 都有一组“本地”内存，访问速度非常快；而访问其他 CPU 上的“远程”内存则较慢。调度器面临一个两难选择：是应该为了公平而将任务移动到负载较轻的 CPU（一个公平性决策），还是应该为了运行得更快而将任务保持在原地，紧挨着其数据（一个局部性决策）？在调度器中启用 NUMA 感知均衡是一个明确的选择，即有时为了更好的性能而牺牲全局公平性，这是高性能计算中的一个关键权衡。
最后，关键要记住，CFS 掌管的是“普通”任务的世界。您的操作系统还有一个独立的、更高优先级的类别，用于实时任务，这些任务在更严格的截止日期下运行。一个实时任务总是会先于 CFS 任务运行。这意味着 CFS 提供的公平性仅在其同级群体内得到保证。整个系统需要额外的保障措施，以防止失控的实时进程饿死所有普通工作。
从一个简单的目标——近似完美的公平理想——出发，完全公平调度器部署了一系列优雅的解决方案。它使用了虚拟时间的美妙抽象、加权更新的数学精度、红黑树的算法效率，以及在复杂多核世界中所需的务实妥协。它是一项卓越的工程杰作，证明了一个深刻的理论概念如何能够被塑造成一个让我们的数字世界平稳、公平运行的系统。
窥探了完全公平调度器那精美的内部机制——它的虚拟运行时间和红黑树——之后，我们可能很想就此打住，将其视为一件优雅的抽象机械。但这样做将错失其真正的魔力。CFS 的原理并不仅限于计算机科学教科书；它们是鲜活的，正积极地塑造着你所接触的几乎每一台计算机的性能和行为。从你的网络浏览器的响应速度，到提供电影、连接朋友的庞大、跨全球的云服务，它们构成了这一切的无形基础。
在本章中，我们将踏上一段旅程，去观察 CFS 的实际应用。我们将从熟悉的个人计算机领域出发，攀登至令人目眩的云数据中心之巅，探索“公平”这一简单理念是如何被应用、延伸，甚至有时被颠覆，以解决工程和计算机科学中的深远挑战。我们将看到，这个调度器不仅仅是一个被动的仲裁者，更是一个强大的工具包，用于驾驭复杂性、执行策略，并在一个不可靠的世界中构建可靠的系统。
让我们从一台单机开始，在这里，数十个进程争夺着单个中央处理器（CPU）的关注。我们如何维持秩序？CFS 的第一个也是最直接的应用就是划分 CPU 的时间。通过将进程组放入“控制组”（cgroups），系统管理员可以为每个组分配不同的“权重”。
想象一场赛跑，有些选手比其他人更强壮。为了公平，我们可以让较弱的选手提前起跑。CFS 做的类似，但对象是时间。一个 cgroup 中权重较高的进程，就像一个个人秒表走得更慢的赛跑者。为了让所有选手的秒表（即他们的虚拟运行时间）大致同步，调度器必须让高权重的进程运行更长的真实时间。其美妙的结果是 CPU 时间完全按照权重比例进行分配。如果 A 组的权重为 ，B 组的权重为 ，那么在竞争条件下，它们期望的 CPU 份额就分别是 和 。这个优雅的机制让我们能够通过一个简单的、可调节的旋钮，来优先处理关键的数据库，而不是后台的数据处理作业。
但是按比例共享也有其局限性。有时候，我们想要的不是“公平”，而是一份“合同”。想象一个 CPU 密集型的编译任务失控，导致整个系统感觉迟缓，因为必要的系统维护服务被饿死了。即使权重很低，编译器仍然会得到一些 CPU 时间，但维护服务可能得不到足够的时间来及时完成其工作。我们需要保证一个最低的服务水平。
这就需要 cgroup 工具包中的另一个工具：CPU 带宽控制。我们不只是用权重来建议比例，而是可以设定硬性限制。我们可以声明，在某个周期内，比如 毫秒，保证维护服务组至少能获得 毫秒的 CPU 时间配额。调度器将强制执行这份合同。一旦维护服务获得了它们的配额，其他进程就可以使用剩余的时间。更重要的是，我们可以限制那个激进的编译器，告诉它在同一窗口内最多只能拥有 毫秒。如果它试图使用更多，调度器会暂时让它休眠——这个过程称为节流。这个强大的机制让我们能够超越简单的公平性，提供强大的服务质量（QoS）保证，确保无论系统上还运行着什么，关键服务都不会遭受无限期的阻塞。
操作系统的世界并非由单一哲学主导。CFS 倡导公平，但其他任务要求的是另一种信条：即时性。这就是实时（RT）调度的领域，其目标不是公平，而是可预测的快速。CFS 如何与这些根本不同的调度器共存呢？
Linux 内核将其调度器安排在一个严格的层级结构中：一个可运行的 RT 任务总是会抢占一个 CFS 任务。这创造了一种有趣的动态。如果我们唤醒两个相同的任务，一个是 RT 任务，一个是 CFS 任务，它们被执行的历程将截然不同。RT 任务就像一个持有全通证的贵宾，几乎瞬间就被调度。而 CFS 任务则必须等待轮到自己，尊重调度器的公平性计算。在一个假设但有启发性的场景中，这可能导致 CFS 任务的调度延迟比 RT 任务大很多倍，这仅仅是由于两者所遵循的哲学不同。
这种严格的优先级可能是危险的。一个单一的、持续运行的 RT 任务——一个“紧凑循环”——可以完全独占一个 CPU，饿死所有 CFS 任务，从而有效地冻结一个系统。这时我们的 cgroup 工具包再次派上用场。正如我们可以对 CFS 任务设置配额一样，我们也可以对 RT 任务设置配额。通过设置一个“实时运行时间”限制，我们可以把这只 RT 猛兽关进笼子，允许它以高优先级运行，但在任何给定周期内只能运行固定的时间量。这确保了无论 RT 任务多么激进，CFS 任务总能有机会运行，从而完美地融合了实时即时性和公平共享吞吐量这两个对立的世界。
交互还不止于此。当调度器的决策与操作系统的其他部分（如同步机制）相交时，可能会产生意想不到的危险后果。考虑经典的*优先级反转问题。想象一个高优先级的任务，我们称之为‘国王’，需要一个资源——一个互斥锁——而这个锁目前被一个低优先级的任务‘贫民’持有。‘国王’必须等待。现在，在 CFS 的场景下，情况变得更加凶险。‘国王’在一个高权重（）的 cgroup 中，而‘贫民’在一个非常低权重（）的 cgroup 中。由于‘贫民’的权重如此之低，调度器只给它极小的时间片。它为释放锁需要做的少量工作被拉伸到一个极其漫长的墙上时钟时间内。‘国王’的延迟不仅仅是‘贫民’工作所需的时间，而是该时间除以‘贫民’微小的 CPU 份额：。一个几毫秒的临界区可能会膨胀成数百毫秒的等待，使高优先级应用陷入停顿。这揭示了一个深刻的真理：调度器不能对进程持有的锁一无所知。现代系统通过优先级继承*等技术来解决这个问题，即‘贫民’在持有锁期间暂时借用‘国王’的高优先级，确保它能迅速完成工作并让路。
当我们在其他系统之上构建系统时，CFS 最深刻和复杂的应用就出现了，就像我们在现代虚拟化和云计算中所做的那样。在这里，调度器层层叠加，产生了既令人困惑又引人入胜的效果。
想象一台虚拟机（VM）运行着它自己的操作系统，而这个操作系统又在调度它自己的进程。与此同时，宿主机将整个 VM 视为一个普通的进程，由其 CFS 进行调度。这导致了一种称为“双重调度”的现象。客户机操作系统可能决定给一个进程 毫秒的时间量子。但宿主机的 CFS 调度器在管理 VM 的虚拟 CPU（vCPU）时，可能只授予 vCPU 2 毫秒的物理执行时间，然后就去调度其他任务了。客户机进程运行了 2 毫秒，然后整个客户机操作系统被冻结，而宿主机在运行其他任务。当客户机再次被调度时，它的进程又运行几毫秒，如此往复。客户机的时间感变得支离破碎和被拉伸。它原打算在一段连续的时间内完成的 10 毫秒工作，现在被分散到一个更长的墙上时钟时间内，并被不可预测的间隙打断。这种“哈哈镜”效应是虚拟化中的一个根本挑战，除非宿主机和客户机调度器能够相互感知，否则性能将变得不可预测。
这段旅程在云端达到高潮，CFS 在这里充当了跨越数千台机器的策略执行者。在数据中心，一台物理服务器可能运行着数十个容器，每个容器都有不同的性能要求。一个对延迟敏感的 Web 服务器可能与一个批处理分析作业共存。我们如何防止它们相互干扰？工程师们结合使用空间和时间隔离。通过使用 cpuset 控制器，他们可以将 Web 服务器固定到一组专用的 CPU 核心（），并将批处理作业固定到其他核心（）。但如果为了最大化利用率，它们必须共享一个核心呢？这时，CFS 的 cpu.shares（权重）就被用来管理竞争。通过在共享核心上给予 Web 服务器更高的权重，工程师可以保证其最坏情况下的排队延迟——即它等待批处理作业让路的时间——保持在严格的阈值以下，例如 1 毫秒，从而满足其服务水平目标（SLO）。
最后，这整个技术栈是由高层业务逻辑驱动的。云提供商提供“金牌”、“银牌”和“铜牌”优先级。像 Kubernetes 这样的容器编排器需要将这些抽象标签转换为具体的 CFS 权重。这不是一个简单的映射。权重应该是线性递增（）还是指数递增（）？例如，指数增长可以在不同层级之间提供强有力的区分。然而，如果相邻层级之间的权重比率过大，可能会违反公平性边界要求，即即使是“铜牌”pod 在与“银牌”pod 竞争时，也应保证获得最低限度的 CPU 份额。设计这个映射函数是在提供强优先级和防止饥饿之间取得微妙的平衡，将一个调度问题转变为一个策略和经济学问题。
从公平共享 CPU 的简单行为，到协调全球云的复杂舞蹈，完全公平调度器证明了一个简单而优雅理念的力量。它提醒我们，在计算这个错综复杂的世界里，对公平的追求恰恰能为我们提供构建不仅高效，而且健壮、可预测和强大的系统所需的工具。