（二）虚拟内存管理

1. 虚拟内存基本概念

1.1. 常规存储管理的特点和局部性原理

• 常规存储管理的特点：(1) 一次性；(2) 驻留性；

  • 一次性：所有程序和数据需要完整加载到内存才能运行；

  • 驻留性：进程一旦开始运行就一直占用内存空间，即使不使用 CPU，直到运行完毕才释放；

• 局部性原理 by P.Denning：在较短的一段时间内，程序的执行仅局限于某个部分，其所使用的存储空间也只局限于某个区域；

  • 时间的局部性：如反复执行循环体语句；

  • 空间的局部性：程序的顺序执行，顺序存储（如数组结构）；

• 由局部性原理可知，程序运行之前无需将全部模块装入内存，而仅需先装入当前要运行的部分，其余部分可留在外存上；

1.2. 虚拟存储器的定义和特征

• 定义：具有请求调入和置换功能，能从逻辑上扩充内存容量的一种存储器系统；

  • 逻辑容量 = 内存容量 + 外存容量；

  • 运行速度接近于内存，单位成本接近于外存；

• 特征：(1) 多次性；(2) 对换性；(3) 虚拟性；

  • 多次性：对要运行程序和数据分成多次加载，而非一次性加载完。相对于常规存储器的一次性而言；

  • 对换性：程序和数据无需常驻内存，而允许其在进程运行时从外存换进换出。相对常规存储器的驻留性而言；

  • 虚拟性：物理上不存在，是用算法实现的逻辑上的存储器系统；

1.3. 虚拟存储器实现方法

• 分页请求系统

  • 1）硬件支持：(1) 请求页表机制；(2) 缺页中断机构；(3) 地址变换机构

  • 2）软件支持：请求分页的软件，即 OS；

2. 请求分页管理

2.1. 请求页表机制

• 和页表机制相似，主要数据结构是请求页表，负责将用户逻辑地址映射到内存物理地址；

• 请求页表和页表相似，为了满足换进换出的需要，增加了几个字段：

  

  • 状态位 $P$：1 位，表示当前页面在内存还是外存，一般 0 是在外存，1 在内存；

  • 访问字段 $A$：携带一些页面访问信息（例如某段时间内访问的次数），用于页面置换算法；

    • 一般也是 1 位，0 代表这段时间内没访问过，1 代表访问过；

  • 修改位 $M$：1 位，表示相对于内存中的页面相对于外存是否改变了，0 未改变，1 改变了；

    • 若改变了，则换出时需要向外存执行写回操作；

  • 外存地址：顾名思义，用于在缺页中断时，将外存上的页装入内存；

2.2. 缺页中断机构

• 负责在指令执行期间产生和处理中断信号；

• 一条指令执行期间可能产生多次缺页中断；

2.3. 地址变换机构

• 除了常规地址变换机构，还增加了缺页中断机构，产生和处理缺页中断，以及从内存中换出一页的机构

  • 产生和处理缺页中断：硬件实现；

  • 从内存中 换出一页：软件实现；

• 请求分页的变换过程示意

  

3. 页框分配

3.1. 最小物理块数的确定

• 最小物理块数：保证进程执行所需最少的物理块数；

  • 和硬件结构，指令功能和寻址方式有关；

3.2. 内存分配策略

• 两种内存分配策略：固定和可变分配；

• 两种置换策略：全局和局部置换；

  • 全局置换：发生置换时，可以用 OS 空闲的页框置换，然后给进程，使得进程获得更多页框，故全局置换不适用于固定分配；

  • 局部置换：发生置换时，只能用进程已有的页框来置换；

• 组合策略：以下三种

  • 固定分配 + 局部置换

  • 可变分配 + 全局置换

  • 可变分配 + 局部置换

3.3. 物理块分配算法

• 固定分配时，决定如何将 OS 可用的物理块分配给各进程；

  • 平均分配：顾名思义；

  • 按比例分配：根据进程的大小，按比例分配物理块；

  • 优先级分配：顾名思义；

