mobile wallpaper 1
mobile wallpaper 2
mobile wallpaper 3
mobile wallpaper 4
9564 字
25 分钟
【872专业课】操作系统第三章:内存管理考研复习--24

操作系统第三章:内存管理#

依据所给 17 份讲义整理。记号约定:除特别说明外,按字节编址;页面大小记为 L,逻辑地址记为 A,页号为 P,页内偏移为 W,物理块号为 b。1 KiB=2^10 B、1 MiB=2^20 B;讲义中的 KB、MB 在计算题里通常按此二进制含义使用。

一、先建立全章框架#

核心问题对应知识
程序放哪里、地址怎么变装入与链接、逻辑地址和物理地址、重定位、地址保护
内存如何分给进程连续分配、动态分区算法、分页、分段、段页式
内存不够怎么办覆盖、交换、虚拟内存、请求分页、页面置换、页面分配策略
怎样提高速度或方便共享快表 TLB、多级页表、局部性、内存映射文件

主线:连续分配容易产生外部碎片;分页以固定大小的页框实现离散分配;分段按程序的逻辑模块划分;段页式兼顾逻辑模块和离散分配;请求分页进一步允许“部分页面在内存”,形成虚拟内存。

二、内存基础、地址与进程内存映像#

1. 编址、地址空间与保护#

  • 内存由可编址的存储单元组成。按字节编址时,每个地址对应 1 B;按字编址时,对应 1 个字,必须结合字长换算容量。若有 N 个可编址单元,至少需要 ceil(log2 N) 位地址。例如 4 GiB、按字节编址,需 32 位物理地址。
  • 逻辑地址由程序使用,描述进程自身地址空间中的位置;物理地址是实际内存单元地址。地址转换或重定位将前者映射到后者。
  • 内存管理的四项任务:内存空间分配与回收、从逻辑上扩充内存、地址转换、内存保护。
  • 连续分配时可用上下限寄存器直接检查物理地址,也可用基址(重定位)寄存器 + 界限(限长)寄存器:先检验逻辑地址在合法范围内,再加基址。考试要留意题目把“界限”定义为长度还是最大合法偏移:若是长度,合法条件 0≤A<长度;若是最大偏移,合法条件 0≤A≤最大偏移。

2. 从源程序到运行#

源程序 → 编译成目标模块 → 链接成装入模块 → 装入内存运行。

装入方式地址何时确定特点
绝对装入编译时形成绝对地址适合已知固定装入位置的简单环境
可重定位装入/静态重定位装入时一次性把逻辑地址改为物理地址运行中一般不能移动;讲义所述模型要求装入时分配所需空间
动态运行时装入/动态重定位执行指令、访问地址时转换依赖重定位硬件;允许运行中移动,便于动态管理

链接方式:静态链接在运行前连接全部目标模块与所需库;装入时动态链接在装入时边装入边链接;运行时动态链接在执行中需要某模块时才链接。不要把“动态链接”和“动态重定位”混为一谈:前者解决模块何时组合,后者解决地址何时转换。

3. 进程内存映像#

典型布局从低地址到高地址可理解为:代码/只读数据 → 可读写数据 → 堆 →(空闲虚拟地址区)→ 栈 → 内核地址区。代码段含指令和只读常量;数据段含全局变量、静态变量;堆用于动态分配;栈保存函数调用信息、参数与局部变量。堆通常向高地址增长,栈通常向低地址增长。

image-20261103160613963

4. 覆盖与交换(选修)#

  • 覆盖:同一程序中不会同时使用的模块共享覆盖区;常用模块常驻固定区。需要程序员设计覆盖关系,历史意义较大。
  • 交换:内存紧张时把整个进程暂时换出到外存,之后再换入;被换出的进程处于挂起态,可细分为就绪挂起、阻塞挂起。选择换入对象涉及中级调度。PCB 仍保留在内存供系统管理。
  • 区分:覆盖针对同一进程的模块,交换针对进程,请求分页的换入换出针对页面。

三、连续分配与动态分区算法#

1. 三种连续分配#

