玻尔百科在竞争任务之间公平地分配计算机的处理能力是操作系统中的一个根本挑战。理想的解决方案，即所谓的比例份额调度，旨在精确地按照每个进程被赋予的重要性，为其分配相应的CPU份额。虽然像彩票调度这样的简单方法可以在长期内实现公平，但其固有的随机性可能导致显著的短期不公平，从而影响用户体验和系统响应性。本文旨在解决此问题，介绍了一种优雅且确定性的算法——步幅调度，它能提供精确、低方差的公平性。在接下来的章节中，我们将首先探讨使步幅调度如此高效的核心原则和机制。然后，我们将超越CPU的范畴，探索其在网络、硬件甚至商业逻辑中出人意料的广泛应用，展示其作为通用分配工具的强大能力。
想象你是一位老师，只有一个备受追捧的玩具和一屋子的孩子。你如何公平地分享它？如果一个叫 Alice 的孩子应该得到比另一个叫 Bob 的孩子多一倍的时间，你该如何执行？这本质上就是操作系统调度器每天面临的困境，它必须在众多竞争的程序（或称进程）之间分配宝贵的中央处理器（CPU）时间。其目标就是我们所说的比例份额调度：如果 Alice 被赋予了2的“权重”，而 Bob 的权重为1，那么从长远来看，她应该获得三分之二的CPU时间，而 Bob 获得三分之一。
实现这一目标的一个简单直观的方法是抽奖。你可以给 Alice 两张彩票，给 Bob 一张。在每个时间片，你随机抽取一张彩票。中奖彩票的所有者得到玩具。这就是彩票调度。在多次抽奖后，Alice 的获胜次数大约是 Bob 的两倍，因此系统在长期内是公平的。
但“长期”可能是一段非常长的时间！短期内会发生什么呢？纯粹出于偶然，Bob 可能连续赢五次。在那段时间里，分配是极不公平的。如果 Alice 的进程正在运行一个视频游戏，而 Bob 的进程在后台检查电子邮件，这种短期的不公平会令人极度沮丧。彩票调度的随机性引入了高方差；在任何短时间窗口内收到的实际CPU份额都可能显著偏离期望的份额。我们能做得更好吗？我们能否设计一个不仅在平均意义上公平，而且在几乎每一刻都精确公平的系统？
这正是计算机科学天才之处。我们可以用一个确定性、优雅的机制取代随机的掷骰子：步幅调度。
步幅调度以非凡的精度实现比例共享，它不依赖于机会，而是通过一个简单而巧妙的记账系统。它建立在三个核心概念之上：票据、步幅和通行值。
票据 ()：就像在彩票调度中一样，票据（或权重）代表进程 期望获得的资源份额。一个拥有200张票据的进程应该获得比拥有100张票据的进程多一倍的CPU时间。这是我们的输入，是我们意图的陈述。
步幅 ()：这是一个巧妙的技巧。我们为每个进程计算一个“步幅”值。步幅与其票据数量成反比。票据多的进程步幅小；票据少的进程步幅大。我们可以用一个简单的公式来形式化这一点： 这里， 是进程 的票据数， 是一个非常大的数，是整个系统的常数，为了方便而选择。可以这样想：每个进程都在参加一场赛跑。步幅是它每次轮到自己时迈出的一步的大小。高优先级进程（票据多）迈出的一步很小，而低优先级进程（票据少）则迈出巨大的一步。
通行值 ()：这是一个累加器，是为每个进程记录其在赛跑中进度的计数器。它代表了进程已经“行进”了多远。最初，每个进程都从同一条起跑线开始，通行值为零。
这场赛跑的规则异常简单：总是选择通行值最小的进程。在该进程运行一个时间片后，我们通过将其步幅加到其通行值上进行更新：。
让我们看看这个机制的实际运作。假设我们有三个进程，、 和 ，它们的票据（权重）分别为1、3和6。我们选择一个大常数，比如 。它们的步幅将是：
注意，权重最高的进程 拥有最小的步幅。现在，让我们观察这场赛跑的展开，所有进程的通行值都从0开始。
初始状态：。所有值都是最小的。我们通过选择最小的进程ID来打破平局，所以 运行。
决策2：最小通行值为0，由 和 共享。我们选择 。
决策3：最小通行值为0，由 持有。 运行。
决策4：最小值显然是 。 再次运行。
决策5：最小值为2，由 和 共享。我们选择 。
如此继续下去。如果你继续这个过程，你会发现经过10个时间片后，这些进程将分别运行了1次、3次和6次——这恰好与它们的权重成正比！调度器通过总是选择在这场虚拟赛跑中“最落后”的进程，确保它们的通行值始终保持非常接近。这是一个自我纠正的系统，在每一步都维持着近乎完美的公平性。
首先要注意的是，这个过程是完全确定性的。给定相同的起始条件，调度将每次都以完全相同的方式展开。这与彩票调度的随机性形成了鲜明对比。这种确定性带来了一个极其有用的属性：低方差公平性。一个进程收到的时间片数量永远不会偏离其理想目标太远。
这种精确性也带来了另一个美妙的涌现属性：基于权重的延迟。考虑一个更传统的调度器，如轮询（Round-Robin, RR），它只是简单地循环遍历所有进程，给每个进程一个固定的时间片。在RR中，高优先级进程等待下一次轮到的时间与低优先级进程相同。但这是我们想要的吗？可能不是。我们希望我们重要的任务响应更快。
步幅调度自然地提供了这一点。高权重进程的步幅小。它运行后，其通行值只增加一点点，这意味着它很可能很快会再次被选中。低权重进程的通行值则会有一个巨大的飞跃，保证了它在一段时间内不会再次运行。这意味着高优先级任务经历较低的延迟，而低优先级任务经历较高的延迟，这一切都无需任何特殊的逻辑。这是核心机制的自然结果。
一个算法的优雅之处不仅在于它在理想世界中的表现，还在于它如何适应现实的混乱。步幅调度以惊人的优雅处理这些复杂性。
休眠进程：当一个进程并非总是准备好运行时会发生什么，例如，如果它在等待一个I/O操作，比如从磁盘读取文件？当它醒来时，我们是否应该给予它一些“补偿”来弥补失去的时间？对于步幅调度，答案是一个优美的*“不”*。当一个进程阻塞时，它的通行值只是简单地冻结了。与此同时，其他进程继续运行，它们的通行值越来越高。当我们的进程最终醒来时，它的通行值现在远低于其他所有进程。调度器的核心规则——选择最小值——自动确保这个进程获得一段集中的CPU时间来“赶上进度”。不需要特殊的代码；正确的行为只是从算法的本质中涌现出来。
优先级反转的危险：一个经典的操作系统噩梦是优先级反转。想象一下，我们的低票据线程 持有一个高票据线程 需要的资源（一个“锁”）。 现在被卡住了，等待着那个运行缓慢、调度频率低的 完成。步幅调度框架提供了一个干净的解决方案。当这种情况发生时，我们可以执行一个两部分的调整：
动态调整优先级：如果用户决定在系统运行时更改一个进程的优先级（即其权重）怎么办？我们不能只为未来的步骤更改步幅。当前的通行值反映了该进程过去获得的所有服务，这些服务是按其旧权重“定价”的。为了维持公平，我们必须“重新定价”这段历史。优雅的解决方案是根据迄今为止收到的总服务量（）重新计算通行值，但要除以新的权重（）：。这会立即调整进程在赛跑中的位置以反映其新状态，从而保持公平的连续性。
一个算法的好坏取决于它的实现。我们如何高效地构建这个优雅的机制？
在每一步，我们都需要找到通行值最小的进程。对一个包含 个进程的列表进行朴素的扫描，所需时间与 成正比，这可能会很慢。一个更聪明的方法是将进程存储在一个称为最小堆的数据结构中。最小堆就像一个锦标赛的对阵图，它在一件事上表现得异常出色：找到最小元素。找到最小值并在一个进程运行后更新堆，所需时间与 的对数成正比，即 。对于大量的进程，这比线性扫描效率高得多，使得步幅调度在现实世界中变得实用。
但还有最后一个美妙而微妙之处。通行值总是在增加。如果我们将它们存储在一个标准的32位或64位整数中，它们最终会溢出并“回绕”——一个非常大的数会变成一个非常小的数。例如，在一个8位系统（数字范围从0到255）中，一个通行值为250，步幅为20，增加后会变成 。一个朴素的比较会认为14远小于比如240，从而错误地调度了刚刚溢出的进程。这将破坏公平性。
解决方案是一段计算上的诗篇。我们不直接比较两个通行值 和 ，而是看它们的差值 ，并将其解释为一个有符号数。由于计算机处理数字的方式（一种称为二进制补码的系统），只要没有单个进程能领先其他进程太远，这个有符号的差值就能正确地告诉我们哪个通行值在概念上、未回绕的赛跑中“领先”。这个将减法结果转换为不同类型的简单技巧，巧妙地解决了回绕问题，使调度器可以永远运行而不会混淆。这是一个完美的例子，展示了对抽象算法和硬件具体现实的深刻理解如何导致健壮而优雅的解决方案。
从一个对公平的简单渴望出发，我们探索了一个确定性的机制，其简单的规则产生了复杂的、理想的行为，其实际实现揭示了软件和硬件之间美妙的联系。这就是步幅调度的精髓。
在揭示了步幅调度优雅的钟表般机制之后，我们可能会忍不住将其视为一个美丽、自洽的理论机械装置来欣赏。但一个伟大科学思想的真正衡量标准，并非其内在的完美，而是其解释、预测和组织我们周围世界的力量。步幅调度正是这样一种思想。其核心原则——一场确定性的赛跑，其中“较慢”的跑者（权重较小者）获得较短的步幅，从而更频繁地运行——是一个惊人地多才多艺的工具。它以各种形式，有时是伪装的，出现在广泛的问题中，从操作系统的核心到庞大的互联网基础设施，乃至更远。让我们来一次穿越这些迷人应用的旅程。
CPU调度器最自然的家园，当然是操作系统内核，在那里它面临着众多复杂的挑战。
首先，考虑现代的多线程应用世界。仅仅给一个进程公平的CPU份额是不够的。问题是，该进程能否有效利用那段时间？想象一个多线程应用，其中许多线程需要访问由锁保护的共享数据。只有当前持有锁的线程才能做有用的工作；所有其他线程如果被调度，只会尝试获取锁然后阻塞，浪费它们的时间片。一个将每个线程视为独立实体的幼稚调度器，可能会尽职地给该应用的四个线程各自分配相等的份额。但如果在任何给定时间只有一个线程能取得进展，那么分配给该应用的时间中有四分之三都被浪费了！一种更智能的方法，即所谓的按进程记账，将整个CPU份额给予进程整体。进程的内部运行时知道哪个线程持有锁，然后可以确保CPU时间被用在那个真正能取得进展的线程上。这种记账方式从按线程到按进程的简单改变，可以通过避免这种“护航效应”来显著提高吞吐量，这有力地说明了有效的调度不仅仅是数字问题——它关乎情境。
在多处理器系统上，情况变得更加复杂。我们应该有一个所有CPU核心都从中抽取任务的单一全局可运行线程队列，还是每个核心都应该有自己的私有队列？全局队列，也许实现为一个按通行值排序的共享堆，似乎能保证完美的、系统范围的公平性。整个系统中通行值最低的两个线程将总是在运行。但这带来了巨大的代价：当多个核心试图访问和修改这个单一数据结构时，会产生持续的通信和竞争。此外，一个线程可能在一个时间片内在核心0上运行，在下一个时间片内又在核心1上运行，这会因其状态被移动和缓存失效而产生高昂的迁移成本。
另一种选择是每核心队列。每个核心管理自己的一组本地线程，消除了竞争和迁移成本。这非常高效，但如果核心0被高优先级工作淹没，而核心1坐着空闲，其唯一的线程有着非常大的通行值，那该怎么办？整个系统就不再公平了。解决方案是一种混合模式：带有*工作窃取*的每核心队列。当一个核心变为空闲时，它会从另一个核心的队列中“窃取”最值得运行的线程（即通行值最低的那个）。这种方法达到了一个微妙的平衡：它在大多数时候保持了高度的本地效率，而工作窃取机制则作为一种纠正力量，防止对全局公平性的严重违反。现代多处理器调度器的设计就是对全局公平性和本地性能之间这一根本权衡的深入探索。
这种在不同粒度上管理资源的想法可以被形式化为一个强大的概念：分层调度。像Linux这样的现代系统使用控制组（cgroups）来在不同的应用或用户之间划分资源。我们可以想象一个两级调度器：在顶层，使用步幅调度在各个cgroup之间划分CPU时间，每个cgroup都有自己的权重。然后，在每个cgroup内部，另一个调度器（也许是彩票调度或再次使用步幅调度）将该组分配到的时间在其组成进程之间进行划分。这样，单个进程的总CPU份额就是其cgroup在系统中所占份额与其自身在cgroup内所占份额的乘积。这种模块化、可组合的方法允许在复杂的容器化环境中实现精密的资源管理策略。
最后，通过提供确定性的服务保证，步幅调度为经典的饿死问题提供了一个强有力的解决方案。在一个简单的基于优先级的系统中，一个高优先级任务可以无限期运行，完全阻止低优先级任务的运行。步幅调度通过确保每个具有非零权重的任务最终都会拥有最小的通行值，从而使饿死变得不可能。这将其从一个用于“共享”的工具转变为一个提供有保障的*服务质量*（QoS）的工具。对于云服务提供商来说，这意味着他们可以使用步幅调度来确保即使是低收入客户也能获得有保障的最低服务水平，同时仍然优先考虑高收入客户——这是一种比严格优先级远为健壮和公平的策略。
步幅调度的逻辑并非与CPU时间片绑定。它是一种用于分配任何离散、可互换资源的通用机制。这一认识开启了一个充满应用的世界。
最著名的类比是网络数据包调度。想象一个路由器，有多个数据流在竞争出站带宽。路由器必须决定接下来发送哪个流的数据包。加权公平排队（WFQ）是一种为每个流提供与其给定权重成比例的带宽份额的算法。它试图模拟的“理想”系统是一个流体模型，其中所有流都以其比例速率同时被服务。步幅调度是WFQ在数据包级实现上的CPU等价物。两者都是确定性的，并提供一个关键保证：与理想流体份额的偏差，通常称为滞后（lag），被一个小的常数（大约一个时间片或一个数据包大小）所限制。这与它们的概率性表亲——彩票调度和随机公平排队（SFQ）形成鲜明对比，后者的随机波动可能导致大的短期公平性偏差，且误差会随时间增长。这种确定性的、有界滞后的特性使得步幅调度和WFQ对于需要可预测性能的应用非常有价值。
但是，当一个任务需要多种资源时会发生什么？考虑一个通过网络发送数据的进程。它既需要CPU周期来准备数据，也需要网络带宽来传输数据。如果我们有两个独立的步幅调度器——一个用于CPU，一个用于网络——彼此毫不知情，我们就会遇到麻烦。一个进程可能被授予大量的网络带宽却因CPU不足而饿死，反之亦然。最终的端到端吞吐量总是受限于最紧的瓶颈。如果我们真的希望最终吞吐量与某个期望的权重成正比，那么调度器之间必须协调。例如，如果CPU是瓶颈，CPU调度器分配周期时不仅要与进程的权重成比例，还要与它的权重和其计算成本（每字节周期数）的乘积成比例。这是一个深刻的见解：在一个多资源的世界里，实现端到端的公平性需要一个整体的视角，其中分配器必须意识到其决策的下游后果。
这种抽象可以被进一步推向硬件层面。一个现代DRAM内存控制器在多个竞争的核心或进程之间仲裁对内存总线的访问。我们可以在这里应用步幅调度，不是针对CPU时间片，而是针对固定大小的内存访问时间“窗口”。然而，这揭示了一个微妙但关键的点。一个进程可能赢得一个比如20个内存周期的窗口，但由于其自身的内部内存访问模式（例如，bank冲突），它可能只能在其中的10个周期内执行有用的内存传输。调度器授予的是一个机会，但进程自身的“可服务性”决定了实际实现的吞吐量。一个具有非常高效、线性访问模式的进程可能会比一个具有随机访问模式的进程获得高得多的有效带宽，即使两者都被调度器给予了相同数量的访问窗口。这突显了资源分配与其实际利用之间的关键区别。
当我们看到步幅调度走出计算机系统的传统范畴，并在全新领域提供解决方案时，它的真正力量才变得显而易见。
考虑一下电池供电设备上的能源管理挑战。我们有几个进程，每个进程运行时消耗不同数量的电力。我们可以为每个进程分配一个“能源预算”。我们如何调度它们来执行这些预算？我们可以使用步幅调度，其中“票据”或“权重”来源于这些物理量。例如，如果我们的目标是让所有进程在完全相同的时刻耗尽其能源预算，我们可以将每个进程 的CPU份额设置为与 成正比，其中 是其能源预算， 是其功耗。通过相应地设置步幅调度权重，操作系统就变成了一个智能的能源管理器，以精确控制的方式协调系统能源储备的下降。
也许最引人注目的现代应用之一是在线广告世界。当你访问一个网站时，一个广告服务器会进行实时拍卖来决定向你展示哪个广告。但它还必须履行与广告商的合同。一个广告活动可能有一个预算，使其有权在一天内获得所有符合条件的展示机会的5%。一个简单的彩票调度器可能会平均交付这5%，但它可能是爆发性的——早上投放20%，下午投放0%。这对广告商来说是不利的。他们想要平滑、可预测的投放。这正是步幅调度的“有界滞后”属性所保证的。通过将每个广告展示视为一个时间片，将广告活动预算视为权重，步幅调度可以确保交付给一个广告活动的展示数量永远不会偏离其理想目标太远。这是一个将核心操作系统原则完美映射到价值数十亿美元的商业逻辑问题上的范例，保证了在混乱的数字市场中的公平性和可预测性。
从确保多核CPU的公平性，到协调跨互联网的数据流，到管理手机的电池寿命，再到在网页上投放广告，通行值和步幅这个简单的理念一次又一次地证明了它的价值。它是一个美丽的证明，展示了一段优雅的算法思想如何能为塑造我们世界的复杂动态系统提供一个健壮和可预测的基础。