• 通常采取的方法：一部分按比例分配，另一部分则按优先级分配；

• 比较重要的实时系统，可完全采用优先级分配；

4. 页面置换算法

4.1. 最佳（Optimal）置换算法

• 是理论上的算法，现实情况无法实现；

• 策略：选择一个以后永远不会用到的，或者很长时间内不会用到的页面换出；

• 可以保证缺页率最低；

• 由于页面使用情况的无法预知性，该算法无法实现，但是可用来评价其他算法；

4.2. 先进先出（FIFO）置换算法

• 策略：总是换出最先进入内存的页面（即当前驻留内存最久的页面）；

• 实现：一个队列即可；

• 实现最简单，但是没考虑页面的使用情况，不合理，性能较差；

4.3. 最近最久未使用（LRU）算法（⭐）

• 用最近一段时间的页面使用情况作为参考，预测将来一段时间内的使用情况，换出最近一段时间未使用时间最久的页面；

• 策略：每个页面设置一个访问字段 $t$，表示上次访问以来经过的时间，每次选择 $t$ 最大的页面换出；

4.4. Clock 置换算法

• 策略

  • 每个页面设置 1 bit 访问位（通常称为 $A$），用于标识是否被访问过，所有页排成循环队列。

  • 换出时，按照 FIFO 原则遍历，若一页的访问位为 0，则直接换出；否则将访问位置为 0，再检查下一个；

• 只考虑页面是否被用过，而不考虑未使用的时长，又称为最近未用算法；

4.5. 改进 Clock 算法

• 用一个 $M$ 访问位标识页面是否被修改过，因为换出被修改的页面需要 IO 操作写磁盘，很花时间；

• 通过 $A,M$ 两个位，计算换出一个页面的代价**（从小到大排列）**：

  • $A=0,M=0$：最近未访问且未修改，换出代价最小，优先换出；

  • $A=0,M=1$：最近未访问但被修改，换出代价略大，次优先换出；

  • $A=1,M=0$：最近被访问但未被修改，换出代价较大，再次优先换出；

    • 注意这个代价比 $A=0,M=1$ 的大；

  • $A=1,M=1$：最近被访问且被修改，换出代价最大，尽量不换出；

• 策略

  • 第一轮扫描循环队列，找 $A=0,M=0$ 的页面，如果找不到，就进入第二轮；

  • 第二轮扫描，找 $A=0,M=1$ 的页面，并将所有扫描过的 $A$ 置为 0，如果找不到，进入第三轮；

  • 第三轮扫描，重复第一轮和第二轮的扫描，因为第二轮置 0 操作，此轮一定可以找到；

• 最好情况扫描 1 轮，最坏情况要扫描 4 轮；

5. 内存映射文件（Memory-Mapped Files）

• 是操作系统支持的一种文件处理方式；

• 通过文件映射，使得用户能够像处理内存一样处理文件；

6. 虚拟存储器性能的影响因素和改进方法

6.1. 进程的抖动

• 进程的大部分时间都在处理页面的换进换出，而不能用于有效工作，就称为抖动状态；

• 原因：OS 中进程太多，分配给进程的内存小，频繁缺页，所以需要频繁换进换出；

• 由于 IO 不占 CPU，进程抖动会降低 CPU 利用率，从而降低 OS 效率；

6.2. 工作集

• 工作集：是指某段时间间隔 $\mathrm{\Delta }t$ 内，进程实际要访问的页面集合；

• 置换：用程序最近一段时间的工作集使用情况，预测未来一段时间的使用情况；

6.3. 抖动的预防方法

• 1）局部置换策略；

• 2）利用工作集；

• 3）"L=S" 准则

  • L：发生缺页的平均时间；

  • S：平均缺页处理时间（即置换一个页面所需的平均时间）；

  • 若 $L>>S$，说明很少发生缺页，磁盘利用率不高，反之说明频繁缺页，磁盘负荷高；

  • 当 $L\approx S$ 时，处理机和磁盘都可以达到最高利用率；

• 4）选择暂停进程；