方式分配规则碎片与局限
单一连续分配内存分系统区、用户区;用户区只放一道程序无外部碎片,可能有较多内部碎片;并发度低
固定分区分配预先划分若干固定分区,每区最多一道作业无外部碎片;进程小于分区时有内部碎片,大进程可能无可用分区
动态分区分配进程到来时按其大小建立分区在讲义模型中通常无内部碎片,但会形成外部碎片

内部碎片在已分配区域内部,不能再分给别的进程;外部碎片是各个已分配区域之间零散的空闲空间。动态分区回收时,必须和前、后相邻的空闲区合并。若总空闲空间足够但没有一块连续空间满足请求,可通过紧凑移动进程合并空闲空间;紧凑需要可用的动态重定位支持,并有移动开销。

2. 动态分区分配算法#

假定空闲区依次为:(起始地址, 大小) = (0,10)、(20,30)、(60,20),请求 18 单位。

算法查找规则本例选中常见影响
首次适应 FF按地址递增,从头找第一块够大的(20,30)实现简单,低地址易产生小空闲区;讲义综合评价较好
最佳适应 BF找满足需求的最小空闲块(60,20)保留大块,但常留下难以利用的小碎片
最坏/最大适应 WF找最大的空闲块(20,30)减少特别小的剩余块,但大块消耗较快
邻近适应 NF按地址循环,从上次查找结束处继续取决于上次位置减少从头扫描,但可能更快用掉高地址的大块

考试做题时先确定空闲分区的排序规则、起点、是否循环、并列时的选择规则,再逐次更新空闲分区表。分配后可能将一个空闲区拆成“已分配区 + 剩余空闲区”;回收时判断前邻、后邻、双邻或无邻四种情况。

image-20261103161550531

四、基本分页存储管理#

1. 页、页框与页表#

  • 将进程的逻辑地址空间分为大小相同的页;将物理内存分为同样大小的页框/页帧/物理块。进程各页可放在不相邻的页框里。
  • 每个进程有自己的页表。页表项至少记录“该页所在的物理块号”;顺序存放的页表项,其页号可以由位置隐含,不一定需要单独存储。
  • 分页不产生外部碎片,但进程最后一页往往未填满,会产生内部碎片。页越大,页表项数越少,但页内浪费可能越大;页越小则相反。
  • 若物理内存 M 字节,页大小 L 字节,则页框数 M/L;物理块号至少需 ceil(log2(M/L)) 位。页表项的实际字节数还要考虑状态位、权限、对齐等,不能机械地等同于块号位数向上取整。

2. 地址结构与换算#

P = floor(A/L),W = A mod L;查页表得物理块号 b;物理地址 E=b×L+W。

若 L=2^k,低 k 位是页内偏移,高位是页号;物理地址也可视为“物理块号的二进制 + 页内偏移的二进制”。例如 32 位逻辑地址、4 KiB 页:页内偏移 12 位,页号 20 位;最多可表示 2^20 个虚拟页。若题目页大小不是 2 的幂,仍按整除和取余计算,不能强行按位切割。

计算例:页大小 1 KiB,逻辑地址 2500,页号 floor(2500/1024)=2,页内偏移 2500 mod 1024=452。若第 2 页映射到第 8 块,则物理地址 8×1024+452=8644。

3. 基本地址变换机构#

页表寄存器 PTR 保存页表始址 F 和页表长度 m。对逻辑地址 A:

  1. 算 P、W;若 P≥m,页号越界。
  2. 计算页表项位置 F+P×页表项长度,读出物理块号 b。
  3. 计算 E=b×L+W,访问目标单元。
image-20261103200712198

注意区分:页表长度是表项个数;页表项长度是每项占多少字节;页面大小是每页容量。若页表存放方式或表项对齐方式有特殊规定,计算表项位置须依题目条件。没有 TLB、也不计缺页时,查内存页表一次、访问数据一次,共 2 次访存。

4. 快表 TLB#

TLB 是保存近期页表项副本的高速缓存。命中时直接得到块号,随后访问目标内存,通常按 1 次主存访问计;未命中时先查主存页表,再访问目标内存,通常按 2 次主存访问计。TLB 查找本身的时间要按题目是否计入处理。

