20 KiB
16. 虚拟存储器
课程: 操作系统 - 存储器管理 核心内容: 虚拟存储器思想、局部性原理、请求分页、页面置换算法、内存分配策略、抖动与工作集
前置知识
一、虚拟存储器的基本思想
问题的提出
在传统的存储管理中，作业必须全部装入内存才能运行。这带来两个问题：
- 作业大小超过物理内存时，无法运行
- 内存中同时驻留多个大程序时，内存不够用
虚拟存储器思想
核心: 程序员在比实际物理内存大得多的虚拟地址空间中编写程序，运行时只需将部分页面调入内存，其余留在外存。当访问到不在内存的页面时，再从外存调入。
flowchart LR
subgraph VA["虚拟地址空间 (很大)"]
direction TB
V0["页面0 ✓ 在内存"]
V1["页面1 ✓ 在内存"]
V2["页面2 ✗ 在外存"]
V3["页面3 ✓ 在内存"]
V4["页面4 ✗ 在外存"]
V5["..."]
end
subgraph MEM["物理内存 (较小)"]
direction TB
M0["页框0"]
M1["页框1"]
M2["页框2"]
M3["页框3"]
end
subgraph DISK["外存 (磁盘)"]
direction TB
D0["页面2"]
D1["页面4"]
D2["..."]
end
V0 --> M0
V1 --> M1
V3 --> M3
V2 -.->|"缺页时调入"| DISK
V4 -.->|"缺页时调入"| DISK
style VA fill:#e3f2fd,stroke:#1976d2
style MEM fill:#fff8e1,stroke:#f9a825
style DISK fill:#fce4ec,stroke:#c62828
实现基础
虚拟存储器的实现依赖两个关键技术：
- 14_分页存储管理或15_段式存储管理: 将程序划分为小块，可以部分装入
- 14_分页存储管理#五、地址变换过程: 访问不在内存的页面时，由OS负责调入
二、局部性原理
虚拟存储器之所以可行，是因为程序运行时具有局部性——程序不会均匀地访问所有地址空间。
时间局部性 (Temporal Locality)
含义: 如果一条指令/数据被访问，那么在不久的将来它很可能再次被访问。
典型场景:
- 循环中的指令反复执行
- 频繁访问的变量
- 栈顶数据的反复操作
空间局部性 (Spatial Locality)
含义: 如果一个存储单元被访问，那么它附近的单元也很可能很快被访问。
典型场景:
- 顺序执行的指令
- 数组的顺序遍历
- 结构体成员的连续访问
局部性的实际影响：行优先 vs 列优先
以二维数组遍历为例，行优先和列优先的性能差异可达 21.5 倍：
// 二维数组: int a[1024][1024];
// 行优先遍历 (空间局部性好)
for (int i = 0; i < 1024; i++)
for (int j = 0; j < 1024; j++)
sum += a[i][j]; // 访问顺序: a[0][0], a[0][1], a[0][2], ...
// 连续内存访问，充分利用缓存行
// 列优先遍历 (空间局部性差)
for (int j = 0; j < 1024; j++)
for (int i = 0; i < 1024; i++)
sum += a[i][j]; // 访问顺序: a[0][0], a[1][0], a[2][0], ...
// 每次跳过一整行，频繁缺页/缓存失效
flowchart LR
subgraph RowMajor["行优先遍历"]
direction LR
R1["a[0][0]"] --> R2["a[0][1]"] --> R3["a[0][2]"] --> R4["..."]
style R1 fill:#c8e6c9
style R2 fill:#c8e6c9
style R3 fill:#c8e6c9
end
subgraph ColMajor["列优先遍历"]
direction LR
C1["a[0][0]"] --> C2["a[1][0]"] --> C3["a[2][0]"] --> C4["..."]
style C1 fill:#ffcdd2
style C2 fill:#ffcdd2
style C3 fill:#ffcdd2
end
RowMajor ---|"性能差异约 21.5 倍"| ColMajor
三、请求分页
基本思想
请求分页 (Demand Paging) 是最常用的虚拟存储器实现方式：
- 页面只在被访问时才调入内存（而非预装入）
- 内存不足时，将某些页面换出到外存，腾出空间
页表项扩展
在14_分页存储管理#四、页表的基础上，请求分页的页表项增加了状态位：
| 字段 | 含义 | 说明 |
|---|---|---|
| 状态位 (Present/Valid) | 页面是否在内存 | 1=在内存，0=不在内存 |
| 访问位 (Reference/Access) | 页面是否被访问过 | 用于置换算法判断 |
| 修改位 (Dirty) | 页面是否被写过 | Dirty=1 时换出需写回外存 |
| 外存地址 | 页面在外存中的位置 | 用于缺页时调入 |
缺页中断处理
flowchart TD
A["CPU访问虚拟地址"] --> B{"页面在内存中?<br/>(检查状态位)"}
B -->|"在内存"| C["正常地址变换，访问数据"]
B -->|"不在内存"| D["触发**缺页中断**"]
D --> E["保存CPU现场"]
E --> F{"外存中存在该页?"}
F -->|"不存在"| G["终止进程<br/>Segmentation Fault"]
F -->|"存在"| H{"内存有空闲页框?"}
H -->|"有空闲"| I["从外存读入该页"]
H -->|"无空闲"| J["执行**页面置换算法**<br/>选择牺牲页"]
J --> K{"牺牲页Dirty=1?"}
K -->|"是"| L["将牺牲页写回外存"]
K -->|"否"| M["直接覆盖"]
L --> I
M --> I
I --> N["更新页表:<br/>状态位=1, PPN"]
N --> O["刷新TLB"]
O --> P["重新执行被中断的指令"]
style D fill:#ffcdd2,stroke:#c62828
style J fill:#fff3e0,stroke:#e65100
style G fill:#ffcdd2,stroke:#c62828
四、页面置换算法
当内存中没有空闲页框时，需要选择一个页面换出到外存，为新页面腾出空间。不同的选择策略就是页面置换算法。
示例参数: 物理内存有 3 个页框，页面引用串为： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
1. OPT (Optimal) 最佳置换算法
策略: 换出将来最长时间不会被使用的页面。
OPT 是理论算法，因为无法预知未来的页面访问序列。它用于衡量其他算法的上限。
执行过程:
| 访问序列 | 页框0 | 页框1 | 页框2 | 缺页? | 说明 |
|---|---|---|---|---|---|
| 7 | 7 | - | - | 缺页 | 空闲页框，直接装入 |
| 0 | 7 | 0 | - | 缺页 | 空闲页框，直接装入 |
| 1 | 7 | 0 | 1 | 缺页 | 空闲页框，直接装入 |
| 2 | 7 | 0 | 2 | 缺页 | 换出1（最久后才用） |
| 0 | 7 | 0 | 2 | 命中 | 0已在内存 |
| 3 | 3 | 0 | 2 | 缺页 | 换出7（最久后才用） |
| 0 | 3 | 0 | 2 | 命中 | |
| 4 | 3 | 0 | 4 | 缺页 | 换出2（最久后才用） |
| 2 | 3 | 2 | 4 | 缺页 | 换出0（最久后才用） |
| 3 | 3 | 2 | 4 | 命中 | |
| 0 | 3 | 2 | 0 | 缺页 | 换出4（最久后才用） |
| 3 | 3 | 2 | 0 | 命中 | |
| 2 | 3 | 2 | 0 | 命中 | |
| 1 | 1 | 2 | 0 | 缺页 | 换出3（最久后才用） |
| 2 | 1 | 2 | 0 | 命中 | |
| 0 | 1 | 2 | 0 | 命中 | |
| 1 | 1 | 2 | 0 | 命中 | |
| 7 | 1 | 7 | 0 | 缺页 | 换出2（最久后才用） |
| 0 | 1 | 7 | 0 | 命中 | |
| 1 | 1 | 7 | 0 | 命中 |
缺页次数: 9，缺页率 = 9/20 = 45%
2. FIFO (First-In First-Out) 先进先出
策略: 换出最早进入内存的页面。
执行过程:
| 访问序列 | 页框0 | 页框1 | 页框2 | 缺页? | 淘汰队列 |
|---|---|---|---|---|---|
| 7 | 7 | - | - | 缺页 | [7] |
| 0 | 7 | 0 | - | 缺页 | [7,0] |
| 1 | 7 | 0 | 1 | 缺页 | [7,0,1] |
| 2 | 2 | 0 | 1 | 缺页 | [0,1,2] 淘汰7 |
| 0 | 2 | 0 | 1 | 命中 | [0,1,2] |
| 3 | 2 | 3 | 1 | 缺页 | [1,2,3] 淘汰0 |
| 0 | 2 | 3 | 0 | 缺页 | [2,3,0] 淘汰1 |
| 4 | 4 | 3 | 0 | 缺页 | [3,0,4] 淘汰2 |
| 2 | 4 | 2 | 0 | 缺页 | [0,4,2] 淘汰3 |
| 3 | 4 | 2 | 3 | 缺页 | [4,2,3] 淘汰0 |
| 0 | 0 | 2 | 3 | 缺页 | [2,3,0] 淘汰4 |
| 3 | 0 | 2 | 3 | 命中 | [2,3,0] |
| 2 | 0 | 2 | 3 | 命中 | [2,3,0] |
| 1 | 0 | 1 | 3 | 缺页 | [3,0,1] 淘汰2 |
| 2 | 0 | 1 | 2 | 缺页 | [0,1,2] 淘汰3 |
| 0 | 0 | 1 | 2 | 命中 | [0,1,2] |
| 1 | 0 | 1 | 2 | 命中 | [0,1,2] |
| 7 | 7 | 1 | 2 | 缺页 | [1,2,7] 淘汰0 |
| 0 | 7 | 0 | 2 | 缺页 | [2,7,0] 淘汰1 |
| 1 | 7 | 0 | 1 | 缺页 | [7,0,1] 淘汰2 |
缺页次数: 15，缺页率 = 15/20 = 75%
Belady 异常: FIFO 算法在某些情况下，增加物理页框数反而会导致缺页率上升。例如本例中 4 个页框时缺页次数可能比 3 个页框时更多。这是 FIFO 算法的独特缺陷。
3. LRU (Least Recently Used) 最近最久未使用
策略: 换出最近最长时间没有被访问的页面。
实现方式:
- 栈法: 用一个栈保存页面号，访问某页时将其移到栈顶。栈底就是最久未使用的页面
- 计数器法: 每个页面记录最后一次访问的时间，淘汰时间值最小的页面
执行过程:
| 访问序列 | 页框0 | 页框1 | 页框2 | 缺页? | 说明 |
|---|---|---|---|---|---|
| 7 | 7 | - | - | 缺页 | |
| 0 | 7 | 0 | - | 缺页 | |
| 1 | 7 | 0 | 1 | 缺页 | |
| 2 | 2 | 0 | 1 | 缺页 | 淘汰7(最久未用) |
| 0 | 2 | 0 | 1 | 命中 | 0被访问，更新时间戳 |
| 3 | 2 | 0 | 3 | 缺页 | 淘汰1(最久未用) |
| 0 | 2 | 0 | 3 | 命中 | |
| 4 | 4 | 0 | 3 | 缺页 | 淘汰2(最久未用) |
| 2 | 4 | 0 | 2 | 缺页 | 淘汰3(最久未用) |
| 3 | 4 | 3 | 2 | 缺页 | 淘汰0(最久未用) |
| 0 | 0 | 3 | 2 | 缺页 | 淘汰4(最久未用) |
| 3 | 0 | 3 | 2 | 命中 | |
| 2 | 0 | 3 | 2 | 命中 | |
| 1 | 0 | 3 | 1 | 缺页 | 淘汰2(最久未用) |
| 2 | 0 | 2 | 1 | 缺页 | 淘汰3(最久未用) |
| 0 | 0 | 2 | 1 | 命中 | |
| 1 | 0 | 2 | 1 | 命中 | |
| 7 | 0 | 2 | 7 | 缺页 | 淘汰1(最久未用) |
| 0 | 0 | 2 | 7 | 命中 | |
| 1 | 1 | 2 | 7 | 缺页 | 淘汰0(最久未用) |
缺页次数: 12，缺页率 = 12/20 = 60%
4. Clock (时钟 / 近似LRU)
策略: 将所有页面组成一个循环链表，每页有一个访问位 R。淘汰指针从当前位置开始扫描：
- R=1：将 R 置 0，指针前移（给第二次机会）
- R=0：淘汰该页
flowchart LR
subgraph Clock["时钟置换算法 (循环链表)"]
direction LR
P0["页0<br/>R=1"]
P1["页1<br/>R=0"]
P2["页2<br/>R=1"]
P3["页3<br/>R=0"]
end
PTR["淘汰指针"] --> P1
P0 --> P1
P1 --> P2
P2 --> P3
P3 --> P0
style P1 fill:#ffcdd2,stroke:#c62828
style PTR fill:#fff3e0,stroke:#e65100
执行示例（简化）:
- 指针指向页1 (R=0) → 淘汰页1，装入新页，指针前移
- 指针指向页2 (R=1) → R置0，指针前移
- 指针指向页3 (R=0) → 淘汰页3
改进型Clock: 同时考虑 R 和 D (修改位)，优先淘汰 R=0 且 D=0 的页面（不需要写回外存）。
| 优先级 | R | D | 淘汰代价 |
|---|---|---|---|
| 最高 | 0 | 0 | 未访问未修改，直接覆盖 |
| 0 | 1 | 未访问但已修改，需写回 | |
| 1 | 0 | 已访问未修改，再给机会 | |
| 最低 | 1 | 1 | 已访问已修改，最不想淘汰 |
5. LFU (Least Frequently Used) 最少使用
策略: 换出访问次数最少的页面。
- 用计数器记录每个页面的访问次数
- 淘汰计数器值最小的页面
- 缺点: 某页面过去被频繁访问但现在不再使用，仍难以被淘汰
- 实现开销: 需要为每个页面维护计数器
算法对比
| 算法 | 策略 | 优点 | 缺点 | 是否有Belady异常 |
|---|---|---|---|---|
| OPT | 淘汰将来最久不用的 | 缺页率最低（理论最优） | 无法实现 | 无 |
| FIFO | 淘汰最早进入的 | 实现简单 | 缺页率高，有Belady异常 | 有 |
| LRU | 淘汰最近最久未用的 | 接近OPT，效果好 | 实现开销大（需时间戳或栈） | 无 |
| Clock | 给访问位R=0的淘汰 | LRU的近似，开销小 | 效果略逊于LRU | 无 |
| LFU | 淘汰访问次数最少的 | 考虑历史频率 | 对访问模式变化响应慢 | 无 |
算法效果对比（本例）
页面引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 (3个物理块)
┌──────────┬──────────┬──────────┐
│ 算法 │ 缺页次数 │ 缺页率 │
├──────────┼──────────┼──────────┤
│ OPT │ 9 │ 45% │ ← 理论最优
│ LRU │ 12 │ 60% │
│ FIFO │ 15 │ 75% │ ← 效果最差
└──────────┴──────────┴──────────┘
五、内存分配策略
物理页框分配方式
| 方式 | 说明 |
|---|---|
| 平均分配 | 将可用页框平均分配给所有进程 |
| 按比例分配 | 按进程大小占总需求的比例分配 |
| 考虑优先权 | 高优先级进程分配更多页框 |
按比例分配公式:
a_i = \frac{s_i}{\sum s_j} \times m
其中 s_i 是进程 i 的页面数，m 是可用页框总数。
置换策略
| 策略 | 说明 | 特点 |
|---|---|---|
| 固定分配局部置换 | 每个进程固定页框数，只能在自己的页面中置换 | 公平，但可能浪费 |
| 可变分配全局置换 | 从全局空闲页框池中分配，可换出任何进程的页面 | 灵活，但可能影响其他进程 |
| 可变分配局部置换 | 进程页框数可调，但只能在自己的页面中置换 | 折中方案 |
六、抖动与工作集
抖动 (Thrashing)
当进程分配到的页框数不足以容纳其工作集时，会频繁发生缺页，CPU 大量时间花在页面置换上，利用率急剧下降——这种现象称为抖动。
flowchart TD
A["进程增多"] --> B["每个进程分到的页框减少"]
B --> C["缺页率上升"]
C --> D["CPU利用率下降"]
D --> E["调度器增加进程数<br/>(以为CPU空闲)"]
E --> B
style C fill:#ffcdd2,stroke:#c62828
style D fill:#ffcdd2,stroke:#c62828
CPU 利用率随进程数的变化：
CPU利用率
↑
100%│ ╱‾‾‾‾╲
│ ╱ ╲
│ ╱ ╲ ← 抖动区域
│ ╱ ╲
│ ╱ ╲
│╱ ╲
└──────────────────────────→ 进程数
↑
最佳点
工作集 (Working Set)
工作集的定义：在最近 \Delta 时间内，进程实际访问的页面集合。
W(t, \Delta) = \text{在时刻 } t-\Delta \text{ 到 } t \text{ 之间访问的页面集合}
示例:
页面访问序列: ... 2, 6, 1, 5, 7, 7, 7, 2, ...
设 $\Delta = 5$（最近 5 次访问），当前访问页面 2：
- 最近 5 次访问: {5, 7, 7, 7, 2}
- 工作集 = {2, 5, 7}，大小 = 3
工作集策略: 为每个进程分配不少于其工作集大小的页框数，就可以避免抖动。
工作集模型的应用
flowchart TD
A["监控每个进程的工作集"] --> B{"总工作集 ≤ 物理页框数?"}
B -->|"是"| C["正常运行，不会抖动"]
B -->|"否"| D["可能发生抖动"]
D --> E["挂起某些进程<br/>释放页框"]
E --> B
style D fill:#ffcdd2,stroke:#c62828
style C fill:#c8e6c9,stroke:#2e7d32
七、请求分段
基本思想
请求分段是虚拟存储器在15_段式存储管理基础上的实现：
- 段不需要全部装入内存
- 访问到不在内存的段时，触发缺段中断，从外存调入
与请求分页的对比
| 对比项 | 请求分页 | 请求分段 |
|---|---|---|
| 调入/调出单位 | 页面（固定大小） | 段（可变大小） |
| 碎片 | 内碎片 | 外碎片 |
| 共享 | 以页为粒度 | 以段为粒度 |
| 中断类型 | 缺页中断 | 缺段中断 |
| 实现复杂度 | 较简单 | 较复杂 |
八、完整计算示例
综合例题
某系统采用请求分页存储管理，页面大小为 4KB，物理内存有 4 个页框。某进程的页面访问序列为：0, 1, 4, 2, 0, 2, 6, 5, 1, 2, 3, 2, 1, 2, 6, 5, 2, 1, 3, 6。分别用 FIFO 和 LRU 算法计算缺页次数。
FIFO 算法:
| 访问 | 页框0 | 页框1 | 页框2 | 页框3 | 缺页? |
|---|---|---|---|---|---|
| 0 | 0 | - | - | - | 缺页 |
| 1 | 0 | 1 | - | - | 缺页 |
| 4 | 0 | 1 | 4 | - | 缺页 |
| 2 | 0 | 1 | 4 | 2 | 缺页 |
| 0 | 0 | 1 | 4 | 2 | 命中 |
| 2 | 0 | 1 | 4 | 2 | 命中 |
| 6 | 6 | 1 | 4 | 2 | 缺页(淘汰0) |
| 5 | 6 | 5 | 4 | 2 | 缺页(淘汰1) |
| 1 | 6 | 5 | 1 | 2 | 缺页(淘汰4) |
| 2 | 6 | 5 | 1 | 2 | 命中 |
| 3 | 6 | 5 | 1 | 3 | 缺页(淘汰2) |
| 2 | 2 | 5 | 1 | 3 | 缺页(淘汰6) |
| 1 | 2 | 5 | 1 | 3 | 命中 |
| 2 | 2 | 5 | 1 | 3 | 命中 |
| 6 | 2 | 6 | 1 | 3 | 缺页(淘汰5) |
| 5 | 2 | 6 | 5 | 3 | 缺页(淘汰1) |
| 2 | 2 | 6 | 5 | 3 | 命中 |
| 1 | 2 | 6 | 5 | 1 | 缺页(淘汰3) |
| 3 | 3 | 6 | 5 | 1 | 缺页(淘汰2) |
| 6 | 3 | 6 | 5 | 1 | 命中 |
FIFO 缺页次数: 14
LRU 算法:
| 访问 | 页框0 | 页框1 | 页框2 | 页框3 | 缺页? |
|---|---|---|---|---|---|
| 0 | 0 | - | - | - | 缺页 |
| 1 | 0 | 1 | - | - | 缺页 |
| 4 | 0 | 1 | 4 | - | 缺页 |
| 2 | 0 | 1 | 4 | 2 | 缺页 |
| 0 | 0 | 1 | 4 | 2 | 命中 |
| 2 | 0 | 1 | 4 | 2 | 命中 |
| 6 | 0 | 1 | 6 | 2 | 缺页(淘汰4) |
| 5 | 0 | 5 | 6 | 2 | 缺页(淘汰1) |
| 1 | 1 | 5 | 6 | 2 | 缺页(淘汰0) |
| 2 | 1 | 5 | 6 | 2 | 命中 |
| 3 | 1 | 5 | 3 | 2 | 缺页(淘汰6) |
| 2 | 1 | 5 | 3 | 2 | 命中 |
| 1 | 1 | 5 | 3 | 2 | 命中 |
| 2 | 1 | 5 | 3 | 2 | 命中 |
| 6 | 1 | 5 | 3 | 6 | 缺页(淘汰2) |
| 5 | 1 | 5 | 3 | 6 | 命中 |
| 2 | 2 | 5 | 3 | 6 | 缺页(淘汰1) |
| 1 | 2 | 1 | 3 | 6 | 缺页(淘汰5) |
| 3 | 2 | 1 | 3 | 6 | 命中 |
| 6 | 2 | 1 | 3 | 6 | 命中 |
LRU 缺页次数: 12
九、小结
mindmap
root((虚拟存储器))
基本思想
虚拟空间>物理内存
部分装入
按需调入调出
局部性原理
时间局部性
空间局部性
行优先vs列优先
请求分页
页表扩展状态位
缺页中断处理
页面置换
置换算法
OPT理论最优
FIFO简单但有Belady异常
LRU效果好但开销大
Clock近似LRU
LFU最少使用
内存分配
平均/按比例/优先权
固定/可变分配
局部/全局置换
抖动与工作集
频繁缺页=抖动
工作集=近期访问页面集
帧数≥工作集大小
思考题
-
概念理解: 为什么说虚拟存储器的基础是局部性原理？如果没有局部性，虚拟存储器还能工作吗？
-
算法对比: 对于页面引用串 1,2,3,4,1,2,5,1,2,3,4,5（3个物理块），分别计算 OPT、FIFO、LRU 的缺页次数。是否存在Belady异常？
-
工作集: 某进程页面访问序列为 2,6,1,5,7,7,7,2,5,1,3,1,5,7,2,5，设 $\Delta=5$，求各时刻的工作集大小。
-
抖动分析: 某系统物理内存可容纳 10 个工作集页面。目前有 5 个进程，工作集大小分别为 {3,2,2,1,3}。此时再增加一个工作集大小为 3 的进程，系统是否会发生抖动？
-
综合题: 在请求分页系统中，页面大小 4KB，页表项 4 字节，虚拟地址 32 位，物理地址 32 位。
- 一级页表有多大？
- 如果采用二级页表，页目录和页表各多大？
- 如果 TLB 命中率 95%，TLB 访问 10ns，内存访问 100ns，有效访问时间是多少？