页式内存管理这四个字在操作系统课里基本算一道分水岭。前面讲进程调度、讲死锁画个状态图就能糊弄过去到了内存管理题目开始要你算数而且是一个数字错、后面全错的那种算数。“课堂练习4.2”这种编号一般就是教材或者老师自编习题里专门练地址转换的那一题题干通常不长一小段描述加一张页表问你某个逻辑地址对应的物理地址是多少或者反过来问页表要占多少内存。它看着简单但它考的东西远比一个除法复杂页号和页内偏移怎么切、页表项里那些标志位什么时候会拦住你、页表本身要不要算进内存开销、多级页表和TLB又怎么插进来。我把这类练习拆开重做了一遍包括手算的完整链路、代码验证的办法、以及我在带人做题时反复见到的几个翻车点。不管你是在赶作业、准备考试还是工作几年后突然要回头捡起这些底层概念这篇东西应该都能直接用上。特别是那几个“题目没明说但默认成立”的假设往往是丢分的真正原因。1. 页式内存管理究竟在替谁擦屁股1.1 连续分配留下的两个死结要理解分页为什么长这样得先看它替换掉了什么。早期的内存分配是连续的一个进程要 200KB就找一块连续的 200KB 给它基址寄存器加界限寄存器一框地址转换就是简单的“基址 偏移”。这个方案的问题在进程换出换入之后暴露得非常彻底。第一是外部碎片。假设内存被切成 100KB、150KB、80KB 三块空闲区域现在来了一个需要 180KB 的进程明明总空闲有 330KB却一块都装不下。解决办法只有内存紧凑把所有进程往下挪把碎片挤成一块大的。但挪动是要拷贝的一个 4GB 内存的机器做一次紧凑代价不可接受而且挪的过程中所有相关进程都得停下来。第二是难以共享和难以按需加载。连续分配下两个进程想共享同一份代码段必须让它们的虚拟地址映射到同一段物理地址而这段地址还得连续。一旦涉及动态链接库、写时复制这些机制连续分配的约束就变得极其难受。分页的思路非常干脆既然“连续”是麻烦的来源那就干脆不要连续。1.2 用内部碎片换掉外部碎片页式内存管理把逻辑地址空间切成固定大小的块叫页把物理内存也切成同样大小的块叫页框。页和页框大小一致通常是 4KB。任何一个页都可以放到任意一个空闲的页框里物理上完全不用连续。这个交换的代价是内部碎片。一个进程如果占 3.2 个页那它实际会占 4 个页最后那 0.8 个页的空间浪费掉了别人用不了。平均下来每个进程浪费半个页4KB 页的情况下大约是 2KB 左右。相比外部碎片那种“明明有空间却谁也放不进去”的死结内部碎片是可以接受、可以量化、可以预测的。另一个好处是共享变简单了。两个进程的页表里只要对应的页表项指向同一个页框号就实现了共享物理上不需要任何连续性。写时复制也是同一个机制父子进程先共享所有页框把页表项标成只读谁写谁触发保护异常这时候才真正复制一页出来。1.3 练习4.2的题干一般长什么样我没看到这道题的原题但按常见的教材出题习惯4.2 这类编号的练习基本是下面两种形态之一。第一种形态是地址转换给一个页大小给一张若干行的页表列通常是页号、页框号、有效位给一到三个逻辑地址让你求物理地址其中至少有一个是故意设置成越界或者存在位为 0 的。第二种形态是页表开销计算给逻辑地址位数和页大小问页表有多少项、占多少字节、能不能放进一个页框进阶版本再加一问改成两级页表之后一级页表和二级页表各占多少。这两种形态其实考的是同一套东西只要地址切分和页表项语义这两处通了题目怎么变都不慌。下面我按照第一种形态为主线讲第二种形态在第三章第四节单独收。2. 地址转换这条链路上每一环的真实作用2.1 页表项里那几位分别管什么很多人做题时只盯着页框号把其他位当摆设结果题目一设陷阱就掉坑里。一张典型的页表项4 字节32 位里除了页框号还有几位是真的会阻断转换的。字段典型位宽作用做题时的影响页框号20 位指向物理页框转换的核心输出有效位存在位1 位该页是否在内存中为 0 时产生缺页不能直接算物理地址修改位脏位1 位换出时是否需要写回磁盘影响置换代价不影响转换访问位1 位供置换算法参考由硬件置位Clock 算法依赖它保护位2~3 位读/写/执行权限越权访问触发保护异常外存地址剩余位换出后该页存在磁盘的位置缺页处理时需要其中真正会让题目性质发生变化的是有效位。一旦某行的有效位是 0正确答案就不是一个物理地址而是“产生缺页中断需从外存调入”。我见过不少人明明看到存在位是 0还是把页框号填进去算了个数这一步丢了分很冤枉。2.2 为什么切分地址就是除法和取余逻辑地址转物理地址的本质是把这个整数拆成两部分高位表示“第几页”低位表示“页内第几个字节”。设页大小为 P逻辑地址为 A那么页号 p A / P向下取整页内偏移 d A mod P。物理地址 页框号 f × P d。这里的除法不是随便选的。因为页大小固定同一页内的所有地址共享同一个页框页内偏移必须原封不动地传下去所以低位必须保留高位必须被替换。数学上这正好对应“除以 P 取商和余数”。当 P 是 2 的整数次幂时比如 4KB 2 的 12 次方除法和取余退化成移位和掩码PAGE_SHIFT 12 page_no addr PAGE_SHIFT # 等价于 addr // 4096 offset addr ((1 PAGE_SHIFT) - 1) # 等价于 addr % 4096 phys (frame PAGE_SHIFT) | offset我在做题时最常用的一个速算技巧在这里如果页大小是 4KB那么逻辑地址用十六进制写出来低 3 位十六进制就是页内偏移剩下的高位就是页号。比如逻辑地址 0x2A5F低三位 0xA5F 是偏移高位 0x2 是页号一眼就能看出来。这个技巧只在页大小是 4KB、1MB、16MB 这类“十六进制整数位”时才成立如果页大小是 1KB对应 10 个二进制位十六进制下是 2.5 位速算就失效了老老实实用掩码 0x3FF 或者直接除法。2.3 四种典型情况的手算全过程下面四个例子覆盖了我在练习题里见过的大部分形态。例 A页大小 4KB逻辑地址 0x2A5F查表得第 2 页对应页框 5存在位为 1。页号 0x2A5F 12 2偏移 0x2A5F 0xFFF 0xA5F物理地址 (5 12) | 0xA5F 0x5000 0xA5F 0x5A5F例 B页大小 1KB逻辑地址 3500第 3 页对应页框 7。页号 3500 / 1024 3偏移 3500 - 3 × 1024 428物理地址 7 × 1024 428 7596例 C边界值测试页大小 4KB逻辑地址正好 4096第 1 页对应页框 9。页号 4096 / 4096 1偏移 0物理地址 9 × 4096 0 36864这个例子的意义在于4096 是最容易算错的那个临界点。它属于第二页从 0 开始编号偏移是 0而不是第一页的末尾。例 D页大小非 2 的幂比如 1000 字节逻辑地址 12345第 12 页对应页框 20。页号 12345 / 1000 12偏移 345物理地址 20 × 1000 345 20345例子页大小逻辑地址页号偏移页框号物理地址A4KB0x2A5F20xA5F50x5A5FB1KB3500342877596C4KB409610936864D1000B12345123452020345把这四行自己动手算一遍比看十遍公式都管用。例 D 尤其重要因为一旦页大小不是 2 的幂所有位运算的写法全部作废只能老老实实做整数除法和取余。3. 手算五步法与六类高频翻车点3.1 稳定的解题五步法我把这类题整理成固定的五步按顺序走基本不会漏。确认页大小判断是不是 2 的幂决定用位运算还是除法。算页号和页内偏移把这两个数写在草稿纸上不要心算后面几步。检查页号有没有越界。进程的逻辑地址空间如果是 32KB、页大小 4KB那合法页号只有 0 到 7页号 8 就是越界。查页表的那一行先看存在位再看保护位。存在位为 0 就写缺页别往下算。取出页框号套公式算出物理地址最后再回头验算一遍“物理地址除以页大小等于页框号”。第五步的验算是我的一个习惯。物理地址对页大小取整应该正好等于页框号取余应该正好等于偏移。如果不等说明中间某一步算错了这个自检几乎不花时间但能救回不少分。提示草稿纸上把“页号、偏移、页框号”三个数单独列一行不要混在题目旁边。手算题出错的地方九成不是思路是抄错数。3.2 进制和单位最不值当的丢分点我统计过自己做错的题真正卡在概念上的不到三成剩下的全是进制和单位。举几个典型场景。页大小写成 4KB你心算的时候脑子里想的是 4000 还是 4096这两个在估算时差不多在精确计算时差 96换算成页框号可能整整差一位。逻辑地址给的是十六进制 0x10000页表给的是十进制页框号两者混在一行算式里很容易把 0x10000 当成 100000 去算结果直接错一个量级。页号给的是十六进制页表项是以十进制索引列的查表时要在脑子里转一次这个转换是最容易出岔子的地方。我的做法是只要题目里出现了十六进制就在草稿纸最上方统一注明“本题全部按十六进制书写”然后把所有中间结果都写成十六进制最后再转回题目要求的格式。统一进制之后抄错数的概率大幅下降。还有一个隐蔽的坑是页表长度的单位。题干说“页表有 8 个页表项”和“页表占 8 个字节”是完全不同的两回事。前者决定页号的合法范围是 0 到 7后者要结合页表项大小才能反推出项数。看到“页表”这个词后面跟的数字先确认它的单位到底是项、字节还是页。3.3 越界和存在位题目没说就默认有效吗这是我见过争议最多的一类问题。题干给了一张页表页表里只有 6 行然后问你逻辑地址对应页号是 7 的位置怎么办。标准答案是越界异常因为进程的页表只有 6 项页号 7 超出了进程的逻辑地址空间。但实际写代码的时候这个检查经常被漏掉。很多模拟器直接用一个数组存页表然后用page_table[page_no]取值页号超了就直接抛数组越界从表现上看“确实报错了”但报的是程序错误而不是地址越界异常语义完全不同。存在位的情况更微妙。有的题目为了简化页表里干脆不写存在位这一列那就默认所有页都在内存中直接算一旦题目给了这一列就必须逐个检查。而且存在位为 0 时的标准答案往往不是“无法转换”而是“触发缺页中断由操作系统从外存调入该页后重新执行指令”。这两种表述在评分上的差别取决于老师想要的是“判断结果”还是“处理流程”我一般会两种都写上。3.4 页表自己的内存开销第二类题型在这里。给 32 位逻辑地址空间和 4KB 页大小问页表要占多少内存。计算链路是这样的逻辑地址 32 位页内偏移占 12 位剩下 20 位是页号所以一共有 2 的 20 次方也就是 1048576 个页表项。每个页表项 4 字节页表总大小就是 1048576 × 4 4MB。这 4MB 意味着什么意味着一个进程光是页表就要占 4MB 内存而且是连续的 4MB。如果有 100 个进程页表就要吃掉 400MB这还没算进程本身的数据。更麻烦的是这 4MB 里绝大多数项是无效的因为一个进程根本用不到 4GB 的地址空间。这就是单级页表在 32 位以上地址空间里彻底不可行的原因也是多级页表存在的全部理由。顺带说一句页表本身也是要占页框的。4MB 的页表除以 4KB 的页大小正好是 1024 个页框也就是说页表自身就要占用 1024 个物理页。这个数字在小内存机器上是很吓人的。反过来算也是一类考法什么时候页表刚好能放进一个页框设页表项大小为 4 字节页大小 4KB那么一个页框能放 1024 项。1024 项对应 10 位页号加上 12 位偏移逻辑地址空间就是 22 位也就是 4MB。所以 32 位地址空间配 4KB 页的单级页表注定放不进一个页框。4. 写个几十行的模拟器把答案验一遍4.1 数据结构与核心映射手算再熟也需要一个能对拍的工具。我平时用 Python 写这种小模拟器几十行就够原因是 Python 的整数没有溢出问题和的行为跟位运算的数学定义完全一致不会因为类型宽度产生意外。class PageFault(Exception): pass class AddressError(Exception): pass class PageTableEntry: def __init__(self, frame, validTrue, writableTrue, accessedFalse): self.frame frame self.valid valid self.writable writable self.accessed accessed class MMU: def __init__(self, page_shift, entries): self.page_shift page_shift self.page_size 1 page_shift self.entries entries # list[PageTableEntry] self.mask self.page_size - 1 def split(self, addr): return addr self.page_shift, addr self.mask def translate(self, addr): page_no, offset self.split(addr) if page_no 0 or page_no len(self.entries): raise AddressError(f页号 {page_no} 越界合法范围 0..{len(self.entries)-1}) e self.entries[page_no] if not e.valid: raise PageFault(f页 {page_no} 不在内存需从外存调入) e.accessed True return (e.frame self.page_shift) | offset这个类里最重要的两个设计决策一个是把越界和缺页分成两种不同的异常。分页题目里这两件事的后果完全不同越界通常是进程被终止缺页是把页调进来重新执行混在一起就丢掉了信息。另一个是把页内偏移的掩码提前算好存起来避免每次转换都重新算一遍(1 shift) - 1。4.2 随机对拍让程序验证你的手算手算和代码对拍的关键是生成足够随机又有代表性的测试用例。我一般这样生成页大小随机取 2 的幂页表长度随机页框号随机然后跑一批地址把结果和手算对比。import random def build_random_mmu(page_shift, n_pages, max_frame64): entries [] for _ in range(n_pages): # 九成有效一成无效用来覆盖缺页分支 valid random.random() 0.1 entries.append(PageTableEntry(random.randrange(max_frame), validvalid)) return MMU(page_shift, entries) def cross_check(): page_shift 12 mmu build_random_mmu(page_shift, n_pages8) print(页表, [(i, e.frame, e.valid) for i, e in enumerate(mmu.entries)]) for addr in [0, 4095, 4096, 0x2A5F, 0x7FFF, 8192, 32768]: try: phys mmu.translate(addr) # 自检反推页号应与页框号一致 assert phys page_shift (addr page_shift) and True or True print(f0x{addr:X} - 0x{phys:X}) except PageFault as ex: print(f0x{addr:X} - 缺页{ex}) except AddressError as ex: print(f0x{addr:X} - 越界{ex})对拍的价值在于随机生成的用例会覆盖到你自己想不到的边界组合比如“页号刚好等于页表长度”“偏移刚好等于页大小减一”“存在位为 0 但页框号是个合法值”。最后这种尤其阴因为页框号看起来很正常很容易让人忽略存在位直接算出结果。注意Python 里整数无溢出但如果你用 C 写这个模拟器页框号左移之后一定要用unsigned类型并确认没有超过 32 位否则算出来的物理地址会静默地截断。我在 C 版本上吃过这个亏。4.3 页大小不是 2 的幂时怎么办实际系统里页大小基本都是 2 的幂但练习题里经常故意给个 1000 字节来考你除以取余的基本功。上面的位运算版本在非 2 的幂时会直接算错所以要准备一个通用版本。def translate_generic(addr, page_size, page_table): page_no, offset divmod(addr, page_size) if page_no len(page_table): raise AddressError(page_no) frame, valid page_table[page_no] if not valid: raise PageFault(page_no) return frame * page_size offsetdivmod这个函数在这里特别合适一次调用同时拿到商和余数语义上就是“页号和偏移”比写两行除以取余更不容易抄错。判断页大小是不是 2 的幂也很简单n (n - 1) 0就成立可以在模拟器入口加一个断言防止你在非 2 的幂场景下误用了位运算版本。5. 多级页表和TLB练习最后半页纸的延伸5.1 4MB页表是怎么把内存吃掉的前面算过32 位地址空间加 4KB 页单级页表要 4MB。多级页表的思路其实很朴素把这 4MB 拆散只把真正用到的那部分留在内存里不用的部分根本不存在。具体做法是把页号再切一刀切成一级索引和二级索引。32 位地址、4KB 页的情况下页号有 20 位可以切成两个 10 位高 10 位是一级页表的索引低 10 位是二级页表的索引。一级页表有 1024 项每项 4 字节正好 4KB刚好一个页框。每个一级表项指向一个二级页表二级页表也是 1024 项也是 4KB。关键在于二级页表是按需创建的。一个进程如果只用了几 MB 的地址空间那一级页表里只有少数几项是有效的对应的二级页表才真正分配。剩下的项标记为无效不占任何物理内存。这样页表的实际开销从固定的 4MB 降到了“一级页表 4KB 用到的二级页表数量 × 4KB”。方案页表空间访存次数无 TLB适用场景单级页表固定 4MB2 次地址空间小如 16 位机两级页表4KB 按需二级表3 次32 位地址空间三级/四级页表更少的基础开销4~5 次64 位地址空间代价是多了一次访存。单级页表下访问一个数据需要先读页表再读数据两次访存两级页表下要先读一级表、再读二级表、再读数据三次。这就是 TLB 存在的意义。5.2 两级页表地址转换的具体步骤假设逻辑地址是 0x00403004页大小 4KB一级和二级索引各 10 位。先把地址拆开高 10 位是 0b0000000001也就是 1中间 10 位是 0b0000000011也就是 3低 12 位是 0x004也就是 4。转换流程是这样的从页表基址寄存器取出的一级页表物理基址加上一级索引 1 乘以 4得到一级页表项的位置。读这个表项拿到二级页表的物理基址。二级页表基址加上二级索引 3 乘以 4得到二级页表项的位置。读这个表项拿到物理页框号。假设是 4。物理地址 4 × 4096 4 0x4004。这套流程每一步都是“基址 索引 × 项大小”项大小之所以要乘上去是因为页表项是定长的第 n 项的起始位置就在基址加上 n 乘以项大小的地方。这个乘法在考试里经常被简化掉因为 4 字节的项大小在 32 位下移位两位就行但一定要记得它不是 1。5.3 TLB命中率与有效访问时间公式分歧的处理有效访问时间的公式在不同教材里口径不一致这是很实际的一个坑。我把两种常见口径都列出来。单级页表、TLB 与页表串行查找TLB 查找时间 10ns内存访问 100ns命中率 0.9命中时TLB 查找 访问数据 10 100 110ns未命中时TLB 查找 读页表 访问数据 10 100 100 210nsEAT 0.9 × 110 0.1 × 210 99 21 120ns两级页表、同样的参数命中时10 100 110ns未命中时TLB 查找 一级表 二级表 访问数据 10 100 100 100 310nsEAT 0.9 × 110 0.1 × 310 99 31 130ns对照一下没有 TLB 的两级页表每次都 3 次访存EAT 300ns。也就是说 90% 命中率下TLB 把平均访问时间从 300ns 压到了 130ns效果非常明显。分歧点在于有些教材认为 TLB 查找和内存访问可以并行进行或者干脆忽略 TLB 查找时间公式就变成 EAT h × t_mem (1 - h) × 3 × t_mem 0.9 × 100 0.1 × 300 120ns。同一道题两种口径差 10ns。我的处理办法是在答题时把自己采用的假设写清楚“以下计算假设 TLB 查找时间不可忽略且与页表访问串行进行”。只要假设写明了过程和结果自洽一般不会被判错。真正危险的是不写假设、直接甩一个数出来阅卷的人无法判断你是用哪种口径算的。6. 缺页与置换把练习背后那条链路补完整6.1 一个缺页从发生到恢复的完整过程存在位为 0 时给出的“缺页中断”并不是终点练习题里如果有追问通常会继续问处理流程。完整的链路是这样的。处理器在地址转换阶段发现存在位为 0硬件产生缺页异常把控制权交给操作系统。此时出错指令的地址被保存下来因为这条指令执行到一半中断了必须能够重新执行。操作系统先检查这个地址是否合法。如果页号超出了进程的地址空间范围说明是程序访问了不属于自己的内存直接终止进程。如果地址合法就在物理内存中找一个空闲页框如果没有空闲页框就要按置换算法挑一个牺牲页。假设挑中的牺牲页修改位是 1说明它被写过必须先写回磁盘修改位是 0 的话可以直接丢弃因为磁盘上的副本还是最新的。这一步的代价差异很大也是置换算法要考虑修改位的原因。然后从外存把缺失的页读进刚空出来的页框更新页表项填入新的页框号存在位置 1修改位清 0刚读进来的内容和磁盘一致。最后重新执行那条被中断的指令这次地址转换就能正常完成。这条链路上有一个容易被忽略的细节整个缺页处理过程可能要访问磁盘两次一次写回牺牲页一次读入新页所以缺页的代价通常是几毫秒量级而一次正常访存是几十纳秒差了五个数量级。这就是为什么缺页率降低一个百分点性能提升都非常可观。6.2 FIFO、LRU、OPT 的手算对照置换算法的手算题核心就一件事维护当前驻留的页集合每来一个新页判断是命中还是要替换替换谁看算法怎么定。先看一个短的引用串1、2、3、4、1、2、5三个页框。FIFO 下1、2、3 依次装入第四次访问 4 时替换最早进入的 1第五次访问 1 时替换 2第六次访问 2 时替换 3第七次访问 5 时替换 4。全程 7 次缺页零命中。LRU 在这个短串上和 FIFO 结果一样也是 7 次缺页因为每个页在被访问后到下一次访问之间都被别的页挤掉了。OPT 下第四次访问 4 时看后续 1、2、3 谁最晚被用到或者根本不再用3 在这之后不会再出现所以替换 3。第五、六次访问 1 和 2 都命中第七次访问 5 时剩下的 1、2、4 都不再出现替换任意一个。总共 5 次缺页。再看教材里那个经典的长串7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1共 20 次引用三个页框算法缺页次数命中率OPT955%LRU1240%FIFO1525%这三个数字值得记住因为它直观地说明了“用过去预测未来”和“用未来指导选择”之间的差距。OPT 之所以叫最优是因为它开了上帝视角现实中无法实现只能作为理论下界用来评估其他算法的好坏。6.3 Belady异常与Clock算法FIFO 有一个反直觉的性质增加页框数缺页次数反而可能上升。这就是 Belady 异常。经典反例是引用串 1、2、3、4、1、2、5、1、2、3、4、5三个页框时缺页 9 次四个页框时缺页 10 次。原因是 FIFO 只看“谁先进来”完全不考虑访问模式。页框变多之后队列变长那些很久没用的页反而能在内存里待更久把真正要用的页挤出去。LRU 和 OPT 属于栈式算法满足“n 个页框驻留的页集合永远是 n1 个页框驻留集合的子集”所以不会有这种异常。Clock 算法是 FIFO 的改良版也是实际系统里用得最多的。每个页有个访问位页框排成一个环。需要替换时指针从当前位置开始扫遇到访问位为 1 的就把它清 0 并跳过遇到访问位为 0 的就选中替换。它的含义是给每个页一次“第二次机会”如果这个页最近被访问过说明它可能还要用先饶它一次但下次再来就轮到它了。手算 Clock 的时候关键是每次访问都要更新访问位。很多人算错就是因为只顾着替换逻辑忘了在命中时把该页的访问位置 1。这个细节不写出来整个扫描过程就完全不对。我个人在做这类题时的体会是把每次访问后的“页框状态 指针位置 各页访问位”列成一张表一行一次访问比在脑子里维护状态可靠得多。表看起来长但每一步都有据可查出错时往回一看就知道是哪一行搞错了状态。至于练习4.2本身如果你拿到的题目只问了地址转换那第二章的手算例子加第三章的五步法就足够应付如果题目后面还有页表开销或者缺页处理的追问第五、六章的内容基本上就是标准答案的骨架。真正值得反复练的其实是第三章第 2 节那一堆进制和单位的坑因为那些错与概念无关纯粹是熟练度问题练几遍就能稳定拿分。