illegalCreed

中文

English

中文

English

Appearance

页面置换算法与抖动 ​

基于通用操作系统概念 · 核于 2026-08

速查 ​

  • 页面置换（Page Replacement）：物理帧满时，选一页淘汰到 swap 腾出空间给新页。算法的优劣直接影响缺页率（缺页=读磁盘=毫秒级慢）。
  • FIFO（先进先出）：淘汰最先装入的页。实现简单（队列），但不顾访问模式——可能淘汰正在用的热页。可能 Belady 异常。
  • LRU（最近最少使用）：淘汰最久未访问的页。理论最优的实用近似（基于局部性：用过的还会用），但需硬件支持（时间戳/计数器/栈）精确实现成本高，工业上多用近似（Clock）。
  • 最优 OPT（Optimal，MIN）：淘汰未来最长时间不被访问的页。是理论下界（缺页率最低），但需预知未来访问序列，不可实现——只用于评估其他算法（与 OPT 的差距就是改进空间）。
  • Clock（时钟/二次机会）：LRU 的廉价近似。所有帧排成环形（时钟），指针扫描；淘汰时看 Accessed 位——1 则清零给"二次机会"跳过，0 则淘汰。开销小，性能接近 LRU。
  • Belady 异常：FIFO 特有——增加物理帧数，缺页率反而上升的反直觉现象。LRU/OPT 不会出现（它们满足"栈式算法"性质：帧多则驻留集是帧少的子集）。
  • 抖动（Thrashing）：内存严重不足，进程频繁缺页，CPU 几乎全在换页而非执行——吞吐崩塌。原因是分配给进程的帧数小于其工作集。
  • 工作集（Working Set）：进程在时间窗口 Δ 内实际访问的页集合。理论指导：给每个进程分配的帧数应≥其工作集大小，否则 thrash。工作集随程序阶段变化（如编译 vs 链接阶段活跃页不同）。
  • 缺页率（Page Fault Frequency, PFF）：另一种控制策略——监测每进程缺页率，过高则加帧（防 thrash），过低则减帧（省给别的进程）。
  • 请求分页（Demand Paging）：页按需装入——首次访问触发缺页才从磁盘读。装入策略：请求调页（纯按需）vs 预调页（预先批量调入相关页，利用空间局部性）。
  • 置换决策：Dirty 位：淘汰时若页 Dirty=1（写过）要写回磁盘（脏页换出慢）；Dirty=0 可直接丢弃（磁盘已有最新副本，如只读代码段）——所以置换算法倾向于先淘汰干净页。
  • 进阶顺序：本文讲置换算法 → 回 分页、分段与页表 复习地址翻译 → 参考 速查对比。

一、为什么需要页面置换 ​

物理帧是有限的，但虚拟地址空间很大。当所有物理帧被占满，又需要装入新页（发生缺页）时，必须淘汰一个旧页腾出空间——这就是页面置换（Page Replacement）。

   物理帧全满 + 发生缺页（需要装入页 X）
         │
         ▼
   ┌─ 调用页面置换算法 ─┐
   │  选一个"最不重要的"页淘汰  │
   └────────────┬────────┘
                ▼
   被淘汰页是 Dirty（写过）？ → 是：写回磁盘 swap
                               否：直接丢弃（如只读代码）
                ▼
   腾出的物理帧装入新页 X（从磁盘读）
                ▼
   更新页表，返回重新执行访存指令
  • 目标：让缺页率最低。因为缺页要读磁盘（毫秒级），比内存访问慢 5 万倍，缺页频繁则系统性能崩塌。
  • 理想 vs 现实：理想是知道未来访问序列（最优 OPT，但不可实现）；现实是基于历史（LRU/Clock，假设"过去用过的未来还会用"，即局部性）。
  • 局部性是基础：所有置换算法都依赖局部性原理（时间局部性：刚用的还会用）。若程序无局部性（随机访问 100GB），任何算法都救不了——频繁缺页（抖动）。

二、FIFO：先进先出 ​

FIFO（First In First Out）淘汰最先装入的页——用队列实现，新页入队尾，淘汰队首：

   访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5（3 个帧）
   
   帧池（队列）：        缺页？
   [1] _ _              ✓ 装入 1
   [2 1] _ _            ✓ 装入 2
   [3 2 1]              ✓ 装入 3
   访问 4（满）→ 淘汰 1（最先入）→ [4 3 2]   ✓ 缺页
   访问 1（不在）→ 淘汰 2 → [1 4 3]          ✓ 缺页
   访问 2 → 淘汰 3 → [2 1 4]                 ✓ 缺页
   ...
  • 优点：实现极简（一个队列），开销低。
  • 缺点：不顾访问模式。一个被反复使用的热页（如循环变量），只要它是"最先装入"的就被淘汰——即使下一秒还要用。
  • 致命缺陷：Belady 异常。FIFO 在增加帧数时，缺页率可能上升（见第五节），这是反直觉的，也使 FIFO 在实际系统中很少单独使用。

