首页/操作系统/第 3 章 内存管理
408 计算机学科专业基础 操作系统 第 3 章

内存管理
分页、多级页表与虚拟内存

OS 计算题的第二大来源,常与组成原理的 Cache/TLB 合出综合题:地址转换、页表大小、多级页表、TLB 有效访问时间、页面置换缺页次数,这五类题必须会动手算。

全章是一个“问题 → 解决 → 新问题”的故事:连续分配有外部碎片 → 分页把内存切小块;页表太大 → 多级页表;内存不够 → 虚拟内存只装一部分;装不下了换谁 → 页面置换。

6 个考点模块 5 类计算 4 个交互模拟器 13 张图
页号 P W 页表 P → 块号 b 块号 b W 偏移原样搬过去
00
复习策略

考频地图

★★★★★ 核心章 选择 + 计算 + 综合

这一章公式不多,但每个公式都要求你先把“地址长什么样”想清楚。建议每个计算都先画一条地址位划分条,再动笔。

考点考频常见题型必须会的动作
连续分配算法★★★☆☆选择:首次/最佳/最坏适应、碎片模拟一串分配/回收后的空闲区
分页地址转换★★★★★选择/综合:页号、偏移、物理地址拆位 → 查表 → 拼接
页表大小、页表项长度★★★★☆选择/综合算位数,再乘项数
多级页表★★★★☆选择/综合:位划分、级数、访存次数每级页表不超过一页
TLB 与有效访问时间★★★★★计算画出命中/未命中两条路径
分段与段页式★★★☆☆选择:越界判断、共享、访存次数两次越界检查
页面置换★★★★★选择/综合:缺页次数、置换顺序画页框表,逐列推
抖动与工作集★★★☆☆选择数窗口内不同页数
地址转换只做三件事:把逻辑地址拆成“页号 + 页内偏移”,用页号查页表得到块号,再把“块号 + 页内偏移”拼成物理地址。页内偏移在转换前后不变。页表太大就用多级页表,内存不够就用虚拟内存。
01
3.1 · 打基础

基础:地址与保护

★★★☆☆ 中频 选择题

一、逻辑地址与物理地址

写程序时,编译器不知道程序将来会被放在内存的哪个位置,所以生成的地址都是从 0 开始的“相对地址”,叫逻辑地址(虚拟地址)。程序真正在内存里的位置叫物理地址。把逻辑地址变成物理地址的过程叫地址重定位(地址变换)。

源程序.c 文件 目标模块各自从 0 编址 装入模块完整逻辑地址空间 内存物理地址 编译链接装入 静态链接 / 装入时动态链接/ 运行时动态链接 绝对装入 / 静态重定位/ 动态重定位
图 3-1 程序从写好到运行的三步。地址转换发生在“装入”这一步或之后。
装入方式地址何时转换特点
绝对装入编译时就确定物理地址只适合单道程序
可重定位装入(静态重定位)装入内存时一次性全部改好必须一次分配全部所需内存;运行中不能移动
动态运行时装入(动态重定位)执行到这条指令时才转换,靠重定位寄存器程序可在内存中移动;可以只装一部分;现代 OS 采用

二、内存保护:不许越界

每个进程只能访问自己的内存。常用“重定位寄存器 + 界地址寄存器”实现,两个寄存器都只能由内核用特权指令修改:

逻辑地址例:346 界地址寄存器 = 500 <? 重定位寄存器 = 10000 + 物理地址10346 越界中断 是 否
图 3-2 先比较逻辑地址是否小于界地址寄存器(进程长度),合法才加上重定位寄存器(起始物理地址)。注意比较的是逻辑地址。

三、覆盖与交换(内存扩充的早期手段)

覆盖

同一个程序内部:把不会同时运行的模块轮流放在同一块内存(覆盖区)里。需要程序员声明覆盖结构,对用户不透明,已基本淘汰。

交换(对换)

在进程之间:把暂时不能运行的进程整个换出到外存的对换区,把就绪进程换入。就是第 2 章的中级调度。对换区用连续分配,追求换入换出速度。

02
3.2 · 中频

连续分配

★★★☆☆ 中频 选择题

最直接的想法:给每个进程一块连续的内存。问题在于“块切多大”,于是有了三种方案,各自产生不同的“碎片”。

