【软考备考】存储管理详解：分页地址转换 + 页面置换缺页率，画张表格就得分（附 10 道练习）

操作系统第三篇讲存储管理。上午题在这块的考法非常实分页地址转换给个逻辑地址让你算物理地址——会拆分就是一分钟一题页面置换给个访问序列用 FIFO 或 LRU 算缺页次数——画对格子就得分。后者是全篇的重头戏也是失分重灾区FIFO 和 LRU 的画格子方法有本质不同很多人用 FIFO 的思路画 LRU 的格子一错错到底。这篇把两种画法彻底分开钉死。一、分页存储把内存切成等大的块分页式管理的思路把程序逻辑空间切成固定大小的页把内存物理空间切成同样大小的块程序运行时以页为单位随便往空块里装再用一张页表记录第几页装在第几块。于是逻辑地址天生是两段结构| 页号 | 页内地址偏移 |页大小决定页内地址占几位页 4KB 2¹² → 低 12 位是页内地址剩下的高位全是页号。地址转换口诀低位照抄高位查表。页内地址原封不动页号去页表里换成块号拼起来就是物理地址。例 1十六进制版真题风格页面 4KB页表中页号 3 对应块号 5逻辑地址 3D16H求物理地址。4KB 2¹²低 12 位正好3 位十六进制→ 页内地址是 D16H页号是 3。查表页 3 → 块 5。物理地址 5D16H。十六进制题根本不用算低三位照抄、高位换数。例 2十进制版页面 1KB1024 字节逻辑地址 2500求页号和页内地址。页号 2500 ÷ 1024 2整除 页内地址 2500 mod 1024 452快表TLB一句话页表本身也在内存里查一次页表就多一次访存太慢——于是把页表的热门条目放进 CPU 里的高速小存储快表先查快表命中就省一次访存。考点就一句快表的作用是加快地址转换。二、页面置换内存满了踢谁出去程序要访问的页不在内存 缺页得从外存调进来内存没有空块就得淘汰一个现有页面。踢谁三种算法FIFO先进先出踢最先进来的。维护一个队列队首最老LRU最近最少使用踢最久没被访问的。看每个页面的最近使用记录OPT最佳置换踢以后最迟才会用的。需要预知未来无法实现只是理论基准。三、缺页率计算画格子大法用同一个序列把两种算法各画一遍访问序列 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2物理块 3 个。FIFO队列画法——先进来的先滚蛋访问: 7 0 1 2 0 3 0 4 2 3 0 3 2 块1: 7 7 7 2 2 2 0 0 0 3 3 3 3 块2: 0 0 0 0 3 3 3 3 0 0 0 0 块3: 1 1 1 1 1 4 4 4 2 2 2 缺页: √ √ √ √ √ √ √ √ √ √逐列看访问 2 时内存满7,0,1淘汰最早进内存的 7访问 3 时淘汰 0此时 0 最早……缺页 10 次命中 3 次。FIFO 最易错的点命中时队列顺序不变。FIFO 记的是入场时间命中不动队伍——很多人手贱把命中的页挪到队尾那是 LRU 的动作安到 FIFO 头上全错。LRU栈式画法——刚用过的压到最上面每访问一页就把它挪到最顶部标记为最新其余往下压缺页时淘汰最底部最久没用的访问: 7 0 1 2 0 3 0 4 2 3 0 3 2 7 0 1 2 0 3 0 4 2 3 0 3 2 ← 栈顶最新 7 0 1 2 0 3 0 4 2 3 0 3 7 0 1 2 2 3 0 4 2 3 0 ← 栈底最久 缺页: √ √ √ √ √ √ √ √ √逐列走一遍关键几步访问 2第 4 列时内存满栈底是 7最久未用淘汰 72 置顶第 5 列访问 0命中但 0 要置顶从中间抽出来压到栈顶访问 4 时栈底是 2淘汰 2……缺页 9 次命中 4 次。LRU 的核心动作命中也要刷新栈序——最近用过的凭证更新了。这就是它和 FIFO 的本质区别FIFO 看入场时间命中不挪窝LRU 看最近使用命中必置顶。快速心算技巧格子画熟了可以提速FIFO心里维护一个队列缺页就队首出、新页进队尾LRU缺页找淘汰对象时回头看访问历史——内存里几页中谁上一次出现的位置最靠左谁就是最久未用淘汰它。四、Belady 异常FIFO 的怪癖直觉上物理块越多缺页应该越少但FIFO 可能物理块增加、缺页反而增多——这叫Belady 异常是 FIFO 的独家怪癖它只看入场时间会蠢到把常用页踢出去。LRU 和 OPT 没有这种异常。概念题常考一句话记住。五、10 道练习题基础题1~51.某系统页面大小为 4KB则逻辑地址中页内地址占 位。A. 4 B. 12 C. 16 D. 102.某系统页面大小为 1KB某逻辑地址为 2500十进制其页号和页内地址分别为 。A. 页号 2、页内地址 452 B. 页号 2、页内地址 476 C. 页号 25、页内地址 0 D. 页号 3、页内地址 5003.页面大小为 4KB页表中页号 3 对应的块号为 5则逻辑地址 3D16H 变换后的物理地址为 。A. 3D16H B. 53D16H C. D165H D. 5D16H4.FIFO 页面置换算法淘汰的页面是 。A. 最久未被使用的 B. 最早进入内存的 C. 以后不再使用的 D. 使用次数最少的5.LRU 页面置换算法淘汰的页面是 。A. 最早进入内存的 B. 随机选择的 C. 最近最长时间未被访问的 D. 刚刚被访问过的进阶题6~10带坑6.页面访问序列为 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5物理块为 4 个采用 LRU 算法缺页次数为 。A. 8 B. 10 C. 9 D. 127.同上题的访问序列和物理块数采用 FIFO 算法缺页次数为 。A. 8 B. 9 C. 10 D. 78.关于 Belady 异常下列说法正确的是 。A. LRU 算法会出现 Belady 异常 B. 所有页面置换算法都会出现 C. 物理块减少时出现的现象 D. FIFO 算法可能出现物理块增加、缺页次数反而增多的现象9.分页系统中引入快表TLB的主要目的是 。A. 加快地址转换速度减少访问内存中页表的次数 B. 扩大内存容量 C. 减少缺页次数 D. 实现虚拟存储10.某系统页面大小为 2KB逻辑地址为 16 位则页号占 位最多可有 页。A. 11 位2048 页 B. 16 位65536 页 C. 3 位8 页 D. 5 位32 页六、答案与详解1. B4KB 2¹² → 页内地址12 位。这类题就一步把页大小凑成 2 的幂。2. A页号 2500 ÷ 1024 2页内 2500 - 2×1024 452。选 B 的算成了 2500-2048 的余数…… 哦那正是 452——选 B 的 476 是拿 2500/1024≈2.44 后的 0.44×1024 凑的老老实实整除取余别用近似小数。3. D十六进制题不用换算4KB 页 → 低 3 位十六进制D16是页内地址照抄页号 3 查表换成块号 5 →5D16H。选 A 的是忘了换页号选 B 的把块号追加而不是替换。4. BFIFO 先进先出淘汰最早进来的和用没用过无关。5. CLRU 最近最少使用淘汰最久没被访问的。注意和 FIFO 划清界限一个看入场时间一个看最近使用。6. ALRU、4 块画栈式格子过程略建议自己画一遍验证缺页8 次序列中 4,3,2,1,5,2,1,5 这几次缺。本题和第 7 题是同一个序列两种算法放在一起就是让你体会算法不同、结果不同。7. C同序列 FIFO缺页10 次。坑这题常见错因有两个——一是命中后把页面挪队尾那是 LRU 的动作FIFO 命中队列不动二是凭LRU 总比 FIFO 好的直觉把两题答案写反本序列恰好 LRU8 次优于 FIFO10 次但这不是定律有的序列两者持平动手画格子才是正道。8. DBelady 异常是FIFO 独家物理块变多、缺页反而变多。LRU、OPT 都没有。记住FIFO 会背叛直觉这一句就够。9. A快表是页表的 Cache先查快表命中就省一次内存访问——加快地址转换。它不扩内存B、不减缺页C快表不管页面在不在内存、与虚拟存储无关D。10. D2KB 2¹¹ → 页内 11 位页号 16 - 11 5 位最多 2⁵ 32 页。选 A 的把页内位数当成了页号位数方向搞反。七、五句话带走地址转换低位照抄高位查表十六进制题低 3 位直接抄页号 逻辑地址 ÷ 页大小整除页内 取余FIFO 看入场命中不挪窝LRU 看使用命中必置顶缺页率画格子FIFO 用队列、LRU 用栈刚用的压栈顶、淘汰栈底Belady 异常FIFO 独家块多反而缺页多。下一篇预告操作系统收官篇——文件管理索引节点i-node里直接索引、一级间接、二级间接怎么算文件最大长度位示图怎么算第几个字第几位。至此操作系统高频考点全部通关。