image-20261103201010984

设 TLB 查找时间 t、一次主存访问时间 T、命中率 h。若先查 TLB,未命中才查页表,平均时间为 h(t+T)+(1−h)(t+2T)。例如 t=1 μs、T=100 μs、h=0.9,结果 111 μs。若题目说明快表与慢表并行查找,则未命中路径可按 2T 计算,例中得到 110.9 μs。有数据 Cache、缺页开销或访存流水等条件时须重新建模。

5. 两级与多级页表#

单级页表可能过大,且需要大量连续位置存放。把页表分成多个页,再用页目录表记录各二级页表的位置,可让页表离散存储,并按需建立/调入下级页表。

经典例:32 位逻辑地址、4 KiB 页、页表项 4 B。页内偏移 12 位,页号共 20 位;每页能放 4096/4=1024=2^10 项,因此地址划分为 10 位页目录号 + 10 位二级页号 + 12 位偏移。无 TLB 且所需页表均在内存时,访问页目录、二级页表、目标数据,共 3 次主存访问。一般 n 级页表需 n+1 次主存访问。

image-20261103203340985

多级页表计算:页内偏移位数 k=log2 L;每页容纳的页表项数 q=L/页表项大小;每级最多索引 log2 q 位页号。40 位逻辑地址、4 KiB 页、4 B 表项:页号 28 位,每级最多 10 位,因此至少三级,可分成 8+10+10+12 位。

五、分段与段页式#

1. 基本分段#

按程序的逻辑模块划分长度可变的段,如主程序段、函数段、数据段。逻辑地址为**(段号 S,段内偏移 W);各段可离散放置,但每个段内部要连续。段表项记录段长 C和物理基址 B**。

地址转换:先检查 S<段表长度;再检查 W<C;最后计算物理地址 E=B+W。两个检查都是关键:页式通常检查页号是否合法,段式还要检查段内偏移是否越界。若段号、段内偏移分别占 s、w 位,则最多 2^s 段,每段可表示 2^w 个按编址单位计的地址;实际段长可以更短。

image-20261103203646958
对比分页分段
划分依据物理管理需要,页长固定程序逻辑模块,段长可变
程序员视角逻辑地址是一维的段名/段号和段内地址,二维
碎片可能有页内碎片,无外部碎片可能有外部碎片
共享和保护可做,但页边界未必对应逻辑模块以逻辑段为单位较方便

共享代码一般要求纯代码/可重入代码,不能因某进程写入而破坏其他进程使用。无快表时,查段表一次、访问数据一次,通常共 2 次主存访问。

2. 段页式#

先把进程按逻辑模块分段,再将每段分页;物理内存按页框分配。逻辑地址在硬件中可拆为段号 S + 段内页号 P + 页内偏移 W,但程序员仍以“段号 + 段内地址”的二维方式理解。

每进程有段表;段表项给出该段的页表位置及页表长度;每段各有页表。地址转换:检查段号 → 查段表 → 检查段内页号 → 查该段页表得物理块号 → 块号与页内偏移组成物理地址。无 TLB 时,查段表、查页表、访问数据,共 3 次主存访问。它便于按段共享和保护,同时用分页避免给整段寻找连续空间;仍可能有最后一页的内部碎片。

六、虚拟内存与请求分页#

1. 虚拟内存的思想#

传统方式常要求作业一次装入并一直驻留。基于时间局部性(近期访问的指令/数据可能再次访问)和空间局部性(邻近地址可能很快访问),系统只先装入当前需要的部分;缺少的部分按需从外存调入,内存不够时换出暂时不用的部分。特征是多次性、对换性、虚拟性。实现需要离散分配,典型方案是请求分页,也可有请求分段、请求段页式。

考研讲义常将可表示的虚拟空间上限写为 2^(虚拟地址位数) × 编址单位大小,并用 min(内存+外存容量,CPU 寻址范围) 作教材化的“实际容量”计算。现实系统还受映射、保留空间和后备存储政策等限制;考试按题目给定的模型计算。

2. 请求分页页表与缺页#

