☰
课堂练习4.2页式内存管理:地址翻译、页表计算与置换算法
2026/9/30 7:51:18 网站建设 项目流程

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 位地址下的页号位数页表项数量
1KB10224M
2KB11212M
4KB12201M
8KB1319512K
2MB21112K

这张表解释了一件事:页面越大,页表越短,但内部碎片越多。4KB 是几十年试出来的折中点——页表不至于太夸张,最后一页的平均浪费也能接受。

拆分之后,逻辑地址的数学表达是:

逻辑地址 = 页号 × 页面大小 + 页内偏移 页号 = 逻辑地址 >> 偏移位数 偏移 = 逻辑地址 & (页面大小 - 1)

用位运算而不是除法,是因为除法和取余在硬件上代价高,移位和按位与几乎不花时间。这一点在做 EAT 分析时很重要——地址拆解本身不产生额外内存访问。

2.2 页表项里到底该存哪些位

页表项不是只存一个页框号,它是一组标志位的打包。很多练习让你"设计页表项格式",其实就是让你把该有的位一位位列出来。

位段位宽作用
页框号18(视物理内存)翻译目标
有效位10 表示该页不在内存,访问触发缺页
修改位(脏位)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

翻译链路:

  1. 页目录物理基址 0x00000000,第 0 项偏移 = 0 × 4 = 0,读取地址 0x00000000,得到内容指向页框 0x100。
  2. 二级页表物理基址 = 0x100 × 0x1000 = 0x100000。
  3. 二级页表第 3 项偏移 = 3 × 4 = 12 = 0xC,读取地址 0x10000C,得到页框号 0x2B,有效位 1。
  4. 物理地址 = 0x2B × 0x1000 + 0xA5C = 0x2BA5C。

结果和单级完全一致,偏移量在整条链路里从头到尾没被碰过,这印证了前面说的那句话。

差别在哪里?单级查一次页表就够了,二级在 TLB 未命中时要查两次内存(先页目录,再二级页表),相当于多花一次内存访问。这就是多级页表用空间换时间的代价,也是为什么 TLB 在多级页表体系里变得不可或缺。

注意:页目录项和二级页表项里除了页框号,同样带有效位。如果页目录项的有效位是 0,说明整个 4MB 区域都没被使用,硬件直接触发缺页,根本不用去读二级页表。这个短路设计显著加快了稀疏访问的速度,是练习里常被忽略的加分点。

3.4 页表内存开销的估算过程

题目问"该进程最少占用多少页表内存",答案是 8KB,但你要能说清楚这 8KB 从哪来。

页目录必须存在,占 1 页 = 4KB。进程只要访问了任何一个页号,对应的那个二级页表就必须分配,占 1 页 = 4KB。合计 8KB。

对比单级页表的 4MB:

方案最少页表内存覆盖全部地址空间所需
单级4MB(必须全量)4MB
二级8KB4MB + 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
单级页表101ns201ns111ns
二级页表101ns301ns121ns
无 TLB 二级不适用301ns301ns

无 TLB 时每次访问都要多两次内存访问,性能直接掉到三分之一。这就是为什么现代 CPU 的 TLB 动辄几百项,还分指令 TLB 和数据 TLB 两级。

提示:算 EAT 最常见的错误是"TLB 命中时还去算页表访问时间",或者"把 TLB 访问时间漏掉"。检查方法很简单——最终结果必须大于一次内存访问时间。如果算出来小于 100ns,说明逻辑错了。


4. 缺页、置换算法与练习里最容易错的点

前面都是稳态下的翻译,这一节讲非稳态:访问的页不在内存里怎么办,内存满了淘汰谁。这部分是练习的难点,也是面试的高频区。

4.1 一次缺页中断到底发生了什么

页表项有效位为 0,MMU 会抛出一个缺页异常,CPU 转入内核的缺页处理程序。整个流程分六步,每一步都值得记住,因为它们直接决定了练习里的"缺页次数"该怎么算。

  1. 硬件把触发缺页的逻辑地址保存到寄存器(比如 x86 的 CR2),并判断这次访问是否合法。访问了不属于自己的地址,直接杀进程,不进入后续步骤。
  2. 操作系统查找该页在磁盘上的位置,通常存在页表项的高位或单独的换出表里。
  3. 在物理内存里找一个空闲页框。有就直接用,没有就触发置换。
  4. 如果被选中的牺牲页修改位为 1,先把它的内容写回磁盘。
  5. 把目标页从磁盘读入页框,更新页表项:填入新页框号、有效位置 1、修改位清 0。
  6. 更新 TLB(要么直接写入,要么让相关表项失效),返回用户态,重新执行那条触发异常的指令。

第六步的"重新执行"是关键。缺页处理完成之后,指令是从头再跑一遍,而不是接着跑,因为第一次执行根本没产生任何副作用。这个细节解释了为什么页式管理对程序是完全透明的。

一次缺页涉及至少一次磁盘 I/O,耗时通常是几十微秒到几毫秒,比一次内存访问慢几个数量级。所以置换算法的目标只有一个:把缺页率压到最低。

4.2 FIFO、LRU、Clock 三种置换策略实测对比

练习里最常考三种算法,我用同一个引用串跑一遍,方便你对照。

引用串:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5,页框数 3。

FIFO(先进先出):淘汰最早进入内存的页,实现最简单,一个队列搞定。

访问内存状态(旧→新)是否缺页
11是
21, 2是
31, 2, 3是
44, 2, 3是
14, 1, 3是
24, 1, 2是
55, 1, 2是
15, 1, 2否
25, 1, 2否
35, 3, 2是
45, 3, 4是
55, 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 位)
4KB256KB4KB4MB 单级
2MB128MB2MB2K 项,8KB
1GB64GB1GB4 项,几乎可忽略

大页的碎片代价很高,所以不能全局启用。实际系统是混合模式:默认 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 位页框号,此刻正在你自己的电脑上,以每秒几百万次的频率被执行着。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询