2009年408统考的第26题操作系统内存管理。这道题我在复习时第一次做就栽了——不是不会算而是把“缺页次数”和“置换次数”混在了一起最后对答案时发现整道题的思路就偏了。后来我拿格子法在草稿纸上重新推了一遍才发现这种题目只要把“帧”的状态变化列清楚根本不会错。今天就把这题拆开讲透顺便把页面置换算法、Belady异常、考场速算技巧一次说清楚。1. 先把这道题“翻译”成人话1.1 题目原文与选项设置这道题在历年资料中的转述版本如下在一个请求分页存储管理系统中页面走向访问序列为1、2、3、4、1、2、5、1、2、3、4、5。若采用FIFO页面置换算法分配给进程的物理块数为3则缺页次数是多少A. 8 B. 9 C. 10 D. 12因为408统考的真题版权不公开网络和各种辅导资料里普遍使用这个“回忆版”。大部分资料给出的标准答案是B. 9。很多同学考场上真正纠结的其实不是FIFO算法本身而是算到第7、第8步时把自己绕晕了把“缺页次数”累加到了11、12甚至更高。这题表面上看是一道单纯的“置换算法模拟计算题”但它踩中的是操作系统内存管理里最核心的“请求分页”模型。如果你只背过“FIFO就是先进先出”这句话不把帧的变化过程走一遍大概率会错。所以下面我从最基础的概念开始重新过一遍。1.2 题干里几个容易理解偏差的词这题里几个关键术语需要先校准一下页面走向reference string进程访问页面的顺序。不是让你排序也不是让你数有哪些不同页面而是严格按照给出的1、2、3……顺序逐个判断。物理块frame内存中真正装页的位置。本题给了3个物理块表示内存同时最多容纳3个页面。缺页page fault访问的页面不在任意一个物理块中就需要从磁盘调入算一次缺页。置换replacement内存满了还要访问新页面时必须把某个旧页面踢出去腾地方。FIFO踢的是“最早进入内存”的那个页面。这里最容易搞混的是“缺页”和“置换”的区别。缺页不一定发生置换——前3次访问时物理块有空位直接装入即可只算缺页不算置换。我第一次算错就是觉得既然题目问“缺了几次页”应该从第4次才开始数直接把前3次给漏掉了。显然不对物理块初始为空时前3次访问全是缺页。2. 页面置换到底在解决什么问题一段恰到好处的背景2.1 为什么会有“置换”这一步你要理解这道题必须先理解虚拟内存里的按需分页demand paging。程序运行时CPU给的逻辑地址并不会直接对应内存物理地址而是要先通过页表把“页号”换成“物理块号”。如果这一页明明被程序引用了却不在内存里硬件会触发缺页中断由操作系统把磁盘上对应的页面调入内存。问题来了内存的物理块数是有限的。一个进程可能有好几百页但内存只给它3个块、4个块。当3个块都装满了进程又访问一个不在内存中的新页怎么办必须踢掉某一页给新页腾地方。那么踢谁这个“踢谁”的决策规则就叫页面置换算法。你可以把它理解为一家只有3张桌子的自习室。来的人页面必须坐桌子才能学习访问。桌子没空位时新来的人必须把某个人赶走。FIFO的规则很简单——谁来得最早就先赶谁走不管他是不是正在学习、是不是马上还要回来。这就是“先进先出”的直觉也是这道题的核心逻辑。2.2 FIFO、LRU、OPT三种算法到底差在哪先建立全局观不然你就算会做这一题换一道LRU的类似题还是容易懵。OPT最佳置换理论上的“上帝视角”——选未来最长时间不会被用到的页面淘汰。它缺页率最低但未来不可知所以只作为衡量标准不能真实现实系统。FIFO按进入内存的时间排队最早进来的先被淘汰。实现成本低用一个队列就行但“最早进来的”不一定“将来最没用”所以效果不算好。LRU最近最久未使用淘汰“最近最长时间没有被访问”的页面。它比FIFO更贴近局部性原理是考试最爱考的算法之一。这里要特别提一个直觉误区FIFO不是按“当前时刻哪个页面最久没被访问”来淘汰的而是按“哪个页面最早被装入”来淘汰的。一个页面哪怕刚刚被访问过只要它是最早装入的那一个FIFO照样会把它踢出去。后面的Belady异常就跟这一点直接相关。题外话生产环境里的近似LRU算法比如Clock算法都做了折中不会真去按访问时间精确排序因为那个代价太高了。但考试和概念题还是以这三种最经典算法为主。3. 逐步推演3个物理块下的FIFO全过程3.1 用表格手把手算一遍下面这张表是整个题的解体过程。我按照“第几步、访问哪个页、三个物理块的内容、命中还是缺页、累计缺页次数”五个维度来写。FIFO的特点在于“按装入顺序”排发生淘汰时踢的是队列最前面的那个页面。步骤访问页三个物理块内容按装入顺序结果累计缺页11[1, 空, 空]缺页装入122[1, 2, 空]缺页装入233[1, 2, 3]缺页装入344[4, 2, 3] 淘汰1缺页置换451[4, 1, 3] 淘汰2缺页置换562[4, 1, 2] 淘汰3缺页置换675[5, 1, 2] 淘汰4缺页置换781[5, 1, 2]命中792[5, 1, 2]命中7103[5, 3, 2] 淘汰1缺页置换8114[5, 3, 4] 淘汰2缺页置换9125[5, 3, 4]命中9逐行核对一遍第1步到第3步物理块从空到装满全部缺页没有置换。第4步访问4物理块已满FIFO看谁最早装进来的——是1所以淘汰1把4放进去。此时物理块里是4、2、3。注意它们的“装入先后”是234。第5步访问1最早装进来的是2淘汰2物理块变成4、1、3。第6步访问2最早装进来的是3淘汰3物理块变成4、1、2。第7步访问5最早装进来的是4淘汰4物理块变成5、1、2。到这里走到一个容易慌乱的地方第8步访问1物理块里有1命中第9步访问2物理块里有2命中。命中的时候FIFO的装入顺序完全不变。很多同学会把命中的页面重新视为“新装入”然后在下一步错误地先淘汰它。这是FIFO和LRU最关键的操作差异。第10步访问3此时物理块5、1、2里没有3需要置换。最早装入的是1淘汰1变成5、3、2。第11步访问4最早装入的是2淘汰2变成5、3、4。第12步访问5命中。累计缺页刚好9次。3.2 我在草稿纸上的“标记法”这种题你在考场上真的画表格吗画完整表格不是不行但12步还好如果出现20步的LRU题时间就紧张了。我复习时总结了一个简化写法非常顺手先写一行页号1 2 3 4 1 2 5 1 2 3 4 5下面画三个格子从左到右表示三个物理块但每个格子标注一个“进入时间序号”。访问某个页时先在三个格子里扫一眼如果命中直接什么都不改如果没命中就找到一个“进入时间序号最小”的格子把里面内容替换掉并把它的进入时间改成当前步骤序号。举个例子第8步访问1看到1在第5步被装进第二格所以现在它的进入时间序号是5不是1。可第10步淘汰1的时候为什么不看进入时间因为第8步“命中1”时没有改变1的进入时间1仍然是第5步装入的所以它是当前最早装入的一个。这就是FIFO与LRU在标记法上的唯一区别——FIFO标记“装入时间”LRU标记“最近访问时间”。这个标记法可以一口气写下来不用画大表格而且出错后容易检查。考场上如果时间紧张直接用它平时练习则建议老老实实画完整表格因为画表格能帮你理解每一步变化尤其是替换那一刻的队列状态。4. 换4个物理块后答案为什么“反直觉”了4.1 完整推演4物理块的情况我刚做这题时产生过一个大疑问物理块从3个增加到4个内存变多了缺页次数就算不减少也至少不该增加吧这题如果追问一句把物理块数改成4FIFO的缺页次数是多少结果会让你大跌眼镜。仍然是同样的访问序列1、2、3、4、1、2、5、1、2、3、4、5但这次分配4个物理块。按FIFO逐步推步骤访问页四个物理块内容按装入顺序结果累计缺页11[1, 空, 空, 空]缺页装入122[1, 2, 空, 空]缺页装入233[1, 2, 3, 空]缺页装入344[1, 2, 3, 4]缺页装入451[1, 2, 3, 4]命中462[1, 2, 3, 4]命中475[5, 2, 3, 4] 淘汰1缺页置换581[5, 1, 3, 4] 淘汰2缺页置换692[5, 1, 2, 4] 淘汰3缺页置换7103[5, 1, 2, 3] 淘汰4缺页置换8114[4, 1, 2, 3] 淘汰5缺页置换9125[4, 5, 2, 3] 淘汰1缺页置换10答案是10次。物理块从3个增加到4个缺页次数反而从9次增加到了10次。这是FIFO算法最著名的“黑点”也是408操作系统里一个必须掌握的知识点——Belady异常。4.2 Belady异常的本质Belady异常指的是在采用FIFO置换算法时分配物理块数增加缺页次数反而增加的异常现象。为什么4个块会比3个块的缺页次数还多核心原因要从FIFO的淘汰逻辑说。FIFO总是淘汰最早装入的内存页面完全不参考“未来会不会被访问”。当物理块是4个时前4次访问把1、2、3、4装满第7次访问5时淘汰的是1。接着第8、9、10、11次连续访问1、2、3、4而这时每个新访问页都会导致一次缺页因为前一步刚刚把其中几个淘汰了。也就是说FIFO在4个块下形成了一种“轮流把老页面赶走马上又要把它们请回来”的死循环。反观LRU和OPT它们都有“栈式性质”——分配更多物理块时缺页次数一定不增加。LRU按“最近访问时间”淘汰内存框更多时最近被访问的页面更容易留在里面不会出现物理块多了反而频繁把刚用过的页面踢走的情况。考场上一旦选项里有“Belady异常只可能出现在FIFO算法”这种判断你要能立刻联想到这题。反过来如果题干说“物理块为4缺页次数为10”你要能反推出这基本是在考FIFO的Belady异常。我在复习时记了一句口诀来避免自己再懵FIFO看“谁先来”LRU看“谁最久没来”OPT看“谁最后才来”。Belady异常只跟FIFO绑在一起。5. 这道题背后的408命题风格看着是计算题考的是概念5.1 别只把它当成算术题很多人以为这种题难在“算”。其实不算难。它真正想考的是你能不能把“请求分页、页表、缺页、置换”这一整条链路串起来。与这题配套的知识点至少还有三个页表项组成页表里有多少位用来映射物理块号、多少位是状态位/访问位/修改位。地址转换过程逻辑地址 → 页号 页内偏移 → 查页表 → 物理块号 页内偏移 → 物理地址。两级页表/多级页表为什么需要分级页目录表怎么定位。比如2009年同卷的其他题目要么考地址变换要么考文件系统的索引结构。第26题选择了“缺页次数计算”这种看起来偏计算的考法但它的提法是“内存管理”那就要你快速定位到请求分页而不要联想到连续分配、分区管理那些模型否则从一开始就会选错方向。5.2 考场上的三个判断技巧我把自己做这类题踩过的坑总结成三条考场上非常实用第一先看初始状态。按大多数408题目的隐含假设页面初始时内存为空。如果题目明确说“内存已经装入某些页”则这些页不算缺页。每一份试卷的表达可能不完全相同做题前先花五秒确认不要默认。第二命中时不要动“进入时间”。这在FIFO题里太重要了。如果某页面在访问序列里第二次出现且在物理块内那么“命中”并不改变它的装入顺序下一个被淘汰的还是它。只要你在这一步把命中页的优先级往后挪了之后每一步都会错。第三替换只看“现在的物理块”不是看“页表”。有些同学会去翻页表的有效位、状态位然后自己脑补“这个页在磁盘上已经失效了”于是提前淘汰它。但是页面置换算法操作的对象是物理块内容不是页表项。页表项只是记录映射关系的“账本”算法是在内存资源有限时决定把哪个物理块腾出来。先有物理块被淘汰再有页表项的对应更新不要搞反因果。5.3 实战建议页面置换题怎么练才扎实我自己的练习方法是把常见的三种算法FIFO、LRU、OPT放在同一张表里对同一访问序列各算一遍然后对比缺页次数。推荐一个百试不厌的序列7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1物理块数3。这个序列在很多经典教材里出现过三块下OPT缺页次数最少FIFO最多LRU居中。你亲手把三种算法的帧状态变化写一遍比背任何结论都管用。再进阶一步试试把FIFO的物理块数改成4看看是否出现Belady异常再把LRU的物理块数改成4验证LRU单调性。这样你就能直观感受到为什么操作系统的真实实现更倾向用LRU近似算法如时钟算法而不是简单FIFO。如果备考时间比较紧我建议至少做到看到任意访问序列和置换算法能在两分钟内写出缺页次数并能准确描述每一步发生了“缺页装入”“缺页置换”还是“命中”。这个能力在选择题和大题里都是基本功。最后再分享一个我到考前的习惯遇到这种模拟题我不直接算答案而是先在题目旁边用一句话写出该算法的淘汰规则比如“FIFO淘汰最早进入的页面”。写完之后再往下算。看起来多花十秒钟但实际上它能拦住绝大多数因为手滑而导致的低级错误。我自己考场上就是靠着这个习惯把这道题的确认时间压缩到了四十秒以内。包含置换的模拟题每一步都写清楚才是最快的解法。