1. 先把"页式内存管理"这件事讲明白
页式内存管理这门功课,我第一次接触是在操作系统课上的一次随堂练习里,题目只有三行字,给的是一段逻辑地址和一个页表,让算物理地址。当时我觉得这有什么难的,不就是整数除法加取余。后来真正写模拟器、翻内核里的页表遍历代码、调真实程序的性能,才发现那三行字背后藏着整个虚拟内存体系的骨架。这篇东西围绕"课堂练习4.2:页式内存管理"展开,把这类练习里所有会被考到、也最容易做错的地方拆开讲一遍:地址怎么翻译、页表项该存什么、多级页表为什么必须有、缺页之后系统做了什么、置换算法怎么选。
如果你正在赶操作系统的实验报告,或者面试前想把虚拟内存这块重新捋顺,下面这些内容可以当成一份能直接抄的解题笔记,外加一份踩坑手册。我不会一上来就甩定义,而是按"为什么需要它—它怎么工作—动手算一遍—哪里会错"这个顺序往下走,每一步都尽量给出可复现的数字,方便你对着自己的题目改参数。
1.1 课堂练习4.2 到底在练什么
拿到这道题的标题,很多人第一反应是"这题考地址翻译"。只对了一半。页式内存管理的随堂练习,本质上在考四件事,而且这四件事的难度是递增的。
第一件是地址拆解,也就是把一个逻辑地址按页面大小切成"页号 + 页内偏移"。这一步只要知道页面大小的位宽就够,属于热身。
第二件是页表查询,用页号去页表里查表项,拿到物理页框号,再拼回物理地址。单级页表这一步很简单,换成二级、三级、四级之后,很多人的错误率会突然飙升,因为中间要多做几次"取地址—读内存—取下一级基址"的操作。
第三件是空间开销估算,题目会问你页表本身占多大内存、二级页表比单级省了多少、一个进程最少需要多少页表页。这一步考的是你能不能把"页表项位数"和"页面大小"两个约束联立起来。
第四件是性能估算,也就是有效访问时间(EAT)和 TLB 命中率。这一步最容易失分,因为公式里每一项的含义要是没吃透,算出来的结果会比一次内存访问还快,明显不合理。
把练习当"四道小题"来做,比把它当"一道大题"来做要稳得多。
1.2 分页机制要解决的三个老大难
为什么不用连续分配,非要搞这么复杂的分页?这个问题想清楚了,后面所有细节都能自己推出来。
第一个问题是碎片。连续分配方案下,程序必须一整块放进内存。程序大小各不相同,内存里就会剩下一堆零散的小空洞,每个都装不下新来的进程,这就是外部碎片。分页的做法是把内存切成固定大小的页框,程序也切成同样大小的页,任何一页都能放进任何页框,外部碎片直接从根上消失。代价是程序最后一页通常填不满,会浪费一点内部碎片,但最多浪费一页,可控。
第二个问题是隔离与保护。每个进程有自己的页表,页号映射到哪块物理内存由操作系统说了算。进程 A 拿不到进程 B 的页表,也就无法构造出指向 B 的物理地址。这种保护不需要在每个地址上都做检查,只在地址翻译这一层做一次,效率很高。
第三个问题是"程序比内存大"。分页天然支持按需装入:页表项里的有效位标 0,表示这一页还没在内存里。程序真正访问到的时候触发缺页,操作系统再去把这一页从磁盘读进来。于是 32 位机器上跑一个比物理内存还大的程序变得理所当然,这就是虚拟内存的基础。
三个问题对应三个设计特征:固定大小的页解决了碎片,独立页表解决了保护,有效位加缺页机制解决容量。你在练习里算的每一个字段,其实都是为这三件事中的某一件服务的。
1.3 一页纸概念地图:页、页框、页表、MMU
先把术语钉死,因为练习里失分的孩子十有八九是概念混了。
| 术语 | 含义 | 常见大小 |
|---|---|---|
| 页(Page) | 逻辑地址空间的固定长度块 | 4KB 为主流 |
| 页框(Frame) | 物理内存的固定长度块,与页等长 | 4KB |
| 页号(VPN) | 逻辑地址的高位部分 | 20 位(32 位地址 + 4KB 页) |
| 页内偏移(Offset) | 逻辑地址的低位部分 | 12 位 |
| 页框号(PFN) | 物理地址的高位部分 | 18 位(1GB 物理内存) |
| 页表(Page Table) | 页号到页框号的映射数组 | 每项通常 4B 或 8B |
| 页表项(PTE) | 页表里的一行 | 含页框号 + 若干标志位 |
| MMU | 负责地址翻译的硬件单元 | 内含 TLB 缓存 |
这里有个特别容易搞混的点:页和页框长度相同,但编号体系完全独立。页号是逻辑空间的编号,从 0 开始,跟物理内存多大没关系;页框号是物理空间的编号,最大编号由物理内存大小决定。你在练习里看到的"页号 3 映射到页框 0x2B",就是两个独立编号体系之间的一次对应关系。
提示:偏移量在翻译前后是原样不变的。这是页式管理最优雅的地方——页内偏移既不参与查表,也不参与运算,逻辑地址的低 12 位和物理地址的低 12 位完全相同。抓住这一点,很多计算可以直接跳步。
2. 地址翻译的完整链路:从逻辑地址到物理地址
上一节把概念铺开了,这一节进入正题:一次内存访问,硬件到底做了哪些动作。我按"拆地址—查页表—拼地址"的顺序走,中间顺带把每个字段存在的意义讲清楚,这样你做题时就不是在套公式,而是在还原一个真实过程。
2.1 逻辑地址怎么拆成页号和偏移
拆分规则只有一条:偏移部分的位宽等于页面大小的以 2 为底的对数。
页面大小 4KB = 2 的 12 次方,所以偏移占 12 位。逻辑地址 32 位,减掉 12 位,页号就是 20 位。这一步看着简单,但练习里有个常见陷阱:题目给的页面大小是 1KB、2KB、8KB,甚至 4MB,你必须能立刻算出偏移位数。
速算表列出来会更直观:
| 页面大小 | 偏移位数 | 32 位地址下的页号位数 | 页表项数量 |
|---|---|---|---|
| 1KB | 10 | 22 | 4M |
| 2KB | 11 | 21 | 2M |
| 4KB | 12 | 20 | 1M |
| 8KB | 13 | 19 | 512K |
| 2MB | 21 | 11 | 2K |
这张表解释了一件事:页面越大,页表越短,但内部碎片越多。4KB 是几十年试出来的折中点——页表不至于太夸张,最后一页的平均浪费也能接受。
拆分之后,逻辑地址的数学表达是:
逻辑地址 = 页号 × 页面大小 + 页内偏移 页号 = 逻辑地址 >> 偏移位数 偏移 = 逻辑地址 & (页面大小 - 1)用位运算而不是除法,是因为除法和取余在硬件上代价高,移位和按位与几乎不花时间。这一点在做 EAT 分析时很重要——地址拆解本身不产生额外内存访问。
2.2 页表项里到底该存哪些位
页表项不是只存一个页框号,它是一组标志位的打包。很多练习让你"设计页表项格式",其实就是让你把该有的位一位位列出来。
| 位段 | 位宽 | 作用 |
|---|---|---|
| 页框号 | 18(视物理内存) | 翻译目标 |
| 有效位 | 1 | 0 表示该页不在内存,访问触发缺页 |
| 修改位(脏位) | 1 | 写操作时置 1,换出时决定是否写回磁盘 |
| 访问位 | 1 | 被读过就置 1,供置换算法参考 |
| 保护位 | 3 | 读/写/执行权限 |
| 用户/内核位 | 1 | 权限级别,防止用户态访问内核页 |
算一下总位宽:18 + 1 + 1 + 1 + 3 + 1 = 25 位。25 位不是一个好用的对齐宽度,向上取到 32 位(4 字节),正好是一个内存字。这就回答了一个经典问题——为什么页表项通常设计成 4 字节而不是紧凑的 25 位。取整到 4 字节,页表项下标可以直接用移位算偏移,硬件实现简单,代价是每项浪费 7 个位。
注意:修改位的维护是有成本的。早期硬件每条写指令都要去写一次页表项,后来改成了"先记在 TLB 里,换出时才同步回页表",这也是练习里常考的细节。
2.3 多级页表:为什么非做不可
单级页表的问题在哪?还是拿 32 位地址、4KB 页、4B 页表项来算。
页号 20 位,说明页表有 2 的 20 次方 = 1048576 项。每项 4B,页表总大小 = 1048576 × 4B = 4MB。每个进程光页表就要占 4MB,而且要连续。一百个进程就是 400MB,这还没算上程序本身。这个开销是灾难性的。
更荒谬的是,一个正常程序用到的地址空间往往是稀疏的——代码段在低地址,堆和栈在两万米外,中间大片区域根本没人访问。为这些空区域维护页表项,纯属浪费。
解决方案是把页表本身也分页,再拿一张"页目录"去索引它。这就是二级页表:
- 页号 20 位拆成高 10 位和低 10 位
- 高 10 位做页目录索引,页目录有 1024 项
- 低 10 位做二级页表索引,每个二级页表也有 1024 项
一页 4KB 能装多少个 4B 页表项?4096 / 4 = 1024 个,正好。也就是说页目录本身正好一页,每个二级页表也正好一页,不需要额外的碎片处理,设计得非常精巧。
覆盖范围验算一下:页目录 1024 项,每项指向一个二级页表;每个二级页表 1024 项;每项映射一页 4KB。总覆盖 = 1024 × 1024 × 4KB = 4GB,正好覆盖完整的 32 位地址空间,一项不多一项不少。
那省了多少?进程只要用到 4MB 范围内的一小块,操作系统就只分配一个页目录页(4KB)加一个二级页表页(4KB),合计 8KB,相比单级的 4MB,省了 99.8%。这个数字在很多教材里出现过,但你要能自己推出来,才算真懂。
提示:64 位机器上有效地址通常只有 48 位,按 4KB 页算偏移 12 位,剩下 36 位拆成 4 段各 9 位,就是四级页表。9 位对应 512 项,每项 8 字节,一页 4KB 还是正好装 512 项。这套"让每一级恰好占满一页"的思路是一致的。
3. 手把手把一道典型练习算到底
到这里原理铺完了,接下来按最典型的题目条件,把一道完整的练习从条件整理算到最后一步。你可以把自己的题号替换进来,流程完全一样。
3.1 题目条件与参数整理
假设条件是这一套(这是绝大多数教材和实验讲义采用的配置):
- 逻辑地址宽度:32 位
- 页面大小:4KB
- 页表项大小:4B
- 页表结构:二级
- 物理内存:1GB
- 当前进程页目录物理基址:0x00000000(简化假设,方便手算)
- 页目录第 0 项内容:指向页框号 0x100
- 该二级页表第 3 项内容:指向页框号 0x2B,有效位为 1
- TLB 命中率 0.9,TLB 访问耗时 1ns,一次内存访问 100ns
求解三个问题:逻辑地址 0x00003A5C 对应的物理地址;该进程最少占用多少页表内存;有效访问时间是多少。
第一步永远是先把位数算全,这是后面所有计算的地基:
- 偏移位数 = log2(4096) = 12 位
- 页号位数 = 32 - 12 = 20 位
- 页目录索引位数 = 10 位,二级索引位数 = 10 位
- 页框号位数 = log2(1GB / 4KB) = 30 - 12 = 18 位
这四个数字先写在草稿纸角上,后面每一次移位都对照它们检查。
3.2 单级页表下的地址翻译全流程
先用单级页表走一遍,把最核心的翻译逻辑固定下来。
逻辑地址 0x00003A5C 写成二进制:
0000 0000 0000 0000 0011 1010 0101 1100高 20 位 =0000 0000 0000 0000 0011,也就是十进制 3,所以页号 = 3。
低 12 位 =1010 0101 1100,也就是 0xA5C = 2652,所以偏移 = 2652。
去页表第 3 项查到页框号 0x2B(十进制 43),有效位为 1。拼物理地址:
物理地址 = 页框号 × 页面大小 + 偏移 = 0x2B × 0x1000 + 0xA5C = 0x2B000 + 0xA5C = 0x2BA5C验算一下合理性:物理内存 1GB = 0x40000000,0x2BA5C 远小于这个值,落在合法范围内,说明没算错位数。如果算出来的结果比物理内存还大,那必然是页框号位数或移位位数搞错了。
这一步三个动作,固化成条件反射:拆、查、拼。拆是移位加掩码,查是查表,拼是乘法加加法。
3.3 二级页表下的地址翻译对照
现在换成二级页表,看同样是 0x00003A5C,中间多了哪些步骤。
20 位页号 = 3,二进制是0000000000 0000000011(前 10 位全 0,后 10 位是 3)。
- 页目录索引 = 高 10 位 = 0
- 二级页表索引 = 低 10 位 = 3
翻译链路:
- 页目录物理基址 0x00000000,第 0 项偏移 = 0 × 4 = 0,读取地址 0x00000000,得到内容指向页框 0x100。
- 二级页表物理基址 = 0x100 × 0x1000 = 0x100000。
- 二级页表第 3 项偏移 = 3 × 4 = 12 = 0xC,读取地址 0x10000C,得到页框号 0x2B,有效位 1。
- 物理地址 = 0x2B × 0x1000 + 0xA5C = 0x2BA5C。
结果和单级完全一致,偏移量在整条链路里从头到尾没被碰过,这印证了前面说的那句话。
差别在哪里?单级查一次页表就够了,二级在 TLB 未命中时要查两次内存(先页目录,再二级页表),相当于多花一次内存访问。这就是多级页表用空间换时间的代价,也是为什么 TLB 在多级页表体系里变得不可或缺。
注意:页目录项和二级页表项里除了页框号,同样带有效位。如果页目录项的有效位是 0,说明整个 4MB 区域都没被使用,硬件直接触发缺页,根本不用去读二级页表。这个短路设计显著加快了稀疏访问的速度,是练习里常被忽略的加分点。
3.4 页表内存开销的估算过程
题目问"该进程最少占用多少页表内存",答案是 8KB,但你要能说清楚这 8KB 从哪来。
页目录必须存在,占 1 页 = 4KB。进程只要访问了任何一个页号,对应的那个二级页表就必须分配,占 1 页 = 4KB。合计 8KB。
对比单级页表的 4MB:
| 方案 | 最少页表内存 | 覆盖全部地址空间所需 |
|---|---|---|
| 单级 | 4MB(必须全量) | 4MB |
| 二级 | 8KB | 4MB + 4KB |
省下的比例是 1 - 8192 / 4194304 ≈ 99.8%。但这里有个容易被忽略的反面:如果一个进程真的用满了 4GB 地址空间,二级页表的总开销反而略大于单级,因为多了页目录的 4KB。多级页表不是无条件更省,它省的是"稀疏访问"这个场景。
如果练习问的是三级、四级怎么算,方法一样:每一级索引位数决定该级表的大小,一页能装多少项就装多少项,最后把最坏情况和最省情况都算一遍。
3.5 TLB命中率与有效访问时间计算
这是最容易算错的一题,因为公式里的每一项都在考察你对流程的理解。
先把两种情况的时间拆清楚。TLB 命中时:访问 TLB(1ns)+ 访问内存取数据(100ns)= 101ns,不需要查页表。TLB 未命中时:访问 TLB(1ns)+ 查页目录(100ns)+ 查二级页表(100ns)+ 访问内存取数据(100ns)= 301ns。
代入命中率 0.9:
EAT = 0.9 × 101 + 0.1 × 301 = 90.9 + 30.1 = 121ns对比一下几种配置,差距就很直观了:
| 页表结构 | TLB 命中耗时 | TLB 未命中耗时 | 命中率 0.9 时 EAT |
|---|---|---|---|
| 单级页表 | 101ns | 201ns | 111ns |
| 二级页表 | 101ns | 301ns | 121ns |
| 无 TLB 二级 | 不适用 | 301ns | 301ns |
无 TLB 时每次访问都要多两次内存访问,性能直接掉到三分之一。这就是为什么现代 CPU 的 TLB 动辄几百项,还分指令 TLB 和数据 TLB 两级。
提示:算 EAT 最常见的错误是"TLB 命中时还去算页表访问时间",或者"把 TLB 访问时间漏掉"。检查方法很简单——最终结果必须大于一次内存访问时间。如果算出来小于 100ns,说明逻辑错了。
4. 缺页、置换算法与练习里最容易错的点
前面都是稳态下的翻译,这一节讲非稳态:访问的页不在内存里怎么办,内存满了淘汰谁。这部分是练习的难点,也是面试的高频区。
4.1 一次缺页中断到底发生了什么
页表项有效位为 0,MMU 会抛出一个缺页异常,CPU 转入内核的缺页处理程序。整个流程分六步,每一步都值得记住,因为它们直接决定了练习里的"缺页次数"该怎么算。
- 硬件把触发缺页的逻辑地址保存到寄存器(比如 x86 的 CR2),并判断这次访问是否合法。访问了不属于自己的地址,直接杀进程,不进入后续步骤。
- 操作系统查找该页在磁盘上的位置,通常存在页表项的高位或单独的换出表里。
- 在物理内存里找一个空闲页框。有就直接用,没有就触发置换。
- 如果被选中的牺牲页修改位为 1,先把它的内容写回磁盘。
- 把目标页从磁盘读入页框,更新页表项:填入新页框号、有效位置 1、修改位清 0。
- 更新 TLB(要么直接写入,要么让相关表项失效),返回用户态,重新执行那条触发异常的指令。
第六步的"重新执行"是关键。缺页处理完成之后,指令是从头再跑一遍,而不是接着跑,因为第一次执行根本没产生任何副作用。这个细节解释了为什么页式管理对程序是完全透明的。
一次缺页涉及至少一次磁盘 I/O,耗时通常是几十微秒到几毫秒,比一次内存访问慢几个数量级。所以置换算法的目标只有一个:把缺页率压到最低。
4.2 FIFO、LRU、Clock 三种置换策略实测对比
练习里最常考三种算法,我用同一个引用串跑一遍,方便你对照。
引用串:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5,页框数 3。
FIFO(先进先出):淘汰最早进入内存的页,实现最简单,一个队列搞定。
| 访问 | 内存状态(旧→新) | 是否缺页 |
|---|---|---|
| 1 | 1 | 是 |
| 2 | 1, 2 | 是 |
| 3 | 1, 2, 3 | 是 |
| 4 | 4, 2, 3 | 是 |
| 1 | 4, 1, 3 | 是 |
| 2 | 4, 1, 2 | 是 |
| 5 | 5, 1, 2 | 是 |
| 1 | 5, 1, 2 | 否 |
| 2 | 5, 1, 2 | 否 |
| 3 | 5, 3, 2 | 是 |
| 4 | 5, 3, 4 | 是 |
| 5 | 5, 3, 4 | 否 |
缺页 9 次。
LRU(最近最少使用):淘汰最久没被访问的页,命中时要把它移到队尾。
按同样流程走下来,缺页 10 次。这个结果很奇怪——LRU 明明比 FIFO "更聪明",为什么反而多了一次?原因在于引用串的具体分布,参照性不是在所有片段上都成立。判断一个算法好坏不能只看单个引用串,要看长期统计规律。
Clock(时钟算法):LRU 的近似实现,用一个环形链表加访问位,指针扫过时把访问位为 1 的清 0 并跳过,遇到 0 就淘汰。开销比严格 LRU 小得多,现代内核普遍用它。
| 算法 | 实现开销 | 缺页率 | 是否会产生 Belady 异常 |
|---|---|---|---|
| FIFO | 极低 | 较高 | 会 |
| LRU | 高(需维护时序) | 低 | 不会 |
| Clock | 低 | 接近 LRU | 不会 |
| 最优(OPT) | 不可实现 | 理论最低 | 不会 |
提示:LRU 和 OPT 都是"栈算法",具备一个数学性质——页框数增加时,内存里的页面集合是原来的超集,因此缺页次数单调不增。FIFO 不满足这个性质,所以才有下面的怪现象。
4.3 Belady异常与"页框越多越慢"的怪现象
接着上面那个引用串,把页框数从 3 加到 4,FIFO 的缺页次数变成了10 次,比 3 个页框时的 9 次还多。页框变多了,缺页反而变多,这叫 Belady 异常。
原因不神秘。FIFO 淘汰的是"进来最早的",和"还有没有用"完全无关。页框数一变,整个淘汰序列错位,可能把马上要用的页提前踢出去。页框多提供了一个更容易错位的舞台,于是出现了反直觉的结果。
LRU 不会有这个问题,因为它维护的是严格的"最近使用顺序",页框增加时原有的页面集合必然被保留。这也是内核普遍选 Clock 而不是 FIFO 的原因之一。
练习里如果让你解释 Belady 异常,答题要点是三条:FIFO 的淘汰决策与访问局部性无关;页框数变化改变了淘汰序列;LRU 属于栈算法,天然免疫。三点写全,基本就是满分。
4.4 常见错误排查速查表
我把这些年带实验时见到的高频错误整理成一张表,你对着自己的答案逐条核。
| 现象 | 大概率根因 | 处理方式 |
|---|---|---|
| 算出的物理地址比物理内存还大 | 页框号位数判断错误,或忘记乘页面大小 | 重算页框号位数 = log2(内存/页大小) |
| 偏移量算错,或者偏移参与了查表 | 掩码用成了移位 | 偏移 = 地址 & (页大小 - 1) |
| 页目录索引和二级索引位置颠倒 | 没记住高位给上级 | 页目录取高 10 位,二级取低 10 位 |
| 单级页表大小算成 4KB | 漏乘页表项大小 | 页表项数 × 页表项字节数 |
| EAT 小于一次内存访问时间 | 漏加 TLB 时间,或命中时多算了页表访问 | 命中就只访问 TLB 加内存 |
| 命中 TLB 后还继续查页表 | 流程理解错 | TLB 命中直接出页框号 |
| 置换算法模拟结果对不上 | 队列更新顺序错 | FIFO 淘汰队首,LRU 命中时要移到队尾 |
| 缺页次数把首次装入算成命中 | 空页框不算命中 | 首次访问必然缺页 |
| 修改位不知道何时置 1 | 混淆读和写 | 只有写操作才置 1 |
| 页表项字段设计遗漏 | 忘了保护位/有效位 | 按"页框号 + 有效 + 修改 + 访问 + 保护 + 权限"列全 |
5. 把课堂知识搬到真实系统里
练习做完了不算完。页式管理是极少数"课本知识和工程实践几乎零距离"的主题,你在练习里算的每一位,在真实系统里都有对应物。这一节讲怎么把纸上的东西用起来。
5.1 大页、TLB与真实性能数字
先算一个很有冲击力的对比。TLB 通常几十到几百项,假设有 64 项,页面大小 4KB,那么 TLB 能覆盖的地址范围是 64 × 4KB = 256KB。程序的热点数据只要超过 256KB,TLB 就开始频繁未命中。
换成 2MB 的大页呢?64 × 2MB = 128MB。覆盖范围扩大了 512 倍,TLB 未命中的概率断崖式下降。
这就是数据库、虚拟机、大数据框架普遍启用大页的原因。代价也很明确:
| 页面大小 | TLB 覆盖范围(64 项) | 内部碎片上限 | 页表大小(32 位) |
|---|---|---|---|
| 4KB | 256KB | 4KB | 4MB 单级 |
| 2MB | 128MB | 2MB | 2K 项,8KB |
| 1GB | 64GB | 1GB | 4 项,几乎可忽略 |
大页的碎片代价很高,所以不能全局启用。实际系统是混合模式:默认 4KB,对内存密集的大块区域显式申请大页。你在练习里算过"页越大页表越短"这个结论,到这里就变成了真实的性能调优手段。
5.2 用五十行代码写一个页式管理模拟器
光看不动手,考完就忘。我用 Python 写一个最小可用的模拟器,包含地址翻译、缺页统计、FIFO 和 LRU 置换,你可以直接拿去验证前面所有手算结果。
PAGE_BITS = 12 PAGE_SIZE = 1 << PAGE_BITS OFFSET_MASK = PAGE_SIZE - 1 class PageFault(Exception): def __init__(self, vpn): super().__init__(f"page fault at vpn={vpn}") self.vpn = vpn class PTE: __slots__ = ("frame", "valid", "dirty", "accessed") def __init__(self, frame=-1, valid=False): self.frame = frame self.valid = valid self.dirty = False self.accessed = False def translate(vaddr, page_table): """把逻辑地址翻译成物理地址,缺页时抛出 PageFault。""" vpn = vaddr >> PAGE_BITS offset = vaddr & OFFSET_MASK if vpn >= len(page_table): raise ValueError(f"地址越界: vpn={vpn}") pte = page_table[vpn] if not pte.valid: raise PageFault(vpn) pte.accessed = True return (pte.frame << PAGE_BITS) | offset if __name__ == "__main__": # 构造一个 8 页的小页表,页号 3 映射到页框 0x2B pt = [PTE() for _ in range(8)] pt[3] = PTE(frame=0x2B, valid=True) print(hex(translate(0x3A5C, pt))) # 期望 0x2ba5c try: translate(0x8000, pt) # 页号 8 越界 except ValueError as e: print("越界:", e)跑一下,输出0x2ba5c,和手算完全一致。接下来加置换算法:
from collections import OrderedDict, deque def fifo_faults(refs, n_frames): q, in_mem, faults = deque(), set(), 0 for p in refs: if p in in_mem: continue faults += 1 if len(q) == n_frames: in_mem.discard(q.popleft()) # 淘汰最早进入的 q.append(p) in_mem.add(p) return faults def lru_faults(refs, n_frames): frames, faults = OrderedDict(), 0 for p in refs: if p in frames: frames.move_to_end(p) # 命中,标记为最近使用 else: faults += 1 if len(frames) == n_frames: frames.popitem(last=False) # 淘汰最久未用 frames[p] = None return faults if __name__ == "__main__": refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] print("FIFO 3框:", fifo_faults(refs, 3)) # 9 print("FIFO 4框:", fifo_faults(refs, 4)) # 10,Belady 异常 print("LRU 3框:", lru_faults(refs, 3)) # 10 print("LRU 4框:", lru_faults(refs, 4)) # 8输出会告诉你 FIFO 从 3 个页框加到 4 个页框,缺页数从 9 涨到 10,Belady 异常被完整复现。LRU 则是从 10 降到 8,单调不增,符合栈算法理论。
提示:
OrderedDict的move_to_end是 LRU 的天然实现。如果想省掉这行,可以用双向链表加哈希表自己搭,原理一样,但几十行代码换来的收益不值得。
5.3 验证与调参的几个实用手法
模拟器写完之后,别急着交作业,用下面几个手法交叉验证,能省掉大量返工。
第一个手法:反向验证。算出物理地址后,把它重新拆一遍,看能不能还原出原来的页号和偏移。物理地址 0x2BA5C 右移 12 位得到 0x2B,正好是页框号;低 12 位是 0xA5C,正好是偏移。两边都对得上,说明翻译没错。
第二个手法:边界值测试。页号 0、页号最大值、偏移 0、偏移 4095,这四个点必须单独跑一遍。尤其是偏移 4095(0xFFF)这个点,最容易暴露掩码写错的问题。
第三个手法:枚举小规模场景。页框数 2、引用串只有 5 个元素的时候,把所有可能的状态手推一遍,和模拟器结果对照。小场景能穷举,出错立刻能定位;大场景只能看总数,出错也不知道错在哪一步。
第四个手法:打印中间状态。在置换算法里把每次访问后的内存集合打印出来,和手算表格逐行对照。这一步看着笨,但定位问题的速度比盯着总数猜快十倍。
5.4 一些踩过坑之后才明白的经验
最后说几条我在做题和带实验过程中踩出来的经验,都是那种"当时不知道,事后想起来拍大腿"的类型。
第一条,先算位数再动笔。我见过太多人上来就开始移位、乘、加,算到一半发现页面大小判别错了,整个结果推倒重来。养成习惯:拿到题目先在草稿纸角落写下偏移位数、页号位数、页框号位数、页表项数这四个数字。它们互相约束,写全了基本不会出错。
第二条,分页和分段别混。这两个概念在练习里经常一起出现。分段是变长的,按逻辑模块划分,段号加段内偏移;分页是定长的,按物理需求划分,页号加页内偏移。分段的地址翻译要先查段表拿到基址再拼,分页是直接映射。混了之后,页表项里莫名其妙多出"段基址"字段,一眼就能看出来是错的。现代系统其实是段页式结合,但练习里的多数题目只考其中一种,看清题目问的是什么再下笔。
第三条,缺页次数的统计口径要明确。有的题目把"首次装入"算作缺页,有的不算,有的只统计"发生置换的次数"。这三种口径对应三个不同的数字,答案能差一倍。看到题目先确认口径,不要凭感觉写。
第四条,EAT 公式要从流程推,不要背。背公式的人遇到三级页表、TLB 分层、写回策略就会卡住。老老实实把"命中走哪条路、未命中走哪条路"画成两条线,把每条线上的访存次数数清楚,公式自己就出来了。这个能力比记住任何一个公式都值钱。
第五条,用模拟器验证一切。手算难免出错,模拟器不会骗人。前面那段代码不到一百行,能覆盖掉练习里 90% 的计算场景。把参数改成你题目里的一套,跑出来对照,比自己反复核对草稿快得多。
做到这五条,这类随堂练习基本就没什么能难住你的了。真要说还有什么,那就是把页表和真实系统的关系再多看一眼——你在纸上算的那些 4KB 页面、20 位页号、18 位页框号,此刻正在你自己的电脑上,以每秒几百万次的频率被执行着。