考频地图
这一章公式不多,但每个公式都要求你先把“地址长什么样”想清楚。建议每个计算都先画一条地址位划分条,再动笔。
| 考点 | 考频 | 常见题型 | 必须会的动作 |
|---|---|---|---|
| 连续分配算法 | ★★★☆☆ | 选择:首次/最佳/最坏适应、碎片 | 模拟一串分配/回收后的空闲区 |
| 分页地址转换 | ★★★★★ | 选择/综合:页号、偏移、物理地址 | 拆位 → 查表 → 拼接 |
| 页表大小、页表项长度 | ★★★★☆ | 选择/综合 | 算位数,再乘项数 |
| 多级页表 | ★★★★☆ | 选择/综合:位划分、级数、访存次数 | 每级页表不超过一页 |
| TLB 与有效访问时间 | ★★★★★ | 计算 | 画出命中/未命中两条路径 |
| 分段与段页式 | ★★★☆☆ | 选择:越界判断、共享、访存次数 | 两次越界检查 |
| 页面置换 | ★★★★★ | 选择/综合:缺页次数、置换顺序 | 画页框表,逐列推 |
| 抖动与工作集 | ★★★☆☆ | 选择 | 数窗口内不同页数 |
基础:地址与保护
一、逻辑地址与物理地址
写程序时,编译器不知道程序将来会被放在内存的哪个位置,所以生成的地址都是从 0 开始的“相对地址”,叫逻辑地址(虚拟地址)。程序真正在内存里的位置叫物理地址。把逻辑地址变成物理地址的过程叫地址重定位(地址变换)。
| 装入方式 | 地址何时转换 | 特点 |
|---|---|---|
| 绝对装入 | 编译时就确定物理地址 | 只适合单道程序 |
| 可重定位装入(静态重定位) | 装入内存时一次性全部改好 | 必须一次分配全部所需内存;运行中不能移动 |
| 动态运行时装入(动态重定位) | 执行到这条指令时才转换,靠重定位寄存器 | 程序可在内存中移动;可以只装一部分;现代 OS 采用 |
二、内存保护:不许越界
每个进程只能访问自己的内存。常用“重定位寄存器 + 界地址寄存器”实现,两个寄存器都只能由内核用特权指令修改:
三、覆盖与交换(内存扩充的早期手段)
同一个程序内部:把不会同时运行的模块轮流放在同一块内存(覆盖区)里。需要程序员声明覆盖结构,对用户不透明,已基本淘汰。
在进程之间:把暂时不能运行的进程整个换出到外存的对换区,把就绪进程换入。就是第 2 章的中级调度。对换区用连续分配,追求换入换出速度。
连续分配
最直接的想法:给每个进程一块连续的内存。问题在于“块切多大”,于是有了三种方案,各自产生不同的“碎片”。
| 方案 | 做法 | 碎片 | 问题 |
|---|---|---|---|
| 单一连续分配 | 内存分系统区和用户区,用户区只放一道程序 | 内部碎片 | 只能单道,利用率极低 |
| 固定分区分配 | 用户区事先划成若干固定大小的分区(可大小相等或不等),每区放一道 | 内部碎片 | 程序太大放不下;小程序浪费 |
| 动态分区分配 | 进程来时按需切一块恰好大小的分区 | 外部碎片 | 要选从哪个空闲区切 → 四种算法 |
一、动态分区的四种分配算法
| 算法 | 空闲分区链排序 | 选哪块 | 效果 |
|---|---|---|---|
| 首次适应 FF | 按地址递增 | 第一个够大的 | 综合性能最好,开销小;低地址处留下很多小碎片 |
| 邻近适应 NF(循环首次) | 按地址递增,循环链表 | 从上次结束的位置往后找第一个够大的 | 空闲区分布更均匀,但高地址的大分区也会被切碎 |
| 最佳适应 BF | 按容量递增 | 够大的里面最小的 | 保留大分区;但会留下最多、最小的外部碎片 |
| 最坏适应 WF | 按容量递减 | 最大的 | 剩下的块还比较大能用;但大分区很快被用光,大进程来了没地方放 |
二、回收:和相邻的空闲区合并
- 最佳适应不是“性能最佳”,反而会产生最多的小碎片。综合性能最好的是首次适应。
- 动态分区没有内部碎片,固定分区没有外部碎片。
- “紧凑”需要动态重定位支持,因为进程在内存中的位置会变。
基本分页与 TLB
连续分配像订酒店要求“一整层楼连着的 20 间房”,很难凑齐。分页像旅行团住宿:把团员按 4 人一组分好(页),酒店里任何空着的 4 人间(页框 / 物理块)都能住,导游手里有一张“第几组住几号房”的对照表(页表)。
一、基本思想
- 把内存切成大小相等的小块,叫页框(页帧、物理块、内存块),编号 0, 1, 2, …
- 把进程的逻辑地址空间切成同样大小的块,叫页(页面),编号 0, 1, 2, …
- 每页装入任意一个空闲页框,不需要连续。用一张页表记录“第 i 页 → 第几号块”。
- 没有外部碎片;只有每个进程最后一页可能没装满,产生少量内部碎片。
二、地址结构:一条地址怎么拆
页面大小一定是 2 的整数次幂。若页面大小为 2k 字节,那么逻辑地址的低 k 位就是页内偏移 W,剩下的高位就是页号 P。以 32 位地址、4 KB 页为例:
十六进制地址最方便:4 KB 页的偏移是 12 位 = 正好 3 个十六进制位,直接“切”就行。
三、地址变换的完整过程
例:十六进制地址
四、页表项长度与页表大小
页表项至少要能放下“块号”。块号有多少位,由物理内存有多少块决定:
第 5 步就是问题所在:每个进程都要一张 4 MB 且连续存放的页表,而大部分表项根本用不到。这引出了第 04 节的多级页表。
五、快表 TLB:让地址转换不用多跑一趟内存
基本分页每次访存要先读一次页表(在内存里),等于访存次数翻倍。根据局部性,最近用过的页很可能马上又用,于是在 CPU 里放一个小而快的相联存储器,缓存最近用过的“页号 → 块号”对,叫快表(TLB);内存中的页表相应叫慢表。
例:t = 10 ns,m = 100 ns,h = 90%,单级页表:EAT = 0.9 × 110 + 0.1 × 210 = 99 + 21 = 120 ns。若无快表要 200 ns。
- 页内偏移在地址转换前后不变,只换页号部分。
- 页表寄存器 PTR 平时存放正在运行的进程的页表始址和长度;进程不运行时,这两个值存在它的 PCB 里。
- 越界检查比较的是 页号 P ≥ 页表长度 M(等于也越界,因为页号从 0 开始)。
- TLB 是页表的缓存,不是页表本身;它和 Cache 是两个东西:TLB 缓存页表项,Cache 缓存数据。
- 页面越大:页表越小、TLB 覆盖范围越大,但内部碎片越大。
多级页表
单级页表像一本“把每一页内容都列在一张巨大目录里”的书:4 MB 的目录,还必须装订在一起。两级页表改成“先查章目录,再查章内的节目录”:没写的章,根本不用印它的节目录。
一、为什么需要多级页表
单级页表的问题不只是“大”,还有两个:必须连续存放(1024 个连续页框不好找),以及大部分表项用不到(一个进程通常只用到代码段附近和栈附近的一小部分地址)。解决办法:把页表本身也分页,再给这些“页表页”建一张目录。
二、两级页表的地址结构
核心规则:每一级页表的大小不超过一页。4 KB 页、4 B 页表项 → 一页能放 4 KB / 4 B = 1024 = 2¹⁰ 项 → 每级索引 10 位。32 位地址减去 12 位偏移剩 20 位页号,正好拆成 10 + 10:
三、页表基址寄存器里存什么
两级页表的“根”是页目录。页表基址寄存器(PTBR;x86 中叫 CR3)保存的是页目录的物理基址,不是二级页表的基址:
| 位置 | 保存的内容 | 例子 |
|---|---|---|
| CR3 / PTBR | 页目录的物理基址 | 0x00002000 |
| 页目录项 PDE[1] | 第 1 张二级页表的物理基址 + 标志位 | 0x00004000 |
| 二级页表项 PTE[3] | 数据页框的物理基址 + 标志位 | 0x00007000 |
四、二级页表地址变换全过程
设 CR3 = 0x00002000,PDE[1] = 0x00004000,PTE[3] = 0x00007000,访问逻辑地址 0x00403A4F:
- 拆地址:页目录号 = (A >> 22) & 0x3FF = 1,二级页号 = (A >> 12) & 0x3FF = 3,偏移 = A & 0xFFF = 0xA4F。
- 查页目录:PDE 地址 = CR3 + 1 × 4 = 0x2004,读出 0x4000(二级页表基址)。
- 查二级页表:PTE 地址 = 0x4000 + 3 × 4 = 0x400C,读出 0x7000(页框基址)。
- 拼地址:0x7000 + 0xA4F = 0x7A4F。
为突出地址关系,上面的 PDE/PTE 省略了 Present、R/W、U/S 等标志位。真实表项的低 12 位是标志位;访问时先检查 Present 位,不存在就触发缺页异常。
- 省空间:只为用到的地址范围建二级页表,稀疏地址空间收益最大
- 不要求连续:页目录和各二级页表都是独立的页
- 可扩展:64 位系统用 4–5 级页表
- 访存次数增加:n 级页表 TLB 未命中要 n + 1 次访存
- 更依赖 TLB:没有 TLB 性能损失很明显
- 全满时不省:地址空间全部用上时,总大小 ≈ 单级页表 + 一个页目录
- CR3 存的是页目录基址;二级页表基址在 PDE 中。CR3、PDE、PTE 里存的都是物理地址。
- 两级页表不是“页表项变少”,总 PTE 数仍是 2²⁰;省掉的是没用到的二级页表页。
- 算级数时,顶级页表不一定满:如 36 位页号、每级 10 位 → 4 级,顶级只用 6 位。
- 题目若说“页目录占一页”,就用“页目录项数 × 项大小 ≤ 页大小”反推每级位数。
分段与段页式
分页是从系统角度切的:一刀一刀等长,不管里面是代码还是数据。可程序员眼中的程序是按逻辑组织的:主程序、子函数、栈、全局数据……分段就按这种逻辑单位来分,每段长度不一,便于共享和保护。
一、分段的地址变换
逻辑地址是二维的:(段号 S, 段内偏移 W)。段表每项记录段长 C 和段基址 b。比分页多一次检查——段内偏移不能超过段长:
| 段号 | 基址 | 段长 |
|---|---|---|
| 0 | 219 | 600 |
| 1 | 2300 | 14 |
| 2 | 90 | 100 |
| 3 | 1327 | 580 |
| 4 | 1952 | 96 |
注意:分段的物理地址是 基址 + 偏移(加法),而分页是 块号 × 页大小 + 偏移(拼接)。
二、分页 vs 分段
| 对比 | 分页 | 分段 |
|---|---|---|
| 划分依据 | 物理单位,系统按固定大小切 | 逻辑单位,按程序的自然结构分 |
| 大小 | 固定,由系统决定 | 不固定,由程序决定 |
| 对用户 | 透明,用户感觉不到 | 可见,编程时需显式给出段名 |
| 地址空间 | 一维:给一个地址就能拆出页号 | 二维:必须同时给出段号和段内偏移 |
| 碎片 | 内部碎片(最后一页) | 外部碎片 |
| 共享与保护 | 不方便:一页里可能混着代码和数据 | 方便:段是完整逻辑单位,整段设权限、整段共享 |
共享:只有纯代码(可重入代码)能被共享——它运行时不修改自己。共享时,各进程的段表项指向同一个物理段。
三、段页式:先分段,段内再分页
- 分段的越界检查有两次:段号 ≥ 段表长度,或段内偏移 ≥ 段长。
- 分段管理有外部碎片,段页式只有内部碎片(段内是分页)。
- 段页式下“页号 + 偏移”的总位数决定了单段最大长度。
虚拟内存与页面置换
前面的分页、分段都要求进程全部装入内存才能运行。可程序在一段时间内往往只用到一小部分(局部性),那就只装一部分,用到别的再从磁盘调进来。这样,一个 8 GB 内存的机器能跑总共需要 20 GB 的程序——这就是虚拟内存。
一、凭什么能“只装一部分”:局部性原理
刚访问过的地址,很可能马上再访问(循环、计数器变量)。
访问了某地址,很可能马上访问附近的地址(顺序执行、遍历数组)。
虚拟内存的三个特征:多次性(分多次调入)、对换性(运行中可换进换出)、虚拟性(逻辑上扩充了容量)。
虚拟内存的最大容量受两个限制:① 地址位数,32 位最多 4 GB;② 内存 + 外存对换区的容量。实际容量取两者的较小值。
二、请求分页:页表要多几个字段
| 页号 | 物理块号 | 状态位 P | 访问字段 A | 修改位 M | 外存地址 |
|---|---|---|---|---|---|
|
状态位:这页在不在内存(1 在 / 0 不在 → 缺页)。 访问字段:最近被访问过没有 / 访问次数,供置换算法挑“该换谁”。 修改位:调入后被写过没有。被写过的“脏页”换出时要写回磁盘,没写过的直接丢弃。 外存地址:这页在磁盘上的位置,缺页时去这里读。 | |||||
三、缺页中断的处理流程
四、页面置换算法
内存满了又缺页,就得挑一页“请出去”。挑得好,后面缺页少;挑得不好,刚换出去马上又要用,来回折腾。
| 算法 | 换出谁 | 能实现吗 | 特点 |
|---|---|---|---|
| OPT 最佳 | 以后最长时间不会再用的页 | 不能(要预知未来) | 缺页最少,作为衡量其他算法的标准 |
| FIFO 先进先出 | 最早调入内存的页 | 能,一个队列 | 简单;与访问规律不符,唯一会出现 Belady 异常 |
| LRU 最近最久未使用 | 过去最长时间没被访问的页 | 能,但需要硬件支持(寄存器或栈) | 性能最接近 OPT,开销大 |
| CLOCK(NRU) | 环形扫描,跳过访问位为 1 的页(并清零),换出第一个访问位为 0 的 | 能,开销小 | LRU 的近似 |
| 改进 CLOCK | 同时看访问位 A 和修改位 M,优先换“没访问也没修改”的 | 能 | 减少写回磁盘的次数 |
手算方法:画页框表
以经典访问串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1、3 个页框为例,三种算法的缺页次数为:OPT 9 次,LRU 12 次,FIFO 15 次(都包含最开始装满 3 个空页框的 3 次缺页)。手算时:
- 横向写访问串,纵向画 3 行(页框)。每一列表示“这次访问之后各页框里装着什么”。
- 命中:照抄上一列。缺页且有空框:放进空框。缺页且满了:按算法挑一页替换,记一个 ✗。
- OPT:往右看,换最晚才再出现(或不再出现)的。LRU:往左看,换最早一次出现的。FIFO:换在框里待得最久的。
Belady 异常
直觉上页框越多缺页越少,但 FIFO 有例外:访问串 1 2 3 4 1 2 5 1 2 3 4 5,3 个页框缺页 9 次,4 个页框反而缺页 10 次。在上面的模拟器里选“Belady 异常示例”,再点“对比”即可看到。LRU 和 OPT 属于“栈式算法”,不会出现 Belady 异常。
CLOCK 算法图解
改进型 CLOCK 用 (访问位 A, 修改位 M) 把页分成四类,优先级从高到低:(0,0) 最近没用也没改 → (0,1) 没用但改过 → (1,0) → (1,1)。扫描规则:
- 第一轮:找 (0,0),不修改任何标志位,找到就换。
- 第二轮:找 (0,1),扫过的页把访问位清 0,找到就换。
- 还没找到:此时所有访问位都已为 0,回到第一轮重复,必然能找到。最多扫描四轮。
五、页框分配与抖动
| 策略 | 含义 | 说明 |
|---|---|---|
| 固定分配 + 局部置换 | 页框数固定,缺页只能换自己的页 | 页框数难以确定 |
| 可变分配 + 全局置换 | 缺页时可以从系统空闲池拿,或换任意进程的页 | 被抢页的进程缺页率会上升 |
| 可变分配 + 局部置换 | 只换自己的页,但 OS 根据缺页率动态增减页框数 | 效果较好 |
| 不存在“固定分配 + 全局置换”:固定了页框数,就不能去抢别人的。 | ||
何时调入:预调页(运行前一次调入若干相邻页,用于首次启动)和请求调页(运行中缺页时调入)。从何处调入:对换区够用时都从对换区(快);不够时不会修改的页从文件区、可能修改的页换出到对换区;UNIX 方式是第一次从文件区,之后从对换区。
抖动(颠簸)
刚换出的页马上又要用,刚换进的页马上又被换出,进程大部分时间花在换页上,CPU 利用率急剧下降。根本原因:分配给进程的页框数太少,装不下它当前频繁访问的页(或置换算法选得差)。
解决:减少并发进程数(挂起一些进程)、增加页框、用工作集模型控制分配。
工作集
工作集大小会随时间变化。OS 的策略:给进程分配的页框数 ≥ 工作集大小,否则会抖动;所有进程工作集之和超过内存时,挂起一些进程。
六、缺页对访存时间的影响
综合题常把 TLB、页表、缺页、Cache 串在一起问“访问某地址共需多少时间”。做法:画出这个地址的完整路径(TLB 是否命中 → 页表是否有效 → 缺页处理后重新执行 → 数据是否在 Cache),每一步的时间逐项相加。
七、内存映射文件
进程通过系统调用(如 mmap)把一个磁盘文件映射到自己的虚拟地址空间,之后像访问内存数组一样读写文件,由缺页机制按需把文件内容调入,写回由 OS 负责。多个进程映射同一文件时,可以共享同一组物理页框,实现进程间共享。
- 只有 FIFO 会出现 Belady 异常。
- OPT 换的是“将来最久不用”,LRU 换的是“过去最久没用”,方向别搞反。
- 缺页次数要算上最开始装入空页框的那几次;“置换次数”则不算。看清题目问哪个。
- 抖动的主要原因是分配的页框太少,不是“页面太大”或“内存太小”本身。
- 虚拟内存的实际容量 ≤ min(2地址位数, 内存 + 对换区)。
真题与自测
一、真题问法
问法 1(地址转换):给出页面大小、页表内容和若干逻辑地址,求物理地址或判断是否缺页。→ 拆位 → 越界检查 → 查有效位 → 拼接。
问法 2(页表结构):“某系统虚拟地址 32 位,页大小 4 KB,页表项 4 B,采用二级页表,页目录占一页。问逻辑地址如何划分?”→ 10 | 10 | 12。
问法 3(访存时间):给出 TLB 时间、内存时间、命中率、缺页率,求有效访问时间或某次访问的具体时间。→ 列出每条路径。
问法 4(置换):给出访问串和页框数,求某算法下缺页次数、被淘汰页序列,或某时刻页框内容。→ 画页框表。
问法 5(综合):与组成原理联合,给出虚拟地址、TLB 内容、页表、Cache 内容,追踪一次访存的全过程。→ 先把虚拟地址拆成“虚页号 + 页内偏移”,再把物理地址拆成“Cache 标记 + 组号 + 块内地址”。
二、折叠自测
1. 页面大小 2 KB,逻辑地址 5000(十进制),页号和偏移各是多少?
P = ⌊5000 / 2048⌋ = 2,W = 5000 − 4096 = 904。
2. 32 位逻辑地址、页面 8 KB、页表项 4 B,单级页表最大多大?
偏移 13 位,页号 19 位,页表 2¹⁹ 项 × 4 B = 2 MB。
3. 内存 100 ns,TLB 20 ns,命中率 80%,单级页表,EAT 是多少?
0.8 × (20 + 100) + 0.2 × (20 + 200) = 96 + 44 = 140 ns。
4. 两级页表、无 TLB,访问一个数据要访问几次内存?有 TLB 且命中呢?
无 TLB:页目录 1 次 + 二级页表 1 次 + 数据 1 次 = 3 次。TLB 命中:只需访问数据 1 次。
5. 页表项能否只存块号?为什么页号不用存?
基本分页中可以只存块号(实际还会有保护位等)。页表按页号顺序连续存放,页号就是表项的下标,通过“页表始址 + 页号 × 项长度”直接定位,所以不必存。
6. 分段为什么比分页更容易实现共享和保护?
段是逻辑上完整的单位(如一个函数库),整段要么可共享要么不可、整段设同一权限;而一页里可能既有可共享的代码又有私有数据,难以统一设置。
7. 访问串 1 2 3 4 1 2 5 1 2 3 4 5,4 个页框,LRU 缺页几次?
8 次。前 4 次装入缺页;之后 1、2 命中;5 缺页换 3;1、2 命中;3 缺页换 4;4 缺页换 5;5 缺页换 1。共 4 + 4 = 8 次。
8. 哪些置换算法会出现 Belady 异常?
只有 FIFO。OPT 和 LRU 都是栈式算法,页框数增加时缺页次数不会增加。
9. 系统发生抖动时,CPU 利用率高还是低?应该增加还是减少多道程序度?
CPU 利用率很低(进程大都在等换页的 I/O),磁盘却很忙。应该减少多道程序度,即挂起一些进程,让剩下的进程有足够的页框。
10. 48 位虚拟地址、页面 4 KB、页表项 8 B、每级页表占一页,需要几级页表?
偏移 12 位,页号 36 位;一页放 4096 / 8 = 512 = 2⁹ 项,每级 9 位;36 / 9 = 4 级。
三、考前速览
偏移不变,只换页号。
页表大小 = 页数 × 页表项长度。
每级页表不超过一页,n 级未命中访存 n + 1 次。
OPT 看未来,LRU 看过去,FIFO 看进入顺序。
抖动 = 页框不够装工作集。
① 最佳适应碎片最多,不是性能最好。
② 页号 = 页表长度也越界。
③ 分页一维、分段二维。
④ 只有 FIFO 有 Belady 异常。
⑤ 不存在固定分配全局置换。