内部碎片:分给你了,你没用完 固定分区 1:10 KB 进程 A 7 KB 3 KB 浪费 在分区内部,别人也用不了 固定分区、分页会产生 外部碎片:没分出去,但太小用不上 A 4K B 5K C 3K 空闲共 12 KB,但新来 8 KB 的进程放不下 在分区之间;动态分区、分段会产生 可用“紧凑”(挪动进程拼成大块)解决,需动态重定位
图 3-3 两种碎片。判断口诀:分配单位是“固定大小”的会有内部碎片,分配单位“按需定大小”的会有外部碎片。
方案做法碎片问题
单一连续分配内存分系统区和用户区,用户区只放一道程序内部碎片只能单道,利用率极低
固定分区分配用户区事先划成若干固定大小的分区(可大小相等或不等),每区放一道内部碎片程序太大放不下;小程序浪费
动态分区分配进程来时按需切一块恰好大小的分区外部碎片要选从哪个空闲区切 → 四种算法

一、动态分区的四种分配算法

算法空闲分区链排序选哪块效果
首次适应 FF按地址递增第一个够大的综合性能最好,开销小;低地址处留下很多小碎片
邻近适应 NF(循环首次)按地址递增,循环链表从上次结束的位置往后找第一个够大的空闲区分布更均匀,但高地址的大分区也会被切碎
最佳适应 BF按容量递增够大的里面最小的保留大分区;但会留下最多、最小的外部碎片
最坏适应 WF按容量递减最大的剩下的块还比较大能用;但大分区很快被用光,大进程来了没地方放

二、回收:和相邻的空闲区合并

① 上邻空闲 空闲 回收区 已占用 合并,改上邻的大小 ② 下邻空闲 已占用 回收区 空闲 合并,起址改为回收区 ③ 上下都空闲 空闲 回收区 空闲 三合一,空闲区数 −1 ④ 上下都不空闲 已占用 回收区 已占用 新建一个表项,空闲区数 +1
图 3-4 回收时的四种情况(上为低地址)。选择题常问:回收后空闲分区数“不变 / 减 1 / 加 1”。①② 不变,③ 减 1,④ 加 1。
  • 最佳适应不是“性能最佳”,反而会产生最多的小碎片。综合性能最好的是首次适应。
  • 动态分区没有内部碎片,固定分区没有外部碎片。
  • “紧凑”需要动态重定位支持,因为进程在内存中的位置会变。
03
3.3 · 计算重点

基本分页与 TLB

★★★★★ 必考 选择 + 计算
比喻

连续分配像订酒店要求“一整层楼连着的 20 间房”,很难凑齐。分页像旅行团住宿:把团员按 4 人一组分好(页),酒店里任何空着的 4 人间(页框 / 物理块)都能住,导游手里有一张“第几组住几号房”的对照表(页表)。

一、基本思想

  • 把内存切成大小相等的小块,叫页框(页帧、物理块、内存块),编号 0, 1, 2, …
  • 把进程的逻辑地址空间切成同样大小的块,叫页(页面),编号 0, 1, 2, …
  • 每页装入任意一个空闲页框,不需要连续。用一张页表记录“第 i 页 → 第几号块”。
  • 没有外部碎片;只有每个进程最后一页可能没装满,产生少量内部碎片。
进程 A 的逻辑空间 第 0 页 第 1 页 第 2 页 第 3 页 页表 02 13 21 36 页号块号 页号不用存,就是表项的下标 物理内存 块 0:OS 块 1:A 的第 2 页 块 2:A 的第 0 页 块 3:A 的第 1 页 块 4:进程 B 块 5:空闲 块 6:A 的第 3 页
图 3-5 进程 A 的 4 个页散落在不连续的页框中。页表只存“块号”,页号就是数组下标。每个进程有自己的页表。

二、地址结构:一条地址怎么拆

页面大小一定是 2 的整数次幂。若页面大小为 2k 字节,那么逻辑地址的低 k 位就是页内偏移 W,剩下的高位就是页号 P。以 32 位地址、4 KB 页为例:

页号 P20 位 → 最多 2²⁰ 页
页内偏移 W12 位 → 4 KB
3112 | 110
页号 P = ⌊A ÷ L⌋     二进制下:取高位 偏移 W = A mod L     二进制下:取低 k 位 物理地址 E = b × L + W  二进制下:块号 b 拼上 W (A:逻辑地址;L:页面大小;b:查页表得到的块号)

