《操作系统导论》第22章：超越物理内存：策略 - 深度知识架构

1. 核心矛盾 (The Crucial Problem)

当物理内存耗尽，系统必须将某些内存页交换到慢速磁盘时，操作系统如何在对未来程序访问模式“一无所知”的情况下，决定踢出（替换）哪些页，从而最大限度地减少极其昂贵的磁盘访问（缓存未命中）开销？

2. 核心概念 (Core Concepts)

• 平均内存访问时间 (Average Memory Access Time, AMAT)：
  • 定义：评估缓存效率的数学指标。公式为 $AMAT=(PHit\times TM)+(PMiss\times TD)$，其中 TM 是内存访问成本，TD 是磁盘访问成本，PHit 和 PMiss 分别是命中率和未命中率。
  • 角色：系统的“性能量尺”。由于磁盘访问（TD）比内存（TM）慢数万倍，只要未命中率有极微小的上升，AMAT 就会被极大地拖慢，这凸显了替换策略的致命重要性。
• 最优替换策略 (Optimal Replacement Policy, OPT/MIN)：
  • 定义：替换在最远将来才会被访问到的页的算法。
  • 角色：系统的“完美假想敌”。它能达到最低的未命中率，但需要预知未来。虽然无法在现实中实现，但被用作对比标尺，用来评估实际策略到底有多好。
• 局部性 (Locality)：
  • 定义：程序倾向于展现出的访问规律，分为空间局部性 (Spatial Locality)（倾向于访问邻近的内存）和时间局部性 (Temporal Locality)（近期访问过的页很快会再次被访问）。
  • 角色：缓存系统生效的“基础物理法则”。它是预测未来的底层依据。
• 近期最少使用 (Least-Recently-Used, LRU) / 先进先出 (First-In-Out, FIFO)：
  • 定义：常见的两种替换策略。LRU 踢出最久未被访问的页，FIFO 踢出最早进入内存的页。
  • 角色：操作系统的上层决策逻辑，决定了缓存的具体置换行为。
• 抖动 (Thrashing)：
  • 定义：内存的超额请求使得正在运行的进程工作集超出了物理内存容量，导致系统不断在硬盘和内存之间进行换页的现象。
  • 角色：虚拟内存系统的“崩溃边缘”，迫使操作系统放弃正常调度，转而采用准入控制或“OOM Killer (Out-Of-Memory Killer)”来暴力减少内存压力。

3. 逻辑演进 (Logical Evolution)

为了在不知道未来的情况下做出最好的替换决策，页面替换算法经历了如下推演：

• 确立理论标尺（最优策略）：Belady 提出了最优策略（MIN算法），即替换最远将来才使用的页。
  • 遇到的问题：我们没有水晶球，无法预知未来，该策略无法在现实系统中实现。
• 最初的简单方案（FIFO 与 Random）：使用简单的数据结构，如先进先出队列（FIFO）或直接随机（Random）踢出页面。
  • 遇到的问题：没有利用程序的任何行为特征（局部性）。FIFO 甚至会将经常使用的核心重要代码页踢出（并且受 Belady 异常影响，即缓存变大时命中率反而可能下降），性能极其糟糕。
• 演进方案（引入历史信息的 LRU）：通过“以史为鉴”预测未来。引入 LRU 策略，踢出最久未使用的页。它完美利用了时间局部性原理，在多数工作负载下命中率非常接近最优策略。
  • 遇到的新的致命挑战：实现成本太高。要在百万个内存页中，每次发生内存读写时都更新时间戳或者调整链表，会消耗大量的 CPU 算力和时间，得不偿失。
• 最终的成熟方案（近似 LRU 的时钟算法）：放弃寻找“绝对最旧”的页，寻找“差不多旧”的页。硬件为每一页增加一个使用位 (Use Bit / Reference Bit)。操作系统维护一个循环列表和一个时钟指针 (Clock Hand)。当需要踢出时，指针扫过页面，如果使用位是 1，则清零并跳过；如果是 0，则踢出该页。
  • 如何克服问题：用极少量的硬件辅助（1个比特位），让操作系统以极低的开销实现了对 LRU 的高度近似，完美平衡了“寻找最佳页面”与“降低查找开销”的矛盾。

4. 机制与策略 (Mechanisms vs. Policies)

在“超越物理内存”的完整框架中，机制与策略得到了极其清晰的解耦：

• 底层的“实现手段”（机制 - Mechanisms）：
  • 硬件标记机制：硬件负责在每次读写时设置使用位 (Use Bit) 和修改位/脏位 (Modified/Dirty Bit)。
  • 按需分页 (Demand Paging)：仅在产生页错误异常（Page Fault）时才将页面“按需”拉入内存的低级执行机制。
• 上层的“决策逻辑”（策略 - Policies）：
  • 页替换策略 (Page-Replacement Policy)：即上述的 FIFO、Random、LRU 和时钟算法，用于决定踢出哪一页。
  • 页选择策略 (Page Selection Policy)：除了按需分页，操作系统还可以采用预取 (Prefetching) 策略，在预测到页面会被使用前提前载入。
  • 写入策略：决定何时将脏页写回磁盘，例如使用聚集 (Clustering/Grouping) 策略将多个页面打包进行一次大的顺序写入，以优化磁盘 I/O。

5. 设计折衷 (Design Trade-offs)

• 牺牲“精准度”，换取“极致的性能开销”：纯软件实现完美的 LRU 代价极其昂贵（每次内存访问都需要记账）。时钟算法通过硬件的 1 个使用位，牺牲了找到“绝对最久未使用页面”的精确性，换取了每次内存访问几乎为零的记录开销以及快速的置换决策。
• 牺牲“干净页”，保护“脏页”：在进行页替换扫描时，现代系统倾向于先踢出未被修改的“干净页 (Clean Page)”，而不是“脏页 (Dirty Page)”。这牺牲了对干净页 LRU 顺序的严格遵守，但换取了极大的性能收益（因为踢出脏页需要进行极其缓慢的磁盘写入 I/O，而踢出干净页几乎是瞬时完成的）。

6. 关键洞察 (Key Insights)

• 与最优策略（OPT）对比是非常有用的标尺：虽然最优策略在现实中极不切实际，但在工程中它有着不可替代的价值。它能让你知道当前算法距离“完美”还有多远：如果你的 LRU 达到了 80% 命中率，而最优策略也是 82%，你就知道优化已经到达天花板，应该立刻停止无谓的折腾。
• 局部性是一种强大的启发式经验（而非定律）：利用历史预测未来（如 LRU）之所以能成功，全靠程序展现出的空间局部性和时间局部性。但这并非不可打破的物理定律（例如遇到循环顺序扫描大数组时，LRU 的命中率会直接跌至 0%）。深刻理解局部性的边界，是构建健壮系统的基础。
• 不要总是追求完美 (Tom West 定律的变体)：在复杂的系统设计中，“寻找差不多旧的页”远比“寻找绝对最旧的页”更具工程价值。通过软硬件的巧妙协同（硬件打标记，软件定时扫描并清零），我们用最低的系统复杂度实现了一个完全能满足实际需求的大型缓存系统。

导师的下一步建议： 至此，我们已经走完了内存虚拟化的整条主线：从底层的地址转换机制（基址界限、分段、分页、TLB、多级页表），一直到突破物理极限的交换机制与替换策略。 为了给”内存虚拟化”画上一个完美的句号，原书安排了 第23章（VAX/VMS 虚拟内存系统），这是一个非常精彩的真实系统案例研究，它将我们学过的所有概念（页表、交换、按需置零、写时复制）融会贯通。

MOC · 下一章：Ch23 VAX/VMS