请求分页的页表项在基本映射信息之外,通常还包括:状态/存在位(页面是否在内存)、访问字段(供置换算法参考)、修改位(脏页是否需写回)、外存地址(页面在磁盘的位置)。

访问流程:查页号和页表项 → 若页面在内存,则转换并访问;若不在内存,产生缺页异常/内中断 → 保存现场,缺页进程等待磁盘 I/O → 若有空闲页框直接装入,否则按置换算法选牺牲页,脏页先写回 → 读入目标页、更新页表和相应 TLB 项 → 唤醒进程并重新执行产生缺页的指令。被换出页面对应的 TLB 项必须失效。缺页不一定置换:有空闲页框时只调页;一条指令可能多次缺页。

区分:页号越界是访问了进程不合法的地址;缺页是合法页面暂时不在主存,通常可以调入后继续。TLB 未命中只表示快表无该项,不必然缺页。

七、页面置换算法#

手算共同规则:画引用串,逐次记录当前页框内容;命中不计缺页;缺页但有空框不计置换;无空框才选择牺牲页。初次装页也要计入缺页次数。若题目给了初始页框状态、指针位置、访问位/修改位,以题目为准。

算法淘汰依据优缺点与考点
OPT 最佳未来最晚再用或永不再用缺页次数理论最少,需预知未来,不能实际实现;用于比较基准
FIFO 先进先出最早进入页框实现简单;命中通常不改变入队先后;可能出现 Belady 异常
LRU 最近最久未使用向过去看,最久未访问性能较好,但精确实现开销高;命中要更新最近使用次序
简单 CLOCK环形扫描,优先访问位为 0 的页遇 1 先置 0 并跳过;最多两轮找到牺牲页;置换后指针继续前进
改进型 CLOCK同看访问位 A 与修改位 M优先未访问且未修改,减少写回;按讲义的四轮扫描规则做题
image-20261103204918149
image-20261103204918149
image-20261103204846468
image-20261103204846468
image-20261103204824614
image-20261103204824614
image-20261103204948002
image-20261103204948002
image-20261103205258500
image-20261103205258500

改进型 CLOCK 的讲义规则:第一轮找 (0,0),不改位;未找到则第二轮找 (0,1),同时将扫描过的访问位置 0;仍未找到则第三轮找 (0,0);最后第四轮找 (0,1)。由于第二轮清除了访问位,最多四轮会选中。写题时要保留时钟指针当前位置,不能只按四类的静态优先级随意挑任一页。

Belady 异常:给更多页框,缺页次数反而增加。讲义用 FIFO 的经典引用串 3,2,1,0,3,2,4,3,2,1,0,4 演示:3 个页框缺页 9 次,4 个页框缺页 10 次。OPT 与 LRU 具有栈性质,不出现这种反常;考试中“只有 FIFO 会出现”应放在这几种常考算法的比较语境理解。

八、页面分配、调页与抖动#

  • 驻留集:分配给进程的物理页框集合。太小会频繁缺页,太大降低多道程序并发度。
  • 固定分配:运行中页框数不变;可变分配:可增减。局部置换只在本进程页框内选牺牲页;全局置换还可利用系统空闲页框或其他进程的页框。常见组合是固定分配局部置换、可变分配全局置换、可变分配局部置换;“固定分配全局置换”逻辑上不成立,因为取得他进程页框会改变驻留集大小。
  • 预调页:在缺页前预测并调入若干页,适合进程初次装入等场景;请求调页实际缺页才调入,目标页必然会用到,但每次缺页 I/O 成本高。
  • 抖动/颠簸:页刚换出又很快需要,频繁调页使系统忙于 I/O。根本原因通常是进程频繁使用的页数超过可用页框数;可适当增加驻留集或降低并发进程数。
  • 工作集:某个长度为 Δ 的近期窗口里实际访问过的不同页面的集合。工作集大小不一定等于窗口长度。驻留集若长期小于工作集,容易抖动。求工作集题只看当前窗口,去重即可。
  • 外存可分文件区与对换区。讲义给出不同的页面调入来源策略:对换区充足时可先把相关数据复制到对换区;对换区不足时只读页可由文件区直接调入、修改页需在换出时写入对换区;UNIX 风格中初次使用的页从文件区调入,已使用并换出的页可由对换区再次调入。按题设选择,不把某一种策略当作所有系统的统一实现。

