页式内存管理核心考点与C模拟：地址转换、页面置换全解析

课堂练习 4.2 这道题我第一次做的时候是在宿舍里对着 A4 纸画了一晚上的页表。当时觉得页式内存管理就是几个公式页号、偏移量、页表项数套进去算完就交卷。直到后来自己动手写了一个小的地址转换模拟器又去翻 Linux 内存子系统里的 pgd、pmd、pte 这套结构才明白这道练习真正想训练的是什么——它要的不是算术能力而是一种把逻辑地址和物理地址当作两套独立坐标系的思维方式。这篇文章会把页式内存管理的核心考点、参数计算、地址转换流程、页面置换算法的模拟细节以及如何用 C 语言把整套机制跑起来一条一条拆开讲。不管你是正在赶作业的学生还是刚接触操作系统、想搞明白虚拟内存到底虚拟在哪的自学者下面的内容应该都能对上你的需求。涉及代码的部分可以直接复制编译涉及计算的部分我会把每一步的推导过程写全。1. 这道练习到底在练什么先把考点拆开1.1 从内存不够用说起分页要解决的真实矛盾要理解页式管理得先回到它诞生的场景。早期的内存分配用的是连续分配一个进程要么整块装进内存要么就装不下。问题在于一个 100MB 的程序如果只要求它先跑起来前 10MB 的代码剩下的 90MB 短时间内根本用不到却必须占着物理内存。更麻烦的是碎片——进程 A 走了留下一个 30MB 的空洞进程 B 需要 40MB就只能干等哪怕内存里散落的空闲加起来有 80MB。这就是所谓的外部碎片问题。分页的思路非常朴素既然整块装太僵硬那就把逻辑地址空间切成固定大小的小块叫页把物理内存也切成同样大小的块叫页框。页可以装到任意一个空闲页框里去不需要连续。这样一来进程不必连续存放外部碎片自然消失因为所有空闲页框都是等大的任何一个都能拿来用。代价是引入了内部碎片——最后一页大概率填不满浪费一点但最大浪费不超过一页完全可控。我认为这道练习的第一个考点就在这儿你得能说清楚为什么选固定大小的页而不是变长的段。固定大小意味着地址拆分可以纯粹靠位运算完成硬件实现极其廉价变长的段虽然更贴合程序的逻辑结构代码段、数据段、栈段但地址转换需要比较运算而且要处理外部碎片。现代系统里两者通常结合段用于描述权限和逻辑划分页用于实际的物理映射这点在第 7 节会展开。1.2 练习 4.2 的三种典型题型与各自的评分点不同教材的课堂练习 4.2内容会有差异但题型基本跑不出三类。第一类是参数计算型给定逻辑地址位数、页面大小、页表项大小求页内偏移占几位、页号占几位、单级页表一共多大、需要多少个页表项。这类题看着简单但陷阱在于单位换算和页表本身也要占内存这个隐含条件很多人算完页表大小就忘了问一句这个页表能不能装进一页。第二类是地址转换型给一个具体的逻辑地址或者十六进制串要求写出二进制拆分、查页表、算出物理地址。这类题的重点是流程完整性少写一步页号逻辑地址右移偏移位数就可能丢分。如果是二级页表还要多一层查表路径更长出错的概率也更高。第三类是页面置换型给一个页面引用串和若干页框分别用 FIFO、LRU、OPT 算法模拟统计缺页次数、算缺页率有时还要求指出是否出现 Belady 异常。这类题是练习 4.2 里最容易拉开差距的部分因为它考的不是公式而是耐心和条理性——手一抖某一步写错了后面全歪。我的建议是拿到题先判断属于哪一类再看分值分布。参数计算通常一两个空地址转换要看步骤分置换算法几乎肯定是重头戏。顺序上我习惯先做置换题因为它最耗时脑子清醒的时候做准确率最高参数计算留到后面纯计算不容易受状态影响。2. 页表、页框与地址位数三个必须算对的参数2.1 页表项里到底存了什么页表本质是一张映射表索引是页号值是页框号。但真实的页表项远不止存一个页框号它还要携带一堆控制位。这些位不是设计者炫技每一条都对应一个具体的内核行为。有效位valid最核心标记这个页当前是否在物理内存里。如果为 0CPU 访问到这个页就会触发缺页中断把控制权交给操作系统。修改位dirty记录这一页自从装入以来有没有被写过置换的时候优先淘汰没被改过的页因为干净的页可以直接丢弃脏页必须先写回磁盘。访问位accessed / reference用于置换算法的近似实现Clock 算法就是靠它扫描的。保护位read / write / execute控制这一页允许什么操作用户态程序试图写一个只读页会触发保护异常这是现代系统里代码段不可写的基础。我做题时常用的一个判断是如果题目给出了页表项大小并且让你算页表项里能放多少位控制信息那就用页表项总位数减去页框号位数。比如 32 位页表项、物理内存 64MB、页大小 4KB那么页框号需要 log2(64MB / 4KB) log2(16384) 14 位剩下的 32 − 14 18 位就是各种标志位和保留位。这个推导比死记结论可靠得多。2.2 地址拆分的通用公式与手算口诀逻辑地址的拆分只有一条公式设逻辑地址共 n 位页面大小 2^k 字节那么低 k 位是页内偏移高 n − k 位是页号。我给它起了个口诀叫低位定大小高位定页数——低 k 位由页面大小决定高 n − k 位决定地址空间里一共有 2^(n−k) 个页。举几个我在练习里反复用到的数值建议直接背下来会省很多时间页面大小 1KB 对应偏移 10 位2KB 对应 11 位4KB 对应 12 位8KB 对应 13 位1MB 对应 20 位。同理页表项数方面2^10 1K2^12 4K2^20 1M2^32 4G。这些数字在页式管理里出现的频率极高靠现算容易出错。单级页表的大小公式是页表大小 页表项数 × 页表项大小 2^(n−k) × 每项字节数。代入最容易考的 32 位地址、4KB 页、4 字节页表项页号 20 位页表项数 2^20 1M页表大小 1M × 4B 4MB。注意是每个进程 4MB。如果系统里有 100 个进程光页表就吃掉 400MB 物理内存而大部分页可能压根没被访问过。这个矛盾的展开就是下面多级页表存在的全部理由。2.3 二级页表省空间的账怎么算二级页表的做法是把 20 位的页号再拆成两段比如前 10 位做一级索引后 10 位做二级索引。一级页表也叫页目录有 2^10 1024 项每项 4 字节占用 4KB正好一页。每个二级页表同样 1024 项、4KB。页内偏移保持 12 位不变。关键差异在于按需分配。如果一个进程实际只用了很少的页比如说它只用到了 4MB 逻辑空间里的一小块那就只需要一个一级页表加极少数几个二级页表。假设用 2 个二级页表总占用就是 4KB 2 × 4KB 12KB而单级页表硬性要 4MB。差了几百倍。不过要诚实地说二级页表并非无条件省空间。如果一个进程几乎用满了整个 4GB 地址空间它的二级页表也得全部建立起来总大小变成 4KB 1024 × 4KB 4MB 4KB反而比单级多了一点点。所以准确的说法是多级页表在稀疏地址空间下大幅省空间在稠密地址空间下略有开销。现代进程的地址空间恰恰是稀疏的——栈在顶端堆在中间某处代码在低端中间大片是空的。我还想补一个容易被忽略的约束多级页表的每一级索引位数不是随便定的它由一级页表必须能装进一页这个条件反推出来。每级索引位数 log2(页面大小 / 页表项大小)。4KB 页、8 字节项就是 log2(512) 9 位。这正是 64 位系统里 9 9 9 9 12 48 位虚拟地址的由来。理解了这条约束再看到 9 这个数字就不会觉得是凭空冒出来的。3. 地址转换手算全流程从逻辑地址到物理地址3.1 单级页表的四步转换法我把单级页表的转换固定成四步做题时按顺序写基本不会漏。第一步确定页面大小对应的偏移位数 k。第二步把逻辑地址写成二进制低 k 位抄下来作为偏移量。第三步高 n − k 位作为页号去查页表取出对应的页框号。第四步页框号左移 k 位加上偏移量得到物理地址。举个具体例子。页面大小 4KBk 12逻辑地址 0x00003A5C。先拆低 12 位偏移 0xA5C高 20 位页号 0x00003。假设页表第 3 项存的是页框号 0x00025那么物理地址 0x25 12 | 0xA5C 0x25000 0xA5C 0x25A5C。这里有两个细节我要提醒。第一物理地址的偏移部分和逻辑地址的偏移部分完全相同只有高位被替换了这是分页机制最漂亮的性质之一。第二页框号左移的时候一定要按位运算理解不是简单乘法拼接如果页框号是 0x25左移 12 位就是 0x25000不要错写成 0x25A5C 之外的其他形式。还有一点做题时如果题目给的是十进制地址先转成二进制或者十六进制再做拆分别硬算除法。十六进制拆分尤其方便因为 4KB 恰好对应 3 个十六进制位低位直接切掉 3 位就是页号。3.2 二级页表转换的完整演算二级页表的转换路径更长但逻辑是同一套只是多做一次查表。把 20 位页号拆成一级 10 位和二级 10 位之后流程变成一级索引查页目录拿到二级页表的起始地址二级索引在二级页表里查拿到页框号最后拼接偏移。继续用 32 位地址、4KB 页的例子逻辑地址 0x00403A5C。二进制拆下来低 12 位偏移 0xA5C中间 10 位二级索引最高 10 位一级索引。0x00403A5C 的页号部分是 0x00403也就是二进制 0000 0000 0100 0000 0011。前 10 位是 0000000001等于 1后 10 位是 0000000011等于 3。所以一级索引 1二级索引 3偏移 0xA5C。假设页目录第 1 项指向的二级页表基址是物理帧 0x80二级页表第 3 项存的页框号是 0x2F1那么物理地址 0x2F1 12 | 0xA5C 0x2F1A5C。整个路径访问了两次内存页目录一次、二级页表一次加上最后取数据一次一共三次内存访问。这就是多级页表在节省空间的同时付出的性能代价。算这笔账的时候我习惯列个小表格把每一级索引值、对应的表项内容、推导出的下一级地址写清楚。考场上时间紧但表格能让你在复查时一眼看出哪一步跳错了。3.3 TLB 命中率与有效访问时间 EAT前面说了多级页表让每次访问的内存次数变多单级 2 次二级 3 次四级 5 次。如果没有硬件帮忙性能会崩掉。TLB快表就是干这个的——它是一块极小但极快的高速缓存通常只有几十到几百个表项专门缓存最近用过的页表项。程序访问内存具有局部性所以命中率往往很高95% 以上是常态。有效访问时间EAT的计算是练习里的常客。无缺页的情况下单级页表的公式是 EAT h × (t_TLB t_M) (1 − h) × (t_TLB 2 × t_M)其中 h 是命中率t_TLB 是查 TLB 的时间t_M 是一次内存访问时间。前面的 t_TLB 无论命中与否都要花。代入一组典型值t_TLB 10nst_M 100nsh 0.9。EAT 0.9 × (10 100) 0.1 × (10 200) 99 21 120ns。作为对比如果完全没有 TLB单级页表要 200ns多级会更糟。TLB 把接近两倍的差距压了下来。换成二级页表未命中时要访问三次内存EAT 0.9 × 110 0.1 × (10 300) 99 31 130ns。可以看到从单级到二级EAT 只多了 10ns因为命中率主导了结果。这解释了为什么工程师愿意为了省内存去加层级代价在可接受范围内。如果题目进一步给出缺页率 p 和缺页处理时间公式要扩展为 EAT (1 − p) × EAT_无缺页 p × 缺页处理时间。这里有个反直觉的结论值得记住假设 p 0.0001万分之一缺页处理时间 8ms那么 EAT 0.9999 × 120 0.0001 × 8,000,000 ≈ 120 800 920ns。仅仅是万分之一的缺页率就把平均访问时间从 120ns 拉到了 920ns。这说明缺页代价是数量级级别的任何降低缺页率的努力更大的内存、更好的置换算法、更合理的预取都远比优化 TLB 更值得投入。4. 页面置换算法缺页率怎么算才不出错4.1 FIFO、OPT、LRU 三种基准算法的模拟规则页面置换算法的题目规则本身不复杂难在手工模拟时保持清醒。FIFO 最简单淘汰最早进入内存的那一页用一个队列维护顺序新页从队尾进淘汰从队头出。它的缺点是会淘汰掉那些虽然进来得早、但一直在被频繁使用的页这种年龄歧视在访问模式下表现很差。OPT最优置换淘汰未来最长时间不会被访问的页。它需要预知未来实际系统做不到所以只作为理论下界用来衡量其他算法的好坏。做题时如果引用串里出现了后面再也不出现的页优先淘汰它。LRU最近最少使用淘汰最长时间没被访问的页。它用过去预测未来依据是程序局部性——刚被访问过的页接下来很可能还会被访问。LRU 的性能通常接近 OPT但硬件实现成本高因为需要精确记录每一页的访问时刻。实际系统常用的是它的近似版本也就是 Clock 算法。模拟这三种算法时我强烈建议用表格而不是口头推演。表格列头写引用串的每一个元素下面是每一帧的内容和是否缺页的标记。每走一步都在表里落笔最后数缺页标记。这样做慢一点但几乎不会错。我曾经试过心算二十个引用串走到第十五个就开始飘回头检查发现前面漏了一次替换。4.2 一组经典引用串的完整推演用操作系统教材里的经典引用串来演示这个串是7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1总共 20 次访问页框数是 3。FIFO 的过程是这样的。前三次 7、0、1 依次装入各缺页一次。第四次访问 2队列里最早的是 7淘汰 7 装入 2。第五次 0 命中。第六次 3此时队列顺序是 0、1、2淘汰 0。第七次 0 缺页淘汰 1。第八次 4淘汰 2。第九次 2淘汰 3。第十次 3淘汰 0。第十一次 0淘汰 4。第十二次 3 命中第十三次 2 命中。第十四次 1淘汰 3。第十五次 2淘汰 1。第十六、十七次 0、1 命中。第十八次 7淘汰 0。第十九次 0淘汰 1。第二十次 1淘汰 2。最终 FIFO 缺页 15 次缺页率 75%。LRU 在同一串上的结果是 12 次缺页。差异出现在第六次访问 3 的时候LRU 看的是最近使用时间此时 7 已经很久没被碰过而 FIFO 淘汰的是 0因为 0 进得比 1 早但比 7 晚队列头是 0。就是这类时刻两个算法分道扬镳。LRU 最终 12 次缺页缺页率 60%。OPT 的结果是 9 次缺页。它的优势在第八次访问 4 的时候体现出来帧里是 2、0、3往后看0 在第 11 次还要用3 在第 10 次马上要用2 在第 9 次就要用于是淘汰那个最晚才被用到的。后续几次它总能把即将被用的页留下来最终只缺 9 次缺页率 45%。把三个数字放在一起看OPT 9 次 LRU 12 次 FIFO 15 次。LRU 距离理论下界只差 3 次FIFO 差了 6 次这组数据很直观地说明了算法质量的差异。做题时如果算出来的 LRU 比 FIFO 还差几乎可以肯定中间某一步推错了。4.3 Clock 算法与 Belady 异常Clock 算法是 LRU 的工程近似。它把页框组织成一个环形链表每个页框带一个访问位。需要置换时指针从当前位置扫描访问位是 1 就清零并继续前进访问位是 0 就选中它作为牺牲者。这个规则的意思是给最近被访问过的页一次机会扫描一圈下来那些长时间没被碰过的页访问位早就被清了自然会被选中。Clock 的好处是实现成本极低——不需要时间戳不需要排序硬件只需要维护一个访问位操作系统只需要移动一个指针。代价是精度不如 LRU它区分不出刚被访问和一个时钟周期前被访问的差别。但实测中它的表现相当接近 LRU这就够了工程上从来追求的是性价比而不是理论最优。Belady 异常是 FIFO 的一个著名缺陷增加页框数缺页次数反而可能上升。经典反例是引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 53 个页框时 FIFO 缺页 9 次4 个页框时缺页 10 次。原因在于 FIFO 不满足栈式算法要求的包含性质——用 n 个帧时的页集合不一定是 n1 个帧时页集合的子集所以增加帧数有可能打乱原本的淘汰节奏。LRU 和 OPT 都属于栈式算法满足包含性质因此不会出现 Belady 异常。判断方法很简单如果算法的淘汰决策只依赖于最后一次访问的时刻或者未来的访问序列那它就是栈式的如果依赖进入内存的时刻那就不是。FIFO 只看进入时间所以会被 Belady 异常击中。这个结论在选择题里出现的频率很高值得记牢。5. 用 C 语言把页式管理模拟一遍5.1 数据结构设计页表、页框与 MMU光看公式容易浮在表面动手写一遍模拟器很多模糊的地方会立刻清晰。先设计最基本的结构。页表用一个数组表示下标是虚拟页号值存页框号再加一个特殊值表示无效。物理内存用另一个数组表示每个页框被哪个虚拟页占用置换的时候需要反查。访问时刻用一个递增的计数器维护LRU 靠它比较。我把配置参数都做成宏方便改页数和帧数来观察行为变化。教学场景下不需要真的开 4GB 的数组用十几个虚拟页、几个页框就能把机制跑通逻辑和真实系统完全一致。代码里我特意把地址拆分单独写成一个函数因为这一步是整套机制的地基。拆分只有两个位运算偏移量等于地址按位与上掩码页号等于地址右移偏移位数。写成函数之后任何地方需要拆分都调它不会出现两处实现不一致的问题。#include stdio.h #include string.h #define PAGE_SHIFT 4 /* 页大小 16 字节教学用小值 */ #define PAGE_SIZE (1 PAGE_SHIFT) #define PAGE_MASK (PAGE_SIZE - 1) #define VPN_NUM 16 /* 虚拟页数 */ #define FRAME_NUM 4 /* 物理页框数 */ #define EMPTY (-1) typedef struct { int page_table[VPN_NUM]; /* 虚拟页 - 页框号EMPTY 表示未映射 */ int frame_owner[FRAME_NUM];/* 页框 - 虚拟页号 */ unsigned long stamp[FRAME_NUM]; /* 每帧最近访问时刻LRU 用 */ unsigned long tick; int fifo_ptr; int faults; } mmu_t; static void mmu_init(mmu_t *m) { memset(m, 0, sizeof(*m)); for (int i 0; i VPN_NUM; i) m-page_table[i] EMPTY; for (int i 0; i FRAME_NUM; i) m-frame_owner[i] EMPTY; } static void split_addr(unsigned va, int *vpn, int *offset) { *offset va PAGE_MASK; *vpn va PAGE_SHIFT; }这里有个细节值得说page_table和frame_owner互为反向映射这是真实系统里也存在的结构Linux 的page结构体里就有mapping字段和反向映射机制目的就是置换时能快速找到这个物理页被哪些虚拟页引用。教学模型里把它简化成一维数组本质没变。5.2 地址转换与缺页处理的实现转换函数要处理两种情况页表项有效直接拼接物理地址返回页表项无效触发缺页处理选一个牺牲页换出去把新页装进来然后再返回。这里要注意顺序——先把新页映射建立好再返回物理地址不能先返回再映射。置换策略我做成可切换的用一个枚举区分 FIFO 和 LRU。选择牺牲页的时候FIFO 用一个循环指针LRU 扫描时间戳找最小值。两者都要处理空闲帧的情况如果还有空帧优先用空帧不进置换逻辑。static int pick_victim(mmu_t *m, int use_lru) { int v 0; for (int i 0; i FRAME_NUM; i) if (m-frame_owner[i] EMPTY) return i; /* 优先用空帧 */ if (use_lru) { for (int i 1; i FRAME_NUM; i) if (m-stamp[i] m-stamp[v]) v i; } else { v m-fifo_ptr; m-fifo_ptr (m-fifo_ptr 1) % FRAME_NUM; } return v; } static int access_mem(mmu_t *m, unsigned va, int use_lru, unsigned *pa) { int vpn, offset, frame; split_addr(va, vpn, offset); m-tick; frame m-page_table[vpn]; if (frame ! EMPTY) { /* 命中 */ m-stamp[frame] m-tick; *pa (unsigned)(frame PAGE_SHIFT) | (unsigned)offset; return 0; } /* 缺页选择牺牲页清理反向映射 */ m-faults; frame pick_victim(m, use_lru); if (m-frame_owner[frame] ! EMPTY) m-page_table[m-frame_owner[frame]] EMPTY; m-frame_owner[frame] vpn; m-page_table[vpn] frame; m-stamp[frame] m-tick; *pa (unsigned)(frame PAGE_SHIFT) | (unsigned)offset; return 1; /* 返回 1 表示本次发生了缺页 */ }access_mem的返回值我设计成是否缺页这样外层统计缺页次数就非常直接。注意m-tick放在拆分之后、命中判断之前保证每次访问都有唯一的时间戳LRU 比较时不会有并列。还有一个容易忽略的点清理反向映射的时候要把被淘汰页的页表项置回 EMPTY否则下次访问会读到一个已经不属于它的页框号产生错误映射。这个 bug 我第一次写的时候踩过表现为缺页次数异常偏低因为脏页表项让系统误以为页还在内存里。5.3 两种置换策略的测试与结果比对测试数据用第 4 节那组经典引用串把每次访问的虚拟地址构造出来页号左移 PAGE_SHIFT 即可偏移取 0分别用 FIFO 和 LRU 跑一遍打印每次是否缺页以及最终的缺页次数。int main(void) { const int ref[] {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; const int n (int)(sizeof(ref) / sizeof(ref[0])); mmu_t m; unsigned pa; mmu_init(m); for (int i 0; i n; i) { int fault access_mem(m, (unsigned)ref[i] PAGE_SHIFT, 0, pa); printf(FIFO 访问页 %2d - 物理地址 0x%03X %s\n, ref[i], pa, fault ? 缺页 : 命中); } printf(FIFO 缺页次数 %d\n\n, m.faults); mmu_init(m); for (int i 0; i n; i) { int fault access_mem(m, (unsigned)ref[i] PAGE_SHIFT, 1, pa); printf(LRU 访问页 %2d - 物理地址 0x%03X %s\n, ref[i], pa, fault ? 缺页 : 命中); } printf(LRU 缺页次数 %d\n, m.faults); return 0; }编译运行gcc -O2 -Wall -o page_sim page_sim.c ./page_sim输出会显示 FIFO 缺页 15 次、LRU 缺页 12 次和手算结果完全一致。这个一致性检查非常关键——先用小规模数据把程序跑对再改成更大的参数才敢相信结果。把FRAME_NUM改成 4 再跑一遍你会发现 FIFO 的缺页次数变成了 10比 3 帧时的表现更差这就亲手复现了 Belady 异常。LRU 在 4 帧时缺页次数降到 8单调下降符合栈式算法的预期。我在调试时就是靠这个对比验证了置换逻辑没写错因为如果 LRU 也出现非单调说明时间戳更新有问题。6. 常见错误排查一份做题与调代码的速查表6.1 高频错误清单下面这张表是我自己整理的错误清单涵盖了做题和写模拟器时最常翻车的几种情况。前四类属于计算和概念后两类属于实现。错误现象根本原因修正办法页表大小算成 KB 级明显偏小把页表项数当成了字节数少乘了每项大小页表大小 页表项数 × 每项字节数单位统一到字节地址转换后物理地址的偏移对不上混淆了页框号与物理地址忘记左移物理地址 页框号 k再按位或上偏移多级页表索引位数取错用了固定值而没按页大小反推每级位数 log2(页面大小 / 页表项大小)缺页率单位写成小数却按百分比读缺页率 缺页次数 / 总访问次数20 次访问缺 15 次是 0.75也就是 75%模拟器缺页次数偏低淘汰时没清空被换出页的页表项置换后同时更新正向和反向映射LRU 结果和 FIFO 一样时间戳没在每次命中时刷新命中路径也要更新时间戳这份清单的价值在于它能帮你把哪个环节出了问题快速定位到具体一行。尤其是最后两条属于只有真正写过代码才会遇到的坑光做题是体会不到的。6.2 我踩过的几个坑第一个坑发生在算二级页表大小的时候。我一开始想当然地认为二级页表的总大小等于一级加二级结果算出来比单级还大一度以为自己推导错了。后来才意识到二级页表是按需建立的不能假设所有二级页表都存在。如果题目没有说明进程的地址空间使用情况就要分情况讨论稀疏场景下省空间稠密场景下略大。这种题目信息不足时主动说明前提的习惯在考试里也是加分项。第二个坑在页面置换的手工模拟上。我早期习惯用脑子记住当前帧里有哪些页结果做到第十几次访问就开始把已经被换出去的页当成还在。后来改成画表格一行代表一个页框列依次对应每次访问缺页的位置打叉帧内容写清楚。这个方法看起来笨但准确率接近百分之百而且复查的时候一眼就能看出哪一列前后不一致。第三个坑在写模拟器的时候。为了图省事我把置换逻辑写在了地址转换函数里结果命中路径和缺页路径耦合在一起加一个新的置换算法就要改一大段代码。后来重构成选牺牲页和执行替换两个独立函数接口清晰了很多。这个教训推开来说就是任何系统里策略和机制都应该分离——机制负责怎么做策略负责做哪个选择。真实操作系统也是这么做的页面置换的框架固定具体选哪个页由注册进来的策略决定。7. 课堂练习之外真实系统里这些结构长什么样7.1 Linux 内存子系统里的关键数据结构课堂练习里的页表是一张简单数组真实内核里的结构要复杂得多但骨架是相通的。Linux 里每个进程有一个mm_struct描述整个地址空间里面挂着pgd指针指向顶级页表。地址空间被划分成若干段每段用一个vm_area_struct描述记录起止地址、权限、对应的文件映射等信息。当进程访问一个地址时内核先查vm_area_struct判断这次访问是否合法再走页表检查映射是否存在。页表本身是四到五级在 x86-64 上依次是 pgd、p4d、pud、pmd、pte。每级都是 9 位索引加最终 12 位偏移凑成 48 位有效虚拟地址。有意思的是Linux 用同一套代码支持不同级数的页表通过折叠中间层级来适配——在只有三级页表的架构上p4d 和 pud 会被编译器优化掉不产生额外开销。这种设计思路很值得学把级数参数化而不是为每种硬件写一套代码。物理页的管理靠struct page每个物理页框对应一个。它记录了引用计数、所属的 zone、是否脏、是否被锁定等信息。物理页的分配用伙伴系统按 2 的幂次拆分合并解决外部碎片内核对象这类小内存的分配则用 slab 分配器减少频繁初始化的开销。这两套机制的分工正好对应了页级大块分配和字节级小对象分配两种不同粒度的需求。7.2 缺页中断在真实内核里的处理链路课堂练习里的缺页处理只有三行伪代码选牺牲页、写回、装入新页。真实内核的路径要长得多。以 x86-64 为例CPU 访问到一个无效页表项时触发 14 号异常硬件把出错地址存入 CR2 寄存器控制权转到内核的异常处理入口。内核读 CR2 拿到地址检查这次访问是否落在某个vm_area_struct范围内——不在就发信号终止进程这就是段错误。如果在范围内就要区分几种情况页从未被装入匿名页首次访问、页被换出到交换区、页属于文件映射但还没读进来、写一个写时复制的页。不同情况走不同的处理路径。文件映射的页从页高速缓存里找找不到就发起磁盘读取匿名页如果没有空闲页框先触发页框回收回收不够就用直接回收还不行就触发内存不足的应对机制。处理完成后内核填写 PTE更新 TLB或者直接让 TLB 失效返回用户态重新执行那条出错的指令。整个链路涉及异常处理、内存管理、文件系统、块设备多个子系统这也是为什么缺页这个词在性能分析里分量这么重——它一次要拉动的资源太多了。我在学这部分的时候最大的收获是理解了课堂模型里被省略的那些分支判断恰恰是真实系统性能优化的主战场。7.3 从课堂模型到工程实现的三个差距第一个差距是并发。课堂上的页表假设只有一个执行流在访问现实中多个 CPU 核心可能同时缺页、同时修改页表。内核用页表锁、原子操作、内存屏障来保证一致性还要处理 TLB 在多核之间的同步所谓 TLB shootdown。这部分在练习里完全不会涉及但它是真实系统里最容易出问题的区域。第二个差距是换出策略。课堂练习里页面置换的代价是均一的换出任何一页代价相同。现实中完全不同脏页换出要写磁盘干净的文件页可以直接丢被锁定的页根本不能动某些页有多个映射关系需要特殊处理。所以真实算法要结合脏位、访问位、页类型、引用计数综合打分权重是调优出来的远不是 FIFO 或 LRU 能直接套用的。第三个差距是预读与延迟分配。课堂模型永远等到缺页了才去取页真实系统会在顺序访问时预读后续几页把多次磁盘访问合并成一次。文件写入则采用延迟分配先记下要写等真正需要落盘时再分配物理块。这些优化都建立在大多数访问具有局部性这个统计规律上效果相当可观。理解了这一层再回头看练习里那道计算 EAT的题就知道它其实是在为理解这些工程手段做铺垫——没有那些数字上的对比你不会意识到缺页代价有多高。我个人在把课堂练习做完之后习惯拿一个小程序去实测一下缺页开销一个循环按顺序访问大数组另一个循环按步长跨越访问用系统提供的时间统计工具对比耗时。顺序访问的缺页次数远少于跨步访问耗时的差距能到十倍以上。这个亲手测出来的数字比任何教科书上的结论都让人印象深刻。最后再分享一个做题时的小习惯凡是遇到参数计算题我都在草稿纸角落写一行单位检查把每一步的数值和单位对齐最后确认结果量级合理再落笔。页式内存管理的题目算出 4MB 的页表是合理的算出 4GB 那肯定是哪里乘错了。这个方法帮我省下了不少回头检查的时间。至于置换算法的模拟画表格虽然慢但换来的是确定性比省下的那几分钟值钱得多。