玻尔百科在复杂的计算世界中，决定下一个任务使用 CPU 是一个根本性挑战。传统的调度算法可能变成一张由规则和优先级交织成的复杂网络，常常导致意想不到的问题。是否存在一种更简单、更优雅的方式来确保公平性呢？彩票调度正是这样一种解决方案，它利用随机抽签的直观力量来分配资源。这种方法用简单的概率取代了复杂的状态跟踪，但也引发了关于其在真实世界系统中的可预测性和实用性的问题。
本文将分两大部分探讨彩票调度的全貌。首先，在“原理与机制”部分，我们将剖析概率比例共享的核心思想，量化其性能，并考察其确定性对应方案——步幅调度。我们还将看到，简单的“票据”比喻如何被巧妙地扩展，以处理资源阻塞、进程饥饿和优先级反转等系统复杂性。随后，“应用与跨学科联系”一章将展示这一概念惊人的通用性，追溯其从分层操作系统调度器和实时系统，到在线广告平台和网络排队算法核心逻辑的影响。我们从探索其基本原则开始：计算领域中最公平的一场博弈。
想象一下，你是一位经理，管理着一个速度惊人的单一工人——CPU，而一系列任务（进程）正在排队等待它的处理。你如何决定下一个由谁来执行？是像面包店一样按到达顺序服务吗？如果某些任务比其他任务更重要怎么办？这就是 CPU 调度的根本挑战。你可以设计一个由规则、优先级和列表组成的复杂系统，但这往往会陷入迷宫般的复杂性中。彩票调度提出了一个异常简洁而优雅的解决方案：让我们来抽奖吧。
其核心思想是：对于每一个 CPU 时间片（quantum），我们都举行一次抽奖，以决定哪个进程获得运行权。每个进程被赋予一定数量的票据。一个拥有 20 张票据的进程在任何一次抽奖中获胜的机会是一个拥有 10 张票据进程的两倍。就这么简单。调度器无需维护关于进程历史或优先级的复杂状态，它只需要知道谁在参与竞争以及他们持有多少票据。
这种优雅的机制产生了概率比例共享。在任何短时间内，一个进程获得的 CPU 份额是不确定的，但其在长周期内的期望份额会精确地收敛于其所持票据占总票据的比例。如果一个进程 持有 张票据，而系统中的总票据数为 ，那么它在任何单次抽奖中获胜的概率是 。在 个时间片的长期范围内，它所获得的 CPU 时间的期望比例就是 。这是一个源于非常简单规则的、极其公平的结果。
但是，“概率性”部分又如何呢？这正是其魅力和潜在缺陷所在。短期内，分配并不精确。就像抛硬币一样，即使是公平的硬币也不会产生完美的“正-反-正-反”序列，而是会出现连续多次相同结果的情况。在有限的时间窗口内，一个进程获得的时间片数量会在其期望值附近波动。我们可以使用方差来量化这种“运气因素”。对于一个包含 个时间片的窗口，一个进程所获时间比例的方差由公式 给出。注意两点：当进程获胜概率为 50%（）时，方差最大；随着时间窗口 的增大，方差会减小。这从数学上证实了我们的直觉：在更长的时间段内，运气会被平均掉，分配会变得越来越公平。
彩票调度的随机性既简单又稳健，但如果你需要更高的可预测性呢？如果短期波动对于你的应用来说是不可接受的呢？这就引出了彩票调度的一个巧妙的、确定性的“近亲”：步幅调度。
想象一下，现在所有进程都是一场赛跑中的选手。一个进程的“通行值”（pass value）是它已经跑过的距离。调度器作为裁判，总是选择跑过距离最短的选手来迈出下一步。这一步的长度——即它的“步幅”（stride）——是关键。为了给予一个进程更大的 CPU 份额，我们希望它被更频繁地选中。这意味着它应该在比赛中更快地落后。实现这一点的方法就是给它一个更小的步幅。
这就导出了一个优美而简单的反比关系：一个进程的步幅 与其票据数 成反比。我们可以将其定义为 ，其中 是一个很大的常数。拥有很多票据的进程步子很小，其通行值增长缓慢，调度器会不断选择它以帮助它赶上。而票据很少的进程则步子很大，很快就遥遥领先，必须等待很长时间让其他进程追上来之后才能再次轮到它。
其结果是对 CPU 时间进行确定性且极其精确的分配。与理想比例份额的偏差总是最小的，通常小于一个时间片。步幅调度用近乎完美的短期精度换取了彩票调度的优美简洁性和随机性。
那么，我们有了“CPU 份额”这个抽象概念。它对程序的性能到底意味着什么？更高的份额意味着 CPU 更频繁地关注你，这反过来又意味着你等待的时间更少。
让我们考虑三个作业 A、B 和 C，它们同时到达，每个都只需要一个时间片的工作量。假设它们分别持有 2、3 和 5 张票据。彩票调度器会选择一个来运行，然后从剩下的两个中选择一个，最后运行最后一个。每个作业的期望等待时间是多少？
通过计算所有可能执行顺序的概率，我们发现拥有最多票据（10 张中的 5 张）的作业 C，其期望等待时间最低。而拥有最少票据（10 张中的 2 张）的作业 A，其期望等待时间最高。例如，C 需要等待（即没有被第一个选中）的概率仅为 ，而对于 A，这个概率是 。这直接转化为拥有更多票据的进程能获得更好的性能指标，例如更低的期望等待时间和响应时间。票据不仅仅是一个抽象的权重；它们是购买更优性能的直接货币。
如果抽奖的获胜者被阻塞了，比如在等待磁盘读取完成，会发生什么？答案异常简单：你只需重新抽奖，直到找到一个准备好运行的获胜者。这会带来一个有趣的后果：系统会自动并动态地将被阻塞进程的 CPU 份额重新分配给当前可运行的进程。
一个进程的有效 CPU 份额不再仅仅是其票据比例。它是其票据比例乘以其非阻塞概率，然后根据所有竞争进程的平均可运行性进行重新归一化。如果一个进程 的票据比例为 ，阻塞概率为 ，其有效份额 将变为 。这种机制确保了 CPU 时间不会浪费在无法使用它的进程上。资源会自然地流向能产生效益的地方。
那饥饿问题呢？在一个简单的抽奖系统中，一个票据很少的进程可能因为运气太差而等待极长时间才能被调度。我们可以用另一个优雅的技巧来解决这个问题：票据老化。
这个想法是，一个进程等待的时间越长，就给它越多的票据。例如，一个进程在时间 的票据数可以是 ，其中 是一个“老化率”。无论其基础票据数多么少，它的票据数最终都会增长到足够大，使其赢得抽奖的概率接近 1。这为防止饥饿提供了硬性保障。等待超过 个时间步长的概率呈指数级下降，确保每个进程最终都能轮到自己。
也许票据比喻最精妙的扩展是它对优先级反转问题的解决方案。想象一个低票据进程（比如一个简单的日志记录器）持有一个高票据进程（一个视频渲染器）所需的关键资源（一个互斥锁）。重要的视频渲染器现在被卡住了，等待着不重要的日志记录器运行并释放锁。但由于日志记录器的票据太少，它可能很长时间都无法被调度。高优先级任务实际上被一个低优先级任务阻塞了。
解决方案是票据继承。等待中的视频渲染器将其票据“捐赠”或“借给”持有锁的日志记录器。突然间，这个不起眼的日志记录器就拥有了大量票据！它在下一次 CPU 抽奖中获胜的机会非常高，使其能够运行、完成任务并释放锁。锁一旦被释放，票据就被归还，视频渲染器就可以继续执行。我们甚至可以有不同的实现方案，例如锁持有者的票据数变为它自己和等待者票据数之和（），或者其他变体。调度器不需要理解互斥锁或资源依赖关系；它只需遵循票据的流向，正确的事情就会发生。
一个健壮的系统必须能抵抗被“滥用”。恶意应用程序能否获得不公平的优势？假设一个应用程序有 张票据的预算。是作为一个拥有 张票据的单进程运行更好，还是作为 10 个每个拥有 张票据的子进程运行更好？一个设计良好的调度器，如果能按应用程序计算票据，或者能正确地将一个应用程序所有线程的票据加总，那么它就是免疫的。该应用程序的任何一个线程获胜的总概率保持不变，其总 CPU 份额也保持不变。然而，有缺陷的实现可能会被利用。如果创建新进程会错误地给予它们全额的票据分配，那么应用程序就能有效地“印自己的钱”，占领 CPU。这表明，虽然概念很简单，但核算必须严谨。
最后，当情况变得非常动态，当票据分配本身随时间快速变化时会发生什么？考虑一个其票据数呈正弦波动的进程。在彩票调度中，如果振荡相对于调度时间片非常快，抽奖的随机性会起到自然平均的作用。在短时间内，调度器会从整个振荡周期中采样，进程获得的份额会迅速稳定到长期平均值。
但这里有一个奇妙的转折。在步幅调度的确定性世界里，这些快速振荡是灾难性的。步幅值在相邻的两个时间片之间剧烈变化，破坏了“通行值”作为进度度量的意义。其结果是极具突发性和不公平性的行为。在这种特殊情况下，“不可预测的”彩票调度器实际上比其确定性对应方案更稳定、更可预测。这是一个绝佳的提醒：在复杂系统的世界里，简单规则的相互作用可以导致出人意料且极具洞察力的结果。
在上一章中，我们接触到了一个为实现公平性而设计的、异常简洁而优雅的思想：彩票调度。这个概念像抽奖一样直观。想要获得更多资源份额？只需获得更多票据。每次有机会时，系统都会随机抽取一张中奖票据，该票据的所有者将获得资源。这种概率性方法对于像现代操作系统这样复杂的东西来说，似乎过于简单，难以实用。它只是一个可爱的理论玩具，还是这个想法真的有力量？
我们即将看到，这个简单的抽奖概念不仅仅是教科书中的一个注脚。它是一个深刻而通用的原则，以多种形式出现，从你电脑 CPU 调度器的核心，到决定你在线看到哪些广告的系统。本章是一次探索之旅，旨在发现抽奖机制惊人的广度和力量。我们将看到它是如何被使用的，它的局限在哪里，以及它的核心逻辑如何与看似不相关的问题联系起来，揭示了复杂系统设计中一种优美的统一性。
让我们从一个熟悉的场景开始：教室。想象一位老师想点名让学生回答问题。为了公平，她决定使用彩票调度。每个学生都会得到一定数量的“参与票据”——也许那些渴望回答的学生会得到更多。如果一个学生有 8 张票据，而另一个只有 1 张，那么在任何一个问题上，第一个学生被点到的机会是后者的八倍。在整个学年中，我们可以预期每个学生被点到的次数与他们的票据数量成正比。我们甚至可以使用像 Jain 公平性指数这样的指标来量化这种公平性，该指数会显示结果的“公平性”是票据分布本身的内在属性，而不是所提问题数量的属性。
这个简单的类比可以直接映射到软件世界。想象一下，不是学生争夺老师的注意力，而是一个程序的许多线程在争夺单一资源，比如保护共享数据的“互斥锁”。一次只有一个线程可以持有该锁。我们如何决定下一个谁来获取它？我们可以举行一次抽奖！通过给每个线程票据，我们可以概率性地管理访问权限。高优先级线程获得许多票据；低优先级线程获得少量票据。
这立即解决了一个经典问题：饥饿。即使只有一个票据的线程，最终也会赢得抽奖。它永远不会被永久忽略。然而，这也揭示了一个微妙之处。如果一个线程有 1000 张票据，而另一个只有 20 张，第二个线程可能需要等待很长时间才能轮到它。我们可以计算饥饿概率——即该线程在（比如说）200 次机会中一次也没有轮到的机会。这个概率可能很小，但它不是零。这突显了其中的权衡：彩票调度为我们提供了概率上的公平性，但没有关于等待时间的绝对保证。
这个想法一个有趣的扩展是使系统具有自我纠正能力。想象一下，每当一个线程赢得抽奖，它的票据数就被重置为一个较低的基准值，而所有没有赢得的线程都会得到几张额外的票据。会发生什么？一个运气不好连续输掉几次抽奖的线程会看到它的票据数——以及它获胜的机会——稳步增加。这就创造了一个优美的负反馈循环，自动将系统推回到公平状态。事实上，由于这个过程的深度对称性，我们可以证明，从长远来看，每个线程都将获得平等的资源份额，而不管具体的票据调整值是多少。系统优雅地自我调节。
所以，抽奖是共享单一资源的稳健方法。但现代计算机是一个复杂的巨兽，有成千上万个进程，并组织成不同的组。我们简单的抽奖模型如何扩展呢？答案是分层。
现代操作系统使用“控制组”（cgroups）来管理一组进程的资源。我们可以将我们的抽奖原则用作一个两级系统中的构建块。在顶层，操作系统在控制组之间进行抽奖，以决定哪个组在下一个时间片获得 CPU。然后，在获胜的控制组内部，在其成员进程之间进行第二次抽奖，以选出最终的获胜者。
这背后的数学原理非常简单。一个进程长期获得的 CPU 比例就是它在其组内的票据份额，乘以该组在整个系统中的票据份额。即，。这种组合属性使得彩票调度成为构建复杂的、分层的资源管理器的强大而模块化的工具。
现实世界甚至更混乱。如果我们的计算机有多个 CPU 核心，而且它们并非完全相同怎么办？也许一个是高性能核心，另一个是低功耗效率核心。当一个进程从一个核心移动到另一个核心时会发生什么？它的数据不再位于本地缓存中，因此会遭受性能损失。我们简单的抽奖模型能处理这个问题吗？
令人惊讶的是，可以。我们可以调整这个框架。“奖品”的价值现在取决于进程被分配到的核心的速度。我们可以通过计算迁移发生的概率以及在不同核心速度下预期的性能损失，来精确地模拟由于迁移惩罚而导致的预期性能损失。该模型的概率性质使我们能够对所有这些复杂事件进行平均，以预测一个进程将获得的有效的、长期的份额。这个简单的抽奖模型被证明是一个非常灵活的分析工具。
到目前为止，我们的抽奖机制表现出色。但它有一个致命弱点：对机会的依赖。对于许多任务来说，“长期来看可能是公平的”已经足够好。但如果不够呢？
考虑一个有硬性截止日期的关键进程——比如说，一个必须在 16 毫秒内完成一帧的视频渲染进程。随着截止日期的临近，我们可以给这个进程越来越多的票据。这极大地增加了它赢得所需 CPU 时间的机会。但失败的概率，无论多么小，都永远不为零。一连串的坏运气总是可能发生的。我们可以计算出我们的关键进程错过截止日期的确切概率，这是一个发人深省的提醒：概率性调度器无法提供硬性保证。
这时，彩票调度的一个确定性近亲登场了：步幅调度。你可以把步幅调度看作是“去随机化”的彩票。它不是每次都随机抽取一张票据，而是保留着一丝不苟的记录。每个进程都有一个“通行值”。为了获得一次运行机会，进程必须“支付”一定数量，即它的“步幅”，该值与其票据数量成反比。调度器只需选择通行值最低的进程——即“最应该”轮到的那个进程。
结果是一个能够实现与彩票调度相同的长期比例份额的系统，但它以近乎完美的短期精度来做到这一点。与理想的、完全平滑的分配的偏差，即所谓的“延迟”（lag），总是被限制在一个小的常数内（通常是一个时间片）。相比之下，彩票调度的误差会随时间随机增长，在 次分配后约为 的量级。
这种区别不仅仅是学术上的。它反映了计算机网络中的一个经典二分法。彩票调度类似于随机公平队列（SFQ），这是一种利用随机化来近似公平带宽分配的轻量级算法。而步幅调度，凭借其确定性保证和有界延迟，是加权公平队列（WFQ）的直接类比，后者是一种用于高端路由器以提供强大服务质量（QoS）保证的更复杂的算法。无论是在 CPU 调度还是网络包调度中，我们都看到了同样的基本权衡：随机性的优雅简洁性与确定性的可预测保证之间的较量。
这个思想——通过比例份额分配资源——的力量远远超出了操作系统。让我们看两个令人惊讶的例子。
首先，考虑一个在线广告平台。一个广告商，比如说可口可乐，为一个特定的广告展示“预算”付费。平台的任务是向用户展示他们的广告，其比例要与他们的预算成正比。用户访问量是出了名的突发和不可预测的。在这里，步幅调度的“有界延迟”属性不仅仅是一个好的特性；它是一个核心业务需求。可口可乐公司不能承受因为彩票调度器的“坏运气”而在超级碗期间没有展示广告，即使系统承诺“稍后会补上”。他们需要他们的展示份额能够平滑且可预测地交付，尤其是在流量高峰期。通过将广告活动建模为进程，将预算建模为票据，一个基于步幅的调度器可以精确地提供这种保证，使其成为解决该问题的完美选择。
其次，让我们思考一个完整的系统。一个进行视频流的进程可能既需要 CPU 周期来解码视频，也需要网络带宽来下载它。如果只给这个进程 50% 的 CPU 份额，但只分配了 10% 的网络带宽，这是无用的——网络成了瓶颈。真正的端到端吞吐量由最紧张的约束决定。
这引出了一个深刻的见解。如果我们希望进程的最终吞吐量与其网络“票据”（份额）的比例相匹配，我们不能仅仅给它们相同比例的 CPU 票据。因为不同的进程每字节数据有不同的 CPU 成本，我们必须进行调整。为了实现一个平衡的系统，分配给一个进程的 CPU 周期 必须不仅与其期望的吞吐量份额 成正比，而且要与该份额与其计算成本 的乘积成正比。也就是说，我们必须确保 。这种“协同调度”或平衡资源分配的原则是高性能系统设计的基石，它自然地源于对比例份额调度器相互作用的分析。
最后，对于我们最令人惊讶的联系，让我们考虑一个操作系统如何管理硬盘上的可用空间。假设你需要保存一个特定大小的文件。操作系统有一个包含许多空闲“区段”（连续空间块）的列表。为了最小化浪费的空间（内部碎片），理想的方法是“最佳适配”算法：检查每一个空闲区段，并选择那个刚好足够大的。但是当有成千上万个空闲区段时，这样做非常慢。
如果我们转而举行一次“可用空间抽奖”呢？我们随机选择少量（比如 个）空闲区段，然后只对这个小样本应用最佳适配规则。这是一种随机化近似算法。数学分析表明，如果空闲空间大小呈指数分布，这种“抽奖”方法得到的结果平均比真正的最优解差 倍（其中 是总区段数），但它只用了搜索工作量的一小部分就完成了。在这里，抽奖原则重生了，它不再是追求公平的工具，而是一种用最优性换取效率的强大启发式方法。
从一个简单的争取公平的抽奖，我们穿越了分层操作系统、实时性保证、数十亿美元的广告平台以及系统平衡的深层原理。我们已经看到抽奖思想，无论是其概率形式还是确定性形式，都为资源分配提供了一个统一的框架。它的优雅不仅在于其简单性，还在于其非凡的通用性以及它所开辟的丰富的理论和实践前景。