三、LRU：最近最少使用 ​

LRU（Least Recently Used）淘汰最久未访问的页——基于局部性：用过的还会用，最久没用的最可能不再用：

   LRU 维护一个"按最近访问时间排序"的栈：
   栈顶 = 最近刚访问的，栈底 = 最久没访问的（淘汰候选）

   访问序列：1, 2, 3, 4, 1, 2, 5（3 个帧）
   访问 1：[1]                  （栈：1 在顶）
   访问 2：[2 1]
   访问 3：[3 2 1]
   访问 4（满）：淘汰 1（栈底）→ [4 3 2]   缺页
   访问 1（不在）：淘汰 2 → [1 4 3]         缺页
   访问 2（不在）：淘汰 3 → [2 1 4]         缺页
   访问 5（满）：淘汰 4 → [5 2 1]           缺页
  • 优点：理论最优的实用近似。基于局部性，性能接近 OPT，是工业界的"金标准"目标。
  • 缺点：需要硬件支持。精确 LRU 要给每个页维护时间戳或计数器，每次访问都要更新（用栈移动），开销大。纯软件实现太慢。
  • 实现方式：①计数器法（每个 PTE 有计数器，每次访问计数器+1，淘汰最小的）；②栈法（维护栈，访问则移到栈顶，淘汰栈底）——两者都要硬件支持才高效。
  • 不会 Belady：LRU 是"栈式算法"（n 帧的驻留集是 n+1 帧驻留集的子集），帧多则缺页少，满足直觉。

四、最优 OPT：理论下界 ​

最优（OPT，又称 MIN/Belady 算法）淘汰未来最长时间不被访问的页：

  • 理论最优：在固定帧数下，OPT 的缺页率最低——它是其他算法的评估基准（一个算法与 OPT 的差距就是改进空间）。
  • 不可实现：需要预知未来访问序列，现实中无法做到（除非离线分析）。
  • 用途：用于离线评估。给定一个访问序列，算出 OPT 缺页率，再算 LRU/Clock 的，比较差距——这指导算法改进。
  • 不会 Belady：OPT 是栈式算法，帧多则缺页少。

五、Clock：LRU 的廉价近似 ​

精确 LRU 太贵，工业系统多用 **Clock（时钟/二次机会）**算法近似 LRU：

   所有帧排成环形（时钟），有一个指针。每个帧有 Accessed 位（硬件访问时自动置 1）。

   淘汰流程：
   1. 指针扫描
   2. 当前帧 Accessed=1？→ 清零，给"二次机会"，指针前进
   3. 当前帧 Accessed=0？→ 淘汰它（最近一轮没被访问过）
   4. 回到 1 直到找到淘汰目标

   直觉：被访问过的页（A=1）给一次豁免，下一轮才可能被淘汰
         ——近似"最近未用"（LRU）
  • 优点：开销极小。只需 Accessed 位（硬件免费维护），不需时间戳/栈。性能接近 LRU（工业界大量使用，Linux 的活跃/非活跃链表是变种）。
  • 二次机会的直觉：最近被访问过的页（A=1）"值得留下"，给一次豁免（清零）；若一轮扫描后 A 仍=0，说明确实很久没用，淘汰。
  • 改进：Clock 的多轮变体。若所有页都 A=1，Clock 要扫一圈才淘汰（性能差）。改进：维护"第二次机会"——更精细地近似 LRU（如 Linux 的双链表 active/inactive + 引用位）。

六、Belady 异常：FIFO 的反直觉缺陷 ​

1969 年 Belady 发现：用 FIFO 算法，增加物理帧数，缺页率反而上升：

   访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
   
   FIFO, 3 个帧：缺页 9 次
   FIFO, 4 个帧：缺页 10 次   ← 帧多了，缺页反而多！
  • 原因：FIFO 淘汰"最先装入"的页，与访问模式无关。帧多时，某些页被保留得更久（因为队尾更长），反而挤掉了即将使用的页。
  • 谁会 Belady：只有 FIFO（及类似非栈式算法）。LRU、OPT 是栈式算法（n 帧驻留集 ⊆ n+1 帧驻留集），帧多则缺页必然不增——不会 Belady。
  • 意义：Belady 异常揭示了"帧多≠缺页少"的反直觉可能，是区分算法优劣的重要依据。FIFO 因此在实用中常被 Clock/LRU 取代。

