是什么
-
定义:请求分页系统中,当进程访问的逻辑页面不在物理内存且驻留集已满时,通过页面置换算法(FIFO / Clock / LRU)选出淘汰页换出到外存;结合快表(TLB)与缺页中断重执机制,计算完成一次逻辑地址访问的端到端耗时。
-
大白话:书架(内存驻留集)位置满了,想看新书(缺页)就得按某种规矩把一本旧书丢回仓库;查书时先看手边备忘录(TLB),没有再去翻目录大表(页表),如果连书都没有就得跑趟仓库,回来后再把书翻开(重新执行指令读数据)。
核心内容
1. 三大经典页面置换算法机制对比
| 置换算法 | 淘汰依据 / 决策逻辑 | 数据结构与维护开销 | 核心特性 / 考点 |
|---|---|---|---|
| FIFO(先进先出) | 淘汰装入内存时间最早的页面 | 队列记录进入顺序;开销极低 | 会产生 Belady 异常(分配页框变多,缺页次数反而增加) |
| LRU(最近最少使用) | 淘汰距当前时刻最久未被访问的页面 | 栈或寄存器记录访问历史;硬件开销大 | 性能接近最优(OPT),严格遵循局部性原理,无 Belady 异常 |
| Clock(时钟/二次机会) | 顺时针循环扫描,访问位(Use bit)为 0 直接淘汰,为 1 则清 0 免死并后移 | 循环链表 + 扫描指针;软硬件折中最佳方案 | 本质是兼顾 FIFO 简单性与 LRU 局部性的二次机会策略 |
2. Clock 算法转动淘汰执行流水线
设时钟指针当前指向某物理页框:
-
检查指针当前所指页框的访问位 :
-
若 :立即选中该页框作为淘汰目标,将新页装入该页框,指针顺时针下移一位,置换结束。
-
若 :获得免死机会,==将访问位清 0()==,指针顺时针下移一位,继续检查下一个页框。
-
-
第二轮兜底:若第一轮所有页框的 原本均为 1,则一圈下来全部被清 0;指针转回起点后,起点页框的 已为 0,必定在第二轮首个被淘汰。
3. 请求分页访问耗时推导流水线(无死角分解)
无论题目如何变化,一次完整的虚拟地址访存耗时必然属于以下三种情形之一:
情形 1:TLB 命中(极速路径)
-
触发条件:虚页号在 TLB 中存在。
-
流水线:查 TLB 直接拿物理地址访存读写数据。
-
计算公式:
-
:访问一次快表(TLB)耗时(如 )。
-
:访问一次主存(Memory)耗时(如 )。
-
情形 2:TLB 未命中,页表命中(普通路径)
-
触发条件:虚页号不在 TLB 中,但在主存页表中有效位为 1。
-
流水线:查 TLB 失败 查主存页表获取页框号并更新 TLB 访存读写目标数据。
-
计算公式:
-
第一个 为查页表耗时;第二个 为真正访存读取数据耗时。
-
情形 3:TLB 未命中,发生缺页中断(慢速异常路径)
-
触发条件:虚页号在页表中有效位为 0。
-
流水线(五步闭环):
-
查 TLB 未命中(耗时 );
-
查主存页表,有效位为 0 触发缺页异常(耗时 );
-
执行缺页中断处理:调页、置换、更新页表与 TLB(耗时 );
-
重新执行产生缺页的访存指令,查 TLB 必然命中(耗时 );
-
访存读取目标数据(耗时 )。
-
-
计算公式:
-
:操作系统缺页中断处理平均时间(通常达 )。
-
物理地址合成的双轨速算法:直接拼接法 vs 二进制对齐法
1. 底层原理:为什么能“直接拼接”?
-
地址结构本质:在分页存储管理中,无论是逻辑地址还是物理地址,其==页内偏移量 的二进制位数和具体数值在转换前后绝对不变==。
-
物理地址公式的位运算本质:
-
:物理页框号。
-
:页内偏移量占用的二进制位数(由页面大小 决定)。
-
:页内偏移量(占低 位)。
-
-
乘 的物理本质就是“左移 位”:把 放到高位,低 位全部腾出来补 0,再与低 位的 相加,本质就是高低位直接拼在一起。
2. 分支一:直接拼装法(当偏移量位数 为 4 的整数倍时)
-
判定条件:
-
十六进制下,1 个 Hex 字符严格等于 4 位二进制(bit)。
-
若页内偏移量位数 满足 (即 是 4 的整数倍,如 位对应页面大小 4KB),则低 位二进制恰好完整对应十六进制的低 位字符。
-
-
计算规则:
-
无需任何进制转换与乘除运算,直接将 的十六进制写在前面,把 的十六进制写在后面:
-
-
经典真题实例(以 2009 年真题为例):
-
页面大小 位,恰好占用 3 个 Hex 位()。
-
逻辑地址为
1565H剥离低 3 位得到 。 -
查询得到目标物理页框号 。
-
直接拼接:
-
3. 分支二:二进制对齐合成法(当偏移量位数 不是 4 的整数倍时)
-
判定条件:
-
若页内偏移量位数 满足 (如 位对应页面大小 1KB, 位对应 512B 等)。
-
此时偏移量 在十六进制中不是整数字符位(如 10 位二进制对应 2.5 个 Hex 位),严禁直接用十六进制字符硬拼,否则会发生位错位。
-
-
万能三步计算流程:
-
转二进制:将 转换为二进制,将偏移量 转换为补齐的 位二进制。
-
拼接对齐:高位写 二进制,低位写 二进制,直接并置形成完整的二进制物理地址。
-
4位一组转回 Hex:从最低位开始,每 4 位二进制划分为一组,转换为十六进制输出。
-
-
经典真题实例(以 2010 年真题为例):
-
页面大小 位(不是 4 的倍数)。
-
逻辑地址为
17CAH,转二进制为0001 0111 1100 1010,截取低 10 位得到偏移量: -
情形 A(FIFO 换入 7 号页框,):
-
(补齐为 6 位即
000111) -
拼接二进制(高 6 位 + 低 10 位 ):
Plaintext
PFN(7): 0 0 0 1 1 1 d(3CAH): 1 1 1 1 0 0 1 0 1 0 ----------------------------------------- 合并后: 0 0 0 1 | 1 1 1 1 | 1 1 0 0 | 1 0 1 0 Hex对照: 1 | F | C | A -
最终物理地址为:
1FCAH。
-
-
情形 B(Clock 换入 2 号页框,):
-
(补齐为 6 位即
000010) -
拼接二进制(高 6 位 + 低 10 位 ):
Plaintext
PFN(2): 0 0 0 0 1 0 d(3CAH): 1 1 1 1 0 0 1 0 1 0 ----------------------------------------- 合并后: 0 0 0 0 | 1 0 1 1 | 1 1 0 0 | 1 0 1 0 Hex对照: 0 | B | C | A -
最终物理地址为:
0BCAH。
-
-
4. 易错对照速查口诀
“4KB(12位)直接抄字符,1KB(10位)老实拆二进制。”
遇 1KB 页面切忌直接把页框号 7 和 3CA 拼成“73CAH”,因为 1KB 跨度是
400H(不是1000H),,加上3CAH必须是1FCAH。
例题
例题 1:置换算法具体轨迹对比(2010 统考真题)
-
题目:
逻辑与物理空间均为 64KB,按字节编址。页大小 1KB,分配 4 个页框。当前驻留集状态:
0号页(7号页框,时刻130,访问位1);1号页(4号页框,时刻230,访问位1);2号页(2号页框,时刻200,访问位1);3号页(9号页框,时刻160,访问位1)。
时刻 260 访问逻辑地址
17CAH:-
求该逻辑地址对应的页号。
-
分别用 FIFO 和 Clock(当前指针指向 2 号页框,顺时针方向:2号 4号 7号 9号)计算对应的物理地址。
-
-
分析:
-
页大小 1KB()。
17CAH转二进制低 10 位偏移为3CAH,高 6 位页号为 。访问 5 号页发生缺页。 -
FIFO:0号页装入时刻最早(130),淘汰 0 号页,将其占用的 7 号页框分配给 5 号页。物理地址 。
-
Clock:当前指针指向 2 号页框。第一轮顺时针扫过 2、4、7、9 号页框,各页访问位均从 1 置 0;指针再次指向 2 号页框时访问位为 0,选中淘汰 2 号页,5 号页装入 2 号页框。物理地址 。
-
-
答案:
-
逻辑地址
17CAH对应的页号为 5。 -
FIFO 算法下的物理地址为
1FCAH;Clock 算法下的物理地址为0BCAH。
-
例题 2:缺页重执与访存耗时流水线(2009 统考真题)
-
题目:
页面大小 4KB,内存访问时间 100ns,快表(TLB)访问时间 10ns,缺页中断处理时间 (含更新 TLB 和页表时间)。驻留集大小为 2,采用 LRU 置换算法。初始 TLB 为空,主存中驻留:0号页(
101H,有效位1)、2号页(254H,有效位1)。逻辑地址访问序列:2362H,1565H,25A5H。-
依次访问三个虚拟地址各需多少时间?
-
虚拟地址
1565H对应的物理地址是多少?说明理由。
-
-
分析:
-
页大小 4KB,低 3 位 Hex 为偏移量。
-
访问
2362H(2号页):查 TLB 缺失(10ns) 查页表命中(100ns) 访存取数(100ns)。耗时 。2号页入 TLB。 -
访问
1565H(1号页):查 TLB 缺失(10ns) 查页表缺页(100ns) 调页中断处理(,LRU 淘汰 0 号页,1 号页装入101H页框,更新 TLB) 重新执行指令查 TLB 命中(10ns) 访存取数(100ns)。耗时 。 -
访问
25A5H(2号页):查 TLB 命中(10ns) 访存取数(100ns)。耗时 。
-
-
答案:
-
访问耗时依次为:
2362H需 210 ns;1565H需 ;25A5H需 110 ns。 -
1565H对应的物理地址为101565H。理由:驻留集满且访问 1 号页缺页,按 LRU 策略淘汰最久未访问的 0 号页,腾出101H页框分配给 1 号页,拼接页内偏移565H得到101565H。
-
⚠️ 易错点
Warning
缺页耗时漏算“指令重执”阶段:
极易算成 。必须牢记:操作系统中断服务程序只负责把数据搬到内存并建立页表映射,==返回后硬件 CPU 必须重走一遍 TLB 命中与访存读数(额外叠加 )==。
混淆“被淘汰的页号”与“所在页框号”:
算物理地址时必须用物理页框号(Page Frame)乘页面大小,严禁直接拿逻辑页号相乘。
Clock 算法扫描顺序误区:
Clock 算法严格沿表盘顺时针指针顺序轮转,不要擅自按页号(0, 1, 2, 3)的数字升序去检查。
程序访问不需要“按顺序翻页”:
- 内存置换只针对 CPU 当前指令正在请求的目标页(如直接从 3 跳到 5),无需先将中间未请求的页调入。