操作系统第三章的内存管理是很多人复习到这一章时最容易卡壳的地方。前面进程调度那几章还能靠直觉蒙一蒙到了内存管理地址转换、页表计算、页面置换、有效访问时间几乎每道大题都要求你拿起笔一步一步算算错一步后面全崩分数直接掉档。我把汤小丹版、王道版、慕课版以及几本校内讲义里第三章的大题做了系统梳理从连续分配一路捋到虚拟内存再把手算页面置换、多级页表地址拆分、EAT 估算这些反复出现的题型拆成固定套路。这篇内容适合两类人。一类是正在准备操作系统期末或者考研 408 的同学想找一份能直接照着练的大题清单不用再自己从零归纳另一类是把这门课丢了好几年、现在因为工作或者项目又需要重新捡起内存管理概念的人比如做嵌入式、写底层驱动、优化程序内存占用的工程师。文章里每道例题都给了完整解法公式的来源、参数为什么这么取、单位怎么换算我尽量讲透不搞“记住就行”那一套。需要提前说明的是内存管理的大题看着五花八门其实出题人翻来覆去就在四个框里转地址转换、页面置换、有效访问时间、动态分区分配。把这四个框吃透剩下的就是套数据。下面我按“先讲原理再上例题”的顺序展开例题都是教材和真题里出现过的高频模型可以当作复现模板。1. 内存管理大题的考点全景与解题思路拆解1.1 第三章到底在考什么教材里第三章的编排基本是一条主线加三个层次。主线是“程序运行时不必把全部代码和数据一次性装进内存也能正常跑”也就是虚拟内存这个核心思想。三个层次是连续分配、离散分配分页和分段、请求分页下的虚拟内存。所有大题都从这三层里长出来理解了这条线你就不会觉得知识点是散的。连续分配这一层考的是动态分区分配算法首次适应、最佳适应、最坏适应、邻近适应以及分区回收时怎么和前后的空闲分区合并。题目通常给你一串作业申请和释放序列让你画出内存分区图算空闲区大小。这类题不难但特别考验细心边界画错一个数字后面全错。离散分配这一层是重头戏分页和分段。分页的核心是页号加页内偏移的地址拆分以及页表项、多级页表的容量计算。分段的核心是段号加段内偏移还要和分页做对比。这一层最常见的问法是给逻辑地址位数和页大小问页内偏移几位、页表多少项、页表占多少字节、能不能放进一个页面。虚拟内存这一层考页面置换算法和有效访问时间。FIFO、LRU、OPT、CLOCK 的手工模拟是必考项EAT 计算则是把缺页率和访问时间结合起来考你单位换算和公式理解。1.2 四类基本盘与出题套路我把近几年见过的第三章大题归成下面这张表你可以对照自己手里的卷子看看每次遇到的到底是哪一类。分类的意义在于每类题的计算步骤是固定的练熟之后读题到动笔不超过三十秒。题型典型问法核心工具最容易丢分的地方地址转换给逻辑地址求物理地址、拆分页号页内偏移进制转换、页表查表偏移位数算错、十六进制与十进制混用页表容量一级/多级页表占多少字节、能否放一页项数乘表项大小忘记页表项也要对齐、级数拆分错误页面置换给引用串求缺页次数和缺页率FIFO、LRU、OPT 模拟表命中判断漏看、替换顺序写反有效访问时间给命中率求 EAT、求缺页率EAT 公式、单位换算毫秒微秒纳秒混算、公式漏项这张表不是让你背是让你形成条件反射。看到“引用串”三个字脑子里就该弹出置换模拟表看到“有效的访问时间”第一反应就是分清 TLB 和请求分页两套公式。很多同学失分不是因为不会而是因为把两套公式套串了比如在请求分页题里用了 TLB 的公式结果怎么算都对不上答案。1.3 为什么这些题值得反复手算有人会问这些计算现在都有工具为什么还要手算。我的体会是手算的过程其实是在逼你理解地址转换的层级关系。你自己动手拆一次 32 位地址、把页号拆成两段 10 位你对多级页表为什么能节省空间的感受比看十遍文字描述都深。工作里排查内存问题时能一眼看出“这个地址落在第几级页表的哪一项”靠的就是这种被大题虐出来的直觉。所以我的建议是第三章的大题至少要手写三遍。第一遍照着答案抄理解每一步第二遍盖住答案自己算卡住了再翻第三遍掐时间做模拟考场节奏。三遍下来这类题基本就变成送分题了。2. 核心计算题型的细节拆解与手算要点2.1 分页与分段的地址转换地址转换的底层逻辑只有一句话逻辑地址等于页号乘以页大小加页内偏移而页内偏移就是逻辑地址对页大小取模。页大小是 2 的整数次幂时这一步可以纯靠位运算完成根本不用做除法。以 4KB 页大小为例4KB 等于 2 的 12 次方所以页内偏移固定占低 12 位。一个 32 位逻辑地址低 12 位是偏移剩下高 20 位就是页号。页号最多有 2 的 20 次方个也就是一百多万个页面。如果逻辑地址是 0x00003A2C低 12 位 0xA2C 是偏移高 20 位 0x00003 是页号这个拆分不用计算器就能做。分段就不一样了。分段是按程序的逻辑结构划分的每个段长度不固定所以逻辑地址是段号加段内偏移段内偏移的位数取决于该段的最大长度。这就带来一个经典对比分页对用户透明页大小固定会产生内部碎片分段对用户可见段大小可变会产生外部碎片但便于共享和保护。考试里经常让你比较这两者的区别答的时候要点到“是否对用户可见”“碎片类型”“地址空间维度”这几个层面。多级页表的出现是为了解决页表本身太大放不进内存的问题。32 位地址、4KB 页、4 字节页表项一级页表要占 2 的 20 次方乘 4 字节等于 4MB太大。拆成两级页号 20 位分成 10 位加 10 位每级页表是 2 的 10 次方乘 4 字节正好 4KB一页就能装下。这个“每级页表刚好一页”的设计不是巧合而是当初设计时特意对齐的结果考试里也常拿这个数字做文章。提示拿到地址转换题先确认三件事——逻辑地址位数、页大小、页表项大小。这三个数决定了后面所有计算任何一个看错整道题白做。2.2 页面置换算法的手工模拟页面置换的手工模拟是最耗时间但也最稳的题型因为步骤固定只要不出低级错误分数一定拿得到。我在草稿纸上画表横向排引用串的每一个页号纵向排物理块按顺序填命中打对勾缺页打叉并记下被替换的页号最后数叉的数量。FIFO 先进先出思路最直白把内存里待得最久的那个换出去。可以用一个队列维护。它的隐患是可能出现 Belady 异常也就是给的物理块越多缺页次数反而越多这一点后面单独说。LRU 最近最久未使用往前看谁最长时间没被访问就换谁。手工模拟时每次命中或替换后都要把被访问的页移到“最近使用”的一端顺序维护不能偷懒否则很快就算乱。OPT 最佳置换往后看谁在未来最长时间内不会被访问就换谁。它是理论上的最优解实际无法实现因为需要预知未来但考试特别喜欢考它用来做缺页次数的下界参照。CLOCK 时钟算法是 LRU 的近似实现给每页一个使用位指针循环扫描遇到使用位为 1 就清零并跳过遇到 0 就替换。改进型 CLOCK 再加上修改位优先淘汰“未使用且未修改”的页。这两类算法手工模拟时要特别注意指针当前位置画一个圈把扫描顺序标出来会清楚很多。算法判断依据是否可实际实现典型缺页表现FIFO进入内存的先后顺序可以有 Belady 异常LRU最近一次访问的时间可以代价高无 Belady 异常OPT未来访问的时间不可以缺页最少作基准CLOCK使用位加指针扫描可以接近 LRU2.3 有效访问时间 EAT 的三种典型考法有效访问时间这类题公式本身不难难在考法有三种很容易套错。我把它拆成三套模型你对号入座就行。第一套是纯分页带快表 TLB 的。设 TLB 查找时间为一内存访问时间为 tTLB 命中率为 a。命中时先查 TLB 拿到物理块号再访问一次内存取数据耗时加 t未命中时查 TLB 白跑一趟要再访问内存查页表拿到物理块号最后再访问一次内存取数据耗时加 2t。所以 EAT 等于 a 乘以括号加 t再加 1 减 a 乘以括号加 2t。第二套是请求分页不考虑 TLB 的。设缺页率为 p内存访问时间为 m缺页处理时间为 s这个 s 通常包含了缺页中断、换页、重新执行指令的全部开销。那么 EAT 等于 1 减 p 乘以 m加 p 乘以 s。有的教材把 s 写成“缺页中断服务时间加内存访问时间”具体以你用的教材为准做题时看清题目给的时间到底含不含重新访问。第三套是二级页表或者多级页表下没有 TLB 的情况。访问一个数据要逐级查页表每级页表本身都在内存里一级页表查一次、二级页表查一次最后取数据一次总共三次内存访问。有 TLB 时再按命中率加权。单位换算是这类题的重灾区。毫秒、微秒、纳秒之间是 1000 倍关系1ms 等于 1000μs 等于 10 的 6 次方 ns。很多题目故意把缺页处理时间给成 8ms访问时间给成 100ns你要是忘了换算答案会差六个数量级一眼就能看出错。2.4 动态分区分配与 Belady 异常动态分区分配的手工题画一条从低地址到高地址的内存条把已分配区标上作业号和大小空闲区标上大小。分配时按算法找位置首次适应从头找第一个够大的空闲区最佳适应找能满足要求的最小空闲区最坏适应找最大的空闲区邻近适应从上次分配结束的地方接着找。回收是这题的隐藏难点。释放一个分区后要判断它的前后是不是也有空闲区有就合并。合并有三种情况和前一个空闲区合并、和后一个空闲区合并、和前后都合并。画图的时候把合并后的新空闲区大小重新标出来别保留两个相邻的空闲区那是最常见的错误。Belady 异常专门考 FIFO。经典反例是引用串 1、2、3、4、1、2、5、1、2、3、4、5。我给三帧和四帧分别模拟一遍。三帧时缺页序列是第一次装入 1、2、3、4 缺四次随后 1、2 各缺一次5 缺一次接着 3、4 各缺一次总共九次缺页。四帧时前四次仍然是缺页1、2 命中5 开始缺之后 1、2、3、4、5 每一轮都缺总共十次缺页。帧数从三涨到四缺页次数反而从九涨到十这就是 Belady 异常。它说明 FIFO 不满足栈式置换的性质而 LRU 和 OPT 都属于栈式算法不会出现这个问题。注意Belady 异常只在 FIFO以及类似的非栈式算法上出现答题时千万不要说 LRU 也有 Belady 异常这是送命题。3. 完整大题实操演练从读题到落笔3.1 例题一两级页表地址转换题目某系统按字节编址逻辑地址 32 位页面大小 4KB页表项大小 4 字节采用两级页表页号高位部分用于一级页表低位部分用于二级页表。求页内偏移位数、两级页表各有多少项、每级页表占多少字节、每级页表能否刚好放入一个页面。先是页内偏移。页面大小 4KB 等于 2 的 12 次方所以页内偏移占 12 位。这一步直接写不需要推导但要写清“因为 4KB 是 2 的 12 次幂”把理由摆出来改卷老师看的是过程。再是页号位数。逻辑地址 32 位减去偏移 12 位页号占 20 位。两级页表把 20 位拆成两段常见拆法是 10 位加 10 位。一级页表项数等于 2 的 10 次方也就是 1024 项二级页表同样是 1024 项。接着算容量。每级页表 1024 项乘 4 字节等于 4096 字节也就是 4KB。而这个系统的页面大小正好是 4KB所以每级页表刚好占用一个页面。这也解释了两级页表为什么选 10 加 10 的拆法如果拆成 8 加 12一级页表 256 项占 1KB二级页表 4096 项占 16KB二级就装不进一页了需要三级。所以“每级页表刚好一页”是设计目标反过来决定了位数拆分。这道题的价值在于它把“为什么是 10 加 10”这个原理摆在明面上。你理解了这一层再遇到 48 位地址、8 字节页表项、四级页表的 x86-64 模型就能自己推。48 位去掉 12 位偏移还剩 36 位页号拆四段每段 9 位每级 2 的 9 次方即 512 项512 乘 8 字节等于 4KB又是一页。规律是一致的页号位数除以级数每级页表大小对齐到一页。3.2 例题二页面置换算法综合模拟题目给引用串 1、2、3、4、1、2、5、1、2、3、4、5物理块分别为 3 和 4分别用 FIFO 算法模拟求缺页次数指出是否出现 Belady 异常。三帧模拟逐步展开。第一页 1内存空缺页装入 1。第二页 2缺页装入 2。第三页 3缺页装入 3此时内存为 1、2、3。第四页 4缺页按 FIFO 换出最早的 1内存变 4、2、3。第五页 1缺页换出 2内存变 4、1、3。第六页 2缺页换出 3内存变 4、1、2。第七页 5缺页换出 4内存变 5、1、2。第八页 1命中。第九页 2命中。第十页 3缺页换出 1内存变 5、3、2。第十一页 4缺页换出 2内存变 5、3、4。第十二页 5命中。数下来缺页九次。四帧模拟重新走一遍。前四页 1、2、3、4 依次缺页装入内存满。第五页 1 命中第六页 2 命中。第七页 5 缺页换出最早的 1内存变 2、3、4、5。第八页 1 缺页换出 2内存变 3、4、5、1。第九页 2 缺页换出 3内存变 4、5、1、2。第十页 3 缺页换出 4内存变 5、1、2、3。第十一页 4 缺页换出 5内存变 1、2、3、4。第十二页 5 缺页换出 1内存变 2、3、4、5。缺页十次。对比结果三帧九次缺页四帧十次缺页物理块增加而缺页增加Belady 异常成立。这道题的答题关键是表格要画全每一行都标清楚命中还是缺页替换了谁。只写最终数字是拿不到过程分的这类题通常是按步给分。如果同一组数据用 LRU 和 OPT 做结果会明显不同。LRU 下四帧不会比三帧差OPT 的缺页次数是最少的。你可以自己动手把这两个算法也模拟一遍作为对照练习体会三者的差别。3.3 例题三TLB 与 EAT 计算题目某系统采用分页存储管理快表 TLB 的查找时间为 10ns内存访问时间为 100nsTLB 命中率为 98%不考虑缺页情况求平均有效访问时间。套第一套公式。命中时先查 TLB 花 10ns拿到物理块号后访问内存一次花 100ns合计 110ns。未命中时查 TLB 白花 10ns然后访问内存查页表花 100ns 拿到物理块号再访问内存取数据花 100ns合计 210ns。EAT 等于 0.98 乘 110 加 0.02 乘 210等于 107.8 加 4.2等于 112ns。答案写 112ns过程要写清 110 和 210 是怎么来的。这里有个细节要提醒。有的教材把 TLB 查找和内存访问做成并行也就是命中时耗时为 max 或者直接等于内存访问时间加一个小量公式会有出入。做题时以题目和教材的定义为准如果题目只说“TLB 命中率为 98%访问内存时间 100nsTLB 访问时间 10ns”没有特别说明就按上面这套串行的来。3.4 例题四请求分页 EAT 与缺页率题目某请求分页系统内存访问时间为 100ns缺页率为 1%缺页处理时间含中断处理、页面调入、重新执行为 8ms求平均有效访问时间。先统一单位。8ms 等于 8 乘 10 的 6 次方 ns也就是 8,000,000ns。缺页率 1% 即 0.01。套第二套公式。不命中缺页时正常访问内存 100ns。命中缺页时要花缺页处理时间 8,000,000ns再加上重新访问内存的 100ns所以这一项是 8,000,100ns。EAT 等于 0.99 乘 100 加 0.01 乘 8,000,100。算一下0.99 乘 100 等于 99ns0.01 乘 8,000,100 等于 80,001ns两者相加等于 80,100ns约等于 80.1μs。这道题最想让你体会的是缺页的代价有多大。正常访问才 100ns缺页处理要 8ms差了五个数量级。哪怕缺页率只有 1%平均访问时间也从 100ns 被拉到 80μs慢了八百倍。这也解释了为什么真实系统里缺页率要压到极低页面置换算法和内存分配的调优意义全在这里。提示请求分页题的 8ms 是否含重新访问内存各教材定义不同。题目如果明确写“缺页处理时间”一般理解为完整开销如果写“缺页中断服务时间加页面调入时间”再单独加上重新访问的 100ns。4. 常见问题与排查技巧实录4.1 高频丢分点速查表把下面这张表贴在书桌前考前扫一遍能挡掉大部分低级失误。症状根因现场处理办法页内偏移位数算错没把页大小转成 2 的幂先把页大小写成 2 的 n 次方n 就是偏移位数页表容量少一个数量级项数算错或漏乘表项大小项数等于 2 的页号位数次方再乘表项字节数置换题命中判断错只看当前页号没看内存中是否有每次填表前先在当前内存列里找一遍EAT 结果差六个数量级毫秒没换成纳秒统一化成纳秒再算动态分区回收没合并只改了空闲区没看相邻释放后立刻检查左右邻居Belady 异常答错算法把 LRU 也算进去只有 FIFO 这类非栈式算法会出现4.2 手算模拟的偷懒技巧与验算方法置换模拟写起来费时间我总结了两个小技巧。第一个是把引用串先抄一遍在每个页号下面用符号标记是否是新出现的页这样能快速估一个缺页下界。第二个是维护内存列的排列顺序LRU 和 FIFO 的排列顺序都有明确含义FIFO 按进入顺序排LRU 按最近访问时间排排对了替换对象一目了然。验算方法也有讲究。缺页次数的下界是这个引用串里不同页号的个数上界是引用串长度。你算出来的数如果小于不同页号数肯定错了如果等于引用串长度说明一次都没命中除非引用串里没有重复页号否则也可疑。用这个区间卡一下能挡掉粗心错。EAT 题可以用量级感验算。正常内存访问是百纳秒级缺页是毫秒级所以只要缺页率不是特别小EAT 就会被拉到微秒甚至毫秒级。如果你算出 EAT 只有几十纳秒还带着缺页那一定是公式套错了或者单位没换。4.3 答题格式与卷面细节大题阅卷是按步骤给分的所以过程比结果重要。我的习惯是每道题分三步写先列已知条件和要求解的未知量再写公式并说明公式来源最后代入数据给出结果并带单位。这样即便最后数字错了前面的公式分也能拿到。画表的时候用直尺横向的引用串和纵向的物理块对齐命中打勾、缺页打叉被替换的页号写在旁边。地址转换题要在草稿上把二进制位数标出来低多少位是偏移、高多少位是页号标清楚再换算成十六进制。单位和下标别省。物理块号、页号、页框号这些术语在不同教材里叫法不同答题时统一用题目里的叫法不要自己造词。比如题目说“页框”你就别写成“物理块”虽然意思一样但阅卷老师可能扣分。5. 复习节奏与错题整理5.1 一周冲刺安排如果只剩一周我建议这样排。第一天把地址转换和多级页表容量计算练熟做五道不同参数的题重点是页号位数拆分。第二天专攻页面置换FIFO、LRU、OPT、CLOCK 各模拟三组数据把 Belady 异常的例子默写一遍。第三天集中练 EATTLB 和请求分页两套公式各做三道专门练单位换算。第四天做动态分区分配的分配和回收画图为主。第五天开始做整卷模拟把第三章和其他章节混在一起做训练在综合卷里快速识别题型的能力。第六天整理错题把这一周做错的题重做一遍。第七天只看错题本和公式表不再做新题保持手感就行。这个安排的核心逻辑是前四天按题型分块突破后三天转向综合和纠错。分块阶段追求正确率综合阶段追求速度和识别速度。别一上来就做整卷那样容易在还没掌握方法的时候就被打击信心。5.2 错题本怎么记才有用我见过很多人的错题本就是抄题目抄答案抄完再也不看基本没用。有效的错题本应该记三样东西这道题我第一次错在哪一步、这一步为什么错、下次遇到同类题怎么避免。比如“页表容量题漏乘表项大小”原因是我只算了项数没算字节数下次先把公式写全再代数据。每道错题旁边标上题型标签比如“地址转换”“置换”“EAT”复习时按标签归类看。同一个标签下错了两三次的说明这个题型的方法你没真正掌握要回去重看原理而不是继续刷题。错题本不用记太多一章有个十道八道典型错题就足够了。关键是把每道错题吃透做到看到同类题能立刻想起自己当初错在哪这种警觉性比多刷十道新题都管用。最后再分享一个我在带同学复习时反复强调的点内存管理的大题画图永远比心算稳。不管是地址拆分、页表层级还是置换过程落在纸上就成功了一半。考场上时间为王但省下的那几秒画图时间往往就是你避开错误的几秒。