408 高频考点精讲:页面置换算法¶
模块归属:操作系统 · 内存管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
1. 考查频次与题号清单¶
- 近十年考查频次:4 次(2016 年第 26 题、2021 年第 28 题、2022 年第 30 题、2025 年第 26 题)
- 历年总考查频次:5 次(含 2010 年第 27 题)
- 出题形式:单项选择题为绝对核心形式;同时作为综合解答题中虚拟存储系统访存全流程计算的关键子模块。
2. 命题特点分析¶
- 算法执行细节深度追踪:命题不再局限于机械记忆概念,而是着重考察状态转换细节。例如 2016 年第 26 题考查改进型 Clock 算法的状态分类与淘汰次序,2021 年第 28 题要求精确模拟指针扫描过程中的标志位重置,2025 年第 26 题深度考查 LRU 队列状态转移与缺页统计。
- 虚拟存储体系全链路融合:页面置换算法往往与虚实地址变换、页表结构、TLB 命中判定紧密结合(如 2021 年第 28 题)。考生必须建立从虚拟地址拆分、缺页中断响应、页框淘汰到物理地址合成的完整认知闭环。
- 系统宏观性能机理辨析:深入考查抖动(颠簸)现象的成因、工作集模型、驻留集动态调节以及页缓冲队列(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) 常见页面置换算法模型¶
- 最佳置换算法(OPT, Optimal Replacement):
- 决策原则:淘汰未来最长时间内不再被访问的页面。
-
特性:具有最低的缺页率。因系统无法预知未来的页面访问序列,该算法在实际工程中无法实现,常作为衡量其他置换算法性能的理论上限(Benchmark)。
-
先进先出置换算法(FIFO, First-In First-Out):
- 决策原则:淘汰最先进入内存的页面,即驻留时间最长的页面。
- 实现数据结构:维护一个驻留页面的先进先出队列。
-
异常缺陷:存在 Belady 异常(Belady's Anomaly),即当为进程分配的物理页框数增加时,缺页次数反而增加。
-
最近最久未使用置换算法(LRU, Least Recently Used):
- 决策原则:淘汰过去最长时间未被访问的页面。利用时间局部性原理,以过去的访问历史推断未来的访问行为。
- 实现机制:
- 活动页面栈:每当访问某页时,将其从栈中抽出并压入栈顶;发生缺页时淘汰栈底页面。
- 移位寄存器/逻辑时钟:为每个页表项配置计数器或移位寄存器,周期性更新访问记录。
-
特性:理论性能接近 OPT,属于堆栈型算法,严格杜绝 Belady 异常;但硬件实现开销较大。
-
最不经常使用置换算法(LFU, Least Frequently Used):
- 决策原则:淘汰过去一段时间内访问频次最少的页面。
-
缺陷:早期频繁访问但后期不再使用的页面会长期滞留在内存中(计数过大无法迅速衰减)。
-
简单时钟置换算法(Clock / NRU / 二次机会算法):
- 结构:将内存中的驻留页面链接成一个循环队列,设置一个循环指针。每个页面设置一位访问位 \(A\)。
-
流程:
- 当某页被访问时,硬件自动将其访问位置 \(A = 1\)。
- 发生置换时,指针从当前位置开始扫描:
- 若当前页 \(A = 0\),选择该页换出;
- 若当前页 \(A = 1\)$ \text{,将其清零(} $\(A \leftarrow 0\)),指针移动到下一个页面继续检查。
- 最多经过两轮扫描即可找到可淘汰页面。
-
改进型时钟置换算法(Enhanced Clock):
- 设计动机:置换一个被修改过的页面需要写回外存(消耗一次磁盘 I/O),而置换未修改的页面只需直接覆盖(无需写回外存)。在考虑访问历史的同时兼顾 I/O 开销。
- 页面四元分类 \((A, M)\):
- 第 1 类 \((0, 0)\):最近未被访问,且未被修改。置换首选,代价最低。
- 第 2 类 \((0, 1)\):最近未被访问,但已被修改。置换次选,需写回磁盘。
- 第 3 类 \((1, 0)\):最近已被访问,但未被修改。存在局部性,保留优先级高。
- 第 4 类 \((1, 1)\):最近已被访问,且已被修改。最不倾向淘汰。
- 四轮扫描淘汰算法流程:
- 第 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)
【解析】¶
- 知识定位:考查改进型 Clock 页面置换算法的类别划分原则及其优先级判定逻辑。
- 核心推导:
- 改进型 Clock 算法的核心思想是:优先淘汰最近未被访问的页面(利用时间局部性原理,保证置换命中率);在访问位相同的情况下,优先淘汰未被修改过的页面(减少外存磁盘 I/O 写回开销)。
- 根据此原则,页面分为四类优先级:
- 第 1 优先级:\((A=0, M=0)\),最近未访问且未修改,淘汰时代价最小且不影响局部性,最先淘汰。
- 第 2 优先级:\((A=0, M=1)\),最近未访问但被修改,虽然需写回外存,但因其不具有活跃局部性,次优先淘汰。
- 第 3 优先级:\((A=1, M=0)\),最近被访问且未修改,具有时间局部性,暂不淘汰。
- 第 4 优先级:\((A=1, M=1)\),最近被访问且被修改,具有时间局部性且修改代价大,最不应被淘汰。
- 算法的淘汰遍历次序严格为:\((0, 0) \to (0, 1) \to (1, 0) \to (1, 1)\)。
- 选项辨析:
- A 选项:顺序为 \((0, 0), (0, 1), (1, 0), (1, 1)\),完全符合算法设计规范,正确。
- B 选项:错误地将 \((1, 0)\)$ \text{排在} $\((0, 1)\)$ \text{之前。若先淘汰} $\((1, 0)\),则违背了“未访问页优先于已访问页”的局部性核心原则。
- 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
【解析】¶
- 知识定位:考查虚拟地址分解、页表项结构判定、改进型 Clock 置换过程模拟以及物理地址合成。
- 地址分解:
- 页面大小为 \(4\text{ KB} = 2^{12}\text{ B}\),按字节编址,因此虚拟地址低 12 位(3 位十六进制数)为页内偏移量,高位为虚拟页号。
- 虚拟地址为
02A01H:- 页内偏移量为低 12 位:
A01H。 - 虚拟页号为高位:
02H(即 2 号页)。
- 页内偏移量为低 12 位:
- 查表判断与缺页处理:
- 查看 2 号页对应的页表项:存在位为 \(0\),说明 2 号页不在主存中,触发缺页中断。
- 进程 P 分配了 2 个固定的页框,此时驻留主存的页面为 3 号页(占用页框
60H)与 4 号页(占用页框80H)。驻留集已满,必须执行页面置换。 - 改进型 Clock 置换模拟:
- 内存中存在的两页初始状态为:
- 3 号页:\((A=1, M=0)\)
- 4 号页:\((A=1, M=1)\)
- 指针依次遍历当前驻留页面(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 号页。
- 物理地址合成:
- 淘汰 3 号页,将 3 号页占用的物理页框
60H分配给 2 号页。 - 2 号页装入页框
60H,物理地址由页框号拼接页内偏移量构成: $$ \text{物理地址} = \text{页框号 (60H)} \parallel \text{页内偏移 (A01H)} = 60\text{A01H} $$ - 选项辨析:
- A 选项:
00A01H,无此页框号,错误。 - B 选项:
20A01H,直接将页表项历史残留的页框号 20H 当作目标,忽视了存在位为 0,错误。 - C 选项:
60A01H,正确淘汰 3 号页并取得其页框号,正确。 - D 选项:
80A01H,错误淘汰 4 号页,计算错误。
正确答案:C
【真题 3】2022 年 408 第 30 题 · 影响系统缺页率的关键因素辨析¶
题目:
下列选项中,不会影响系统缺页率的是( )。
A. 页面置换算法
B. 工作集的大小
C. 进程的数量
D. 页缓冲队列的长度
【解析】¶
- 知识定位:考查请求分页系统中缺页率的影响因素及页缓冲机制(PBA)的本质作用。
- 影响因素逐项深度剖析:
- A 选项(页面置换算法):页面置换算法的核心目标就是减少未来的缺页次数。OPT、LRU、FIFO 的缺页率具有显著差异,置换算法直接影响缺页率,排除。
- B 选项(工作集的大小):工作集反映了进程在特定时间窗口内活跃引用的页面集合大小。若分配给进程的页框数小于其工作集大小,缺页率将急剧上升;反之,页框数覆盖工作集时缺页率大幅下降。因此工作集大小直接决定了系统缺页率的高低,排除。
- C 选项(进程的数量):系统物理内存总量固定,并发进程数量越多(多道程序度过高),每个进程平均分到的物理块数越少。当物理块数被压缩到临界值以下时,会导致各进程频繁缺页甚至引发抖动。因此并发进程数量显著影响缺页率,排除。
- 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
【解析】¶
- 知识定位:考查固定分配局部置换策略下,LRU 页面置换算法的状态追踪与缺页次数精确计算。
- 审题关键点:
- 页框总数为 3。
- 题干明确指出“其中 0, 1, 2 已调入内存”。这意味着初始状态下 3 个页框已经被页面 0, 1, 2 占满,初始调入不计入后续访问序列的缺页次数。
- 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 |
- 统计结果: 在访问序列执行期间,第 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. 极高频易错陷阱¶
- 初始调入是否计入缺页:
- 若题目说明“初始内存为空”,则调入前 \(k\) 个页面必须计入缺页(冷启动冷不命中)。
- 若题目说明“页面 \(X, Y, Z\) 已调入内存”(如 2025 年第 26 题),则初始预装载的页面绝不能计入缺页次数。
- 缺页次数与置换次数的差异:
- 缺页次数 = 初始调入次数 + 置换调入次数。
- 置换次数 = 物理块已满时发生缺页且必须淘汰旧页的次数。两者在初始装载阶段数值不同!
- 改进型 Clock 指针移动时机:
- 每一轮扫描结束若命中目标,指针必须停留在被置换页面的下一个位置,下一次置换从该位置开始继续扫描。
- 第二轮扫描寻找 \((0, 1)\)$ \text{时,沿途必须将经过的页面的访问位} $\(A\) 强制清零!
4. 秒杀解题口诀¶
页面置换有玄机,四种算法分清奇;
OPT 往后看未来,LRU 向前查过去;
FIFO 易染 Belady,分配块增页反急;
时钟算法转圈指,先零淘汰一清底;
若加修改四类齐,零零优先零一次;
页缓队列保速度,缺页频率不移移!