段页式地址转换与页面置换算法｜软考软件设计师真题精讲
适用对象：备考软考中级「软件设计师」的同学
考查位置：上午综合知识·操作系统部分，稳定占 2~3 分
本文解决三件事：分页地址怎么算、段页式为什么查两次表、FIFO/LRU 缺页次数怎么手算又怎么用代码验证
目录
- 段页式地址转换与页面置换算法｜软考软件设计师真题精讲
- 一、概念先行：分页、分段、段页式的区别
- 1.1 段页式的地址结构与查表路径
- 1.2 三种存储管理方式对比
- 二、分页地址转换：2~3 分的必拿题型
- 2.1 两个必须记住的公式
- 2.2 十六进制下的速算法
- 2.3 真题演练：分页地址转换
- 三、页面置换算法：FIFO 与 LRU 的手算方法
- 3.1 三种算法的判定规则
- 3.2 手算全过程：3 个物理块，序列 1 2 3 4 1 2 5 1 2 3
- 3.3 用代码验证手算结果
- 四、真题精析：缺页次数与淘汰顺序
- 五、易错点清单（考前 5 分钟速看）
- 六、写在最后
存储管理是软考上午题里少有的「公式固定、套路固定、几乎必考」的模块。它不像数据结构那样需要现场推理，只要把地址转换和页面置换两条主线吃透，这部分分数基本是白送的。下面按「概念 → 计算 → 真题 → 易错点」的顺序拆开讲。
一、概念先行：分页、分段、段页式的区别
先明确一件事：分页是为了解决内存碎片，分段是为了贴近程序的逻辑结构。段页式则是两者的折中：先把程序按逻辑划分成段，再把每个段切成固定大小的页。
1.1 段页式的地址结构与查表路径
段页式的逻辑地址被切成三段：段号 S、段内页号 P、页内偏移 W。CPU 访存时需要查两次表：先用 S 查段表拿到该段页表的始址，再用 P 查页表拿到物理块号。
1.2 三种存储管理方式对比
| 对比项 | 分页 | 分段 | 段页式 |
|---|---|---|---|
| 地址空间 | 一维（页号+偏移） | 二维（段号+段内地址） | 二维逻辑、一维物理 |
| 划分依据 | 系统按固定大小切分 | 程序员按逻辑功能划分 | 先分段，段内再分页 |
| 表结构 | 一张页表 | 一张段表 | 段表 + 页表 |
| 碎片类型 | 内部碎片 | 外部碎片 | 内部碎片（页内） |
| 访存次数 | 2 次（查页表 + 访问） | 2 次 | 3 次（段表 + 页表 + 访问） |
记忆点：段页式=「段表找页表、页表找块号、偏移直接拼」，因为多查一次表，所以它最慢，但兼顾了共享保护和内存利用率。
二、分页地址转换：2~3 分的必拿题型
这是全部考点里最容易「秒杀」的：页内偏移量原封不动，只把页号换成物理块号。
2.1 两个必须记住的公式
- 页面大小为2 k 2^k2k字节时，逻辑地址的低k kk位就是页内偏移W WW，其余高位是页号P PP。
- 物理地址= ==物理块号b × b \timesb×页面大小+ ++页内偏移W WW。
2.2 十六进制下的速算法
页面大小取 4 KB 时，4 KB = 2 12 4\text{ KB} = 2^{12}4KB=212，十六进制一位代表 4 bit，所以低 3 位十六进制数是页内偏移，剩下的最高位就是页号。
以2C58H为例：
- 拆位：
C58是页内偏移，2是页号； - 查表：页号 2 对应的物理块号是 3；
- 拼接：把最高位
2换成3，偏移C58照抄，得到3C58H。
整套流程在考场上不超过 15 秒，比按字节运算快得多。
2.3 真题演练：分页地址转换
【题干】某分页存储管理系统中页面大小为 4 KB，某进程页表如下。若访问的逻辑地址为2C58H，则对应物理地址是（ ）。
| 页号 | 物理块号 | 状态位 |
|---|---|---|
| 0 | 5 | 1 |
| 1 | 8 | 1 |
| 2 | 3 | 1 |
| 3 | 7 | 1 |
A. 3C58H B. 5C58H C. 7C58H D. 8C58H
【解析】页面大小 4 KB 对应十六进制 3 位偏移，故2C58H中页号为2、偏移为C58。查表得物理块号3，替换最高位后物理地址为3C58H。答案选 A。
三、页面置换算法：FIFO 与 LRU 的手算方法
当访问的页面不在内存中，就会发生缺页中断；如果此时物理块已满，必须按算法淘汰一页。软考只考 FIFO 和 LRU，OPT 仅作为理论最优基准出现。
3.1 三种算法的判定规则
| 算法 | 淘汰谁 | 软考怎么考 |
|---|---|---|
| OPT（最优） | 未来最长时间不再被访问的页 | 只出现在「性能对比」的选择题里，不会让你手推 |
| FIFO（先进先出） | 最早进入内存的页 | 常与 Belady 异常一起考 |
| LRU（最近最少使用） | 过去最久未被访问的页 | 高频手算题，注意命中要刷新次序 |
3.2 手算全过程：3 个物理块，序列 1 2 3 4 1 2 5 1 2 3
手算的关键是「维护一个按最近使用时间排序的队列」：命中就把该页移到队尾，缺页就淘汰队首页。
从图上可以直接读出两个结论：整个过程缺页 8 次、命中 2 次；第一次淘汰发生在访问 4 时，被淘汰的是页面 1。
3.3 用代码验证手算结果
手算最容易在第七、八步数错，用十几行代码验证一下就稳了。下面这段模拟同时支持 FIFO 和 LRU，改一个参数就能对拍：
defsimulate(seq,frames,algo="LRU"):"""模拟页面置换：返回 (缺页次数, 被淘汰页面序列)"""mem,faults,evicted=[],0,[]forpageinseq:ifpageinmem:# 命中ifalgo=="LRU":mem.remove(page)mem.append(page)# LRU：命中后刷新为最近使用continue# FIFO：命中不改变进入次序faults+=1# 缺页iflen(mem)==frames:evicted.append(mem.pop(0))# 两者都淘汰队首页mem.append(page)returnfaults,evicted seq=[1,2,3,4,1,2,5,1,2,3]print("FIFO:",simulate(seq,3,"FIFO"))print("LRU :",simulate(seq,3,"LRU"))运行结果：
FIFO: (8, [1, 2, 3, 4, 1]) LRU : (8, [1, 2, 3, 4, 5])两者缺页次数都是 8，但淘汰顺序完全不同——这正是软考题喜欢设置的坑：题干问「缺页次数」时两个算法答案相同，问「第一个被淘汰的页面」时答案就分开了。
四、真题精析：缺页次数与淘汰顺序
【题干】系统为某进程分配 3 个物理块，初始为空，访问序列为1, 2, 3, 4, 1, 2, 5, 1, 2, 3。采用 LRU 算法时，缺页中断次数和被淘汰的第一个页面分别是（ ）。
A. 7，页面 1 B. 7，页面 2 C. 8，页面 1 D. 8，页面 3
【逐项推导】
| 步骤 | 访问页面 | 内存状态 | 结果 |
|---|---|---|---|
| 1 | 1 | 1 | 缺页，调入 |
| 2 | 2 | 1, 2 | 缺页，调入 |
| 3 | 3 | 1, 2, 3 | 缺页，调入 |
| 4 | 4 | 2, 3, 4 | 缺页，淘汰页面 1 |
| 5 | 1 | 3, 4, 1 | 缺页，淘汰页面 2 |
| 6 | 2 | 4, 1, 2 | 缺页，淘汰页面 3 |
| 7 | 5 | 1, 2, 5 | 缺页，淘汰页面 4 |
| 8 | 1 | 2, 5, 1 | 命中，刷新次序 |
| 9 | 2 | 5, 1, 2 | 命中，刷新次序 |
| 10 | 3 | 1, 2, 3 | 缺页，淘汰页面 5 |
缺页共 8 次，首次淘汰的是页面 1，答案选 C。
五、易错点清单（考前 5 分钟速看）
- 页面大小与位数换算：4 KB 对应 12 位、3 位十六进制；8 KB 对应 13 位、4 位十六进制，别把 10 进制位数套到十六进制上。
- FIFO 的命中不改变次序：命中只是「又访问了一次」，页面在内存中的进入顺序不变，这是与 LRU 最本质的区别。
- LRU 一定要刷新：命中后必须把该页移到队尾，否则后面几步全错。
- Belady 异常只出现在 FIFO：物理块增加反而缺页率上升，LRU 与 OPT 不会出现。
- 段页式访存次数是 3 次：查段表、查页表、访问数据，题目问「需要访问内存几次」时别答 2 次。
六、写在最后
段页式和页面置换这两块，看着公式多，实际题型高度固定：上午题基本就是「拆位查表算地址」和「数列推缺页」两种。把这篇文章里的两道真题自己手推一遍，再用上面的代码对拍一次，基本就不会再丢分。
后续我会继续按知识点整理软件设计师的真题拆解，下一篇写「文件系统与磁盘调度」，需要的同学可以关注专栏更新。
