玻尔百科在任何现代计算机中，大量程序——从关键的系统服务到用户应用程序——都在持续争夺最基本的资源：处理时间。操作系统如何管理这种竞争，以确保系统保持响应迅速、高效，并且最重要的是，公平？虽然简单的轮询共享平等地对待所有任务，但这通常无法满足动态环境的复杂需求，在动态环境中，某些进程比其他进程更重要。这就引出了一个关键的知识缺口：我们如何才能不均等地，而是公平地分配资源？
本文深入探讨比例份额调度，这是一个优雅而强大的原则，它通过按任务指定的重要性或“权重”比例分配资源来回答这个问题。通过探索这一概念，您将对驱动我们日常使用的操作系统的复杂机制有深刻的理解。本文的结构旨在引导您从核心理论走向真实世界的影响。首先，“原理与机制”一章将揭示其核心思想的神秘面纱，介绍两种主要的实现策略——彩票调度和虚拟运行时——并讨论构建实用调度器所涉及的关键权衡。随后，“应用与跨学科联系”一章将拓宽视野，揭示这一单一原则如何在容器中分层应用，如何适应虚拟化环境，甚至如何扩展以在大型数据中心集群中协调公平性。
想象一下，单个中央处理器（CPU）就像一块神奇的披萨，每当一片被拿走，它就会立即补充。现在，想象一群饥饿的程序，或称进程，围在这块披萨周围。我们如何公平地分享它？最简单的答案，“给每个人均等的一份”，是一个好的开始，但如果有些进程比其他进程更重要呢？一个关键的数据库进程可能比一个后台文件索引任务更“饥饿”。这就引出了一个更精妙的公平概念：比例共享。
其核心原则异常简单：为每个进程分配一个权重，这是一个代表其重要性或权利的数字。权重为 2 的进程应获得权重为 1 的进程两倍的 CPU 时间。CPU 不是均等地划分，而是根据这些权重按比例划分。这就是比例份额调度法的核心。
但这其中有一个关键的微妙之处。如果其中一个进程现在不饿怎么办？也许它正在等待来自慢速磁盘驱动器的一些数据——我们称之为输入/输出（I/O）操作。在等待期间，它是阻塞的；即使提供了 CPU，它也无法使用。它那份披萨应该堆积起来等它吗？那将是浪费。当其他饥饿的进程在等待时，披萨却无人问津。
比例份额公平原则对这个问题有一个聪明的答案。份额只在当前能够运行的进程——即可运行集——之间划分。如果一个进程进入休眠，它就自愿地离开餐桌。剩下的可运行进程则在它们之间共享整个 CPU，仍然按照它们的权重比例分配。当休眠的进程醒来时，它重新加入这个群体，份额被重新计算。这确保了只要有工作要做，CPU就总是繁忙的——这一特性被称为工作守恒。这是一个动态而高效的系统：只有当你准备好吃的时候，你才能分到一份馅饼。
按比例划分资源的想法很优雅，但作为计算机主控制器的操作系统，究竟是如何实现它的呢？CPU 在任何一个瞬间只能执行一个进程的指令。调度器的工作是在进程之间快速切换，以至于从人类的角度来看，它们似乎在同时运行。这是通过在抢占一个进程并让另一个进程接替之前，给每个进程一小段 CPU 时间，即一个时间片或量子（quantum）来实现的。
为了实现比例公平，出现了两种主要策略，每种策略都各有其巧妙之处。
也许最直观的实现是彩票调度。想象一下，给每个进程与其权重相应数量的彩票。为了决定下一个运行谁，调度器只需举行一次抽奖：它从所有可运行进程持有的所有彩票中随机抽取一张。中奖彩票的所有者将获得下一个时间片的 CPU。
这种概率性方法非常有效。虽然任何单次抽奖的获胜者是随机的，但大数定律确保了随着时间的推移，一个进程赢得的时间片数量将与其持有的彩票数量成正比。这种方法的妙处在于其简单性。添加一个新进程就像将其彩票添加到池中一样容易。
当然，这种公平性不是瞬时的。仅仅几次抽奖后，实际份额可能会偏离理想比例。但随着时间片数量 变得很大，任何进程的观察份额显著偏离其目标份额的概率变得微乎其微。这种收敛性可以被数学量化，表明系统以非常高的概率迅速接近其公平状态。
一种更具确定性的方法，启发了像 Linux 这样的现代系统中的调度器，可以被看作是一场永恒的竞赛。这种方法通常使用一个叫做虚拟运行时的概念来实现。
想象每个进程都有自己的虚拟时钟。当一个权重为 的进程 在真实 CPU 上运行了 的时长，它的虚拟时钟前进的不是 。相反，它前进 。这是关键的技巧：一个高权重的进程拥有一个慢速的虚拟时钟，而一个低权重的进程则拥有一个快速的虚拟时钟。
调度规则因此变得异常简单：始终运行虚拟运行时最低的进程。 这就是在竞赛中“落后最远”的进程。通过总是将 CPU 交给落后者，调度器确保了所有可运行进程的虚拟时钟保持紧密同步。如果它们所有的虚拟时钟都几乎相等，那必然意味着时钟较慢（权重较高）的进程已经获得了按比例更多的真实 CPU 时间。
当一个进程因 I/O 而阻塞时，这个机制的优雅之处就显现出来了。它的虚拟运行时会冻结。其他进程继续运行，它们的虚拟运行时向前推进。当这个 I/O 密集型进程最终醒来时，它几乎肯定会拥有系统中最低的虚拟运行时，并且会几乎立即被调度运行，从而确保了交互式应用的卓越响应性。
这也凸显了记账方法的重要性。如果调度器存在一个 bug，使用挂钟时间（wall-clock time）而不是实际的 CPU 执行时间来推进进程的虚拟时钟，系统将会崩溃。一个等待 I/O 的进程会受到不公平的惩罚，因为即使它无法运行，它的虚拟时钟也会飞速前进。这会导致它最终醒来时被剥夺 CPU 时间，从而违反了公平仅适用于当前竞争进程的核心原则。
虽然核心机制很优雅，但构建一个实用、高性能的调度器需要在一系列关键的权衡中进行导航。
时间片的大小 是一个基本的调节旋钮，对系统行为有深远的影响。
如果 太大： 系统会感觉迟钝。想象有五个进程在运行。一个交互式任务，比如你的网页浏览器，可能需要等待其他四个进程完成它们的长长的时间片，然后才有机会响应你的点击。这个等待时间被称为分派延迟（dispatch latency），而大的 会导致高延迟和差的响应性。
如果 太小： 调度器本身也需要时间来完成工作。从一个进程切换到另一个进程，这个操作称为上下文切换（context switch），有固定的开销 。如果时间片太小，CPU 会花更多的时间在切换任务的开销上，而不是运行任务本身。这会导致系统效率急剧下降。
公平性 vs. 时间片： 的大小也影响公平性的粒度。一个进程应获得的理想服务与它已获得的实际服务之间的差异被称为其滞后（lag）。一个更小的时间片允许调度器更快地纠正偏差，从而导致更小的最大滞后。
显然， 的选择是一种权衡。它必须足够小以提供良好的交互性和低的公平性滞后，但又要足够大以防止上下文切换的开销消耗掉系统资源。
另一个实际问题是调度器本身的计算成本。在一个有 个可运行进程的系统中，调度器如何高效地选出虚拟运行时最低的那个？对列表进行简单的扫描将花费与 成正比的时间，这对于现代操作系统来说太慢了。
取而代之的是，调度器使用复杂的数据结构，如平衡二叉搜索树（Linux CFS 调度器使用红黑树）。使用这种结构，查找最小值和重新插入任务的成本不与 成正比，而是与 的对数成正比，即 。这非常高效，但并非没有代价。当 增长到成百上千时，这个对数成本，再加上上下文切换的开销，仍然可能变得很显著。每个系统都有其有限的容量，在某个点上，调度器开销和响应性需求的综合约束决定了它能够公平有效地管理的最大任务数量。
比例共享的简单原则已被应用于解决现代计算环境中的复杂问题，从容器化的云服务到多核处理器。
正如我们所见，I/O 密集型的交互式任务在虚拟运行时调度器中自然会获得优先级提升。一些系统试图通过睡眠提升（sleep boost）来增强这种效果：当一个任务醒来时，它的虚拟运行时被人为地设置得更低，以确保它能立即运行。然而，这可能被利用。一个恶意的或设计不佳的程序，通过在许多微小的时间间隔内休眠，可以欺骗调度器，使其获得远超其应有份额的 CPU。这揭示了调度器设计中的一个深层矛盾：对快速交互性能的渴望有时会与严格比例公平的数学保证相冲突。一个健壮的调度器必须包含防护措施，例如衰减的提升，以防止这种滥用，同时仍然偏爱合法的交互式任务。
在一个简单的“扁平”调度器中，所有进程都在一个大池子里，用户可以通过简单地启动数百个进程来获得不公平的优势——这种攻击被称为票据膨胀（ticket inflation）。如果用户 A 有 1 个进程，而用户 B 有 100 个进程，用户 B 将垄断 CPU。
解决方案是层级结构。现代系统不仅仅调度进程；它们调度进程组。我们可以将用户 A 的所有进程放在一个组中，将用户 B 的所有进程放在另一个组中。顶层调度器首先在这些组之间按比例划分 CPU。例如，它给 A 组 50%，给 B 组 50%。然后，一个第二级调度器接管分配给 B 组的 50%，并将那部分时间按比例分配给 B 的 100 个进程。这种层级结构，通常使用控制组（cgroups）实现，是多用户系统和云计算中公平性的基础，确保一个租户无论运行多少进程，都不能饿死另一个租户。
到目前为止，我们所有的类比都涉及单个 CPU——一块披萨。在拥有多个 CPU 的现代多核处理器上会发生什么？这并不像在每个核心上简单地运行一个独立的调度器那么简单。
想象一个双核系统。如果我们将一个高权重任务永久固定在核心 1 上，并将几个低权重任务固定在核心 2 上，我们就会造成不平衡。每当高权重任务休眠时，核心 1 可能会闲置，而核心 2 则过载。这是低效的，并破坏了全局公平性。
一个真正的多处理器比例份额调度器必须有全局视野。它需要执行动态负载均衡，定期在核心之间迁移进程。目标是保持每个核心上的总可运行权重大致相等。为了智能地做到这一点，调度器可以为每个任务跟踪一个服务赤字（service deficit）——衡量它相对于其理想份额“欠”了多少 CPU 时间。在重新平衡时，它可以将赤字最大的任务从过载的核心迁移到欠载的核心，不断地纠正不平衡，并引导整个系统走向全局比例公平的状态。
比例份额调度是资源分配的一个优雅而强大的原则，它优先考虑公平性和整体系统吞吐量。它是我们日常使用的操作系统中调度器背后的主力。
然而，它并非万能药。它提供关于长期平均份额的“软”保证。它不提供关于任何单个作业完成时间的“硬”保证。如果你正在构建一个控制工厂机器人或汽车防抱死刹车系统的系统，你需要满足严格、不可侵犯的最后期限。在这种情况下，另一类实时调度器，如最早截止时间优先（Earliest Deadline First, EDF），将是合适的工具。比例份额调度选择公平性作为其指路明灯，为我们所居住的这个复杂、动态和共享的计算世界提供了一个坚固而灵活的基础。
在窥探了比例份额调度的内部机制之后，人们可能很容易将其归档为操作系统设计中一个巧妙的片段。但这就像只欣赏一个漂亮的齿轮，却没看到它所驱动的宏伟时钟。“各取所值（按权重分配）”的原则不仅仅是一个孤立的技巧；它是资源分配的一个基本概念，其回响无处不在，从你个人电脑的嗡嗡声，到云端广阔的分布式智能，甚至延伸到那些看似与硅毫无关联的领域。让我们踏上一段旅程，看看这个简单的想法能带我们走多远。
我们的第一站是最熟悉的：你桌上的电脑。此时此刻，很可能有几十个进程在争夺它的注意力。你可能正在进行视频通话，而后台在运行备份，你偶尔还会切换到你的代码编辑器。这些任务中的每一个——对延迟敏感的视频流、对吞吐量要求高的备份、交互式的编码会话——都有不同的需求，争夺着相同的有限资源：中央处理器（CPU）、磁盘和网络。
系统是如何避免陷入混乱的呢？比例共享最简单的应用提供了一个出人意料的优雅答案。操作系统可以把每种资源都看作一个待分割的饼。对于给定的资源，比如网络，如果所有任务的总需求（它们所需最小数据速率的总和）小于网络连接的总容量，那么公平的分配是可能的。如果需求总和超过了容量，再巧妙的共享也无法满足所有人。这个简单的“准入控制”测试——检查所需速率的总和是否小于或等于总容量——是维持系统稳定和响应迅速的第一道防线。它允许操作系统向你的视频通话承诺一定的服务质量，确保它不会因为备份程序决定消耗整个磁盘带宽而卡顿。这个将需求与容量匹配的基本原则是资源管理的基石。
然而，现代系统很少是简单、扁平的进程集合。我们常常希望为任务组管理资源。想象一下，你在同一台机器上运行一个数据库和一个 Web 服务器。你可能希望保证数据库作为一个整体获得 60% 的 CPU，而 Web 服务器获得 40%，无论它们各自衍生出多少个线程。
这就是层级应用的精妙之处。比例共享原则可以递归地应用。例如，Linux 使用一个名为“控制组”（cgroups）的功能来实现这一点。你可以创建一个拥有特定 CPU 份额的父组，并在其中创建子组来进一步细分该份额。任何单个进程的有效份额就是其家族树上所有层级份额的乘积。这种优雅的乘法逻辑是现代软件容器（如 Docker）背后的引擎，允许在复杂的多应用环境中对资源分配进行细粒度控制。
我们甚至可以将这种“软”共享与“硬”限制结合起来。管理员可以声明一个进程组按比例获得（比如）20% 的 CPU，但同时设置上限，使其永远不能超过总 CPU 的 50%，即使系统在其他方面是空闲的。然而，由于一种称为“工作守恒”的特性，如果该组是唯一运行的组，它可以使用所有可用的资源，直到其硬性上限。未使用的份额不会被浪费；它们会被优雅地重新分配给需要它们的人。这种比例共享和硬性限制的结合，为在服务器和数据中心制定复杂的资源管理策略提供了一个丰富的工具箱。
到目前为止，我们的模型都假设每个任务都是完美的公民，总是准备好运行。但实际上，任务通常是混乱的。数据库中的一个进程可能需要等待一个锁被释放，或者等待数据从慢速磁盘中读取。在这段“阻塞”时间内，它并没有使用 CPU。一个天真的比例份额调度器会简单地跳过它的回合，实际上是对它进行了惩罚。这对交互式应用尤其不公平，因为它们经常因为等待用户输入而阻塞。
为了解决这个问题，调度器可以被赋予记忆。一种巧妙的机制是授予“补偿信用”。如果一个高优先级任务因为被阻塞而错过了它的回合，它会累积信用。当它再次变为可运行时，它被允许“花费”这些信用，暂时获得比正常份额更大的 CPU 份额来追赶进度。这确保了从长远来看，公平性得以保持，一个长时间运行的、CPU 密集型的分析查询不会完全饿死一个交互式的查询。
另一个与理想情况的偏离发生在那些无法被抢占的资源上。你不能在一个图形处理单元（GPU）完成复杂计算的中途停止它。这种“不可抢占性”对公平性构成了挑战。如果一个应用程序提交了一个非常长的内核，所有其他应用程序都必须等待。我们在这里如何谈论公平性？理论家通过将真实的、“粗粒度”的调度器与一个称为通用处理器共享（Generalized Processor Sharing, GPS）的理想化、完美流体模型进行比较，提供了一个优美的答案。虽然真实调度器无法在每个瞬间都与流体模型匹配，但我们可以证明，真实调度器完成的工作与理想模型完成的工作之间的差异——即“滞后”——在数学上是有界的。最大滞后，很直观地，不会超过系统中最长的不可抢占工作块。这给了我们一个强有力的保证：即使公平性不是完美的，我们也确切地知道它能有多不完美。
当我们进入虚拟化的世界，这个驱动云计算的技术时，问题就变得更深了。一个虚拟机（VM）认为它拥有自己私有的硬件，包括一个 CPU。VM 内部的操作系统运行着它自己的调度器，试图公平地分配它认为是自己的 CPU 时间。但现实是，一个 hypervisor 正在底层秘密运行，它可能会抢占整个 VM 去运行另一个 VM 或某些主机任务。这被称为“被盗时间”。
从客户机操作系统的角度来看，挂钟时间似乎正常流逝，但 CPU 却消失了一段时间。如果它的调度器没有意识到这一点，它的整个公平概念都会被破坏。它可能会为一个进程“收取”一整毫秒的 CPU 时间，而由于被盗时间，该进程实际只运行了其中的一小部分。解决方案是客户机和主机之间的协作：通过一个“半虚拟化”接口，hypervisor 可以向客户机报告被盗时间的数量。然后，客户机调度器可以调整其内部记账，将其公平性计算基于真实的、实际的执行时间，而不是挂钟时间。这确保了即使在 VM 的人造现实中，公平性也能得以维持，这是云中可预测性能的一个关键要求。
这就引出了一个非常微妙的观点。我们一直在谈论分享“资源”，但我们必须精确定义我们分享的货币。考虑一个磁盘 I/O 调度器。是给每个进程相同数量的回合（即 I/O 请求）更公平，还是给它们相同数量的时间来使用磁盘更公平？
这两者并不相同！一个发出成千上万个微小、快速请求的进程，可能会被分配到总请求数的一小部分，但最终却垄断了磁盘的时间，饿死了一个发出不频繁但巨大、耗时请求的进程。一个基于 IOPS 的调度器，它按比例分配 I/O 操作的数量，并不能保证时间份额的公平性。为了实现真正基于时间的公平性，调度器必须更加复杂；它必须计算每个请求实际花费的时间。这迫使我们去问公平的最终目标是什么，并认识到我们测量什么——资源的“量子”——的选择与分配它的规则同样重要。
现在，让我们从单台计算机放大到大型数据中心的规模，这是一个由数千个节点组成的分布式系统，构成了互联网的骨干。在这里，像 Kubernetes 这样的“集群编排器”必须将应用程序 pod（容器组）放置到节点上运行。目标是实现集群范围的公平性：一个权重为 的应用程序应该获得与 成比例的整个集群 CPU 算力份额。
从一个中心化的大脑来做这件事似乎复杂得不可能。然而，解决方案是分布式系统中最优美的结果之一。全局的、集群范围的公平性可以通过在每个节点上强制执行一个简单的局部条件来实现。一个放置是公平的，当且仅当，在每一个节点上，该节点容量与放置在其上的 pod 权重总和之比都是相同的常数值。这个常数实际上就是整个集群的总容量与所有 pod 的总权重之比。这个原则允许一个去中心化的系统通过让每个部分遵循一个简单的局部规则来达到一个全局目标——这是一个令人惊叹的涌现秩序的例子。
最后，要看到比例份额调度的真正普适性，我们必须完全走出操作系统的世界。考虑一个在线广告系统。对于网站的每一个访问者，系统都必须选择显示哪个广告活动的广告。广告活动有不同的每日预算，系统理想情况下应该按这些预算的比例来展示它们的广告。
抽象地看，这完全是同一个问题！“展示次数”是资源，而“预算”是权重。但是你如何实现它呢？可以使用“彩票”方法，预算为 的广告活动得到 张彩票。这在平均意义上是公平的，但由于随机性，实际的展示次数可能会与理想情况有显著偏差，其误差会随着时间增长。一个更好的方法是使用像步进调度（stride scheduling）这样的确定性算法。在这里，与理想份额的偏差在数学上被保证是“有界的”——它从不超过一个小的常数量（通常只有一个展示次数！）。这为商业系统提供了强大、可预测的保证，因为这些系统中金钱攸关。
从你的桌面到云端，从 CPU 到广告展示，比例共享这个简单的概念证明了自己是现代系统中最有效、最通用的思想之一。它的美不在于深奥的复杂性，而在于其基础的简单性以及它为混乱的数字世界带来可预测、可扩展和公平秩序的非凡力量。