十六进制地址最方便:4 KB 页的偏移是 12 位 = 正好 3 个十六进制位,直接“切”就行。

三、地址变换的完整过程

逻辑地址 页号 P = 2 W = 452 页表寄存器 PTR 页表始址 F | 页表长度 M = 4 P<M? 否:越界中断 页 0 → 块 2页 1 → 块 3 页 2 → 块 1 页 3 → 块 6 页表在内存中:表项地址 = F + P × 页表项长度 物理地址 b = 1 W = 452 E = 1 × 1024 + 452 = 1476 是 否 偏移不变,直接复制
图 3-6 页面大小 1 KB,逻辑地址 2500:P = ⌊2500/1024⌋ = 2,W = 452;越界检查通过后查页表得块号 1,物理地址 = 1×1024 + 452 = 1476。全程访问内存 2 次:一次查页表,一次取数据。

例:十六进制地址

#
条件:页面大小 4 KB,页表中第 2 页对应第 5 块,求逻辑地址 0x2A4F 的物理地址
结果
1
4 KB = 2¹²,偏移占低 12 位 = 低 3 个十六进制位
0x2A4F → 0x2 | 0xA4F
2
页号 P = 0x2 = 2,偏移 W = 0xA4F
P = 2, W = 0xA4F
3
查页表:页 2 → 块 5
b = 5
4
把块号拼在偏移前面
0x5 | 0xA4F = 0x5A4F

四、页表项长度与页表大小

页表项至少要能放下“块号”。块号有多少位,由物理内存有多少块决定:

#
例:物理内存 4 GB,页面 4 KB,逻辑地址 32 位,按字节编址
结果
1
物理块数 = 4 GB ÷ 4 KB = 2³² ÷ 2¹²
2²⁰ 块
2
块号要 20 位;按字节存储,至少 ⌈20/8⌉ 字节
至少 3 B(实际常取 4 B,还能放标志位)
3
页号 = 32 − 12 = 20 位,所以页表最多有 2²⁰ 项
2²⁰ 项
4
页表最大 = 项数 × 项长度
2²⁰ × 4 B = 4 MB
5
这张页表本身要占多少个页框?
4 MB ÷ 4 KB = 1024 个,还必须连续

第 5 步就是问题所在:每个进程都要一张 4 MB 且连续存放的页表,而大部分表项根本用不到。这引出了第 04 节的多级页表。

五、快表 TLB:让地址转换不用多跑一趟内存

基本分页每次访存要先读一次页表(在内存里),等于访存次数翻倍。根据局部性,最近用过的页很可能马上又用,于是在 CPU 里放一个小而快的相联存储器,缓存最近用过的“页号 → 块号”对,叫快表(TLB);内存中的页表相应叫慢表。

页号 P 快表 TLBCPU 内,查一次时间 t 内存中的页表查一次时间 m 块号 b + W再访问数据,时间 m 命中:t + m 未命中 未命中:t + m + m 同时把这个表项写入 TLB
图 3-7 带快表的地址变换。命中只访存 1 次,未命中访存 2 次(单级页表)。
EAT(有效访问时间) = h × (t + m) + (1 − h) × (t + 2m) 单级页表 推广到 n 级页表: = h × (t + m) + (1 − h) × (t + (n + 1)m) (h:TLB 命中率;t:查 TLB 时间;m:一次访存时间) 若题目说“快表与慢表同时查找”:未命中那项去掉 t,变为 (n + 1)m

例: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 覆盖范围越大,但内部碎片越大。
04
3.4 · 计算重点

多级页表

★★★★☆ 高频 选择 + 计算
比喻

单级页表像一本“把每一页内容都列在一张巨大目录里”的书:4 MB 的目录,还必须装订在一起。两级页表改成“先查章目录,再查章内的节目录”:没写的章,根本不用印它的节目录。

一、为什么需要多级页表

单级页表的问题不只是“大”,还有两个:必须连续存放(1024 个连续页框不好找),以及大部分表项用不到(一个进程通常只用到代码段附近和栈附近的一小部分地址)。解决办法:把页表本身也分页,再给这些“页表页”建一张目录。

