玻尔百科现代计算依赖于一种强大的“无限内存”幻觉，使我们能够在有限的物理内存（RAM）上同时运行大量复杂的应用程序。但是，操作系统是如何在压力下实现这一壮举而又不让性能崩溃的呢？这就是工作集模型所要解决的根本挑战，该模型是计算机科学的基石理论，由 Peter Denning 提出。本文将揭开这一强大概念的神秘面纱，解释系统如何通过基于可预测的程序行为来智能地管理内存，从而避免“颠簸”这一灾难性状态。通过理解程序当前的内存需求，操作系统可以做出明智的决策，保持整个系统平稳运行。首先，我们将深入探讨“原理与机制”，探索局部性原理、工作集的定义以及操作系统采用的控制策略。之后，在“应用与跨学科联系”中，我们将看到这一个模型如何为理解从数据库到机器学习等不同领域的性能提供一个统一的框架。
要想真正理解让我们的计算机在有限内存上同时运行数十个程序的魔力，我们必须首先领会一个关于行为的简单而深刻的真理。这不仅是计算机程序的行为，也是我们自身的行为。
想象一下，你正在研读一本厚厚的物理教科书。你会在一分钟内先读第 1 页，然后读第 500 页，再读第 237 页吗？当然不会。你的注意力是局部的。你会花相当多的时间在当前页面上，也许会翻回一两页检查一个公式，你的眼睛会在邻近的句子和图表上扫视。这种重用最近看过的信息，以及访问靠近当前使用内容的信息的倾向，就是局部性原理的精髓。
计算机程序在很大程度上也是如此。它们不是混乱的野兽，在代码中随意跳转。它们执行循环，一遍又一遍地运行同一组指令。它们调用子程序，这些子程序是反复使用的小而集中的代码块。它们处理数组，一个接一个地访问元素。这种可预测的、局部化的行为是一份礼物。它意味着在任何给定时刻，一个程序并未使用其在内存中的全部足迹。相反，它有一个小得多的“热”或“活动”页面集合，这才是它真正需要的。这是解开整个虚拟内存之谜的关键。
如果一个程序的注意力持续时间很短，我们如何量化它？我们如何为它此刻需要的内存画一个圈？这就是工作集模型背后的核心思想，这个概念由 Peter Denning 完美地阐述。其思想是定义一个时间窗口，我们称之为 ，并声明程序的工作集 就是它在过去 秒内接触过的所有唯一内存页面的集合。
可以把它看作是程序当前“心智”或“焦点”的一个快照。如果 选择得当，这个页面集合就包含了程序继续平稳运行所需的一切。如果其工作集中的所有页面都物理上存在于内存中，程序就可以全速运行。如果它需要一个不在内存中的页面——即发生页面错误（page fault）——它就必须戛然而止，等待操作系统从慢得多的磁盘中获取该页面。
一个简单而优雅的模型有助于将此具体化。想象一个程序，它顺序读取一个很长的代码“章节”，每执行 条指令后，就需要查阅一个大小为 的小型“笔记”子程序。为了让程序高效运行，“笔记”必须在快速内存中随时可用。但在每次查阅之间，程序会引入一连串的“章节”页面。问题是，我们的内存需要多大才能避免“忘记”这些笔记？
其逻辑惊人地简单。内存必须足够大，以容纳整个“笔记”子程序，外加上次使用笔记以来访问过的所有来自“章节”的不同页面。这就给出了一个最低内存需求：核心活动代码的大小加上两次使用之间遍历的代码的大小。在这种情景下，工作集正是这些页面的集合。该模型的美妙之处在于，它将一个复杂的动态过程转化为一个简单的核算问题：我们有足够的空间容纳工作集吗？
现在来看阴暗面。当一个操作系统贪婪地试图一次运行太多程序，而忽略了它们的集体工作集时，会发生什么？这会导致一种被称为颠簸（thrashing）的灾难性状态。
打个比方，这就像一个厨师在狭小的厨房里试图同时准备十几道复杂的菜肴。他的操作台空间只够放一两道菜的食材。为了做第 3 道菜，他必须收起第 1 道菜的所有食材。然后，为了做第 4 道菜，他又收起了第 2 道菜的食材。很快，他所有的时间都花在了从储藏室来回搬运食材上，而没有时间真正做饭。他用于烹饪的“CPU 利用率”接近于零，但他却比以往任何时候都忙。
这正是计算机发生的情况。假设我们有四个正在运行的进程，每个进程的工作集为 900 页，但机器只有 3000 个物理内存帧可供它们使用。总需求是 页，超过了我们拥有的 3000 页。系统处于超额分配状态。
当进程 1 运行时，它开始请求其 900 个页面。为了腾出空间，操作系统不得不换出属于进程 2、3 和 4 的页面。然后，当操作系统切换到进程 2 时，它发现自己的工作集已经不见了！进程 2 此时会遭遇一场页面错误的风暴，为了满足这些请求，操作系统又换出了进程 1 刚刚加载的页面。系统进入了一个恶性循环：它把所有时间都花在处理页面错误上——在快速的 RAM 和慢速的磁盘之间来回倒腾页面——几乎没有时间执行指令。CPU 闲置等待，而磁盘指示灯疯狂闪烁。这就是颠簸。
性能损失不是小数目，而是天文数字。访问内存的时间可能是 100 纳秒，而处理单个页面错误的时间可能是 8 毫秒，即 8,000,000 纳秒——相差近五个数量级！计算表明，即使页面错误率适中，平均内存访问时间也可能飙升，导致程序运行速度慢上数千倍。颠簸不是减速，而是整个系统的崩溃。
现代操作系统如何避免这种命运？它就像一个高档夜总会的聪明保镖。他知道夜总会的容量，即使外面排着长队，也不会让所有人都同时进来。这个原则被称为准入控制（admission control）。
在接纳一个新进程之前，操作系统必须检查是否有足够的空闲内存来容纳其工作集。基本规则是维持以下不变量： 其中 是进程 的工作集大小， 是活动进程的数量， 是可用的物理内存。
当然，这引出了一个棘手的问题：操作系统如何知道一个进程的工作集大小？它无法读懂程序员的心思。相反，它必须通过观察进程最近的行为来测量它。这本身就是一个挑战。一些方法，比如使用硬件引用位（reference bits），相当准确。另一些方法，比如稀疏采样页面访问，可能成本更低，但可能会低估工作集的大小。低估是危险的，就像保镖数错了俱乐部里的人数。它可能导致操作系统接纳过多的进程，从而引发它本应防止的颠簸。
如果操作系统检测到颠簸已经发生（例如，通过观察到高页面错误率和低 CPU 利用率的组合），该怎么办？它必须执行负载削减（load shedding）。它主要有两个选择：
操作系统绝不能做的一件事是，看到 CPU 利用率低就想：“CPU 太闲了，让我们接纳更多进程吧！” 这是一个致命的反馈循环，早期的操作系统曾陷入其中，导致颠簸不断恶化，直到系统完全无响应。
故事变得更加有趣，因为程序的工作集不是静态的。程序会经历不同的阶段（phases）。一个文字处理器可能处于工作集较小的“打字”阶段，然后转换到工作集大得多的“拼写检查”阶段。
这就是该模型展现其真正动态性的地方。考虑一个进程，它在一台拥有 200 个内存帧的机器上，在工作集较小（50页）的阶段 A 和工作集较大（200页）的阶段 B 之间交替。在阶段 A，一切安好；有 150 个帧是空闲的。但当进程切换到阶段 B 的那一刻，它突然需要 180 个不在内存中的新页面！结果是，当进程疯狂地将其新工作集调入内存时，会发生短暂但剧烈的颠簸。
一个真正智能的操作系统可以做得更好。如果它能预测到阶段变化，它就可以利用这 150 个空闲帧，在转换发生之前为阶段 B 预分页（prepage）或预取（prefetch）页面。当进程切换时，其新工作集的大部分已经就位，从而避免了性能的悬崖式下跌。
这就把我们带到了机制本身。这一切是如何实现的呢？像 WSClock（工作集时钟）这样的算法会为每个页面维护一个“年龄”。操作系统设定一个阈值 ；如果一个页面在过去的 秒内没有被使用，它就被认为是“老的”，并成为被淘汰的候选者。但 应该设为多少呢？一个固定的值很笨拙。一个智能的操作系统会根据观察到的运行程序的内存重用模式动态调整 。它会学习特征性的“阶段内”重用时间，并将 设置得足够高以保护这些页面，同时将具有长“阶段间”重用时间的页面暴露出来以供替换。
这就是工作集模型的全部荣耀所在：它不是一个静态的规则，而是一场由操作系统与其所管理的程序之间动态的、由反馈驱动的舞蹈。这是一个绝佳的例子，展示了通过观察、建模和适应程序行为，计算机如何能够创造出无限、即时内存的强大幻觉。
在了解了工作集模型的原理之后，我们可能会想把它归档为一条巧妙的操作系统理论。但这样做就只见树木，不见森林了。工作集模型远不止是一个抽象的定义；它是一个锐利而实用的工具，用于理解几乎所有由小型快速内存服务于大型慢速内存的系统中的性能。它是自然界最基本的组织原则之一——局部性原理——的体现。在时间上一起使用的东西，在空间上倾向于放在一起。当这个原则成立时，效率就高。当它被违反时，性能就会崩溃。
现在，让我们踏上一段旅程，看看这个思想是如何在实践中发挥作用的，从它在计算机操作系统中的原生栖息地，到计算科学令人惊讶的前沿领域。我们将看到，这一个概念如何提供一种统一的语言，来描述那些表面上看起来毫无关联的现象。
工作集模型最直接、最基础的应用是在计算的核心：操作系统。它需要巧妙地处理无数程序对有限物理内存池的争夺需求。
操作系统必须回答的最基本问题是：“我能同时运行多少个程序？”工作集模型提供了一个直接的、定量的答案。如果一台高性能服务器有 GB 的内存，而每个计算任务需要一个大小为 GB 的工作集才能高效运行，那么该系统大约可以支持 个这样的任务。超过这个限制——哪怕只多接纳一个任务——就意味着总工作集需求超过了可用内存。系统将被迫不断地将页面交换到磁盘，进入灾难性的颠簸状态，把所有时间都花在管理内存上，而不是做有用的工作。这个简单的计算是现代数据中心容量规划和准入控制的基石。
当然，操作系统比这更聪明。它们知道并非所有内存都是生而平等的。当你运行两个不同的程序时——比如一个网页浏览器和一个文本编辑器——它们并非完全孤立存在。它们都依赖于一个庞大的通用系统函数集合，即“共享库”。操作系统不是为每个程序加载一份这个通用代码的独立副本，而是只将其加载到物理内存中一次，并将其映射到每个需要它的程序的地址空间中。从工作集模型的角度来看，这是一个神来之笔。整个系统的聚合工作集不是单个工作集的简单相加；共享部分只计算一次。这极大地减少了总内存压力，从而允许更高程度的多道程序设计。然而，每个进程的私有数据仍然是唯一的，随着更多进程的加入，正是这些私有数据区域的增长最终将系统推向颠簸的悬崖。共享代码和私有数据之间的这种平衡是操作系统内存管理的核心戏剧。
有时，操作系统提高效率的尝试本身也可能成为麻烦的来源。一个典型的例子是 [fork()](/sciencepedia/feynman/keyword/fork()|lang=zh-CN|style=Feynman) 系统调用，它通过近乎瞬时地复制父进程来创建一个新进程。这种速度背后的魔力是“写时复制”（Copy-on-Write, CoW）。最初，子进程共享父进程的所有物理内存页面，这些页面被标记为只读。实际上没有内存被复制。只有当父进程或子进程试图写入一个共享页面时，才会创建物理副本。如果子进程主要进行读取操作，这是非常高效的。但如果子进程立即开始一个写密集型任务，修改其继承的大部分内存，会发生什么？每次写入都会触发一个页面错误和新页面的分配。系统的总工作集会突然急剧扩张。如果父进程的原始工作集和子进程新的私有页面的总和超过了物理内存，系统就会陷入颠簸。一个为速度而设计的机制，反而成了灾难性减速的原因。
为了对抗这些压力，操作系统已经开发了对策。如果问题在于工作集，为什么不尝试缩小它呢？现代系统正是通过实时内存压缩来做到这一点。通过将进程工作集中使用频率较低的页面在内存中进行压缩，操作系统可以减少进程的内存足迹。一个曾经占用 800MB 的工作集可能会被压缩到 440MB。这种缩减使得更多进程可以共存于内存中，从而显著增加分时系统在开始颠簸前可以支持的用户数量。
工作集模型的美妙之处在于它是递归的。小型快速内存服务于大型慢速内存的同样戏剧，不仅在操作系统层面发生，也深深地发生在复杂应用程序的内部。这些应用程序实质上运行着自己的微型操作系统，它们也受制于完全相同的法则。
考虑一个大型数据库管理系统（DBMS）。它在主内存中维护一个“缓冲池”，其作用就像操作系统的物理内存。当数据库需要从磁盘上的表中获取一块数据时，它首先将其加载到这个缓冲池的一个页面中。这个缓冲池就是数据库的工作内存。现在，想象一个包含两种查询类型的工作负载：一种是短小的事务性查询，反复访问一小部分客户记录的“热点集”；另一种是长时的分析性查询，对数 TB 的历史数据进行顺序扫描。热点集具有很好的局部性和很小的工作集。而扫描的局部性极差；每个页面只使用一次就被丢弃。如果数据库对其缓冲池使用简单的最近最少使用（LRU）替换策略，顺序扫描将用一次性页面淹没缓冲池，从而挤出至关重要的热点集页面。结果呢？事务性查询会遭受持续的缓冲池未命中，迫使它们访问磁盘。数据库开始颠簸，不是在操作系统层面，而是在其内部。解决方案是让数据库成为它自己的小型操作系统，运用工作集原理：它必须识别出扫描所带来的污染页面，并防止它们驱逐更有价值的热点集，甚至限制并发扫描的数量——这一行为与操作系统降低其多道程序设计程度的行为直接类似。
这种模式在像 Java 或 Python 这样的托管编程语言世界中再次出现。这些语言使用垃圾回收器（GC）来自动管理内存。一个现代的“并发”GC 与主应用程序并行运行，寻找并释放未使用的内存。但 GC 本身就是一个程序！它有自己的工作集，由元数据和它必须检查的堆页面组成。这个 GC 工作集与应用程序自身的工作集争夺物理内存。如果 GC 过于激进，其工作集可能会变得足够大，以致于挤出应用程序的页面，从而引发一场页面错误的风暴。这个本应管理内存的工具，反而成了颠簸的原因。因此，工程师必须将 GC 设计成具有自我意识的，通过调整其操作（例如，一次处理的对象的批量大小）来确保其自身的工作集保持足够小，以便与它所服务的应用程序和平共存。
随着技术的发展，舞台变了，但戏剧依旧。工作集模型为理解当今要求最苛刻的应用程序和复杂硬件的性能提供了至关重要的见解。
机器学习（ML）负载是出了名的内存消耗大户。一个典型的训练任务可能会在“计算阶段”（GPU 处理数据）和“数据加载阶段”（CPU 从磁盘准备下一批数据）之间交替进行。这两个阶段的工作集可能截然不同。计算阶段可能有一个稳定且大小合理的模型权重工作集，而数据加载器可能会触及数 TB 的图像文件，产生一个短暂但巨大的工作集。每次任务从计算阶段转换到加载阶段时，操作系统都会疯狂地换出计算页面，为数据页面腾出空间，反之亦然。结果是在每个阶段转换时都会发生颠簸。一个关键的工程解决方案是明确管理数据加载器的工作集。开发者不是让它不受控制地映射文件，而是创建一个小的、有界的“环形缓冲区”内存，并将其“钉住”（pinned）——意味着操作系统禁止将其换出。数据加载器将数据读入这个固定大小的缓冲区，然后由 GPU 消费。通过严格控制数据加载器的足迹，应用程序的总工作集保持稳定并能容纳在物理内存中，从而消除了颠簸。
虚拟化世界又增加了一个迷人的复杂层次。运行虚拟机监控程序（hypervisor）的主机充当了其他操作系统（客户机）的操作系统。为了管理内存，hypervisor 可以在每个客户虚拟机内部使用一个“气球驱动”（balloon driver）。为了从客户机回收内存，hypervisor 会告诉气球“膨胀”，在客户机内部分配内存。这迫使客户机操作系统，在看到自己的空闲内存消失时，将它认为最不重要的数据分页到它自己的虚拟磁盘上。然后，hypervisor 就可以回收支持这些气球页面的真实物理内存。但如果 hypervisor 太激进会怎样？它可能会将气球膨胀得太大，以至于客户机剩余的内存小于其工作集。客户机操作系统将开始剧烈颠簸。这种客户机级别的颠簸会对其虚拟磁盘产生大量的 I/O。从主机的角度看，这就像一个突然的、密集的磁盘工作负载，导致主机自身的 I/O 缓冲区膨胀并消耗更多的主机内存。这可能产生一个恶性反馈循环：主机试图解决自身的内存压力，却在其客户机中引发了颠簸，而这反过来又给主机带来了更大的内存压力，导致全系统的“交换风暴”（swap storm）。
即使是现代处理器的物理架构也需要从工作集的角度来看待。在一台拥有多个 CPU 插槽的服务器上，内存不是一个统一的池。每个 CPU 都有一组“本地”内存，可以非常快速地访问；它也可以访问其他 CPU 的“远程”内存，但成本要高得多。这被称为非统一内存访问（NUMA）。在这里，工作集模型适用于每个节点。如果操作系统调度器不小心将太多内存密集型进程放在单个 NUMA 节点上，它们工作集的总和可能会超过该节点的本地内存。该节点将开始颠簸，执行缓慢的远程内存访问或交换到磁盘，而同一台机器上的另一个节点却未得到充分利用。先进的解决方案是一个 NUMA 感知调度器，它主动监控进程的工作集和每个节点的内存压力，在机器上迁移进程以平衡负载，并确保每个本地工作集都能容纳在其本地内存中。
我们旅程的最后一站将我们完全带离计算机系统，揭示了工作集作为一个真正普适的概念。在计算量子化学领域，科学家们进行复杂的模拟以理解分子的行为。像 CASSCF（完全活性空间自洽场）这样的方法被用来模拟化学反应。为了使问题易于处理，他们定义了一个“活性空间”——一个由化学上最重要的电子和轨道组成的小子集。然后，计算将其最密集的计算工作集中在这个空间上。
这个“活性空间”本质上就是一个科学上的工作集。代表这个活性空间的数据结构——构型相互作用矢量和积分张量——是计算的核心工作集。模拟的性能取决于一个熟悉的问题：这个工作集是否能装入可用的快速内存？在这种情况下，“快速内存”不是主内存，而是 CPU 的末级缓存。如果活性空间足够小，其数据可以装入缓存，计算就属于“计算密集型”（compute-bound）——仅受处理器数字处理速度的限制。如果活性空间太大，其数据会溢出缓存，迫使数据不断地与主内存进行缓慢的传输。计算就变成了“内存密集型”（memory-bound），其速度由内存带宽决定。通过这个类比，我们看到，化学中活性空间的选择受制于同样的局部性原理，该原理也决定了操作系统中的页面替换策略。
从在超级计算机上调度任务到模拟化学键的断裂，工作集模型为我们提供了一个深刻而统一的视角。它告诉我们，在任何具有内存层次结构的系统中，从 CPU 缓存到物理内存再到磁盘驱动器，性能不是由数据的总大小决定的，而是由我们此刻需要的数据的大小决定的。要设计出快速、高效的系统，就是要理解、尊重和管理引用局部性。