九、内存映射文件#

传统文件 I/O 通过 seek/read/write 在文件与用户缓冲区间传递数据。内存映射文件把文件内容映射到进程虚拟地址区:程序通过普通内存访问读写映射区域;操作系统按需把文件页调入页框,并负责将修改结果按映射策略回写。多个进程映射同一文件的同一部分,可共享相应的物理页,便于共享数据。考试要区分“虚拟地址映射到文件内容”与“整个文件一次性装入内存”;映射并不意味着立即把全文件读进内存。修改何时、是否持久化取决于映射方式和同步机制,题目若未给条件不要绝对化。

十、考前速查公式与易错点#

题型公式/判断
地址位数ceil(log2 可编址单元数);先确认按字节还是按字编址
分页拆地址P=floor(A/L),W=A mod L;若 L=2^k,低 k 位为偏移
页式物理地址E=bL+W;必须先验证页号、存在位等条件
页表项位置连续且等长时 F+P×页表项长度
分段地址S<段表长度 且 W<段长,E=段基址+W
TLB 平均时间先查快表:h(t+T)+(1−h)(t+2T);并行查询另算
多级页表每级索引位数通常为 log2(页大小/页表项大小);无快表且无缺页时,n 级页表需 n+1 次主存访问
缺页率缺页次数/访问页面次数,与“置换次数”分开统计

高频混淆清单:

  1. 页是逻辑单位,页框是物理单位;页号不等于物理块号。
  2. 页表项存的是块号;块首址还需乘页大小。段表项存的是段基址和段长。
  3. TLB 未命中≠缺页;缺页≠页面置换;页号越界≠缺页。
  4. 分页、段页式可能有内部碎片;动态分区、纯分段可能有外部碎片。
  5. FIFO 看进入页框的先后;LRU 看最近访问的先后;OPT 看未来访问。
  6. 多级页表节省了对大块连续页表空间的需求,但若无 TLB,地址转换的主存访问次数上升。
  7. 对请求分页的执行时间题,若发生缺页,磁盘 I/O 耗时通常远大于 TLB 与主存访问,必须单列缺页路径。

十一、自测题(附简答)#

  1. 32 位逻辑地址、4 KiB 页、4 B 页表项,单级页表最多多大? 页号 20 位,最多 2^20 项,页表 2^20×4 B=4 MiB;存放它需要 1024 个 4 KiB 页框。
  2. 页大小 2 KiB,逻辑地址 6000,页 2 映射物理块 17。物理地址是多少? P=2,W=6000−2×2048=1904;E=17×2048+1904=36720。
  3. 段表中 3 号段长 500 B、基址 10000,逻辑地址 (3,500) 是否有效? 无效。段内最大合法偏移是 499。
  4. TLB 命中率 80%,TLB 2 ns,主存一次 100 ns,顺序查找平均时间? 0.8×102+0.2×202=122 ns,假设不发生缺页且不计其他缓存。
  5. 三个空页框,引用串 1,2,3,1,4,FIFO 与 LRU 各缺页多少次? 都是 4 次;最后访问 4 时,FIFO 淘汰 1,LRU 淘汰 2。虽然次数相同,最终页框内容不同。
  6. 窗口大小 5,最近五次访问为 2,3,2,4,3,工作集是什么? {2,3,4},大小为 3。

十二、专题精讲:把地址变换题做成固定流程#

地址变换是本章最值得反复练的题。做题时先写出地址结构,再做越界检查,最后算目标物理地址和访存次数。不要一看到地址就直接除以页大小。

1. 连续分配:基址与界限#

设某进程连续占用物理地址 [12000, 16999],基址为 12000,长度为 5000 B。逻辑地址 4999 合法,对应物理地址 16999;逻辑地址 5000 非法。若题目给的是“上限物理地址 16999”,则可先算 12000+A,再判定是否超过 16999。两种表述得到相同结论,但比较的对象不同。