CR3 / PTBR 页目录(1 页,1024 项) PDE 0 → 表 A PDE 1 → 表 B PDE 2 无效 …… 无效 …… 无效 PDE 1023 → 表 C 二级页表(每张 1 页) 表 A1024 个 PTE 表 B1024 个 PTE 表 C(栈区)1024 个 PTE 数据页框 数据页框 数据页框 数据页框 每个 PDE 管 4 MB 每个 PTE 管 4 KB 只用了 3 个 4 MB 区域的进程:1 个页目录 + 3 张二级页表 = 4 页 = 16 KB 单级页表需要 4 MB 连续空间,相差约 256 倍;而且这 4 页可以散落在内存任意位置
图 3-8 两级页表(32 位地址、4 KB 页、4 B 表项)。页目录里标记为“无效”的项,对应的二级页表根本不存在,这就是省空间的来源。

二、两级页表的地址结构

核心规则:每一级页表的大小不超过一页。4 KB 页、4 B 页表项 → 一页能放 4 KB / 4 B = 1024 = 2¹⁰ 项 → 每级索引 10 位。32 位地址减去 12 位偏移剩 20 位页号,正好拆成 10 + 10:

页目录号(一级)10 位
二级页号10 位
页内偏移12 位
3122 | 2112 | 110
每级索引位数 = log₂(页面大小 ÷ 页表项大小) 页表级数 = ⌈ 页号总位数 ÷ 每级索引位数 ⌉ 例:48 位虚拟地址、4 KB 页、8 B 表项 偏移 12 位,页号 36 位;每级 log₂(4096/8) = 9 位 级数 = ⌈36 / 9⌉ = 4 级(这就是 x86-64 的四级页表)

三、页表基址寄存器里存什么

两级页表的“根”是页目录。页表基址寄存器(PTBR;x86 中叫 CR3)保存的是页目录的物理基址,不是二级页表的基址:

位置保存的内容例子
CR3 / PTBR页目录的物理基址0x00002000
页目录项 PDE[1]第 1 张二级页表的物理基址 + 标志位0x00004000
二级页表项 PTE[3]数据页框的物理基址 + 标志位0x00007000

四、二级页表地址变换全过程

设 CR3 = 0x00002000,PDE[1] = 0x00004000,PTE[3] = 0x00007000,访问逻辑地址 0x00403A4F:

页目录号 = 100 0000 0001
二级页号 = 300 0000 0011
偏移 = 0xA4F1010 0100 1111
0x00403A4F = 0000 0000 0100 0000 0011 1010 0100 1111
CR30x2000 页目录[1]读 0x2004 → 0x4000 二级页表[3]读 0x400C → 0x7000 物理地址0x7A4F + 1 × 4(第 1 次访存) + 3 × 4(第 2 次访存) + 0xA4F(第 3 次访存取数据)
图 3-9 两级页表地址变换。TLB 未命中时共访存 3 次;若 TLB 命中,直接用缓存的页框 0x7000 拼地址,只访存 1 次。
  1. 拆地址:页目录号 = (A >> 22) & 0x3FF = 1,二级页号 = (A >> 12) & 0x3FF = 3,偏移 = A & 0xFFF = 0xA4F。
  2. 查页目录:PDE 地址 = CR3 + 1 × 4 = 0x2004,读出 0x4000(二级页表基址)。
  3. 查二级页表:PTE 地址 = 0x4000 + 3 × 4 = 0x400C,读出 0x7000(页框基址)。
  4. 拼地址: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 位。
  • 题目若说“页目录占一页”,就用“页目录项数 × 项大小 ≤ 页大小”反推每级位数。
05
3.5 · 中高频

分段与段页式

★★★☆☆ 中频 选择题

分页是从系统角度切的:一刀一刀等长,不管里面是代码还是数据。可程序员眼中的程序是按逻辑组织的:主程序、子函数、栈、全局数据……分段就按这种逻辑单位来分,每段长度不一,便于共享和保护。

一、分段的地址变换

逻辑地址是二维的:(段号 S, 段内偏移 W)。段表每项记录段长 C 和段基址 b。比分页多一次检查——段内偏移不能超过段长:

段号基址段长
0219600
1230014
290100
31327580
4195296
#
逻辑地址 (S, W)
两次检查 → 物理地址
a
(0, 430)
0 < 5 ✓,430 < 600 ✓ → 219 + 430 = 649
b
(1, 10)
10 < 14 ✓ → 2300 + 10 = 2310
c
(2, 500)
500 ≥ 100 ✗ → 越界中断
d
(3, 400)
400 < 580 ✓ → 1327 + 400 = 1727
e
(5, 20)
段号 5 ≥ 段表长度 5 ✗ → 越界中断

