跳转至

408 高频考点精讲:页面置换算法

模块归属:操作系统 · 内存管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

1. 考查频次与题号清单

  • 近十年考查频次:4 次(2016 年第 26 题、2021 年第 28 题、2022 年第 30 题、2025 年第 26 题)
  • 历年总考查频次:5 次(含 2010 年第 27 题)
  • 出题形式:单项选择题为绝对核心形式;同时作为综合解答题中虚拟存储系统访存全流程计算的关键子模块。

2. 命题特点分析

  1. 算法执行细节深度追踪:命题不再局限于机械记忆概念,而是着重考察状态转换细节。例如 2016 年第 26 题考查改进型 Clock 算法的状态分类与淘汰次序,2021 年第 28 题要求精确模拟指针扫描过程中的标志位重置,2025 年第 26 题深度考查 LRU 队列状态转移与缺页统计。
  2. 虚拟存储体系全链路融合:页面置换算法往往与虚实地址变换、页表结构、TLB 命中判定紧密结合(如 2021 年第 28 题)。考生必须建立从虚拟地址拆分、缺页中断响应、页框淘汰到物理地址合成的完整认知闭环。
  3. 系统宏观性能机理辨析:深入考查抖动(颠簸)现象的成因、工作集模型、驻留集动态调节以及页缓冲队列(PBA)对系统性能的具体影响维度(如 2022 年第 30 题对“缺页率”与“缺页处理延迟”本质区别的辨析)。

3. 近十年考查年份分布表格

+------+--------+----------------------------------------------------+------------+
| 年份 | 题号   | 核心考点                                           | 题型       |
+------+--------+----------------------------------------------------+------------+
| 2016 | 第26题 | 改进型 Clock 算法页面分类与置换淘汰优先级          | 单项选择题 |
| 2017 | 无     | -                                                  | -          |
| 2018 | 无     | -                                                  | -          |
| 2019 | 无     | -                                                  | -          |
| 2020 | 无     | -                                                  | -          |
| 2021 | 第28题 | 改进型 Clock 算法置换模拟结合虚拟地址变换计算      | 单项选择题 |
| 2022 | 第30题 | 缺页率影响因素辨析与页缓冲队列(PBA)机制特性      | 单项选择题 |
| 2023 | 无     | -                                                  | -          |
| 2024 | 无     | -                                                  | -          |
| 2025 | 第26题 | 固定分配局部置换下 LRU 算法缺页次数计算与状态转移  | 单项选择题 |
+------+--------+----------------------------------------------------+------------+

二、 具体考察内容

1. 核心概念与机制原理

(1) 请求分页存储管理与缺页中断

请求分页系统建立在基本分页系统基础之上,为了实现虚拟存储,增加了请求调页功能和页面置换功能。 - 页表项结构:除了基本物理块号(页框号)之外,请求分页系统的页表项增加了控制信息字段: $$ \text{页表项} = {\text{页号}, \text{物理页框号}, \text{存在位 } P, \text{访问位 } A, \text{修改位 } M, \text{外存地址}} $$ - 存在位(有效位)\(P\)$ \text{:标识该页是否已调入主存(} $\(1\)$ \text{表示在内存,} $\(0\) 表示在外存)。 - 访问位(引用位)\(A\):记录该页最近是否被访问过,供置换算法参考。 - 修改位(脏位)\(M\):记录该页调入主存后是否被修改过。若未修改,淘汰时无需写回外存;若已修改,淘汰时必须写回外存。 - 外存地址:指出该页在外存上的物理存放位置(磁盘块地址)。 - 缺页中断处理特性: - 缺页中断属于内部异常(Fault,故障)。 - 在指令执行期间产生和处理,处理完成后返回到发生故障的指令重新执行。 - 一条指令在执行过程中可能产生多次缺页中断(例如访存指令跨页或源/目标操作数分布于不同页面)。

