====== 第五章 虚拟存储器 ======

===== 5.1 虚拟存储器的基本概念 =====

==== 5.1.1 虚拟存储器的引入 ====

在早期的计算机系统中，程序必须全部装入内存才能运行。这带来了几个问题：

1. **内存容量限制**：大程序无法在小内存系统中运行
2. **内存利用率低**：程序可能只使用了部分代码和数据，但占用整个内存空间
3. **程序地址冲突**：多个程序可能使用相同的绝对地址
4. **编程困难**：程序员需要考虑内存的实际布局

虚拟存储技术的引入解决了这些问题，使得：
- 程序可以在部分装入内存的情况下运行
- 程序员使用统一的虚拟地址空间编程
- 多个程序可以共享内存而互不干扰
- 内存得到更有效的利用

==== 5.1.2 虚拟存储器的工作原理 ====

虚拟存储器是一种存储管理技术，它将主存和辅助存储器（通常是磁盘）统一编址，形成一个比实际主存大得多的地址空间。

**基本概念**：

- **虚拟地址（逻辑地址）**：程序中使用的地址
- **物理地址**：实际内存单元的地址
- **地址空间**：地址的集合
  - 虚拟地址空间：程序可使用的地址范围
  - 物理地址空间：实际内存的地址范围

**工作过程**：

1. 程序使用虚拟地址编写和编译
2. 运行时，虚拟地址需要转换为物理地址（地址映射）
3. 如果所需页面已在物理内存中，直接访问
4. 如果不在内存中（缺页），从磁盘调入所需页面
5. 如果内存已满，需要选择一页换出到磁盘（页面置换）

**虚拟存储器的特点**：

1. **离散性**：程序可以分散存储在内存的不同位置
2. **多次性**：程序可以分多次装入内存
3. **对换性**：程序可以在运行过程中换入换出
4. **虚拟性**：从逻辑上扩充了内存容量