静态重定位会把装入模块中的地址在装入时改好,因此进程运行后移动会让已改写的地址失效。动态重定位保留逻辑地址,每次访问时通过基址寄存器转换;进程移动后更新基址寄存器即可。这里的“每次访问”指硬件执行地址转换的逻辑,不等于一定要额外访问一次主存,访存次数仍按题设给出的机构计。

2. 分页:先确定“哪个页”,再确定“哪个块”#

设按字节编址,页大小 4 KiB,某进程页表如下:

逻辑页号物理块号
05
112
27
320

逻辑地址 10000:10000=2×4096+1808,所以页号 2,偏移 1808。页 2 在物理块 7,故物理地址 7×4096+1808=30480。如果页表长度是 4,页号 4 就越界;不能因为“内存里有第 4 块”就认为第 4 页有效。

页表项大小题要先求物理块编号范围。例如物理内存 4 GiB、页大小 4 KiB,共 2^20 个物理块,块号至少 20 位。若只记录块号,理论上 3 B 能放下 20 位;但实际页表项可能选 4 B,便于 4 KiB 的页正好容纳 1024 项,也为权限等信息留位。页表项“理论最少字节数”和题目指定的“实际字节数”必须分开。

一页可放多少页表项:floor(页面大小/页表项大小)。若页 4096 B、表项 3 B,可放 1365 项,剩余 1 B。若题目规定页表的每个存储页都不得跨页放表项,则第 1365 号表项从下一页开始,不能简单用 页表始址+1365×3;若题目明确页表紧密连续、允许表项跨页,则按连续公式。讲义强调为了简化查表,常把表项长度选成能整除页面大小的值。

3. 分段:必须做两次合法性检查#

设段表长度为 3,段 1 的段长为 3000 B、物理基址为 50000。逻辑地址 (1,2999) 合法,对应 52999;(1,3000) 段内越界;(3,0) 段号越界。这里段长 3000 的合法偏移范围是 0~2999,段号从 0 起,段表长度 3 对应段号 0、1、2。

纯分段的段长随程序模块而变。即使段内偏移字段有 16 位、理论上能表示 0~65535,某个实际段也可能只有 3000 B,因此仍须检查段表项中的实际段长。

4. 段页式:分段检查在前,分页查询在后#

设页大小 1 KiB;段表长度为 2;段 1 的页表长度为 3,页表映射 页 0→块 8、页 1→块 4、页 2→块 11。要访问段内地址 2500,可拆为段号 1、段内页号 floor(2500/1024)=2、页内偏移 452。段 1 合法,页 2 也合法,物理地址是 11×1024+452=11716。若段内地址改为 3072,段内页号变为 3,页表长度只有 3,因此越界。

有的题目直接给三元组 (段号,页号,页内偏移);有的给 (段号,段内地址)。先按题目格式拆地址,不能将段号误当成全进程统一的页号。段页式中各段有各自的页表,页号从每段内部重新编号。

5. 多级页表:从最高级逐级索引#

32 位逻辑地址、4 KiB 页、4 B 页表项的两级页表,地址格式是 [10 位目录号 | 10 位二级页号 | 12 位偏移]。例如 (目录号 0, 二级页号 1, 偏移 4095):若目录项 0 指向的二级页表中,第 1 项给出物理块 4,最终物理地址 4×4096+4095=20479。目录项记录的是下一级页表的位置,不是目标数据页框。

与单级相比,两级页表可在页目录里把尚未用到的大片地址范围标成不存在,无须为其分配二级页表。进程只用到一个小范围时,页目录加少量二级页表即可;但没有 TLB 时查表级数增多,所以单次地址转换更慢。页表本身若也被换出,具体缺页处理和计时要看题设。

十三、专题精讲:时间、次数与异常的判题顺序#

1. 访存次数表#

下表只计主存访问,假设页表或段表已在主存、没有数据 Cache、也没有缺页:

机构转换时要查的表访问目标合计
基本分页,单级页表1 次1 次2 次
分段1 次1 次2 次
段页式段表、页表各 1 次1 次3 次
两级页表页目录、二级页表各 1 次1 次3 次
n 级页表n 次1 次n+1 次
快表命中0 次主存查表1 次1 次
快表未命中、单级页表1 次主存查表1 次2 次