七、抖动：频繁缺页的灾难 ​

抖动（Thrashing）：进程频繁缺页，CPU 几乎全在换页而非执行——系统吞吐崩塌。

   CPU 利用率 vs 多道程序度（并发进程数）：
   
   利用率 ↑
         │           ╱ ← 正常：进程多了，总有进程在运行
         │         ╱
         │       ╱
         │     ╱
         │   ╱  ↓ ← 抖动拐点：进程太多，每个进程帧数不够工作集
         │ ╱  ╱     频繁缺页，CPU 都在等磁盘，利用率骤降
         │╱ ╱
         └────────────→ 多道程序度
  • 原因：进程数过多，每个进程分到的帧数小于其工作集。进程的活跃页频繁被换出又换入（互相抢占），导致每次访问都缺页。
  • 后果：磁盘 IO 飙升（swap 狂转），CPU 利用率骤降（都在等磁盘），系统像"卡死"。极端下只能杀进程或重启。
  • 应对：
    1. 工作集模型：估算每进程工作集，保证 Σ工作集 ≤ 物理帧数；超了就挂起/换出部分进程（降低多道度），让剩下的进程有足够帧。
    2. 缺页率反馈（PFF）：监测每进程缺页率，过高→加帧，过低→减帧。超过阈值则减少并发进程数。
    3. 增加物理内存：根本解法——更多帧让每进程工作集都驻留。

八、工作集理论 ​

工作集（Working Set）：进程在时间窗口 Δ 内实际访问的页集合，反映程序的"当前活跃内存需求"：

  • 定义：W(t, Δ) = 进程在 [t-Δ, t] 时间段内访问过的页集合。Δ 是窗口大小（如 10000 条指令）。
  • 变化：工作集随程序阶段变化——如编译阶段活跃的是语法分析相关页，链接阶段活跃的是符号表相关页。阶段切换时工作集会"抖动"（旧工作集淘汰、新工作集装入）。
  • 指导调度：若 Σ（所有进程工作集大小）≤ 物理帧数，所有进程可高效运行；若 >，则 thrash——此时应挂起部分进程（换出整个进程到 swap），降低多道度。
  • 与局部性的关系：工作集是局部性的量化度量。局部性好的程序，工作集小且稳定（少量活跃页）；局部性差的程序，工作集大且波动（频繁切换活跃页，易 thrash）。

九、置换算法对比与选型 ​

算法淘汰谁复杂度Belady？需硬件实用性
FIFO最先装入的O(1) 队列会否少用（有缺陷）
LRU最久未访问的O(n) 栈/计数器不会需（时间戳）金标准但成本高
OPT未来最久不用的O(n)不会需预知不可实现（评估用）
ClockA=0 的（二次机会）O(n) 均摊不会Accessed 位主流（Linux 变种）
  • 工业实践：Linux 用双链表 + 引用位（active list / inactive list，类似 Clock 改进），近似 LRU 且开销小。Windows 类似。纯 LRU 因硬件成本极少精确实现。
  • 选型原则：对缺页率敏感（如数据库），尽量精确 LRU；对通用系统，Clock（开销小、性能近 LRU）足够。

十、请求分页：按需装入 ​

请求分页（Demand Paging）：页按需装入——首次访问触发缺页才从磁盘读：

  • 纯请求调页：页在第一次被访问时装入。程序启动慢（前期大量缺页），但内存利用率高（只用到的页才占帧）。
  • 预调页（Prepaging）： anticipating 访问，预先批量调入相关页（如代码段连续几页、数组所在几页）。利用空间局部性减少缺页次数，但可能调入用不到的页（浪费）。
  • 写时复制（COW）：fork 时共享只读页，写时才复制——这也是"按需"思想的体现（不立即复制，写到才复制）。
  • swap 策略：被淘汰的页写到哪里？磁盘 swap 分区（Linux）或 swap 文件（Windows）。swap 速度直接影响缺页代价——SSD 让 swap 可接受，机械硬盘 swap 几乎不可用（毫秒级）。

下一步 ​

理解了置换算法与抖动后，建议回看分页、分段与页表复习地址翻译的完整流程，或到参考速查分页 vs 分段、各置换算法的对比表与易错点清单。