**图5-1：虚拟存储器地址转换示意图**
{{https://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Virtual_memory.svg/800px-Virtual_memory.svg.png?direct|虚拟存储器地址映射|500}}

===== 5.2 页式虚拟存储器 =====

==== 5.2.1 分页的基本概念 ====

**页（Page）**：
将虚拟地址空间和物理内存都划分为固定大小的块，虚拟地址空间的块称为页，物理内存的块称为页框（Page Frame）或物理页。

页的大小通常为4KB（也可以是2KB、8KB、16KB等），是2的幂次方便地址计算。

**页表（Page Table）**：
页表用于记录虚拟页到物理页框的映射关系。每个进程都有自己的页表。

页表项（PTE）通常包含：
- 物理页框号
- 有效位（存在位）：该页是否在内存中
- 修改位（脏位）：该页是否被修改过
- 访问位：该页是否被访问过
- 保护位：读/写/执行权限
- 缓存禁用位等

**地址结构**：

虚拟地址分为两部分：
| 虚拟页号（VPN） | 页内偏移（Offset） |

物理地址分为两部分：
| 物理页框号（PFN） | 页内偏移（Offset） |

页内偏移位数由页大小决定（如4KB页，偏移为12位）

==== 5.2.2 地址转换过程 ====

**基本地址转换**：

1. 将虚拟地址拆分为虚拟页号和页内偏移
2. 用虚拟页号作为索引查找页表，得到页表项
3. 检查有效位，若为1则取出物理页框号
4. 物理页框号与页内偏移拼接，形成物理地址

**快表（TLB）加速**：

页表通常存放在内存中，每次地址转换需要访问内存，开销很大。快表（Translation Lookaside Buffer）是一种特殊的Cache，用于缓存最近使用的页表项。

TLB的工作原理：
1. 用虚拟页号查询TLB
2. 如果命中（TLB Hit），直接得到物理页框号
3. 如果不命中（TLB Miss），访问内存中的页表
4. 将页表项装入TLB（可能需要替换）

TLB通常采用全相联或组相联映射，项数为32-512项。

**带TLB的地址转换过程**：

1. 根据虚拟页号访问TLB
2. TLB命中：用TLB中的页框号和页内偏移组成物理地址
3. TLB不命中：访问页表获取页表项
   - 如果页在内存中，更新TLB，重新访问TLB
   - 如果页不在内存中（缺页），触发缺页异常

==== 5.2.3 多级页表 ====

**引入多级页表的原因**：

对于大地址空间（如64位系统），如果使用单级页表，页表本身会占用大量内存。

例如：64位地址空间，4KB页，每页8字节页表项
- 虚拟页号位数 = 64 - 12 = 52位
- 页表项数 = 2^52
- 页表大小 = 2^52 × 8字节 = 32PB（不可能实现）

**多级页表的结构**：

将页表本身也分页，建立层次结构。以二级页表为例：

虚拟地址划分：
| 一级页表索引 | 二级页表索引 | 页内偏移 |

地址转换过程：
1. 用一级页表索引查找页目录，得到二级页表地址
2. 用二级页表索引查找二级页表，得到物理页框号
3. 拼接物理地址

**优点**：
- 只需要为实际使用的虚拟地址空间分配页表空间
- 页表可以分散存储，不需要连续的大块内存

**缺点**：
- 地址转换需要多次内存访问，增加了延迟
- 现代处理器使用页表遍历缓存（Page Walk Cache）加速

==== 5.2.4 缺页中断与页面置换 ====

**缺页中断（Page Fault）**：

当访问的页面不在物理内存中时，产生缺页中断。处理过程：

1. 保存当前执行状态
2. 查找所需页面在磁盘上的位置
3. 如果内存已满，选择一页换出（页面置换）
4. 从磁盘读入所需页面
5. 更新页表和TLB
6. 恢复执行被中断的指令

缺页中断是一种异常，与普通中断不同，它在指令执行期间产生，处理后需要重新执行该指令。

**页面置换算法**：

当需要调入新页面而内存已满时，需要选择一页换出。常用的置换算法有：

**最佳置换算法（OPT）**：
置换以后永不使用或最长时间内不再被访问的页面。
- 理论最优算法，但无法实现（需要预知未来）
- 用作评价其他算法的标准

**先进先出算法（FIFO）**：
置换最先进入内存的页面。
- 实现简单（使用队列）
- 可能淘汰经常使用的页面
- 可能出现Belady异常（物理页增加，缺页率反而上升）

**最近最久未使用算法（LRU）**：
置换最久未被访问的页面。
- 符合局部性原理，性能接近OPT
- 需要记录访问时间或顺序
- 硬件实现复杂（需要计数器或栈）

**时钟置换算法（Clock）**：
LRU的近似实现，使用访问位。
- 页面组织成环形队列，有指针
- 检查页面的访问位：
  - 为0则置换该页
  - 为1则清0，指针前移
- 实现简单，性能较好，广泛使用

**改进的时钟算法（Clock with Second Chance）**：
同时考虑访问位和修改位，优先置换未修改的页面（减少磁盘写入）。

===== 5.3 段式与段页式虚拟存储器 =====

==== 5.3.1 段式虚拟存储器 ====

**分段的概念**：

按程序的逻辑结构（代码段、数据段、堆栈段等）将地址空间划分为若干段，每段有独立的逻辑意义。

**段的特点**：
- 段长不固定，根据实际需要分配
- 每段有段名或段号
- 段内地址从0开始编址

**地址结构**：
| 段号 | 段内偏移 |

**段表**：
记录各段的信息，包括：
- 段基址（在内存中的起始地址）
- 段长（界限）
- 保护位（读/写/执行）

**地址转换**：
1. 用段号查找段表，得到段基址和段长
2. 检查段内偏移是否越界
3. 段基址 + 段内偏移 = 物理地址

**分段的优点**：
- 符合程序的逻辑结构
- 便于共享和保护（以段为单位）
- 便于动态增长（如堆栈段）

**分段的缺点**：
- 段长不固定，内存分配复杂，容易产生外部碎片
- 需要紧凑（compaction）操作

==== 5.3.2 段页式虚拟存储器 ====

**段页式的概念**：

结合分段和分页的优点，先将程序分段，每段再分页。

**地址结构**：
| 段号 | 段内页号 | 页内偏移 |

**地址转换**：
1. 用段号查找段表，得到页表地址
2. 用段内页号查找页表，得到物理页框号
3. 拼接物理地址

**优点**：
- 既有段的逻辑独立性，又有页的物理管理方便性
- 便于共享和保护
- 无外部碎片（分页的特点）

**缺点**：
- 地址转换需要多次查表，开销较大
- 现代x86架构采用段页式（虽然段功能常被简化）

===== 5.4 虚拟存储器的实现与优化 =====

==== 5.4.1 内存管理单元（MMU） ====

MMU是CPU中负责虚拟地址到物理地址转换的硬件单元。

**MMU的主要功能**：
1. 地址转换：虚拟地址到物理地址的映射
2. 访问控制：检查读/写/执行权限
3. 缺页检测：检测页是否在内存中
4. TLB管理：维护快表

**MMU的工作流程**：
1. CPU发出虚拟地址
2. MMU查询TLB
3. 如果TLB命中，得到物理地址，进行访问
4. 如果TLB不命中，进行页表遍历
5. 如果页在内存中，更新TLB，继续访问
6. 如果页不在内存，触发缺页异常

==== 5.4.2 写时复制（Copy-on-Write） ====

**概念**：
当复制一个页面时，不立即复制物理页，而是让两个虚拟页共享同一物理页，并标记为写保护。只有当某个进程试图写入时，才真正复制页面。

**优点**：
- 减少不必要的内存复制
- 加速进程创建（fork）
- 节省内存空间

==== 5.4.3 内存映射文件 ====

**概念**：
将磁盘文件映射到虚拟地址空间，对内存的访问就是对文件的读写。

**优点**：
- 简化文件I/O编程
- 利用虚拟存储管理机制自动缓存文件内容
- 多个进程可以共享映射，实现进程通信

**实现**：
- 文件的页映射到虚拟地址空间
- 首次访问时从磁盘调入（类似缺页）
- 修改后的页由写回策略决定是否写回磁盘

===== 5.5 虚拟存储器的性能 =====

==== 5.5.1 影响性能的因素 ====

**缺页率**：
缺页率是影响虚拟存储器性能的关键因素。缺页会导致磁盘I/O，开销很大（毫秒级，相当于数百万个时钟周期）。

**影响缺页率的因素**：
1. 分配给进程的物理页面数（工作集大小）
2. 页面置换算法
3. 程序的局部性
4. 页面大小

**工作集模型**：
工作集是指进程在最近一段时间Δ内访问的页面集合。保持工作集在内存中可以最小化缺页率。

**抖动（Thrashing）**：
当分配给进程的物理页面太少，导致频繁缺页，系统大部分时间用于页面换入换出，CPU利用率急剧下降。

防止抖动的方法：
- 增加物理内存
- 减少并发进程数
- 使用工作集模型分配页面

==== 5.5.2 页面大小的选择 ====

**大页面的优点**：
- 减少页表大小
- 减少TLB不命中（每个TLB项覆盖更大范围）
- 减少缺页中断次数
- 提高I/O效率（磁盘按块读取）

**大页面的缺点**：
- 增加内部碎片（页内未使用空间）
- 增加页面换入换出时间
- 降低内存利用率

现代系统通常采用4KB标准页面，同时支持大页（如2MB、1GB）用于特定应用。

===== 5.6 例题分析 =====

**例题1**：某计算机采用页式虚拟存储器，虚拟地址32位，物理地址24位，页面大小4KB。问：
（1）虚拟地址空间和物理地址空间各多大？
（2）页表项至少有多少位？
（3）一个进程最多有多少页？

解：
（1）虚拟地址空间 = 2^32 = 4GB
物理地址空间 = 2^24 = 16MB

（2）页面大小4KB = 2^12，页内偏移12位
物理页框号位数 = 24 - 12 = 12位
页表项至少包含12位页框号，加上有效位、保护位等，通常32位或64位

（3）虚拟页号位数 = 32 - 12 = 20位
最多页数 = 2^20 = 1M页

**例题2**：某系统使用二级页表，虚拟地址32位，页面大小4KB，页表项4字节。每个页表占一页。问：
（1）页目录和二级页表各有多少项？
（2）虚拟地址如何划分？

解：
（1）页面大小4KB = 4096字节，页表项4字节
每个页表可存储 4096/4 = 1024 = 2^10 项
页目录和二级页表都是1024项

（2）页内偏移：12位
二级页表索引：10位
页目录索引：10位
地址划分：| 页目录10位 | 二级页表10位 | 偏移12位 |

**例题3**：某程序访问页面的顺序为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。分配给该进程的物理页框数为3，分别用FIFO和LRU算法计算缺页次数。

解：
FIFO算法：
| 访问 | 内存状态 | 是否缺页 |
|------|----------|----------|
| 1 | 1 | 缺 |
| 2 | 1,2 | 缺 |
| 3 | 1,2,3 | 缺 |
| 4 | 2,3,4 | 缺 |
| 1 | 3,4,1 | 缺 |
| 2 | 4,1,2 | 缺 |
| 5 | 1,2,5 | 缺 |
| 1 | 1,2,5 | 命中 |
| 2 | 1,2,5 | 命中 |
| 3 | 2,5,3 | 缺 |
| 4 | 5,3,4 | 缺 |
| 5 | 5,3,4 | 命中 |
缺页次数：9次

LRU算法：
| 访问 | 内存状态 | 是否缺页 |
|------|----------|----------|
| 1 | 1 | 缺 |
| 2 | 1,2 | 缺 |
| 3 | 1,2,3 | 缺 |
| 4 | 2,3,4 | 缺 |
| 1 | 3,4,1 | 缺 |
| 2 | 4,1,2 | 缺 |
| 5 | 1,2,5 | 缺 |
| 1 | 2,5,1 | 命中 |
| 2 | 5,1,2 | 命中 |
| 3 | 1,2,3 | 缺 |
| 4 | 2,3,4 | 缺 |
| 5 | 3,4,5 | 缺 |
缺页次数：10次

===== 5.7 本章重点总结 =====

**核心概念：**
- 虚拟地址与物理地址的映射
- 页表和TLB的作用
- 缺页中断的处理
- 页面置换算法

**关键知识点：**
1. 虚拟存储器的工作原理和特点
2. 分页系统的地址转换过程
3. TLB的作用和工作原理
4. 多级页表的结构和优点
5. 常见页面置换算法：FIFO、LRU、Clock
6. 段式、页式、段页式的比较
7. 工作集模型和抖动

**重要公式：**
- 虚拟地址 = 虚拟页号 + 页内偏移
- 物理地址 = 物理页框号 + 页内偏移

**学习要点：**
- 理解虚拟存储器解决什么问题
- 掌握页式地址转换的完整过程
- 了解TLB的重要性
- 理解各种页面置换算法的原理

**思考题：**
1. 为什么页式虚拟存储器比段式更常用？
2. TLB不命中会对性能产生什么影响？
3. 什么情况下会发生抖动？如何防止？
4. 写时复制有什么优点？