操作系统-虚拟存储器
6.1 虚拟存储器概述
常规存储器管理方式的特征和局部性原理
常规存储器管理方式的特征
- 一次性：进程执行前必须将全部信息装入内存，否则无法运行
- 驻留性：进程的全部信息在整个运行期间始终占用内存，不会被换出
这两个特征意味着：如果一个程序比内存大，就根本无法运行；即使能装入，它也会一直霸占内存直到结束，即使其中大部分代码只在某个瞬间被用到。这对内存的利用率是极大的浪费。
局部性原理
- 时间局限性：某条指令被执行后，不久的将来它很可能再次被执行
- 空间局限性：某条指令被访问后，它附近的指令也很可能被访问
局部性原理是虚拟存储器能工作的理论基础。正因为程序的执行模式具有这种聚集性，我们才有可能只把「当前需要的部分」装入内存，而不需要一次性全部加载。
虚拟存储器的基本工作情况
基于局部性原理，虚拟存储器不需要把进程的全部信息装入内存，只装入当前需要的部分页面。不在内存时从磁盘调入，内存不够时换出暂时不用的页面。
虚拟存储器的定义与特征
虚拟存储器的定义
虚拟存储器是具有请求调入功能和置换功能的，能从逻辑上对内存容量加以扩充的存储器系统。其逻辑容量由内存和外存之和决定，其运行速度接近内存速度，每位成本却接近外存。
虚拟存储器的特征
- 多次性：作业被分成多次装入内存运行，而非一次性全部装入
- 对换性：允许作业在运行过程中换进换出，不需要常驻内存
- 虚拟性：逻辑上扩充了内存容量，使用户看到的内存空间远大于实际物理内存
虚拟存储器的实现方法
请求分页系统
- 硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构
- 实现请求分页的软件：实现请求调页的软件和页面置换的软件
请求分段系统
- 硬件支持：请求分段的段表机制、缺段中断机构、地址变换机构
- 实现请求分段的软件：实现请求调段的软件和段置换的软件
6.2 请求分页管理存储方式
请求分页是虚拟存储器最主要的实现方式。它的核心思路是：页表不再只记录「逻辑页到物理块的映射」，还要额外记录每一页是否在内存中、是否被修改过、最近是否被访问过等状态信息，以便 OS 按需调页和置换。
请求分页中的硬件支持
请求页表机制
在纯分页的页表基础上增加若干字段：
- 状态位 P：标识该页是否已在内存中。1=在内存，0=不在内存
- 访问字段 A：记录该页最近被访问的次数或最近访问的时间，供置换算法参考
- 修改位 M：标识该页调入内存后是否被修改过。1=修改过，换出时需写回外存；0=未修改，可直接丢弃
- 外存地址：该页在外存中的存放地址
缺页中断机构
- 在指令执行期间，产生和处理中断信号
- 一条指令在执行期间，可能会产生多次缺页中断
地址变换机构
在基本地址变换机构基础上增加缺页中断处理和页面调入功能。查页表时发现 P=0 则产生缺页中断，从外存调入页面，内存已满时先按置换算法换出，再重新执行被中断的指令。
请求分页中的内存分配与回收
最小物理块数的确定
- 保证进程正常运行所需的最少物理块数，指进程即使在最坏的内存访问模式下，也不会因缺页而立即死锁所需的最小块数
- 与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式
- 单地址指令且直接寻址时，最坏情况是指令和数据分别在不同页，至少需要 2 个物理块
内存分配策略
- 固定分配局部置换：为每个进程分配固定数量的物理块，缺页时只能从该进程的页面中置换
- 可变分配全局置换：先为每个进程分配一定数量的物理块，OS 保留若干空闲块。某进程缺页时，若有空闲块则分配，否则从所有进程中选一页换出
- 可变分配局部置换：为每个进程分配一定数量的物理块，缺页时只能从该进程的页面中置换，但会定期根据缺页率动态调整分配数量
- 固定分配不存在全局置换：固定分配要求每个进程的物理块数固定不变，而全局置换允许从其他进程或空闲块中获取页面，两者互相矛盾
物理块分配算法
- 平均分配：将所有物理块平均分配给每个进程
- 按比例分配：根据进程大小按比例分配物理块
- 考虑优先权的分配：优先级高的进程分配更多物理块
内存回收
- 进程终止时
- 主动释放内存时
- 内存不足时
页面调入策略
何时调入页面
- 预调页策略：根据局部性原理，一次调入若干相邻页面。但预调页的成功率不高，因为进程初始运行时的页面访问顺序难以预测
- 请求调页策略：每次只调入需要的一页。实现简单，但缺页一次调入一次，系统开销较大
从何处调入页面
- 系统拥有足够的对换空间：从外存对换区调入
- 系统缺少足够的对换空间：从文件区调入，若页面是共享页面则直接从文件区读取
如何调入页面
产生缺页中断时，由 OS 的缺页中断处理程序负责调入。
缺页率
缺页率 = 缺页次数 / 访问页面总次数。影响因素：
- 页面大小：页面越大，缺页率越低，但浪费越多
- 进程所分配物理块的数目：分配的物理块越多，缺页率越低
- 页面置换算法：算法越优，缺页率越低
- 程序的固有特性：程序本身的局部性程度决定了缺页率的下限
- 置换代价：被换出的页面是否被修改过，若未修改则可直接丢弃，代价小；若修改过则需写回外存，代价大
6.3 页面置换算法
当内存已满、需要调入新页面时，必须选择一个页面换出。选哪个、怎么选，就是页面置换算法要解决的问题。不同算法在缺页率和实现开销之间做了不同的权衡。
最佳页面置换算法 OPT
- 所选择的淘汰页面是以后永不使用的，或在未来最长时间不会被访问的页面
- 通常可保证获得最低的缺页率
- 但由于无法预知访问情况，算法无法实现
- 作用：作为理论上限，用来衡量其他算法的优劣
先进先出页面置换算法 FIFO
- 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰
- 算法实现简单：把进程已调入内存的页面按先后次序链接成一个队列，设置一个指针指向最老的页面即可
- 该算法与进程实际运行规律不相适应，不能保证经常访问的页面不被淘汰
- Belady 异常：增加物理块数反而可能导致缺页率上升，FIFO 是唯一可能出现此现象的置换算法
最近最久未使用页面置换算法 LRU
- 赋予每个页面一个访问字段，记录该页面自上次被访问以来所经历的时间 t，值最大的予以淘汰
- 性能接近 OPT，是实际可用算法中最优的
硬件支持
LRU 需要记录每个页面的访问时间，这需要硬件支持。两种主要方案：
- 寄存器方式：为内存中每个页面配置一个移位寄存器。当进程访问某物理块时最高位取 1，定时信号每隔一定时间将寄存器右移一位。把这个 n 位寄存器看作一个整数，数值最小的寄存器所对应的页面就是最近最久未使用的页面
- 栈方式：利用一个栈保存当前使用的各个页面的页面号。当进程访问某页面时，将该页面号从栈中移出并压入栈顶，栈顶始终是最新被访问的页面号，栈底则是最近最久未使用的页面号
最少使用页面置换算法 LFU
- 直接利用计数器记录某页面被访问次数是不现实的，采用 LRU 的移位寄存器方案可近似得到
- LFU 不能真正反映页面的使用情况：在一个时间间隔内，对某页访问 1 次和访问 1000 次是完全等效的
Clock 页面置换算法
LRU 的精确实现开销太大，Clock 算法是它的近似版本，用访问位代替精确的时间记录，大幅降低了开销。
简单 Clock（NRU / 二次机会）
- 为每页设置一个访问位，将内存中所有页面通过链接指针链接成一个循环队列
- 当某页被访问时访问位置 1
- 选择页面淘汰时检查访问位：为 0 则换出；为 1 则置为 0 暂不换出
- 又称最近未用页面置换算法 NRU 或二次机会页面置换算法
- 是 LRU 的近似实现，开销远小于精确 LRU
改进型 Clock
改进型 Clock 在简单 Clock 的基础上进一步考虑了置换代价——修改过的页面换出时需要写回磁盘，代价更高。
- 除访问位 A 外，增加修改位 M，同时考虑置换代价
- 优先淘汰 (A=0, M=0) 的页面——既未使用又未修改，换出代价最小
- 其次淘汰 (A=0, M=1) 的页面——未使用但修改过，需写回
- 淘汰顺序：(0,0) → (0,1) → (1,0) → (1,1)
页面缓冲算法
影响页面换入换出效率的因素
- 页面置换算法
- 写回磁盘的频率
- 读入内存的频率
原理
在原页面置换算法的基础上，增设已修改页面链表，保存已修改且需要被换出的页面。等被换出的页面数目达到一定值时，再一起换出到磁盘，以减少页面换出开销。
请求分页系统的内存有效访问时间 EAT
有效访问时间 = 命中快表时的访问时间 × 命中率 + 未命中时的访问时间 × 未命中率
三种情况
- 被访问页在内存中，且页表项在快表中：只需访问快表和内存一次
- 被访问页在内存中，但页表项不在快表中：先查页表发现不在快表，再查快表并加入，最后访问内存
- 被访问页不在内存中：产生缺页中断，完成页面调入后重新执行指令
6.4 抖动与工作集
当系统中同时运行的进程太多，每个进程分到的物理块不够用时，就会出现一种称为抖动的现象——进程频繁缺页，CPU 大部分时间花在等待页面换入换出上，而不是执行有效工作。
多道程序度与抖动
多道程序度与处理机利用率
产生抖动的原因是同时在系统中运行的进程太多，导致分配给每个进程的物理块太少，致使每个进程在运行中会频繁出现缺页，系统中排队等待页面换入换出的进程数量增加，造成每个进程大部分时间用于页面的换入换出而不能进行有效工作。
工作集
工作集的基本概念
工作集是基于局部性原理提出的概念。进程在一段时间内总是集中访问少数几个固定的页面，如果内存中能容纳这些页面，缺页率就会很低。
工作集的定义
在某段时间间隔 Δ 内，进程实际访问的页面集合，记为 w(t, Δ)。其中 t 为当前时刻，Δ 为工作集窗口大小。
- Δ 太小：漏掉常用的页面，工作集不完整
- Δ 太大：包含已经不再使用的页面，浪费内存
- 实际系统中 Δ 通常取固定值（如 5000~10000 次内存访问）
抖动的预防方法
- 采取局部置换策略：每个进程只能从自己的页面中置换，避免一个进程的抖动影响其他进程
- 把工作集算法融入处理机调度中：调度新进程前先检查其工作集能否装入内存，不能则暂停
- 采用 l=s 准则调节缺页率：l 为缺页之间的平均时间，s 为工作集的平均访问间隔。l > s 说明缺页不频繁（内存足够），l < s 说明缺页太频繁（内存不足），需要减少并发进程数
- 选择暂停的进程：优先挂起不活跃或占用物理块多但贡献低的进程
6.5 内存映射文件
内存映射文件将文件直接映射到进程的虚拟地址空间，对映射区域的读写由 OS 自动转为文件 I/O。实际磁盘读写通过缺页中断按需调入，而非立即发生。多个进程可映射同一文件实现共享内存，需同步机制防止并发写入冲突。