1. 先建一张题型地图内存管理大题就这六类问法内存管理这一章教材上理论铺得最开但落到卷子上大题的形状其实非常固定。你翻十套卷子会发现它们反反复复就在问那六件事地址怎么变、页表占多大、页面怎么换、缺页率怎么算、分区怎么分、工作集怎么求。真正让人丢分的从来不是没学过而是同一个知识点换一种问法就认不出来或者算到一半被单位、进制、表格抄写搞崩。我自己的复习顺序是先归类再刷题。归类就是把这六类题各自的输入—工具—输出写在一张纸上做题时先判断这是哪一类再调用对应模板。这个动作看着笨但比无脑刷五十道题管用得多因为考场上最怕的是这道题我没见过而归类之后你会发现所谓的新题只是老题换了个外壳。1.1 六类题型的核心公式速查下面这张表是我自己整理并反复修订过的版本左边是题型中间是核心工具右边那一列特意写了最容易翻车的地方——这一列才是这张表的真正价值所在。题型典型问法核心工具/公式高频翻车点动态分区分配给空闲分区表和作业序列画分配过程首次适应、最佳适应、最坏适应、循环首次适应回收时的相邻空闲区合并分页地址变换给逻辑地址求物理地址页号 逻辑地址 / 页面大小偏移 逻辑地址 mod 页面大小十六进制拆位、页号起始值页表尺寸与多级页表求页表占用多少字节项数 2^(页号位数)页表大小 项数 × 项长忘记乘进程数、项长取值页面置换算法给引用串求缺页次数/缺页率FIFO、LRU、OPT、Clock首次访问是否计缺页、表格抄错列有效访问时间求 EAT命中率×单次时间 未命中率×多次时间再叠加缺页率单位不统一、缺页时间是否含访存工作集与抖动求工作集大小、判断是否抖动WS(t, Δ)可用页框数对比窗口定义按次数还是按时间把这张表背下来意义不大真正要做的是每一类都亲手推演三五道直到你能在不看答案的情况下自己解释为什么这一步要这么做。比如最佳适应为什么容易产生小碎片、两级页表为什么能省空间、LRU 为什么不会被 Belady 异常影响这些问题想通了题目怎么变形都不怕。1.2 为什么这些题总在细节上丢分说个很实在的观察内存管理大题的难度是台阶型的——看答案觉得简单自己动手就错。原因通常集中在这几处。第一是单位混乱。有效访问时间那道题内存访问给的是纳秒磁盘访问给的是毫秒缺页率给的是小数或百分数稍不留神就是三个数量级的偏差。我踩过最典型的一次是把 8ms 直接代进以 ns 为单位的公式算出 EAT 等于八千多纳秒还觉得答案挺合理。第二是进制转换。十六进制地址和页面大小的关系是天然的对齐关系页面大小是 4KB 时末三位十六进制数就是页内偏移前面是页号这个规律一旦掌握拆地址就是两三秒的事反过来如果硬算十进制就等着出错。第三是表格推演过程中的抄写错误。置换算法题给十几个引用数字要在三四行里反复比对手写时漏一个数、抄错一列后面全盘皆错而这类题通常不给分步骤的宽容度。提示置换算法题一律用逐列推进的表格不要用文字叙述过程。表格每一列对应一个引用数字命中就在格子里打勾缺页就写下当前页框内容这样即使最后结果错了过程分也拿得到。还有一类隐形的坑是概念前提被忽略。比如题目没写采用请求分页你就不能默认有缺页题目前面给的是页表项 4 字节你就不能用 2 字节去算题目问页表占用你要先判断是问单个进程的还是整个系统的。这些前提通常在题干第一句或者一句不起眼的括号里读题时用笔圈出来是值得的。2. 动态分区分配大题三种算法的手算差异与空闲分区表怎么画连续分配管理方式里的动态分区分配是内存管理章节里最动手的一类题。它不需要复杂公式但要你在纸上模拟一个分配器一步步更新空闲分区表。这类题的评分点非常明确分配位置对不对、剩余分区大小对不对、要不要合并——三项全对才给满分。2.1 题目给的是什么你要画什么题目的标准形态是这样的给一张空闲分区表每项包含起始地址和大小分区按地址递增排列再给一个作业序列每个作业请求若干大小的内存要求画出每次分配后的空闲分区表或者计算某次分配之后剩余的碎片大小。手算的时候我建议用下面这个格式横着一行写清楚作业—请求大小—分配到的位置—剩余情况比画方块图快得多也清楚得多。关键字在于分配之后空闲分区表要重新按地址排序这一步很多人会漏。2.2 一个例子跑通三种算法假设初始空闲分区表如下地址递增序号起始地址大小1100K50K2200K40K3300K20K4400K60K作业序列A 请求 30KB 请求 45KC 请求 15K。首次适应从低地址开始找第一个够大的分区。A(30K)100K 处的 50K 够 → 分配 30K剩 20K起始地址变为 130K。B(45K)130K 处的 20K 不够200K 处的 40K 不够300K 处的 20K 不够400K 处的 60K 够 → 分配 45K剩 15K起始地址 445K。C(15K)回到低地址130K 处的 20K 够 → 分配 15K剩 5K起始地址 145K。最终空闲区145K/5K、200K/40K、300K/20K、445K/15K。最佳适应每次找容量最小且足够的分区。这里必须注意最佳适应是把空闲区按容量递增排序来找的不是按地址。A(30K)候选 50K、40K、60K20K 不够最小够大的是 40K → 分配在 200K 处剩 10K起始地址 230K。B(45K)候选 50K、60K、10K不够最小够大的是 50K → 分配在 100K 处剩 5K起始地址 145K。C(15K)候选 10K 不够、5K 不够、20K 够、60K 够 → 最小够大是 300K 处的 20K → 全部用掉该分区从表中消失。最终空闲区145K/5K、230K/10K、400K/60K。最坏适应每次挑最大的分区切。A(30K)最大的是 400K 处 60K → 分配 30K剩 30K起始地址 430K。B(45K)候选 50K、40K、20K、30K → 最大是 100K 处的 50K → 分配 45K剩 5K起始地址 145K。C(15K)候选剩下的 40K、20K、30K → 最大是 200K 处的 40K → 分配 15K剩 25K起始地址 215K。对同一个作业序列三种算法给出了三套完全不同的空闲分区表。这就是为什么这类题必须老老实实按算法规则走凭感觉分配必错。2.3 内存回收的四种相邻情况分配会做回收更容易错。当一个作业释放它占用的分区时要看它的前后是否有空闲分区一共四种情况情况处理方式前后都不空闲单独成一个新空闲区前空闲、后占用与前面的空闲区合并起始地址取前者的前占用、后空闲与后面的空闲区合并大小相加前后都空闲三块合并成一块大小是三者之和注意合并后的起始地址一律取地址较小的那块大小是相加中间不能留空洞。很多同学会在前后都空闲时只合并一侧结果空闲区表里出现两块本该连着却分开的记录。2.4 内部碎片与外部碎片的判定连续分配的两种典型问题内部碎片和外部碎片。固定分区会产生内部碎片——分区内部分配出去但用不完的部分动态分区会产生外部碎片——分区之间那些太小、谁都放不下的小空闲块。上面那个例子跑完之后最佳适应留下了 5K 和 10K 两个小块最坏适应留下了 15K、20K 级别的块。如果后面再来一个请求 25K 的作业最佳适应的结果就放不下尽管空闲总量够——这就是外部碎片带来的总量够但用不上的典型困境。解决办法是紧凑把已分配区移到一端空闲区合并成一大块代价是需要重定位和动态重定位寄存器的支持。3. 分页地址变换逻辑地址拆分的三步法分页系统的地址变换是整章出现频率最高的计算题几乎没有一份卷子会跳过它。它的核心只有一句话逻辑地址被拆成页号和页内偏移页号查表换成页框号页框号和原偏移拼起来就是物理地址。听起来简单但真正做题时麻烦在于进制和单位。3.1 先算页面大小的位数第一步永远是确定页面大小对应几位二进制。这一步决定了后面所有拆分的位置。1KB 2^10偏移占 10 位2KB 2^11偏移占 11 位4KB 2^12偏移占 12 位1MB 2^20偏移占 20 位。如果逻辑地址是 32 位、页面大小 4KB那么页号就是 32 − 12 20 位页号取值范围是 0 到 2^20 − 1。这一步要先写在草稿纸边上后面所有计算都依赖它。3.2 十进制与十六进制两条路十进制路线适合题目给的是十进制地址。公式就两条页号 逻辑地址 / 页面大小整除向下取整 页内偏移 逻辑地址 mod 页面大小 物理地址 页框号 × 页面大小 页内偏移十六进制路线在页面大小是 4KB也就是 0x1000的时候极其好用因为除以 0x1000 在十六进制里就是右移三位。举个例子逻辑地址 0x3A5F末三位是偏移0xA5F前面的部分是页号0x3也就是十进制 3查页表若页号 3 对应页框号 5物理地址就是 0x5A5F。换算一下验证0x3A5F 3 × 4096 2655 14943物理地址 0x5A5F 5 × 4096 2655 23135。两边完全一致。提示只要页面大小是 2 的整数次幂十六进制地址的低位就是偏移这个性质就成立。页面大小是 16KB 时偏移占 14 位也就是末三位半十六进制这时候要小心半位的处理最好回到二进制去数别硬套。3.3 缺页发生在哪一步地址变换的完整链路是CPU 给出逻辑地址 → 拆出页号和偏移 → 查 TLB → 命中直接拿页框号 → 未命中查页表 → 页表项有效位为 1 则取页框号 → 有效位为 0 触发缺页中断 → 操作系统调页 → 更新页表 → 重新执行指令。所以在题目里看到页表项有效位为 0那不是让你算物理地址而是让你写缺页中断的处理流程。这两类问法经常出现在同一道题的两个小问里第一问算地址第二问模拟一次缺页答的时候要把重新执行这一步写出来因为缺页中断处理完之后是回到原指令重试不是接着往下执行。另外还有一个容易被忽略的细节如果题目给了访问位和修改位置换的时候要判断是不是脏页。修改位为 1 说明页面被写过换出时必须写回磁盘换出代价更高。这个点在置换算法和有效访问时间两类题里都会用到但很多同学只把它当成页表结构的知识点背做题时想不起来。4. 页表尺寸与多级页表一道页表占多大题目的完整推演页表占多少内存这类题看着像送分实际上是最容易因为一个默认取值而全盘错掉的一类。它的难点不在计算在于你对页表结构的假设必须和题目一致。4.1 页表项数怎么来页表的项数只取决于页号的位数和物理内存大小无关。页号有多少位就最多有多少个不同的页每一项对应一个页的映射。以一个典型配置为例逻辑地址 32 位页面大小 4KB页表项 4 字节。页内偏移 12 位页号 20 位页表项数 2^20 1M 项单个进程的页表大小 1M × 4B 4MB。如果系统里同时有 100 个进程光是页表就要占 400MB。这个数字本身就回答了为什么要多级页表这个问题——不是因为算法高级而是因为一级页表实在太胖了。注意页表项的大小是题目给的重要前提。教材上常见的有 2 字节、4 字节、8 字节三种。页表项里通常包含页框号、有效位、修改位、访问位、保护位等字段所以它的尺寸往往比存页框号所需的字节数更大。题目给什么就用什么不要自己按页框号的位数去推。4.2 两级页表的分拆规则两级页表的做法是把 20 位的页号再切成两段。常见的分法是外层的页目录索引 10 位内层的页表索引 10 位。这样一级页表页目录有 2^10 1024 项每项 4 字节正好 4KB ——刚好一页这就是分拆位数的隐含目标让每一级页表自己也占用整数个页面这样才能被分页机制统一管理。二级页表每个也是 4KB。关键在于进程不需要为整个 4GB 逻辑空间都建二级页表只需要为实际用到的区域建。如果某个进程只用到了最低的 8MB 空间那它需要的二级页表可能只有两三个总开销是 4KB页目录 2 × 4KB二级页表 12KB而不是 4MB。这就是多级页表真正的收益所在。方案页表空间开销访存次数不含 TLB一级页表4MB每进程2 次两级页表页目录 4KB 按需的二级页表3 次加 TLB不变命中时接近 1 次访存次数从 2 次变成 3 次这是多级页表付出的代价。所以真实系统里多级页表一定和 TLB 搭配使用TLB 命中时根本不走多级查找这条路。4.3 反置页表为什么能省空间反置页表的思路是反过来记不为每个逻辑页建表项而是为每个物理页框建一个表项里面记录这个页框现在装的是哪个进程的哪一页。物理内存 4GB、页面 4KB 时页框数是 2^20 1M反置页表就是 1M 项。每项包含进程标识和页号按 8 字节算总共 8MB而且整个系统只有这一份所有进程共享。对比一下就清楚了正排页表每进程 4MB100 个进程 400MB反置页表全系统 8MB。省空间的原理是表项数跟着物理内存走不跟逻辑地址空间走。它的代价是查表变慢——要按进程标识和页号去搜索整张表这个搜索通常靠散列表来加速。另外反置页表在换页时不好处理共享页面。这些细节在概念题里出现过答题时点出省空间、但查找复杂就够了。5. 页面置换算法FIFO/LRU/OPT/Clock 的推演模板与 Belady 异常置换算法是整章最考验耐心的题型。给一串访问序列给一个页框数让你求缺页次数和缺页率。核心能力只有两个把手算过程组织成表格以及准确判断该换谁。5.1 画表规则我的做法是画一张横向的表格列数等于引用串长度每一列记录三件事当前访问的页号、页框里现在装了什么、是否缺页。页框内部用一个顺序标记表示谁最老。引用串我统一用教材上那个经典序列方便和标准答案对7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1页框数取 3。5.2 FIFO、LRU、OPT 的推演结果先把结论列出来再解释一个算法的完整过程。算法缺页次数缺页率OPT最佳置换945%LRU最近最久未使用1260%FIFO先进先出1575%FIFO 的完整推演过程每个页框维护一个进入顺序缺页时淘汰最早进入的那个。访问 7缺页装入页框为 [7]访问 0缺页装入[7, 0]访问 1缺页装入[7, 0, 1]访问 2缺页淘汰 7[2, 0, 1]访问 0命中访问 3缺页淘汰 0[2, 3, 1]访问 0缺页淘汰 1[2, 3, 0]访问 4缺页淘汰 2[4, 3, 0]访问 2缺页淘汰 3[4, 2, 0]访问 3缺页淘汰 0[4, 2, 3]访问 0缺页淘汰 4[0, 2, 3]访问 3命中访问 2命中访问 1缺页淘汰 2[0, 1, 3]访问 2缺页淘汰 3[0, 1, 2]访问 0命中访问 1命中访问 7缺页淘汰 0[7, 1, 2]访问 0缺页淘汰 1[7, 0, 2]访问 1缺页淘汰 2[7, 0, 1]统计缺页共 15 次缺页率 15/20 75%。LRU 的区别只在于淘汰谁淘汰的是最长时间没有被访问过的那一页。刚才那串里第一次淘汰发生在访问 2 的时候FIFO 淘汰的是 7最先进入LRU 淘汰的也是 7最近最久没用。但到后面就分道扬镳了比如访问 3 的时候FIFO 淘汰 0LRU 淘汰的是 1因为 0 在之前刚被访问过。这就是为什么 LRU 在这串上比 FIFO 少 3 次缺页。OPT 需要看到未来淘汰未来最长时间不会被访问的页。做题时要在引用串的当前位置往后扫找出每个页框里的页下一次出现的位置谁的下次出现位置最靠后或者干脆不再出现就淘汰谁。回到访问 2 那一步页框里是 [7, 0, 1]7 的下一次出现在第 18 位0 在第 5 位1 在第 14 位最靠后的是 7淘汰它。提示OPT 手算最容易在后面还出现不出现上漏看。建议在引用串下方用铅笔标出每一页的所有出现位置判断时直接对照不要凭眼扫。5.3 Belady 异常FIFO 有一个反直觉的毛病页框数增加缺页次数反而可能变多。经典反例是引用串 1、2、3、4、1、2、5、1、2、3、4、5。页框数 3缺页 9 次1、2、3、4、1、2、5、3、4页框数 4缺页 10 次1、2、3、4、5、1、2、3、4、5多了 1 个页框反而多缺 1 次。这种现象叫 Belady 异常LRU 和 OPT 不会出现因为它们满足栈算法性质——页框数 n 的驻留集一定是页框数 n1 驻留集的子集。考场上如果题目问为什么 FIFO 会出现这种异常标准答法是FIFO 的淘汰策略与页面的访问历史无关新增页框会打乱原有的置换节奏导致原本还能命中的页面被提前换出而 LRU 具有栈性质增加页框只会让驻留集单调扩大因此不会异常。5.4 Clock 算法的正确手算姿势Clock 是 LRU 的近似实现硬件开销小真实系统里用得比 LRU 多题目也会考。它的规则是页框排成一个环形缓冲区每个页有一个访问位需要一个页框时指针从当前位置向前扫遇到访问位为 1 的就把它清零并跳过遇到访问位为 0 的就选它淘汰。手算时的常见错误是跳过之后忘了把访问位清零。一定要记住指针扫过的每一页访问位都被改成 0——这正是 Clock 用一次遍历就把最近用过的信息抹掉的机制。改进型 Clock 引入修改位把页面分成四类(访问位, 修改位) (0,0)、(0,1)、(1,0)、(1,1)。淘汰顺序是优先选 (0,0)其次是 (0,1)然后才是 (1,0)、(1,1)。题目如果给了访问位和修改位的当前值照着这个优先级挑就行。6. 缺页率与有效访问时间公式怎么拼、单位怎么统一有效访问时间EAT这类题的可怕之处在于它的公式看起来很长但本质上就是把一条访存路径上所有可能的分支按概率加权。拆开看只有两类分支命中或者未命中未命中里再分 TLB 未命中和缺页。6.1 只有 TLB 的情况设 TLB 查找耗时 ε内存访问耗时 tTLB 命中率 α。命中查 TLBε 访问内存一次t未命中查 TLBε 访问内存查页表t 访问内存取数据t所以EAT α × (ε t) (1 − α) × (ε 2t)代入一组实际数字ε 10nst 100nsα 98%。EAT 0.98 × 110 0.02 × 210 107.8 4.2 112ns注意 TLB 查找时间在两种情况里都要算因为它无论如何都会执行一次。这一点是很多人的失分点直接把命中写成 t、未命中写成 2t忘了加 ε。6.2 再叠加缺页缺页的场景要把缺页率 p 叠上去EAT (1 − p) × (上面算出的无缺页 EAT) p × 缺页处理时间缺页处理时间通常是一个很大的数量级在毫秒来源包括缺页中断的处理开销、判断所需页面是否在内存、有空闲页框就分配、没有就选一页换出脏页要写回磁盘、从磁盘读入所需页面、更新页表和 TLB、恢复进程运行。用上一节的 112ns加上 p 0.001、缺页处理时间 10ms也就是 10^7 nsEAT 0.999 × 112 0.001 × 10^7 ≈ 111.9 10000 ≈ 10111.9ns ≈ 10.1μs千分之一的缺页率把 112ns 抬到了 10μs 左右慢了近 90 倍。这个结果本身就是一道很好的概念题答案缺页是极其昂贵的操作必须用尽可能好的置换算法把它压下去哪怕把缺页率从 0.001 降到 0.0001EAT 也会从 10μs 掉到 1.1μs 量级。6.3 单位陷阱与量级感这类题丢分八成栽在单位上。我的对策是所有时间统一换算成纳秒后再代入并且换算时把指数写全。单位纳秒表示记忆方式1μs10^3 ns微秒是千分之一毫秒1ms10^6 ns毫秒是百万纳秒1s10^9 ns秒是十亿纳秒养成一个习惯把磁盘访问时间、缺页处理时间先换算成 ns再进公式。如果最后算出的 EAT 比单次内存访问时间还小那一定是哪一步错了——EAT 永远不小于最好情况下的单次访存时间这是个很好的量级自检。注意有的题目把缺页处理时间写成包括 6ms 的磁盘访问和 1ms 的中断处理这时候要相加而不是取其一。也有题目直接说缺页处理开销为 M忽略其他时间那就不用再叠加。读题时把包含和另有这两个词划出来。7. 分段与段页式越界检查与访存次数分页是按固定大小切分段是按逻辑单位切两者的地址变换结构不同题目问法也不同。分段的地址变换多了一步越界检查这是它区别于分页的关键也是最常被考的地方。7.1 段表结构与越界检查逻辑地址由段号和段内偏移组成。段表每一项包含两个关键字段段长和基址段的起始物理地址。变换流程是用段号查段表取出段长和基址比较段内偏移和段长如果偏移 ≥ 段长产生越界中断否则物理地址 基址 段内偏移。注意这里的判定条件是偏移 ≥ 段长就中断不是偏移 段长。因为偏移是从 0 开始计数的段长为 L 时合法偏移范围是 0 到 L−1偏移等于 L 已经越界了。这个等号是个高频陷阱我在模拟卷上错过两次。还有一点分段中段的长度可变所以每个段的越界界限都不同必须查段表才能判断而分页中所有页大小相同越界检查只需要看页号是否超过页表项数比分段简单。7.2 段页式地址变换段页式把两者结合先按逻辑单位分段再把每个段按固定大小分页。逻辑地址的结构变成三段段号、段内页号、页内偏移。变换过程是这样的用段号查段表得到该段的页表起始地址用段内页号查这个页表得到页框号页框号拼接页内偏移得到物理地址。这需要三次访存查段表、查页表、取数据。如果只用段表是两次访存只用页表也是两次访存。段页式为了同时获得逻辑上便于共享和保护和物理上消除外部碎片这两个好处付出了多一次访存的代价——这个取舍在概念题里经常被问。段页式的越界检查要在两个地方做一是段内页号不能超过该段的页表长度二是页内偏移不能超过页面大小。两个检查缺一不可因为一段的最后一页通常是不满的光检查页号范围还不够。7.3 访存次数与 TLB 的配合把各类方案的访存次数放在一起对照会更清楚为什么真实系统最后都选了带 TLB 的分页或者段页式方案无 TLB 访存次数有 TLB命中一级分页21二级分页31分段21段页式31TLB 命中时页框号直接从快表拿到不需要走页表层级这是它能把三次访存压到一次的原因。但要注意TLB 里存的是页号—页框号的映射段页式下 TLB 的表项还要额外带上段号的标识否则不同段里的同一个页号会混淆。这个细节在选择题里出现过。8. 虚拟内存边界工作集、抖动与页框分配这一类题属于看似简单、实则定义决定答案。工作集的算法本身很简单但不同教材对窗口的定义不一样做题第一步必须确认题目用的是哪一种。8.1 工作集窗口的两种定义工作集 WS(t, Δ) 指的是在时刻 t 之前的 Δ 时间窗口内进程访问过的所有页面的集合。这里的 Δ 可以是时间长度比如最近 10ms也可以是访问次数比如最近 k 次访存。题目给了哪一种就用哪一种。用引用串 2、6、1、5、7、7、7、7、5、1、6、2、3、4、1 走一遍取窗口大小为最近 4 次访问含当前这次时刻当前访问窗口内引用工作集122{2}262, 6{2, 6}312, 6, 1{1, 2, 6}452, 6, 1, 5{1, 2, 5, 6}576, 1, 5, 7{1, 5, 6, 7}671, 5, 7, 7{1, 5, 7}775, 7, 7, 7{5, 7}877, 7, 7, 7{7}957, 7, 7, 5{5, 7}1017, 7, 5, 1{1, 5, 7}1167, 5, 1, 6{1, 5, 6, 7}1225, 1, 6, 2{1, 2, 5, 6}1331, 6, 2, 3{1, 2, 3, 6}1446, 2, 3, 4{2, 3, 4, 6}1512, 3, 4, 1{1, 2, 3, 4}从这张表能直观看到工作集的收缩—扩张节奏第 5 到第 8 时刻因为反复访问 7工作集缩小到只有一页之后又逐步扩回 4 页。这正对应操作系统在运行过程中访存局部性的变化。8.2 抖动判定与页框数的关系抖动的定义是刚被换出的页面很快又要被访问于是又要换入系统把大量时间花在换页上CPU 利用率急剧下降。判定的方法就是拿可用页框数和工作集大小比可用页框数小于当前工作集大小时进程就会频繁缺页处在抖动状态。用上面的表来说明如果给这个进程分配 4 个页框那在工作集最大为 4 的时刻第 4、5、12、13、14、15 时刻它刚好够用不抖动如果只给 2 个页框那第 4 时刻之后就一直不够必然抖动。防止抖动的思路有三条局部置换策略每个进程只在自己的页框里置换不去抢别人的缺点是不能灵活调剂工作集模型操作系统周期性统计每个进程的工作集给它分配不小于工作集大小的页框数不够就把部分进程挂起把页框腾出来页错误频率控制设定上下阈值缺页率超过上阈值就多给页框低于下阈值就收回一些页框。这三条里工作集模型最直观也最常被出成大题。8.3 页框分配和置换范围分配策略上常见的有两种问法。平均分配是把 m 个页框平均分给 n 个进程每个进程 m/n 个按比例分配是依据进程大小按比例给比如进程大小分别是 10 页、30 页、60 页总页框 100 个那就分别给 10、30、60 个。置换范围上分为局部置换和全局置换置换范围特点缺点局部置换只在本进程分到的页框里换页框分配不合理时无法自我调节全局置换可以从系统空闲页框里取也可以换其他进程的页可能影响其他进程的缺页率提示局部置换和全局置换跟固定分配/可变分配是一对组合常见的有固定分配局部置换、可变分配全局置换、可变分配局部置换三种。答题时如果题目问哪种策略能动态调整页框数答案一定是可变分配的那两种。9. 考场上怎么答模板与易错清单刷到最后你会发现真正决定分数上限的不是会不会而是能不能在有限时间里把会的东西完整落纸。我总结了一套自己用着顺手的答题顺序供参考。9.1 通用答题模板拿到一道内存管理大题先花半分钟做完三件事圈出前提页面大小、地址位数、页表项大小、是否使用 TLB、是否请求分页、页框数写出公式在草稿纸左上角把要用到的公式和单位换算写出来避免中途找公式判断题型属于第一节那张表里的哪一类然后调用对应模板。写答案时计算题一定要把中间步骤留下来——页号是多少、偏移是多少、查表得到的页框号是多少。一是方便自己回查二是阅卷时步骤分很实在尤其置换算法这种过程繁多的题。9.2 二十条易错点清单下面这份清单是我自己攒的每条后面都来自真实踩过的坑。序号易错点正确做法1首次访问不算缺页首次访问页面一定缺页要计入2页号从 1 开始编号页号从 0 开始3越界判定用偏移 段长应为偏移 ≥ 段长4页表大小忘记乘进程数看清题目问单进程还是全系统5页表项大小自己猜用题目给的值6多级页表分级位数随意拆让每级页表正好占一页7有效访问时间漏算 TLB 查找命中和未命中都要加 ε8单位混用全部换算成纳秒再算9缺页处理时间漏加写回时间脏页换出要算进去10FIFO 用页框数算索引用进入顺序维护不要算下标11LRU 用上次访问时刻判断却记错时刻每步更新访问时刻表12OPT 漏看以后不再出现不再出现的优先级最高13FIFO 增加页框后缺页数一定减少Belady 异常可能变多14Clock 扫过不清访问位指针扫过即清零15局部置换能自动调整页框只有可变分配可以16工作集窗口定义想当然先确认按时间还是按次数17抖动判定只看缺页率要和可用页框数、工作集大小对比18分区回收只合并一侧四种邻近情况都要判断19动态分区分配后不重排序空闲表每次操作后按地址重排20十六进制地址硬算十进制页面为 2 的幂时直接按位对齐拆最后再补一句关于复习节奏的体会。我第一次做内存管理大题的时候是按照教材顺序一道一道刷的结果刷完第三章回头再看第二章的置换算法又忘了。后来改成按题型刷——今天只刷地址变换明天只刷置换算法每个题型连着做十道以上直到能在两三分钟内判断题型并写出公式。这个方法的效率比按章节顺序刷高出很多因为同一类题之间共享的套路被反复强化而跨题型的干扰被排除了。另外这类题建议手写练习而不是看着答案点头。看着答案觉得原来如此的题目真正动笔时大概率还是会在第一行就卡住。我自己的做法是把做错的题抄在一个本子上只写题干关键条件和最后卡住的那一步隔一周再做一次能独立做出来才算过。这个笨办法帮我省下了考场上大量的犹豫时间看到求有效访问时间我的手会先写出那几个单位换算而不是先发呆。
操作系统内存管理大题通关：分页、页面置换与有效访问时间
1. 先建一张题型地图内存管理大题就这六类问法内存管理这一章教材上理论铺得最开但落到卷子上大题的形状其实非常固定。你翻十套卷子会发现它们反反复复就在问那六件事地址怎么变、页表占多大、页面怎么换、缺页率怎么算、分区怎么分、工作集怎么求。真正让人丢分的从来不是没学过而是同一个知识点换一种问法就认不出来或者算到一半被单位、进制、表格抄写搞崩。我自己的复习顺序是先归类再刷题。归类就是把这六类题各自的输入—工具—输出写在一张纸上做题时先判断这是哪一类再调用对应模板。这个动作看着笨但比无脑刷五十道题管用得多因为考场上最怕的是这道题我没见过而归类之后你会发现所谓的新题只是老题换了个外壳。1.1 六类题型的核心公式速查下面这张表是我自己整理并反复修订过的版本左边是题型中间是核心工具右边那一列特意写了最容易翻车的地方——这一列才是这张表的真正价值所在。题型典型问法核心工具/公式高频翻车点动态分区分配给空闲分区表和作业序列画分配过程首次适应、最佳适应、最坏适应、循环首次适应回收时的相邻空闲区合并分页地址变换给逻辑地址求物理地址页号 逻辑地址 / 页面大小偏移 逻辑地址 mod 页面大小十六进制拆位、页号起始值页表尺寸与多级页表求页表占用多少字节项数 2^(页号位数)页表大小 项数 × 项长忘记乘进程数、项长取值页面置换算法给引用串求缺页次数/缺页率FIFO、LRU、OPT、Clock首次访问是否计缺页、表格抄错列有效访问时间求 EAT命中率×单次时间 未命中率×多次时间再叠加缺页率单位不统一、缺页时间是否含访存工作集与抖动求工作集大小、判断是否抖动WS(t, Δ)可用页框数对比窗口定义按次数还是按时间把这张表背下来意义不大真正要做的是每一类都亲手推演三五道直到你能在不看答案的情况下自己解释为什么这一步要这么做。比如最佳适应为什么容易产生小碎片、两级页表为什么能省空间、LRU 为什么不会被 Belady 异常影响这些问题想通了题目怎么变形都不怕。1.2 为什么这些题总在细节上丢分说个很实在的观察内存管理大题的难度是台阶型的——看答案觉得简单自己动手就错。原因通常集中在这几处。第一是单位混乱。有效访问时间那道题内存访问给的是纳秒磁盘访问给的是毫秒缺页率给的是小数或百分数稍不留神就是三个数量级的偏差。我踩过最典型的一次是把 8ms 直接代进以 ns 为单位的公式算出 EAT 等于八千多纳秒还觉得答案挺合理。第二是进制转换。十六进制地址和页面大小的关系是天然的对齐关系页面大小是 4KB 时末三位十六进制数就是页内偏移前面是页号这个规律一旦掌握拆地址就是两三秒的事反过来如果硬算十进制就等着出错。第三是表格推演过程中的抄写错误。置换算法题给十几个引用数字要在三四行里反复比对手写时漏一个数、抄错一列后面全盘皆错而这类题通常不给分步骤的宽容度。提示置换算法题一律用逐列推进的表格不要用文字叙述过程。表格每一列对应一个引用数字命中就在格子里打勾缺页就写下当前页框内容这样即使最后结果错了过程分也拿得到。还有一类隐形的坑是概念前提被忽略。比如题目没写采用请求分页你就不能默认有缺页题目前面给的是页表项 4 字节你就不能用 2 字节去算题目问页表占用你要先判断是问单个进程的还是整个系统的。这些前提通常在题干第一句或者一句不起眼的括号里读题时用笔圈出来是值得的。2. 动态分区分配大题三种算法的手算差异与空闲分区表怎么画连续分配管理方式里的动态分区分配是内存管理章节里最动手的一类题。它不需要复杂公式但要你在纸上模拟一个分配器一步步更新空闲分区表。这类题的评分点非常明确分配位置对不对、剩余分区大小对不对、要不要合并——三项全对才给满分。2.1 题目给的是什么你要画什么题目的标准形态是这样的给一张空闲分区表每项包含起始地址和大小分区按地址递增排列再给一个作业序列每个作业请求若干大小的内存要求画出每次分配后的空闲分区表或者计算某次分配之后剩余的碎片大小。手算的时候我建议用下面这个格式横着一行写清楚作业—请求大小—分配到的位置—剩余情况比画方块图快得多也清楚得多。关键字在于分配之后空闲分区表要重新按地址排序这一步很多人会漏。2.2 一个例子跑通三种算法假设初始空闲分区表如下地址递增序号起始地址大小1100K50K2200K40K3300K20K4400K60K作业序列A 请求 30KB 请求 45KC 请求 15K。首次适应从低地址开始找第一个够大的分区。A(30K)100K 处的 50K 够 → 分配 30K剩 20K起始地址变为 130K。B(45K)130K 处的 20K 不够200K 处的 40K 不够300K 处的 20K 不够400K 处的 60K 够 → 分配 45K剩 15K起始地址 445K。C(15K)回到低地址130K 处的 20K 够 → 分配 15K剩 5K起始地址 145K。最终空闲区145K/5K、200K/40K、300K/20K、445K/15K。最佳适应每次找容量最小且足够的分区。这里必须注意最佳适应是把空闲区按容量递增排序来找的不是按地址。A(30K)候选 50K、40K、60K20K 不够最小够大的是 40K → 分配在 200K 处剩 10K起始地址 230K。B(45K)候选 50K、60K、10K不够最小够大的是 50K → 分配在 100K 处剩 5K起始地址 145K。C(15K)候选 10K 不够、5K 不够、20K 够、60K 够 → 最小够大是 300K 处的 20K → 全部用掉该分区从表中消失。最终空闲区145K/5K、230K/10K、400K/60K。最坏适应每次挑最大的分区切。A(30K)最大的是 400K 处 60K → 分配 30K剩 30K起始地址 430K。B(45K)候选 50K、40K、20K、30K → 最大是 100K 处的 50K → 分配 45K剩 5K起始地址 145K。C(15K)候选剩下的 40K、20K、30K → 最大是 200K 处的 40K → 分配 15K剩 25K起始地址 215K。对同一个作业序列三种算法给出了三套完全不同的空闲分区表。这就是为什么这类题必须老老实实按算法规则走凭感觉分配必错。2.3 内存回收的四种相邻情况分配会做回收更容易错。当一个作业释放它占用的分区时要看它的前后是否有空闲分区一共四种情况情况处理方式前后都不空闲单独成一个新空闲区前空闲、后占用与前面的空闲区合并起始地址取前者的前占用、后空闲与后面的空闲区合并大小相加前后都空闲三块合并成一块大小是三者之和注意合并后的起始地址一律取地址较小的那块大小是相加中间不能留空洞。很多同学会在前后都空闲时只合并一侧结果空闲区表里出现两块本该连着却分开的记录。2.4 内部碎片与外部碎片的判定连续分配的两种典型问题内部碎片和外部碎片。固定分区会产生内部碎片——分区内部分配出去但用不完的部分动态分区会产生外部碎片——分区之间那些太小、谁都放不下的小空闲块。上面那个例子跑完之后最佳适应留下了 5K 和 10K 两个小块最坏适应留下了 15K、20K 级别的块。如果后面再来一个请求 25K 的作业最佳适应的结果就放不下尽管空闲总量够——这就是外部碎片带来的总量够但用不上的典型困境。解决办法是紧凑把已分配区移到一端空闲区合并成一大块代价是需要重定位和动态重定位寄存器的支持。3. 分页地址变换逻辑地址拆分的三步法分页系统的地址变换是整章出现频率最高的计算题几乎没有一份卷子会跳过它。它的核心只有一句话逻辑地址被拆成页号和页内偏移页号查表换成页框号页框号和原偏移拼起来就是物理地址。听起来简单但真正做题时麻烦在于进制和单位。3.1 先算页面大小的位数第一步永远是确定页面大小对应几位二进制。这一步决定了后面所有拆分的位置。1KB 2^10偏移占 10 位2KB 2^11偏移占 11 位4KB 2^12偏移占 12 位1MB 2^20偏移占 20 位。如果逻辑地址是 32 位、页面大小 4KB那么页号就是 32 − 12 20 位页号取值范围是 0 到 2^20 − 1。这一步要先写在草稿纸边上后面所有计算都依赖它。3.2 十进制与十六进制两条路十进制路线适合题目给的是十进制地址。公式就两条页号 逻辑地址 / 页面大小整除向下取整 页内偏移 逻辑地址 mod 页面大小 物理地址 页框号 × 页面大小 页内偏移十六进制路线在页面大小是 4KB也就是 0x1000的时候极其好用因为除以 0x1000 在十六进制里就是右移三位。举个例子逻辑地址 0x3A5F末三位是偏移0xA5F前面的部分是页号0x3也就是十进制 3查页表若页号 3 对应页框号 5物理地址就是 0x5A5F。换算一下验证0x3A5F 3 × 4096 2655 14943物理地址 0x5A5F 5 × 4096 2655 23135。两边完全一致。提示只要页面大小是 2 的整数次幂十六进制地址的低位就是偏移这个性质就成立。页面大小是 16KB 时偏移占 14 位也就是末三位半十六进制这时候要小心半位的处理最好回到二进制去数别硬套。3.3 缺页发生在哪一步地址变换的完整链路是CPU 给出逻辑地址 → 拆出页号和偏移 → 查 TLB → 命中直接拿页框号 → 未命中查页表 → 页表项有效位为 1 则取页框号 → 有效位为 0 触发缺页中断 → 操作系统调页 → 更新页表 → 重新执行指令。所以在题目里看到页表项有效位为 0那不是让你算物理地址而是让你写缺页中断的处理流程。这两类问法经常出现在同一道题的两个小问里第一问算地址第二问模拟一次缺页答的时候要把重新执行这一步写出来因为缺页中断处理完之后是回到原指令重试不是接着往下执行。另外还有一个容易被忽略的细节如果题目给了访问位和修改位置换的时候要判断是不是脏页。修改位为 1 说明页面被写过换出时必须写回磁盘换出代价更高。这个点在置换算法和有效访问时间两类题里都会用到但很多同学只把它当成页表结构的知识点背做题时想不起来。4. 页表尺寸与多级页表一道页表占多大题目的完整推演页表占多少内存这类题看着像送分实际上是最容易因为一个默认取值而全盘错掉的一类。它的难点不在计算在于你对页表结构的假设必须和题目一致。4.1 页表项数怎么来页表的项数只取决于页号的位数和物理内存大小无关。页号有多少位就最多有多少个不同的页每一项对应一个页的映射。以一个典型配置为例逻辑地址 32 位页面大小 4KB页表项 4 字节。页内偏移 12 位页号 20 位页表项数 2^20 1M 项单个进程的页表大小 1M × 4B 4MB。如果系统里同时有 100 个进程光是页表就要占 400MB。这个数字本身就回答了为什么要多级页表这个问题——不是因为算法高级而是因为一级页表实在太胖了。注意页表项的大小是题目给的重要前提。教材上常见的有 2 字节、4 字节、8 字节三种。页表项里通常包含页框号、有效位、修改位、访问位、保护位等字段所以它的尺寸往往比存页框号所需的字节数更大。题目给什么就用什么不要自己按页框号的位数去推。4.2 两级页表的分拆规则两级页表的做法是把 20 位的页号再切成两段。常见的分法是外层的页目录索引 10 位内层的页表索引 10 位。这样一级页表页目录有 2^10 1024 项每项 4 字节正好 4KB ——刚好一页这就是分拆位数的隐含目标让每一级页表自己也占用整数个页面这样才能被分页机制统一管理。二级页表每个也是 4KB。关键在于进程不需要为整个 4GB 逻辑空间都建二级页表只需要为实际用到的区域建。如果某个进程只用到了最低的 8MB 空间那它需要的二级页表可能只有两三个总开销是 4KB页目录 2 × 4KB二级页表 12KB而不是 4MB。这就是多级页表真正的收益所在。方案页表空间开销访存次数不含 TLB一级页表4MB每进程2 次两级页表页目录 4KB 按需的二级页表3 次加 TLB不变命中时接近 1 次访存次数从 2 次变成 3 次这是多级页表付出的代价。所以真实系统里多级页表一定和 TLB 搭配使用TLB 命中时根本不走多级查找这条路。4.3 反置页表为什么能省空间反置页表的思路是反过来记不为每个逻辑页建表项而是为每个物理页框建一个表项里面记录这个页框现在装的是哪个进程的哪一页。物理内存 4GB、页面 4KB 时页框数是 2^20 1M反置页表就是 1M 项。每项包含进程标识和页号按 8 字节算总共 8MB而且整个系统只有这一份所有进程共享。对比一下就清楚了正排页表每进程 4MB100 个进程 400MB反置页表全系统 8MB。省空间的原理是表项数跟着物理内存走不跟逻辑地址空间走。它的代价是查表变慢——要按进程标识和页号去搜索整张表这个搜索通常靠散列表来加速。另外反置页表在换页时不好处理共享页面。这些细节在概念题里出现过答题时点出省空间、但查找复杂就够了。5. 页面置换算法FIFO/LRU/OPT/Clock 的推演模板与 Belady 异常置换算法是整章最考验耐心的题型。给一串访问序列给一个页框数让你求缺页次数和缺页率。核心能力只有两个把手算过程组织成表格以及准确判断该换谁。5.1 画表规则我的做法是画一张横向的表格列数等于引用串长度每一列记录三件事当前访问的页号、页框里现在装了什么、是否缺页。页框内部用一个顺序标记表示谁最老。引用串我统一用教材上那个经典序列方便和标准答案对7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1页框数取 3。5.2 FIFO、LRU、OPT 的推演结果先把结论列出来再解释一个算法的完整过程。算法缺页次数缺页率OPT最佳置换945%LRU最近最久未使用1260%FIFO先进先出1575%FIFO 的完整推演过程每个页框维护一个进入顺序缺页时淘汰最早进入的那个。访问 7缺页装入页框为 [7]访问 0缺页装入[7, 0]访问 1缺页装入[7, 0, 1]访问 2缺页淘汰 7[2, 0, 1]访问 0命中访问 3缺页淘汰 0[2, 3, 1]访问 0缺页淘汰 1[2, 3, 0]访问 4缺页淘汰 2[4, 3, 0]访问 2缺页淘汰 3[4, 2, 0]访问 3缺页淘汰 0[4, 2, 3]访问 0缺页淘汰 4[0, 2, 3]访问 3命中访问 2命中访问 1缺页淘汰 2[0, 1, 3]访问 2缺页淘汰 3[0, 1, 2]访问 0命中访问 1命中访问 7缺页淘汰 0[7, 1, 2]访问 0缺页淘汰 1[7, 0, 2]访问 1缺页淘汰 2[7, 0, 1]统计缺页共 15 次缺页率 15/20 75%。LRU 的区别只在于淘汰谁淘汰的是最长时间没有被访问过的那一页。刚才那串里第一次淘汰发生在访问 2 的时候FIFO 淘汰的是 7最先进入LRU 淘汰的也是 7最近最久没用。但到后面就分道扬镳了比如访问 3 的时候FIFO 淘汰 0LRU 淘汰的是 1因为 0 在之前刚被访问过。这就是为什么 LRU 在这串上比 FIFO 少 3 次缺页。OPT 需要看到未来淘汰未来最长时间不会被访问的页。做题时要在引用串的当前位置往后扫找出每个页框里的页下一次出现的位置谁的下次出现位置最靠后或者干脆不再出现就淘汰谁。回到访问 2 那一步页框里是 [7, 0, 1]7 的下一次出现在第 18 位0 在第 5 位1 在第 14 位最靠后的是 7淘汰它。提示OPT 手算最容易在后面还出现不出现上漏看。建议在引用串下方用铅笔标出每一页的所有出现位置判断时直接对照不要凭眼扫。5.3 Belady 异常FIFO 有一个反直觉的毛病页框数增加缺页次数反而可能变多。经典反例是引用串 1、2、3、4、1、2、5、1、2、3、4、5。页框数 3缺页 9 次1、2、3、4、1、2、5、3、4页框数 4缺页 10 次1、2、3、4、5、1、2、3、4、5多了 1 个页框反而多缺 1 次。这种现象叫 Belady 异常LRU 和 OPT 不会出现因为它们满足栈算法性质——页框数 n 的驻留集一定是页框数 n1 驻留集的子集。考场上如果题目问为什么 FIFO 会出现这种异常标准答法是FIFO 的淘汰策略与页面的访问历史无关新增页框会打乱原有的置换节奏导致原本还能命中的页面被提前换出而 LRU 具有栈性质增加页框只会让驻留集单调扩大因此不会异常。5.4 Clock 算法的正确手算姿势Clock 是 LRU 的近似实现硬件开销小真实系统里用得比 LRU 多题目也会考。它的规则是页框排成一个环形缓冲区每个页有一个访问位需要一个页框时指针从当前位置向前扫遇到访问位为 1 的就把它清零并跳过遇到访问位为 0 的就选它淘汰。手算时的常见错误是跳过之后忘了把访问位清零。一定要记住指针扫过的每一页访问位都被改成 0——这正是 Clock 用一次遍历就把最近用过的信息抹掉的机制。改进型 Clock 引入修改位把页面分成四类(访问位, 修改位) (0,0)、(0,1)、(1,0)、(1,1)。淘汰顺序是优先选 (0,0)其次是 (0,1)然后才是 (1,0)、(1,1)。题目如果给了访问位和修改位的当前值照着这个优先级挑就行。6. 缺页率与有效访问时间公式怎么拼、单位怎么统一有效访问时间EAT这类题的可怕之处在于它的公式看起来很长但本质上就是把一条访存路径上所有可能的分支按概率加权。拆开看只有两类分支命中或者未命中未命中里再分 TLB 未命中和缺页。6.1 只有 TLB 的情况设 TLB 查找耗时 ε内存访问耗时 tTLB 命中率 α。命中查 TLBε 访问内存一次t未命中查 TLBε 访问内存查页表t 访问内存取数据t所以EAT α × (ε t) (1 − α) × (ε 2t)代入一组实际数字ε 10nst 100nsα 98%。EAT 0.98 × 110 0.02 × 210 107.8 4.2 112ns注意 TLB 查找时间在两种情况里都要算因为它无论如何都会执行一次。这一点是很多人的失分点直接把命中写成 t、未命中写成 2t忘了加 ε。6.2 再叠加缺页缺页的场景要把缺页率 p 叠上去EAT (1 − p) × (上面算出的无缺页 EAT) p × 缺页处理时间缺页处理时间通常是一个很大的数量级在毫秒来源包括缺页中断的处理开销、判断所需页面是否在内存、有空闲页框就分配、没有就选一页换出脏页要写回磁盘、从磁盘读入所需页面、更新页表和 TLB、恢复进程运行。用上一节的 112ns加上 p 0.001、缺页处理时间 10ms也就是 10^7 nsEAT 0.999 × 112 0.001 × 10^7 ≈ 111.9 10000 ≈ 10111.9ns ≈ 10.1μs千分之一的缺页率把 112ns 抬到了 10μs 左右慢了近 90 倍。这个结果本身就是一道很好的概念题答案缺页是极其昂贵的操作必须用尽可能好的置换算法把它压下去哪怕把缺页率从 0.001 降到 0.0001EAT 也会从 10μs 掉到 1.1μs 量级。6.3 单位陷阱与量级感这类题丢分八成栽在单位上。我的对策是所有时间统一换算成纳秒后再代入并且换算时把指数写全。单位纳秒表示记忆方式1μs10^3 ns微秒是千分之一毫秒1ms10^6 ns毫秒是百万纳秒1s10^9 ns秒是十亿纳秒养成一个习惯把磁盘访问时间、缺页处理时间先换算成 ns再进公式。如果最后算出的 EAT 比单次内存访问时间还小那一定是哪一步错了——EAT 永远不小于最好情况下的单次访存时间这是个很好的量级自检。注意有的题目把缺页处理时间写成包括 6ms 的磁盘访问和 1ms 的中断处理这时候要相加而不是取其一。也有题目直接说缺页处理开销为 M忽略其他时间那就不用再叠加。读题时把包含和另有这两个词划出来。7. 分段与段页式越界检查与访存次数分页是按固定大小切分段是按逻辑单位切两者的地址变换结构不同题目问法也不同。分段的地址变换多了一步越界检查这是它区别于分页的关键也是最常被考的地方。7.1 段表结构与越界检查逻辑地址由段号和段内偏移组成。段表每一项包含两个关键字段段长和基址段的起始物理地址。变换流程是用段号查段表取出段长和基址比较段内偏移和段长如果偏移 ≥ 段长产生越界中断否则物理地址 基址 段内偏移。注意这里的判定条件是偏移 ≥ 段长就中断不是偏移 段长。因为偏移是从 0 开始计数的段长为 L 时合法偏移范围是 0 到 L−1偏移等于 L 已经越界了。这个等号是个高频陷阱我在模拟卷上错过两次。还有一点分段中段的长度可变所以每个段的越界界限都不同必须查段表才能判断而分页中所有页大小相同越界检查只需要看页号是否超过页表项数比分段简单。7.2 段页式地址变换段页式把两者结合先按逻辑单位分段再把每个段按固定大小分页。逻辑地址的结构变成三段段号、段内页号、页内偏移。变换过程是这样的用段号查段表得到该段的页表起始地址用段内页号查这个页表得到页框号页框号拼接页内偏移得到物理地址。这需要三次访存查段表、查页表、取数据。如果只用段表是两次访存只用页表也是两次访存。段页式为了同时获得逻辑上便于共享和保护和物理上消除外部碎片这两个好处付出了多一次访存的代价——这个取舍在概念题里经常被问。段页式的越界检查要在两个地方做一是段内页号不能超过该段的页表长度二是页内偏移不能超过页面大小。两个检查缺一不可因为一段的最后一页通常是不满的光检查页号范围还不够。7.3 访存次数与 TLB 的配合把各类方案的访存次数放在一起对照会更清楚为什么真实系统最后都选了带 TLB 的分页或者段页式方案无 TLB 访存次数有 TLB命中一级分页21二级分页31分段21段页式31TLB 命中时页框号直接从快表拿到不需要走页表层级这是它能把三次访存压到一次的原因。但要注意TLB 里存的是页号—页框号的映射段页式下 TLB 的表项还要额外带上段号的标识否则不同段里的同一个页号会混淆。这个细节在选择题里出现过。8. 虚拟内存边界工作集、抖动与页框分配这一类题属于看似简单、实则定义决定答案。工作集的算法本身很简单但不同教材对窗口的定义不一样做题第一步必须确认题目用的是哪一种。8.1 工作集窗口的两种定义工作集 WS(t, Δ) 指的是在时刻 t 之前的 Δ 时间窗口内进程访问过的所有页面的集合。这里的 Δ 可以是时间长度比如最近 10ms也可以是访问次数比如最近 k 次访存。题目给了哪一种就用哪一种。用引用串 2、6、1、5、7、7、7、7、5、1、6、2、3、4、1 走一遍取窗口大小为最近 4 次访问含当前这次时刻当前访问窗口内引用工作集122{2}262, 6{2, 6}312, 6, 1{1, 2, 6}452, 6, 1, 5{1, 2, 5, 6}576, 1, 5, 7{1, 5, 6, 7}671, 5, 7, 7{1, 5, 7}775, 7, 7, 7{5, 7}877, 7, 7, 7{7}957, 7, 7, 5{5, 7}1017, 7, 5, 1{1, 5, 7}1167, 5, 1, 6{1, 5, 6, 7}1225, 1, 6, 2{1, 2, 5, 6}1331, 6, 2, 3{1, 2, 3, 6}1446, 2, 3, 4{2, 3, 4, 6}1512, 3, 4, 1{1, 2, 3, 4}从这张表能直观看到工作集的收缩—扩张节奏第 5 到第 8 时刻因为反复访问 7工作集缩小到只有一页之后又逐步扩回 4 页。这正对应操作系统在运行过程中访存局部性的变化。8.2 抖动判定与页框数的关系抖动的定义是刚被换出的页面很快又要被访问于是又要换入系统把大量时间花在换页上CPU 利用率急剧下降。判定的方法就是拿可用页框数和工作集大小比可用页框数小于当前工作集大小时进程就会频繁缺页处在抖动状态。用上面的表来说明如果给这个进程分配 4 个页框那在工作集最大为 4 的时刻第 4、5、12、13、14、15 时刻它刚好够用不抖动如果只给 2 个页框那第 4 时刻之后就一直不够必然抖动。防止抖动的思路有三条局部置换策略每个进程只在自己的页框里置换不去抢别人的缺点是不能灵活调剂工作集模型操作系统周期性统计每个进程的工作集给它分配不小于工作集大小的页框数不够就把部分进程挂起把页框腾出来页错误频率控制设定上下阈值缺页率超过上阈值就多给页框低于下阈值就收回一些页框。这三条里工作集模型最直观也最常被出成大题。8.3 页框分配和置换范围分配策略上常见的有两种问法。平均分配是把 m 个页框平均分给 n 个进程每个进程 m/n 个按比例分配是依据进程大小按比例给比如进程大小分别是 10 页、30 页、60 页总页框 100 个那就分别给 10、30、60 个。置换范围上分为局部置换和全局置换置换范围特点缺点局部置换只在本进程分到的页框里换页框分配不合理时无法自我调节全局置换可以从系统空闲页框里取也可以换其他进程的页可能影响其他进程的缺页率提示局部置换和全局置换跟固定分配/可变分配是一对组合常见的有固定分配局部置换、可变分配全局置换、可变分配局部置换三种。答题时如果题目问哪种策略能动态调整页框数答案一定是可变分配的那两种。9. 考场上怎么答模板与易错清单刷到最后你会发现真正决定分数上限的不是会不会而是能不能在有限时间里把会的东西完整落纸。我总结了一套自己用着顺手的答题顺序供参考。9.1 通用答题模板拿到一道内存管理大题先花半分钟做完三件事圈出前提页面大小、地址位数、页表项大小、是否使用 TLB、是否请求分页、页框数写出公式在草稿纸左上角把要用到的公式和单位换算写出来避免中途找公式判断题型属于第一节那张表里的哪一类然后调用对应模板。写答案时计算题一定要把中间步骤留下来——页号是多少、偏移是多少、查表得到的页框号是多少。一是方便自己回查二是阅卷时步骤分很实在尤其置换算法这种过程繁多的题。9.2 二十条易错点清单下面这份清单是我自己攒的每条后面都来自真实踩过的坑。序号易错点正确做法1首次访问不算缺页首次访问页面一定缺页要计入2页号从 1 开始编号页号从 0 开始3越界判定用偏移 段长应为偏移 ≥ 段长4页表大小忘记乘进程数看清题目问单进程还是全系统5页表项大小自己猜用题目给的值6多级页表分级位数随意拆让每级页表正好占一页7有效访问时间漏算 TLB 查找命中和未命中都要加 ε8单位混用全部换算成纳秒再算9缺页处理时间漏加写回时间脏页换出要算进去10FIFO 用页框数算索引用进入顺序维护不要算下标11LRU 用上次访问时刻判断却记错时刻每步更新访问时刻表12OPT 漏看以后不再出现不再出现的优先级最高13FIFO 增加页框后缺页数一定减少Belady 异常可能变多14Clock 扫过不清访问位指针扫过即清零15局部置换能自动调整页框只有可变分配可以16工作集窗口定义想当然先确认按时间还是按次数17抖动判定只看缺页率要和可用页框数、工作集大小对比18分区回收只合并一侧四种邻近情况都要判断19动态分区分配后不重排序空闲表每次操作后按地址重排20十六进制地址硬算十进制页面为 2 的幂时直接按位对齐拆最后再补一句关于复习节奏的体会。我第一次做内存管理大题的时候是按照教材顺序一道一道刷的结果刷完第三章回头再看第二章的置换算法又忘了。后来改成按题型刷——今天只刷地址变换明天只刷置换算法每个题型连着做十道以上直到能在两三分钟内判断题型并写出公式。这个方法的效率比按章节顺序刷高出很多因为同一类题之间共享的套路被反复强化而跨题型的干扰被排除了。另外这类题建议手写练习而不是看着答案点头。看着答案觉得原来如此的题目真正动笔时大概率还是会在第一行就卡住。我自己的做法是把做错的题抄在一个本子上只写题干关键条件和最后卡住的那一步隔一周再做一次能独立做出来才算过。这个笨办法帮我省下了考场上大量的犹豫时间看到求有效访问时间我的手会先写出那几个单位换算而不是先发呆。