TLB 本身也耗时,但题目若问“访存次数”,通常不把访问 TLB 算为访问主存。遇到快表与慢表同时查找的题,要看它问次数还是耗时:并行不等于没有查慢表,而是两路查找的时间重叠。

2. 平均访问时间怎么列式#

先画两条路径,再乘概率。例:TLB 查找 2 ns,主存一次 100 ns,命中率 80%,先查 TLB,未命中再查主存页表。

  • 命中:2+100=102 ns。
  • 未命中:2+100+100=202 ns。
  • 平均:0.8×102+0.2×202=122 ns。

若还给缺页率 f,先分别列出“没有缺页时”和“发生缺页时”的完整路径,再写 平均时间=(1−f)×正常路径时间+f×缺页路径时间。缺页路径可能包含查页表、磁盘读取、脏页写回、进程切换和指令重启;题目给哪些费用就计哪些,切勿直接在 122 ns 上机械加一个磁盘时间。

3. 三种情况必须区分#

现象判断点常见处理
TLB 未命中快表里没有这个页的映射查内存页表;页面可能仍在内存
缺页页表项显示合法页面当前不在内存产生可恢复异常,调页;可能需要置换
地址越界/非法访问页号、段号或段内偏移超合法范围不能靠调页使非法地址变合法

请求分页中,先判断访问的虚拟地址属于进程的合法范围;之后再根据存在位判断是否缺页。缺页次数统计“需要调入目标页”的次数;置换次数统计“因无空闲页框而赶走旧页”的次数;后者通常不大于前者。

十四、专题精讲:分区分配题的完整推演#

假设初始空闲分区为 A:(0,10)、B:(20,30)、C:(60,20),括号内是 (起始地址, 大小);先后申请 18、9 单位,每次从选中空闲区的低地址端划出请求大小。暂不考虑其他已分配区。

算法第一次申请 18更新后的空闲区第二次申请 9再次更新后
首次适应选 B,分配 [20,38)(0,10),(38,12),(60,20)从头选 A,分配 [0,9)(9,1),(38,12),(60,20)
最佳适应选 C,分配 [60,78)(0,10),(20,30),(78,2)选 A,分配 [0,9)(9,1),(20,30),(78,2)
最坏适应选 B,分配 [20,38)(0,10),(38,12),(60,20)选 C,分配 [60,69)(0,10),(38,12),(69,11)

此表的区间采用左闭右开记法,[20,38) 长度 18。正式题目若给地址范围为“起始地址到结束地址,均包含”,则末地址是 起始地址+长度−1。邻近适应还必须知道上次搜索停在何处;少了这一条件,可能不能唯一决定第二次选哪个空闲区。

回收练习:已有空闲区 [100,120)、[140,160),回收 [120,140) 后,三个相邻区应合并成 [100,160),长度 60。若只和前一个区合并而忘了后一个,后续分配题就会错。紧凑则是移动仍在使用的进程以消除不相邻的外部碎片,和“回收时合并相邻空闲区”不同。

十五、专题精讲:置换算法逐步演算#

设有 3 个初始为空的页框,引用串是 1,2,3,1,4,1,2。每一步先判断命中,再决定是否有空框,最后才按算法选择牺牲页。

访问FIFO 页框状态FIFO 缺页?LRU 页框状态LRU 缺页?OPT 页框状态OPT 缺页?
1[1,-,-]是[1,-,-]是[1,-,-]是
2[1,2,-]是[1,2,-]是[1,2,-]是
3[1,2,3]是[1,2,3]是[1,2,3]是
1[1,2,3]否[1,2,3]否[1,2,3]否
4[4,2,3],淘汰 1是[1,4,3],淘汰 2是[1,2,4],淘汰 3是
1[4,1,3],淘汰 2是[1,4,3]否[1,2,4]否
2[4,1,2],淘汰 3是[1,4,2],淘汰 3是[1,2,4]否
合计缺页654