注意:分段的物理地址是 基址 + 偏移(加法),而分页是 块号 × 页大小 + 偏移(拼接)。

二、分页 vs 分段

对比分页分段
划分依据物理单位,系统按固定大小切逻辑单位,按程序的自然结构分
大小固定,由系统决定不固定,由程序决定
对用户透明,用户感觉不到可见,编程时需显式给出段名
地址空间一维:给一个地址就能拆出页号二维:必须同时给出段号和段内偏移
碎片内部碎片(最后一页)外部碎片
共享与保护不方便:一页里可能混着代码和数据方便:段是完整逻辑单位,整段设权限、整段共享

共享:只有纯代码(可重入代码)能被共享——它运行时不修改自己。共享时,各进程的段表项指向同一个物理段。

三、段页式:先分段,段内再分页

段号 S 页号 P 偏移 W 段表(每进程 1 张)页表长度 | 页表始址① 第 1 次访存 页表(每段 1 张)块号 b② 第 2 次访存 物理地址 b | W取数据③ 第 3 次访存 两次越界检查:S 与段表长度比;P 与该段页表长度比。有 TLB 时可用 (S, P) 作为关键字查快表
图 3-10 段页式:一个进程一张段表、每个段一张页表。无快表时一次取数要访存 3 次。地址仍是二维的(段号由用户给出)。
  • 分段的越界检查有两次:段号 ≥ 段表长度,或段内偏移 ≥ 段长。
  • 分段管理有外部碎片,段页式只有内部碎片(段内是分页)。
  • 段页式下“页号 + 偏移”的总位数决定了单段最大长度。
06
3.6 · 计算重点

虚拟内存与页面置换

★★★★★ 必考 选择 + 计算 + 综合

前面的分页、分段都要求进程全部装入内存才能运行。可程序在一段时间内往往只用到一小部分(局部性),那就只装一部分,用到别的再从磁盘调进来。这样,一个 8 GB 内存的机器能跑总共需要 20 GB 的程序——这就是虚拟内存。

一、凭什么能“只装一部分”:局部性原理

时间局部性

刚访问过的地址,很可能马上再访问(循环、计数器变量)。

空间局部性

访问了某地址,很可能马上访问附近的地址(顺序执行、遍历数组)。

虚拟内存的三个特征:多次性(分多次调入)、对换性(运行中可换进换出)、虚拟性(逻辑上扩充了容量)。
虚拟内存的最大容量受两个限制:① 地址位数,32 位最多 4 GB;② 内存 + 外存对换区的容量。实际容量取两者的较小值。

二、请求分页:页表要多几个字段

页号物理块号状态位 P访问字段 A修改位 M外存地址
状态位:这页在不在内存(1 在 / 0 不在 → 缺页)。
访问字段:最近被访问过没有 / 访问次数,供置换算法挑“该换谁”。
修改位:调入后被写过没有。被写过的“脏页”换出时要写回磁盘,没写过的直接丢弃。
外存地址:这页在磁盘上的位置,缺页时去这里读。

三、缺页中断的处理流程

CPU 给出逻辑地址 查 TLB 查内存中的页表 形成物理地址并更新 TLB 状态位 = 0产生缺页中断(内中断) 内存有空闲块吗? 选一页换出(置换算法) 修改位 = 1?是:先写回磁盘 从外存调入所需页进程阻塞,I/O 完成后唤醒 修改页表返回,重新执行该指令 TLB 命中 未命中 在内存 不在内存 没有 有 重新执行,再查一遍
图 3-11 请求分页的地址变换与缺页处理。缺页属于内中断(故障),处理完要重新执行引起缺页的那条指令;一条指令执行期间可能产生多次缺页(如指令和操作数跨页)。

四、页面置换算法

内存满了又缺页,就得挑一页“请出去”。挑得好,后面缺页少;挑得不好,刚换出去马上又要用,来回折腾。

算法换出谁能实现吗特点
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 次缺页)。手算时:

  1. 横向写访问串,纵向画 3 行(页框)。每一列表示“这次访问之后各页框里装着什么”。
  2. 命中:照抄上一列。缺页且有空框:放进空框。缺页且满了:按算法挑一页替换,记一个 ✗。
  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 算法图解

