OS-06 虚拟存储器

一、虚拟存储的基本原理

虚拟存储器的核心思想是：程序在运行时不需要全部装入内存，只需要装入当前需要使用的部分。这基于一个重要的观察——程序的局部性原理。

时间局部性：刚被访问过的地址很可能在不久的将来再次被访问。这是因为程序中有大量的循环结构。

空间局部性：刚被访问过的地址附近的地址也很可能被访问。这是因为程序中的代码和数据通常顺序存放、顺序执行。

基于局部性原理，操作系统可以在物理内存有限的情况下运行比内存大得多的程序：只将当前需要的页面装入内存，其余的保持在磁盘上。当程序访问的页面不在内存中时，操作系统负责将其从磁盘调入。这就是"按需调页"技术。

二、缺页中断处理过程

当CPU访问的页面不在物理内存中时，MMU（内存管理单元）会触发一个缺页异常（Page Fault），操作系统捕获这个异常后进行以下处理：

  1. 保护现场：保存当前进程的CPU寄存器状态
  2. 检查页表：确认该页面确实在磁盘上（而非非法访问）
  3. 查找空闲页框：如果内存中有空闲页框，直接使用；如果没有，需要选择一个页面置换出去
  4. 启动磁盘I/O：从磁盘读取所需的页面到页框中
  5. 更新页表：添加新的页号→页框号映射关系
  6. 恢复现场：重新执行引起缺页的指令

这个过程中，步骤4是需要大量时间的（磁盘I/O通常在毫秒级，而CPU操作在纳秒级，相差百万倍）。

三、页面置换算法

当内存没有空闲页框时，必须选择一个已经存在的页面置换出去，为新页面腾出空间。不同的置换策略对系统的性能影响很大。

页面引用串：7,0,1,2,0,3,0,4,2,3,0,3,2 内存3块 FIFO 7 0 1 2 3 0 4 2 3 0 缺页: 7,0,1,2,3,0,4 → 9次 LRU 7 0 1 2 3 0 4 2 3 0 缺页: 7,0,1,2,3,4 → 6次 OPT（最佳） 7 0 1 2 3 4 缺页: 7,0,1,2,3,4 → 5次 影响缺页率的四个因素 1. 页面大小：页面越大，页表越小，但内部碎片和缺页传输开销增大 2. 进程分配的物理块数：块数越多，缺页概率越低 3. 置换算法：LRU和OPT优于FIFO，但OPT无法实现（需预知未来） 4. 程序局部性：时间局部性好的程序缺页率显著降低

3.1 FIFO（先进先出）

FIFO选择最先进入内存的页面进行置换。它用一个队列来维护页面进入的顺序，每次淘汰队首的页面。

优点：实现简单，只需要维护一个队列。

缺点：没有考虑页面的使用频率。一个被频繁访问的页面可能因为"来得早"而被置换出去，导致刚被置换又立刻需要调回来。更糟糕的是，FIFO存在Belady异常——增加可用页框数反而会导致缺页率上升。

3.2 LRU（最近最久未使用）

LRU选择最长时间没有被访问的页面进行置换。它基于一个合理的假设：如果一个页面很久没被访问过，那么它在未来被访问的可能性也比较小。

优点：性能接近理论最优的OPT算法，没有Belady异常。

缺点：实现成本较高，需要记录每个页面的最后访问时间，或者维护一个按访问时间排序的链表。

3.3 OPT（最佳置换）

OPT置换未来最长时间内不会被访问的页面。它需要"预知未来"——知道进程未来的页面访问序列。

优点：理论上缺页率最低。

缺点：无法在实际系统中实现，只能作为衡量其他算法性能的参考标准。通常用于教学和算法评估。

3.4 置换过程详解

以引用串 7,0,1,2,0,3,0,4,2,3,0,3,2 为例，3块物理帧：

FIFO置换过程：

7 → [7]           缺页
0 → [7,0]         缺页
1 → [7,0,1]       缺页
2 → [0,1,2]       缺页，7被置换（最早进入）
0 → [0,1,2]       命中
3 → [1,2,3]       缺页，0被置换
0 → [2,3,0]       缺页，1被置换
4 → [3,0,4]       缺页，2被置换
2 → [0,4,2]       缺页，3被置换
3 → [4,2,3]       缺页，0被置换
0 → [2,3,0]       缺页，4被置换
3 → [2,3,0]       命中
2 → [2,3,0]       命中
缺页9次，缺页率9/13≈69%

LRU置换过程：

7 → [7]           缺页
0 → [7,0]         缺页
1 → [7,0,1]       缺页
2 → [0,1,2]       缺页（7是最久未用）
0 → [1,2,0]       命中（0被提到最近）
3 → [2,0,3]       缺页（1最久未用）
0 → [2,3,0]       命中
4 → [3,0,4]       缺页（2最久未用）
2 → [0,4,2]       缺页（3最久未用）
3 → [4,2,3]       缺页（0最久未用）
0 → [2,3,0]       缺页（4最久未用）
3 → [2,0,3]       命中
2 → [0,3,2]       命中
缺页6次，缺页率6/13≈46%

四、影响缺页率的因素

  1. 页面大小：页面越大，页表占用越小，但每次缺页传输的数据量也越大，且可能造成更多的内部碎片
  2. 进程分配的物理块数：块数越多，缺页率越低（但不是线性关系）
  3. 页面置换算法：OPT > LRU > FIFO（按缺页率升序排列）
  4. 程序的局部性：局部性好的程序（如矩阵按行访问）缺页率显著低于局部性差的程序（如矩阵按列访问）

五、系统颠簸（Thrashing）

颠簸是虚拟存储系统中一种最糟糕的状态。它的发生过程是：

  1. 进程频繁缺页，不断发出磁盘I/O请求
  2. CPU大部分时间在等待磁盘I/O，利用率下降
  3. 操作系统误以为"CPU不够用"，引入更多进程
  4. 更多进程竞争有限的内存，每个进程的可用页框更少
  5. 缺页更加频繁，CPU利用率进一步下降

这是一个恶性循环，最终导致系统瘫痪——CPU利用率接近0%，而磁盘持续繁忙。

改进方法：采用工作集模型，为每个进程分配足够的工作集（当前正在使用的那部分页面），使缺页率保持在可接受的水平。