在访问第 4 页时,OPT 看后面的 1,2,发现当前在内存的 3 以后不会再用,因此淘汰 3。FIFO 的第 4 次访问虽然命中页 1,也不改变它最早进入内存这一事实;LRU 则必须把这次命中记作页 1 的最近使用。

CLOCK 手算步骤:先画页框的环、标每页访问位和指针。发生替换时,从指针处逐项检查:遇访问位 1,就清 0 并向前;遇 0,就选中替换;新页的访问位通常置 1,指针移向下一框。访问已在内存的页,只把该页访问位置 1,不要因为命中就随意移动替换指针。题目若指定初始位与替换后指针规则,严格依其设定。

改进型 CLOCK 手算除了访问位还要标修改位。(0,0) 代价最小,(0,1) 需要写回;遇到 (1,0)、(1,1) 时,按讲义的轮次规则清访问位后再考虑。由于扫描有起点,两个同类页不一定选页号小的那个,应该选本轮扫描先碰到的那个。

十六、专题精讲:驻留集、工作集与磁盘来源#

1. 固定/可变与局部/全局是两个维度#

“固定”回答页框数是否随运行改变;“局部”回答牺牲页从哪里挑。因此固定分配局部置换的规则是:进程缺页且自己的页框已满,只在自己的页中淘汰一个,页框数保持不变。可变分配全局置换则可为缺页进程增加一个空闲框,甚至从其他进程取得框;缺页进程与受害进程的驻留集都可能改变。可变分配局部置换允许根据缺页频率调整页框数,但某一次置换仍在本进程页面内进行。

2. 工作集用滑动窗口求#

访问串 2,4,2,5,4,7,窗口大小 Δ=4:

  • 访问到第 4 次时,窗口 2,4,2,5,工作集 {2,4,5},大小 3。
  • 访问到第 5 次时,窗口 4,2,5,4,工作集仍为 {2,4,5}。
  • 访问到第 6 次时,窗口 2,5,4,7,工作集 {2,4,5,7},大小 4。

窗口移动时要删掉过期访问,但若同一页仍在窗口内,不能把它从工作集删掉。工作集是集合,重复访问只算一个页面。工作集大小增大通常说明该进程近期活跃页变多,可考虑增加驻留集;多个进程的工作集总需求超过可用页框时,系统容易抖动。

3. 脏页与后备存储#

读入页面是一次磁盘 I/O;替换未修改页一般不需要写回,替换修改页/脏页则通常要先写回再读入新页,所以代价更高。改进型 CLOCK 把修改位纳入选择依据正是为减少这类写盘。磁盘上页面的来源可能是可执行文件/普通文件,也可能是对换区,具体回写目标按文件映射方式和题目描述判断。

十七、考研答题模板与复习优先级#

1. 地址转换题模板#

已知页面大小 L=…,因此页内偏移占 log2 L 位;逻辑地址 A=… 得 P=…、W=…。检查 P<页表长度,并查得页表项中的块号 b=…。故物理地址 E=bL+W=…。无快表/快表命中/未命中的访存次数分别按题设列出。

分段题把中间两句改为“检查段号合法、检查偏移小于实际段长、取段基址”,再用 E=段基址+偏移。段页式题则先查段表和该段页表,再算地址。

2. 算法题模板#

写出当前空闲分区/页框状态 → 指明本次请求是否命中或能直接分配 → 如须选择,说明依据 → 更新状态 → 统计缺页、置换、写回等不同次数。

不要只写最终数字。考研主观题往往要看每一步选择是否符合算法,尤其是 FIFO、LRU、CLOCK 和动态分区的连续操作。

3. 建议的复习顺序#

  1. 先拿稳计算:页号/偏移/物理地址、段长越界、TLB 平均时间、多级页表位数。
  2. 再刷算法:首次/最佳/最坏/邻近适应;OPT/FIFO/LRU/CLOCK,练到能逐步更新状态。
  3. 最后串概念:内部与外部碎片、局部性、请求分页流程、驻留集与工作集、抖动、内存映射文件。
分享

如果这篇文章对你有帮助,欢迎分享给更多人!

部分信息可能已经过时

目录