页3 1 页5 1 页2 0 页7 1 页1 0 缺页时,指针从当前位置顺时针扫描: 页3 访问位 1 → 清零,跳过 页5 访问位 1 → 清零,跳过 页2 访问位 0 → 换出它,新页放这里(访问位置 1) 指针停在下一个位置(页7) 若一圈全是 1,清零一圈后回到起点,第二圈必然找到 → 最多扫描两圈。命中时只把访问位置 1,指针不动
图 3-12 简单 CLOCK 算法。访问位为 1 表示“最近用过,给它第二次机会”。

改进型 CLOCK 用 (访问位 A, 修改位 M) 把页分成四类,优先级从高到低:(0,0) 最近没用也没改 → (0,1) 没用但改过 → (1,0) → (1,1)。扫描规则:

  1. 第一轮:找 (0,0),不修改任何标志位,找到就换。
  2. 第二轮:找 (0,1),扫过的页把访问位清 0,找到就换。
  3. 还没找到:此时所有访问位都已为 0,回到第一轮重复,必然能找到。最多扫描四轮。

五、页框分配与抖动

策略含义说明
固定分配 + 局部置换页框数固定,缺页只能换自己的页页框数难以确定
可变分配 + 全局置换缺页时可以从系统空闲池拿,或换任意进程的页被抢页的进程缺页率会上升
可变分配 + 局部置换只换自己的页,但 OS 根据缺页率动态增减页框数效果较好
不存在“固定分配 + 全局置换”:固定了页框数,就不能去抢别人的。

何时调入:预调页(运行前一次调入若干相邻页,用于首次启动)和请求调页(运行中缺页时调入)。从何处调入:对换区够用时都从对换区(快);不够时不会修改的页从文件区、可能修改的页换出到对换区;UNIX 方式是第一次从文件区,之后从对换区。

抖动(颠簸)

刚换出的页马上又要用,刚换进的页马上又被换出,进程大部分时间花在换页上,CPU 利用率急剧下降。根本原因:分配给进程的页框数太少,装不下它当前频繁访问的页(或置换算法选得差)。
解决:减少并发进程数(挂起一些进程)、增加页框、用工作集模型控制分配。

工作集

2615777751 623412 3444343444 1323 t1 t2 W(t1, 10) = {1, 2, 5, 6, 7} 窗口内 10 次访问,5 个不同页 W(t2, 10) = {3, 4} 进入局部性更强的阶段,只需 2 个页框
图 3-13 工作集 W(t, Δ):在时刻 t 往前看 Δ 次访问(窗口),其中出现过的不同页面的集合。重复的只算一次。

工作集大小会随时间变化。OS 的策略:给进程分配的页框数 ≥ 工作集大小,否则会抖动;所有进程工作集之和超过内存时,挂起一些进程。

六、缺页对访存时间的影响

EAT = (1 − p) × 访存时间 + p × 缺页处理时间 (p:缺页率) 例:访存 100 ns,缺页处理 8 ms = 8 000 000 ns,p = 0.001 EAT = 0.999 × 100 + 0.001 × 8 000 000 ≈ 8 100 ns → 慢了约 80 倍 若要求性能下降不超过 10%(EAT ≤ 110 ns):p < 约 1.25 × 10⁻⁶

综合题常把 TLB、页表、缺页、Cache 串在一起问“访问某地址共需多少时间”。做法:画出这个地址的完整路径(TLB 是否命中 → 页表是否有效 → 缺页处理后重新执行 → 数据是否在 Cache),每一步的时间逐项相加。

七、内存映射文件

进程通过系统调用(如 mmap)把一个磁盘文件映射到自己的虚拟地址空间,之后像访问内存数组一样读写文件,由缺页机制按需把文件内容调入,写回由 OS 负责。多个进程映射同一文件时,可以共享同一组物理页框,实现进程间共享。

  • 只有 FIFO 会出现 Belady 异常。
  • OPT 换的是“将来最久不用”,LRU 换的是“过去最久没用”,方向别搞反。
  • 缺页次数要算上最开始装入空页框的那几次;“置换次数”则不算。看清题目问哪个。
  • 抖动的主要原因是分配的页框太少,不是“页面太大”或“内存太小”本身。
  • 虚拟内存的实际容量 ≤ min(2地址位数, 内存 + 对换区)。
07
实战

真题与自测

★★★★★ 收口 选择 + 综合

一、真题问法

问法 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 异常。
⑤ 不存在固定分配全局置换。