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

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

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

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

基本概念：

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

1. 虚拟地址空间：程序可使用的地址范围
2. 物理地址空间：实际内存的地址范围

工作过程：

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

虚拟存储器的特点：

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

图5-1：虚拟存储器地址转换示意图

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

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

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

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

地址结构：

虚拟地址分为两部分：

物理地址分为两部分：

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

基本地址转换：

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不命中：访问页表获取页表项

1. 如果页在内存中，更新TLB，重新访问TLB
2. 如果页不在内存中（缺页），触发缺页异常

引入多级页表的原因：

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

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

多级页表的结构：

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

虚拟地址划分：

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

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

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

缺页中断（Page Fault）：

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

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

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

页面置换算法：

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

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

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

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

时钟置换算法（Clock）： LRU的近似实现，使用访问位。 - 页面组织成环形队列，有指针 - 检查页面的访问位：

1. 为0则置换该页
2. 为1则清0，指针前移

- 实现简单，性能较好，广泛使用

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

分段的概念：

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

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

地址结构：

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

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

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

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

段页式的概念：

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

地址结构：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例题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算法：

缺页次数：9次

LRU算法：

缺页次数：10次

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

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

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

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

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