(2) 常见页面置换算法模型

  1. 最佳置换算法(OPT, Optimal Replacement):
  2. 决策原则:淘汰未来最长时间内不再被访问的页面。
  3. 特性:具有最低的缺页率。因系统无法预知未来的页面访问序列,该算法在实际工程中无法实现,常作为衡量其他置换算法性能的理论上限(Benchmark)。

  4. 先进先出置换算法(FIFO, First-In First-Out):

  5. 决策原则:淘汰最先进入内存的页面,即驻留时间最长的页面。
  6. 实现数据结构:维护一个驻留页面的先进先出队列。
  7. 异常缺陷:存在 Belady 异常(Belady's Anomaly),即当为进程分配的物理页框数增加时,缺页次数反而增加。

  8. 最近最久未使用置换算法(LRU, Least Recently Used):

  9. 决策原则:淘汰过去最长时间未被访问的页面。利用时间局部性原理,以过去的访问历史推断未来的访问行为。
  10. 实现机制:
    • 活动页面栈:每当访问某页时,将其从栈中抽出并压入栈顶;发生缺页时淘汰栈底页面。
    • 移位寄存器/逻辑时钟:为每个页表项配置计数器或移位寄存器,周期性更新访问记录。
  11. 特性:理论性能接近 OPT,属于堆栈型算法,严格杜绝 Belady 异常;但硬件实现开销较大。

  12. 最不经常使用置换算法(LFU, Least Frequently Used):

  13. 决策原则:淘汰过去一段时间内访问频次最少的页面。
  14. 缺陷:早期频繁访问但后期不再使用的页面会长期滞留在内存中(计数过大无法迅速衰减)。

  15. 简单时钟置换算法(Clock / NRU / 二次机会算法):

  16. 结构:将内存中的驻留页面链接成一个循环队列,设置一个循环指针。每个页面设置一位访问位 \(A\)。
  17. 流程:

    • 当某页被访问时,硬件自动将其访问位置 \(A = 1\)。
    • 发生置换时,指针从当前位置开始扫描:
    • 若当前页 \(A = 0\),选择该页换出;
    • 若当前页 \(A = 1\)$ \text{,将其清零(} $\(A \leftarrow 0\)),指针移动到下一个页面继续检查。
    • 最多经过两轮扫描即可找到可淘汰页面。
  18. 改进型时钟置换算法(Enhanced Clock):

  19. 设计动机:置换一个被修改过的页面需要写回外存(消耗一次磁盘 I/O),而置换未修改的页面只需直接覆盖(无需写回外存)。在考虑访问历史的同时兼顾 I/O 开销。
  20. 页面四元分类 \((A, M)\):
    • 第 1 类 \((0, 0)\):最近未被访问,且未被修改。置换首选,代价最低。
    • 第 2 类 \((0, 1)\):最近未被访问,但已被修改。置换次选,需写回磁盘。
    • 第 3 类 \((1, 0)\):最近已被访问,但未被修改。存在局部性,保留优先级高。
    • 第 4 类 \((1, 1)\):最近已被访问,且已被修改。最不倾向淘汰。
  21. 四轮扫描淘汰算法流程:
    • 第 1 轮:从指针当前位置开始循环扫描,寻找第一个 \((0, 0)\) 的页面。扫描过程中不修改任何访问位。若找到,将其置换并指针步进。
    • 第 2 轮:若第 1 轮未找到,开始第 2 轮扫描,寻找第一个 \((0, 1)\)$ \text{的页面。在扫描过程中,将经过的所有页面的访问位} $\(A\)$ \text{均置为} $\(0\)。若找到,将其置换并指针步进。
    • 第 3 轮:若第 2 轮仍未找到,此时所有驻留页面的访问位已全部变为 \(0\)$ \text{,重新扫描寻找第一个} $\((0, 0)\)$ \text{页面(对应原先的} $\((1, 0)\))。扫描过程中不修改任何访问位。若找到直接置换。
    • 第 4 轮:若第 3 轮仍未找到,重新扫描寻找第一个 \((0, 1)\)$ \text{页面(对应原先的} $\((1, 1)\))。本轮必定能找到目标页面。

(3) 物理页框分配策略与置换范围

  • 固定分配局部置换:为每个进程分配固定数量的物理块,运行期间块数不变;缺页时只能在该进程的驻留集中选择页面淘汰。
  • 可变分配全局置换:系统维护一个空闲物理块队列,进程缺页时优先从全局空闲块分配;若空闲块耗尽,可从其他任何进程中选择页面换出。
  • 可变分配局部置换:根据进程缺页率动态增减分配给该进程的物理块数;缺页时仅置换该进程自身的页面。

(4) 抖动颠簸现象与工作集模型

  • 抖动(Thrashing,颠簸):页面频繁在内存与外存之间置换,导致调度和 I/O 耗费的时间远大于实际执行指令的时间,CPU 利用率急剧下降。
  • 产生根本原因:多道程序并发度过高,导致系统分配给进程的物理块数小于其工作集大小。
  • 工作集(Working Set):
  • 定义:在某段时间间隔 \(\Delta\)$ \text{(工作集窗口大小)内,进程实际访问的页面集合,记作} $\(W(t, \Delta)\)。
  • 机制:操作系统动态监测进程的工作集大小,并为进程分配不小于工作集大小的物理页框(驻留集 \(\ge\) 工作集),从根本上预防抖动。
  • 页缓冲系统(Paging Buffering System, PBA):
  • 结构:系统设立空闲页链表与修改页链表。
  • 运行机制:淘汰页面并不立刻写回外存,而是挂入相应链表尾部。若该页短时间内再次被访问,直接从链表中取回,避免高代价的磁盘 I/O。
  • 核心性质:页缓冲队列改善了缺页中断处理效率和系统吞吐率,但并没有改变页面命中与缺失的判定准则,因而不会影响系统的缺页率。

2. 核心定理推导与计算模型

(1) 缺页率与有效访存时间(EAT)计算模型

设进程总访存次数为 \(N\)$ \text{,发生缺页中断的次数为} $\(F\)$ \text{,则缺页率} $\(P\) 定义为: $\(P = \frac{F}{N}\)$

在请求分页系统中,单次有效访存时间(Effective Access Time, EAT)由命中内存访问与缺页处理耗时加权构成: $\(EAT = (1 - P) \times t_{mem} + P \times (t_{fault} + t_{mem})\)$

若考虑快表(TLB)命中率 \(\alpha\)$ \text{、TLB 访存时间} $\(t_{tlb}\)$ \text{、单次内存物理访问时间} $\(t_{mem}\)$ \text{以及包含磁盘写回开销的缺页处理平均时间} $\(t_{fault}\): 1. TLB 命中(概率 \(\alpha\)): $\(t_{hit} = t_{tlb} + t_{mem}\)$ 2. TLB 缺失且页表命中(概率 \((1 - \alpha)(1 - P)\)): $$ \text{t_{miss_page_hit} = t_{tlb} + t_{mem} (\text{查页表}) + t_{mem} (\text{访物理数据})} $$ 3. 缺页中断处理(概率 \((1 - \alpha)P\)): $\(t_{page\_fault} = t_{tlb} + t_{mem} + t_{fault} + t_{tlb} + t_{mem}\)$ 综合有效访存时间模型可表达为: $\(EAT = t_{tlb} + t_{mem} + (1 - \alpha) \times t_{mem} + (1 - \alpha) \times P \times t_{fault}\)$

(2) 堆栈型置换算法与 Belady 异常判定定理

  • 堆栈型算法(Stack Algorithm)数学定义: 若页面置换算法满足:对于任意页面访问序列,在任意时刻 \(t\)$ \text{,当分配物理页框数为} $\(n\)$ \text{时的驻留页面集合} $\(S_t(n)\)$ \text{,恒为分配物理页框数为} $\(n+1\)$ \text{时的驻留页面集合} $\(S_t(n+1)\) 的子集,即: $\(S_t(n) \subseteq S_t(n+1), \quad \forall t, \forall n\)$ 则称该置换算法为堆栈型算法。
  • 单调性定理: 若某算法为堆栈型算法,则其缺页率关于物理页框数 \(n\) 单调不增。因此:
  • OPT 算法:属于堆栈型算法,不产生 Belady 异常。
  • LRU 算法:驻留集严格对应过去访问历史排序的前 \(n\)$ \text{个独特页面,} $\(S_t(n) \subset S_t(n+1)\) 恒成立,属于堆栈型算法,杜绝 Belady 异常。
  • FIFO 算法:驻留集取决于各页面最早载入内存的时间戳,当页框数增加时,换出次序可能发生紊乱,不满足子集包含性,因而会产生 Belady 异常。

3. 核心对比辨析

表 1:主流页面置换算法全维度对比

算法名称 决策准则 算法类型 Belady 异常 硬件支持要求 软件实现复杂度 实际工程应用
OPT 未来最长时间不访问 堆栈型 绝对无 无法实现(需预知未来) 理论模型 理论性能基准
FIFO 驻留时间最长 非堆栈型 存在 无需特殊硬件 简单(队列结构) 极少独立使用
LRU 过去最久未被访问 堆栈型 绝对无 较高(时钟/寄存器/栈) 极高(需频繁调序) 虚拟内存近似实现
Clock 循环检查访问位 \(A\) 非堆栈型 极罕见 低(硬件置访问位) 简单(循环链表+指针) 主流操作系统通用
改进型 Clock 综合考量 \((A, M)\) 非堆栈型 极罕见 低(硬件置访问位、修改位) 中等(四轮扫描状态机) 类 UNIX / Linux 内核
LFU 访问频次最小 非堆栈型 存在 较高(频次计数器) 较高(需定期衰减防滞后) 局部特定场景应用

表 2:影响系统缺页率的关键因素与非关键因素辨析

影响因素 是否影响缺页率 作用机理与内在因果链条
页面置换算法 是 算法决定了淘汰命中率高低,直接决定缺页发生的绝对频次。
分配给进程的页框数 是 驻留集越大,能够容纳的局部活跃页面越多,缺页率越低。
工作集大小 是 工作集表征进程在当前阶段的活跃页面量,决定了所需物理块基数。
并发进程数量 是 并发度提高会加剧内存争用,使得每个进程分得的物理块减少,缺页率升高。
程序自身的局部性 是 空间局部性与时间局部性优良的程序缺页率显著较低。
页缓冲队列(PBA)长度 否 仅用于暂缓被淘汰页面的物理写入,降低单次缺页中断的磁盘 I/O 耗时,不改变缺页判定。

三、 近十年真题精讲(2016~2025)

【真题 1】2016 年 408 第 26 题 · 改进型 CLOCK 置换算法淘汰次序

题目:
某系统采用改进型 CLOCK 置换算法,页表项中字段 A 为访问位,M 为修改位。A=0 表示页最近没有被访问,A=1 表示页最近被访问过。M=0 表示页没有被修改过,M=1 表示页被修改过。按 (A, M) 所有可能的取值,将页分为四类:(0, 0)、(1, 0)、(0, 1) 和 (1, 1),则该算法淘汰页的次序为( )。
A. (0, 0), (0, 1), (1, 0), (1, 1)
B. (0, 0), (1, 0), (0, 1), (1, 1)
C. (0, 0), (0, 1), (1, 1), (1, 0)
D. (0, 0), (1, 1), (0, 1), (1, 0)

【解析】

  1. 知识定位:考查改进型 Clock 页面置换算法的类别划分原则及其优先级判定逻辑。
  2. 核心推导:
  3. 改进型 Clock 算法的核心思想是:优先淘汰最近未被访问的页面(利用时间局部性原理,保证置换命中率);在访问位相同的情况下,优先淘汰未被修改过的页面(减少外存磁盘 I/O 写回开销)。
  4. 根据此原则,页面分为四类优先级:
    • 第 1 优先级:\((A=0, M=0)\),最近未访问且未修改,淘汰时代价最小且不影响局部性,最先淘汰。
    • 第 2 优先级:\((A=0, M=1)\),最近未访问但被修改,虽然需写回外存,但因其不具有活跃局部性,次优先淘汰。
    • 第 3 优先级:\((A=1, M=0)\),最近被访问且未修改,具有时间局部性,暂不淘汰。
    • 第 4 优先级:\((A=1, M=1)\),最近被访问且被修改,具有时间局部性且修改代价大,最不应被淘汰。
  5. 算法的淘汰遍历次序严格为:\((0, 0) \to (0, 1) \to (1, 0) \to (1, 1)\)。
  6. 选项辨析:
  7. A 选项:顺序为 \((0, 0), (0, 1), (1, 0), (1, 1)\),完全符合算法设计规范,正确。
  8. B 选项:错误地将 \((1, 0)\)$ \text{排在} $\((0, 1)\)$ \text{之前。若先淘汰} $\((1, 0)\),则违背了“未访问页优先于已访问页”的局部性核心原则。
  9. C 选项、D 选项:后两项顺序颠倒,均不符合算法规范。

正确答案:A


【真题 2】2021 年 408 第 28 题 · 改进型 Clock 置换模拟与物理地址合成

题目:
某请求分页存储系统的页大小为 4KB,按字节编址。系统给进程 P 分配 2 个固定的页框并采用改进型 Clock 置换算法,进程 P 页表的部分内容如下表所示:

页号 页框号 存在位 (1:存在, 0:不存在) 访问位 (1:访问, 0:未访问) 修改位 (1:修改, 0:未修改)
... ... ... ... ...
2 20H 0 0 0
3 60H 1 1 0
4 80H 1 1 1
... ... ... ... ...

若 P 访问虚拟地址为 02A01H 的存储单元,则经地址变换后得到的物理地址是( )。
A. 00A01H
B. 20A01H
C. 60A01H
D. 80A01H

【解析】

  1. 知识定位:考查虚拟地址分解、页表项结构判定、改进型 Clock 置换过程模拟以及物理地址合成。
  2. 地址分解:
  3. 页面大小为 \(4\text{ KB} = 2^{12}\text{ B}\),按字节编址,因此虚拟地址低 12 位(3 位十六进制数)为页内偏移量,高位为虚拟页号。
  4. 虚拟地址为 02A01H:
    • 页内偏移量为低 12 位:A01H。
    • 虚拟页号为高位:02H(即 2 号页)。
  5. 查表判断与缺页处理:
  6. 查看 2 号页对应的页表项:存在位为 \(0\),说明 2 号页不在主存中,触发缺页中断。
  7. 进程 P 分配了 2 个固定的页框,此时驻留主存的页面为 3 号页(占用页框 60H)与 4 号页(占用页框 80H)。驻留集已满,必须执行页面置换。
  8. 改进型 Clock 置换模拟:
  9. 内存中存在的两页初始状态为:
    • 3 号页:\((A=1, M=0)\)
    • 4 号页:\((A=1, M=1)\)
  10. 指针依次遍历当前驻留页面(3 号页与 4 号页):
    • 第一轮扫描:寻找 \((0, 0)\),不修改访问位。
    • 检查 3 号页:\((1, 0) \ne (0, 0)\),未命中;
    • 检查 4 号页:\((1, 1) \ne (0, 0)\),未命中。
    • 第二轮扫描:寻找 \((0, 1)\)$ \text{,沿途将扫描页面的访问位} $\(A\)$ \text{置为} $\(0\)。
    • 检查 3 号页:原为 \((1, 0)\)$ \text{,将} $\(A\)$ \text{置 0 变为} $\((0, 0)\)$ \text{,不匹配} $\((0, 1)\);
    • 检查 4 号页:原为 \((1, 1)\)$ \text{,将} $\(A\)$ \text{置 0 变为} $\((0, 1)\),匹配成功!
    • 关键注意:在第二轮扫描中,4 号页在被检查时,其 \(A\)$ \text{位被置为} $\(0\)$ \text{,状态瞬间变为} $\((0, 1)\) 从而被第二轮命中淘汰?
    • 算法规范审视:根据汤子瀛教材及经典操作系统定义,第二轮扫描是“寻找 \((0, 1)\)$ \text{,同时将所有扫描过的页面} $\(A\) 置 0”。
      • 当检查 3 号页时:初始为 \((1, 0)\)$ \text{,不符合} $\((0, 1)\)$ \text{,将其置为} $\((0, 0)\),指针移向 4 号页。
      • 当检查 4 号页时:初始为 \((1, 1)\)$ \text{,不符合} $\((0, 1)\)$ \text{(判定依据是扫描时当前页面的初始状态),将其置为} $\((0, 1)\)$ \text{,第二轮扫描结束仍未找到初始即为} $\((0, 1)\) 的页。
    • 第三轮扫描:重新寻找 \((0, 0)\)。
    • 此时 3 号页状态已为 \((0, 0)\)$ \text{,4 号页状态为} $\((0, 1)\)。
    • 指针回到 3 号页,检查发现其状态为 \((0, 0)\),命中!选择淘汰 3 号页。
  11. 物理地址合成:
  12. 淘汰 3 号页,将 3 号页占用的物理页框 60H 分配给 2 号页。
  13. 2 号页装入页框 60H,物理地址由页框号拼接页内偏移量构成: $$ \text{物理地址} = \text{页框号 (60H)} \parallel \text{页内偏移 (A01H)} = 60\text{A01H} $$
  14. 选项辨析:
  15. A 选项:00A01H,无此页框号,错误。
  16. B 选项:20A01H,直接将页表项历史残留的页框号 20H 当作目标,忽视了存在位为 0,错误。
  17. C 选项:60A01H,正确淘汰 3 号页并取得其页框号,正确。
  18. D 选项:80A01H,错误淘汰 4 号页,计算错误。

正确答案:C


【真题 3】2022 年 408 第 30 题 · 影响系统缺页率的关键因素辨析

题目:
下列选项中,不会影响系统缺页率的是( )。
A. 页面置换算法
B. 工作集的大小
C. 进程的数量
D. 页缓冲队列的长度

【解析】

  1. 知识定位:考查请求分页系统中缺页率的影响因素及页缓冲机制(PBA)的本质作用。
  2. 影响因素逐项深度剖析:
  3. A 选项(页面置换算法):页面置换算法的核心目标就是减少未来的缺页次数。OPT、LRU、FIFO 的缺页率具有显著差异,置换算法直接影响缺页率,排除。
  4. B 选项(工作集的大小):工作集反映了进程在特定时间窗口内活跃引用的页面集合大小。若分配给进程的页框数小于其工作集大小,缺页率将急剧上升;反之,页框数覆盖工作集时缺页率大幅下降。因此工作集大小直接决定了系统缺页率的高低,排除。
  5. C 选项(进程的数量):系统物理内存总量固定,并发进程数量越多(多道程序度过高),每个进程平均分到的物理块数越少。当物理块数被压缩到临界值以下时,会导致各进程频繁缺页甚至引发抖动。因此并发进程数量显著影响缺页率,排除。
  6. D 选项(页缓冲队列的长度):页缓冲系统(Page Buffering Algorithm)将淘汰出的页面暂存在内存中的空闲链表或修改页链表中。当缺页发生时,若所需页面恰好在缓冲链表中,则只需修改指针将其取回,从而免去了耗时的磁盘 I/O。页缓冲机制改善的是单次缺页中断的处理时间与磁盘 I/O 吞吐率,并不改变页面是否缺失的判定逻辑,因此不会影响缺页率的统计数值。符合题意。

正确答案:D


【真题 4】2025 年 408 第 26 题 · LRU 页面置换与缺页次数精确推导

题目:
现有一 LRU 算法,采用固定分配局部置换的页面置换策略,已为进程分配 3 个页框,页面访问序列为 {0, 1, 2, 0, 5, 1, 4, 3, 0, 2, 3, 2, 0},其中 0, 1, 2 已调入内存。则缺页次数是( )。
A. 5
B. 6
C. 7
D. 8

【解析】

  1. 知识定位:考查固定分配局部置换策略下,LRU 页面置换算法的状态追踪与缺页次数精确计算。
  2. 审题关键点:
  3. 页框总数为 3。
  4. 题干明确指出“其中 0, 1, 2 已调入内存”。这意味着初始状态下 3 个页框已经被页面 0, 1, 2 占满,初始调入不计入后续访问序列的缺页次数。
  5. LRU 状态追踪模拟表: 我们将 LRU 栈表示为一个列表,约定左端为最久未使用的页面(淘汰目标),右端为最近刚访问的页面。
序号 访问页号 当前驻留页面(LRU 栈:[最久 \(\to\) 最新]) 是否缺页 淘汰页面 缺页累计
- 初始状态 [0, 1, 2](已装入,按初始顺序排列) - - 0
1 0 [1, 2, 0](命中,0 移至最新端) 命中 - 0
2 1 [2, 0, 1](命中,1 移至最新端) 命中 - 0
3 2 [0, 1, 2](命中,2 移至最新端) 命中 - 0
4 0 [1, 2, 0](命中,0 移至最新端) 命中 - 0
5 5 未命中,淘汰最久未用的 1,调入 5 \(\to\) [2, 0, 5] 缺页 1 1
6 1 未命中,淘汰最久未用的 2,调入 1 \(\to\) [0, 5, 1] 缺页 2 2
7 4 未命中,淘汰最久未用的 0,调入 4 \(\to\) [5, 1, 4] 缺页 0 3
8 3 未命中,淘汰最久未用的 5,调入 3 \(\to\) [1, 4, 3] 缺页 5 4
9 0 未命中,淘汰最久未用的 1,调入 0 \(\to\) [4, 3, 0] 缺页 1 5
10 2 未命中,淘汰最久未用的 4,调入 2 \(\to\) [3, 0, 2] 缺页 4 6
11 3 [0, 2, 3](命中,3 移至最新端) 命中 - 6
12 2 [0, 3, 2](命中,2 移至最新端) 命中 - 6
13 0 [3, 2, 0](命中,0 移至最新端) 命中 - 6
  1. 统计结果: 在访问序列执行期间,第 5、6、7、8、9、10 次访存发生缺页,缺页总次数为 6 次。

正确答案:B


四、 综合考法拓展

1. 虚存全流程综合大题解题图谱

在 408 综合应用大题中,页面置换算法经常与页式地址映射、快表(TLB)、Cache 映射高度交叉命题。标准解题执行链路如下:

虚拟地址 (VA)
   │
   ├─► 划分:[ 虚拟页号 VPN | 页内偏移量 Offset ]
   │
   ▼
[ 检索 TLB ] ───(命中)───► 获取物理页框号 PFN ────────────────────────┐
   │                                                                 │
 (未命中)                                                            │
   │                                                                 │
   ▼                                                                 │
[ 访问内存页表 ]                                                     │
   │                                                                 │
   ├─► 存在位 P = 1 (命中) ──► 更新访问位 A / 修改位 M,加载至 TLB ──┤
   │                                                                 │
   └─► 存在位 P = 0 (缺失)                                           │
         │                                                           │
         ▼                                                           │
     [ 触发缺页异常(中断向量号) ]                                  │
         │                                                           │
         ▼                                                           │
     [ 操作系统执行缺页中断服务程序 ]                                │
         │                                                           │
         ├─► 检查驻留集是否有空闲页框                                │
         │      ├─► 有空闲页框:直接分配                             │
         │      └─► 无空闲页框:执行页面置换算法 (FIFO/LRU/Clock)    │
         │             │                                             │
         │             └─► 选定淘汰页,检查修改位 M                  │
         │                    ├─► M = 1:启动磁盘写回 (Write-Back)   │
         │                    └─► M = 0:直接释放页框                │
         │                                                           │
         ├─► 从磁盘读取目标页面填入页框                              │
         ├─► 修改页表项:PFN = 目标页框, P = 1, A = 1, M = 0         │
         └─► 恢复上下文,重新执行触发缺页的访存指令                  │
                                                                     │
                                                                     ▼
物理地址 (PA) ◄──────────────────────────────────────────────────────┘
   │
   ▼
[ 访问 Cache 与物理主存 ]

2. 页面置换算法大题规范作答范式

在应对复杂的页面置换计算大题时,推荐采用“三行追踪法”或“矩阵表格法”书写步骤: 1. 明确初始条件:写明初始分配的物理页框数、初始驻留页面(若为空,前 \(k\) 次访问必须计入缺页)。 2. 标明置换准则: - FIFO:严格按照入队时间戳淘汰最早进入者。 - LRU:每次命中或调入,均更新当前页面的最近使用时间(或调整至栈顶);缺页时淘汰距离当前最远者。 - Clock / 改进型 Clock:清晰写出每轮扫描过程中指针指引的页面、标志位的判断与重置过程。 3. 统计结算表:列出总访存次数 \(N\)$ \text{、缺页次数} $\(F\)$ \text{、置换次数} $\(R\)$ \text{(注意:若分配有空闲块,缺页时直接载入,只算缺页不算置换;只有物理块满后发生的缺页才产生置换),最后代入公式计算缺页率} $\(P = F/N\)。

3. 操作系统虚存置换与组成原理 Cache 替换的横向对比

比较维度 操作系统:页面置换 计算机组成原理:Cache 替换
主要发生层次 主存 - 外存(磁盘/SSD)之间 CPU - Cache - 主存之间
管理主体 操作系统内核软件与硬件协同(MMU) 纯硬件控制器(Cache Controller)完成
数据交换块大小 页面(通常为 \(4\text{ KB} \sim 2\text{ MB}\)$ \text{) Cache 行 / 块(通常为} $\(32\text{ B} \sim 64\text{ B}\))
时间惩罚尺度 极高(毫秒级,涉及机械/固态存储 I/O) 极低(纳秒级,数十个 CPU 时钟周期)
算法复杂度承受度 能够容忍复杂的软件算法(如改进型 Clock) 只能采用极简单的纯硬件算法(如硬件 LRU、随机)
写策略 全写回法(Write-Back),脏位为 1 才写回 写回法(Write-Back)或全写法(Write-Through)

五、 考点速记清单

1. 核心要点速记

  • OPT 算法:未来最久不访问;不可实现;理论基准。
  • FIFO 算法:最早调入最早淘汰;队列实现;唯一存在 Belady 异常的高频考点算法。
  • LRU 算法:过去最久未访问;栈或寄存器实现;堆栈型算法,无 Belady 异常。
  • Clock 算法:循环链表,访问位 \(A\)$ \text{;命中置} $\(1\)$ \text{;置换时逢} $\(1\)$ \text{置} $\(0\)$ \text{、遇} $\(0\) 淘汰。
  • 改进型 Clock 算法:\((A, M)\)$ \text{四轮扫描;优先淘汰} $\((0, 0)\)$ \text{,次淘汰} $\((0, 1)\);扫过访问位全清零;平衡算法命中率与磁盘写回开销。
  • 工作集与抖动:工作集是当前活跃页面的集合;驻留集小于工作集会导致频繁缺页进而产生抖动。
  • 页缓冲系统(PBA):空闲链表与修改链表;减少磁盘 I/O 次数并提升响应时间;不改变缺页率。

2. 计算公式汇总

  • 缺页率: $$ \text{P = \frac{\text{缺页次数 } F}{\text{总访存次数 } N}} $$
  • 两级访存有效访问时间(EAT): $\(EAT = (1 - P) \times t_{mem} + P \times (t_{fault} + t_{mem})\)$
  • 带快表的 EAT: $\(EAT = t_{tlb} + t_{mem} + (1 - \alpha)t_{mem} + (1 - \alpha) P \cdot t_{fault}\)$

3. 极高频易错陷阱

  1. 初始调入是否计入缺页:
  2. 若题目说明“初始内存为空”,则调入前 \(k\) 个页面必须计入缺页(冷启动冷不命中)。
  3. 若题目说明“页面 \(X, Y, Z\) 已调入内存”(如 2025 年第 26 题),则初始预装载的页面绝不能计入缺页次数。
  4. 缺页次数与置换次数的差异:
  5. 缺页次数 = 初始调入次数 + 置换调入次数。
  6. 置换次数 = 物理块已满时发生缺页且必须淘汰旧页的次数。两者在初始装载阶段数值不同!
  7. 改进型 Clock 指针移动时机:
  8. 每一轮扫描结束若命中目标,指针必须停留在被置换页面的下一个位置,下一次置换从该位置开始继续扫描。
  9. 第二轮扫描寻找 \((0, 1)\)$ \text{时,沿途必须将经过的页面的访问位} $\(A\) 强制清零!

4. 秒杀解题口诀

页面置换有玄机,四种算法分清奇;
OPT 往后看未来,LRU 向前查过去;
FIFO 易染 Belady,分配块增页反急;
时钟算法转圈指,先零淘汰一清底;
若加修改四类齐,零零优先零一次;
页缓队列保速度,缺页频率不移移!