传统存储管理有两个限制：

一次性：作业必须一次性全部装入主存后才能运行。
驻留性：作业装入后通常一直驻留在主存，直到运行结束。

这两个限制会降低主存利用率：程序运行时往往只会在一段时间内集中访问少量代码和数据，暂时不用的部分不必长期占用主存。

虚拟存储器的核心思想是：基于局部性原理，只把当前需要的页面装入主存；暂时不用的页面留在外存；访问到不在主存的页面时，再由操作系统把它调入。

虚拟存储器

在用户看来，系统好像提供了一片比实际主存更大的内存；实际物理主存没有变，只是操作系统和硬件共同把主存与外存组织成了一个逻辑上的大地址空间。

虚拟存储器有三个特征：

特征	含义
多次性	作业不必一次性全部装入主存，可以分多次调入
对换性	作业运行过程中，页面可以在主存和外存之间换入、换出
虚拟性	从逻辑上扩充内存容量，使用户看到的容量大于实际主存容量

容量上限

虚拟存储器的最大容量受 CPU 地址结构限制，实际可用容量还受主存与外存容量限制：

$$
\text{虚拟存储实际容量} = \min(\text{CPU 寻址范围}, \text{主存容量} + \text{外存可用容量})
$$

例如 32 位按字节编址的系统，CPU 寻址范围最大是 $2^{32}B=4GB$。若主存为 512MB，外存可供虚拟存储使用 2GB，则实际容量不是 4GB，而是 2.5GB。

## 透明性

虚拟存储的透明性要分两层看。

对进程来说，虚拟存储是透明的：进程只使用虚拟地址，不需要知道某个页面现在在主存、在外存、还是刚被换出。

对硬件来说，虚拟存储并不透明：MMU 拆分页号和页内偏移，查 TLB 或页表，检查状态位和权限，命中时直接形成物理地址。

对操作系统来说，虚拟存储并不透明。OS 必须维护页表、外存地址、状态位、访问位、修改位；发生缺页时，OS 还要决定从哪里调入页面、分配哪个页框、是否置换、是否写回。

虚拟地址与物理地址

虚拟地址是进程发出的地址，也就是前面分页、分段中说的逻辑地址。它描述的是进程自己看到的地址空间。

物理地址是主存中的实际地址。CPU 执行访存指令时先产生虚拟地址，再由 MMU、页表、TLB 等地址变换机构把虚拟地址翻译成物理地址。

所以在虚拟存储语境下，可以把“逻辑地址”和“虚拟地址”近似看作同一个概念；强调程序视角时常说逻辑地址，强调虚拟存储和地址空间时常说虚拟地址。

# 请求分页

请求分页是在基本分页基础上实现虚拟存储的一种方式。它和基本分页的主要区别是：页面不必全部在主存中。

页表项需要记录页面是否已调入主存以及页面在外存的位置。请求页表项通常包含：

字段	作用
页号	标识逻辑页
页框号	页面已在主存时，指出所在页框
状态位 / 有效位	表示该页是否已调入主存
访问字段	记录访问情况，供置换算法参考
修改位	表示该页调入主存后是否被写过
外存地址	页面不在主存时，指出从外存哪里调入

状态位是请求分页的关键：状态位为 1，说明页面在主存；状态位为 0，说明页面不在主存，访问该页会触发缺页故障。

一次访存的完整路径

CPU 一次访存会连续经过两类问题：

地址翻译：由虚拟地址能不能拿到物理地址？
数据访问：有了物理地址后，目标数据能不能从 Cache 直接取到？

完整流程如下：

CPU 执行取指或读写数据指令，发出虚拟地址。
MMU 用虚拟页号查 TLB。
1. 若 TLB 命中，直接得到页框号，与页内偏移拼接成物理地址。
2. 若 TLB 未命中，继续查页表。
  1. 若页表项状态位为 1，说明页面已在主存：取出页框号，必要时把页表项写入 TLB，再形成物理地址。
  2. 若页表项状态位为 0，说明页面不在主存：产生缺页故障，转入 OS 缺页处理；调页完成后重新执行原访存指令。
已经得到物理地址后，再查 Cache。
1. 若 Cache 命中，直接从 Cache 读出数据，或在 Cache 中完成写入。
2. 若 Cache 未命中，说明目标主存块不在 Cache 中；硬件访问主存，把相应主存块调入 Cache，再完成本次访问。

这三种“缺失”层次不同：

情况	缺的是什么	页面是否在主存	主要处理者	结果
TLB 未命中	页表项不在 TLB	不一定缺页	硬件为主	查页表；若页面在主存，就补 TLB
页面缺失	目标页不在主存	不在	OS 为主	缺页故障，调页，更新页表 / TLB，重试指令
Cache 未命中	目标主存块不在 Cache	已在主存	硬件为主	从主存取块装入 Cache

Note

TLB 命中意味着对应页面一定在主存。
若某页面被换出，OS 必须使对应 TLB 项失效，否则硬件可能拿着过期页框号访问错误位置。

## 缺页故障

缺页故障是指 CPU 执行访存指令时，MMU 查页表发现目标页面尚未调入主存，于是产生的可恢复异常。处理程序把缺失页面调入主存并更新页表后，通常返回原指令重新执行。

一次缺页处理过程：

CPU 执行访存指令，产生虚拟地址。
MMU 查 TLB 或请求页表。
1. 若页表项状态位为 0，硬件产生缺页故障，转入 OS 缺页处理程序。
  1. OS 保存现场，将缺页进程阻塞。
  2. OS 判断访问是否合法；若非法，终止进程；若合法，继续调页。
  3. 若有空闲页框，直接分配；若没有空闲页框，按页面置换算法选择换出页。
    1. 若被换出页修改位为 1，写回外存；修改位为 0，则不必写回。
  4. 根据页表项中的外存地址，把缺失页面从外存读入页框。
  5. 修改页表项：填入页框号，状态位置为 1，更新访问字段、修改位等。
  6. 必要时把页表项复制到 TLB。
  7. 唤醒进程，重新执行引发缺页的原指令。

Note

一条指令可能产生多次缺页故障，例如把地址 A 的数据复制到地址 B，而 A 和 B 分属不同页面。

Warning

缺页故障处理开销远大于一次普通访存，所以虚拟存储依赖局部性；如果频繁缺页，性能会急剧下降。

# 页面调入

何时调入

策略	做法	特点
预调页	预测即将访问的页面，提前调入若干页	可利用空间局部性，但预测不准会浪费 I/O
请求调页	访问缺失页面时才调入	调入的一定会被访问，但每次缺页都要付出 I/O 开销

预调页常用于进程首次调入或程序员能指出初始工作区域的场景；请求调页是请求分页的核心，运行时缺哪页调哪页。

从何处调入

外存通常可以分为文件区和对换区。

区域	用途	分配方式	特点
文件区	存放可执行文件、共享库、普通文件映像	离散分配	更重视空间利用率，速度相对慢
对换区	存放被换出的页面或进程数据	连续分配	更重视换入换出速度，通常采用更适合顺序 I/O 的管理方式

页面来源有三种典型情况：

情况	调入与调出方式
对换区空间充足	运行前可把进程相关页面复制到对换区；之后换入、换出主要在主存和对换区之间进行
对换区空间不足	不会被修改的页面可从文件区调入，换出时不写回；可能被修改的页面换出到对换区，再次需要时从对换区调入
UNIX 方式	未使用过的页面从文件区首次调入；被使用过并换出的页面写回对换区，再次调入时从对换区读取

页框分配算法

页面调入主存前，OS 还要决定进程能分到多少页框。常见页框分配算法有三种：

算法	做法	特点
平均分配算法	把可分配页框平均分给各进程	简单，但没有考虑进程大小差异
按比例分配算法	按进程大小比例分配页框	大进程得到更多页框，小进程得到较少页框
优先权分配算法	按进程优先级分配页框	高优先级进程可获得更多页框，低优先级进程可能被压缩

页框分配必须先满足[[#最小页框数|最小页框数]]。剩余页框再按平均、比例或优先权分配。若某进程低于最小页框数，即使页面置换算法再好，也可能无法稳定执行指令。

如何调入页面

页面调入要完成页框选择、磁盘 I/O、页表项修改和现场恢复。

根据缺页页表项中的外存地址，确定页面来源：文件区或对换区。
检查主存是否有空闲页框。
1. 若有空闲页框，直接分配给缺失页面。
2. 若没有空闲页框，根据页面置换算法选择一个牺牲页。
  1. 检查牺牲页的修改位：若修改位为 1，先把该页写回外存；若修改位为 0，不必写回。
  2. 将牺牲页对应页表项的状态位置为 0，清除或保留其页框号，并确保相关 TLB 项失效。
  3. 启动磁盘 I/O，把缺失页面读入选定页框。
更新缺失页的页表项：填写页框号，状态位置为 1，访问字段按置换算法需要设置，修改位通常置为 0。
必要时把新的页表项写入 TLB。
唤醒缺页进程，恢复现场，重新执行引发缺页的指令。

Example

页号 5 原本不在主存，页表项为：页框号空、状态位 0、访问字段 0、修改位 0、外存地址 x。缺页处理把它调入 12 号页框后，页表项要变为：页框号 12、状态位 1、访问字段按规则更新、修改位 0、外存地址仍保留 x。

# 页面分配

最小页框数

进程运行时必须有一个最小页框数。如果分配页框数低于这个下限，进程可能连一条指令都无法顺利执行，陷入“刚调入一个页面，又因为缺另一个页面把它换出”的局面。

最小页框数由指令集结构决定，取决于一条指令在执行期间最多需要同时访问多少个不同页面，即寻址方式：

指令本身所在页面至少需要驻留。
取操作数可能需要额外页面。
写回结果也可能落在另一个页面。
若指令或操作数跨页，还可能需要更多页框。

例如一条 copy A to B 指令至少可能同时涉及指令页、源操作数页、目标操作数页。若页框数太少，调入源页面时可能换出目标页面，调入目标页面时又可能换出源页面，指令无法稳定向前推进。

Note

最小页框数不是越大越好，而是“能正确推进执行”的下限；具体数值由机器指令格式、寻址方式、页面大小和是否允许跨页访问共同决定。

驻留集

请求分页要决定一个进程在主存中能占多少页框，这个集合称为驻留集。

驻留集太小，缺页率会很高；驻留集太大，会降低系统并发度。因此页面分配策略的本质是控制每个进程的驻留集大小和变化方式。

内存分配策略

这里要分清两个维度：

维度	问题	选择
分配策略	一个进程的驻留集大小是否固定	固定分配、可变分配
置换范围	缺页时能从哪里选页换出	局部置换、全局置换

固定分配指 OS 在进程运行前或装入时给它分配固定数量的页框，进程运行期间驻留集大小不变。它的难点在于初始数量很难刚好合适：太少会频繁缺页，太多会降低并发度。

可变分配指进程运行期间驻留集大小可以调整。OS 可以根据缺页率、进程优先级、系统空闲页框数量等因素，为进程增加或回收页框。

局部置换指某进程发生缺页时，只能从该进程自己的驻留集中选页换出。它不会直接抢走其他进程的页框，但如果该进程页框本来就少，可能长期高缺页率。

全局置换指某进程发生缺页时，可以从系统范围内获得页框：可以使用空闲页框，也可以换出其他进程的未锁定页面。它更灵活，但会影响其他进程的驻留集大小。

分配策略和置换范围有以下三种可行组合：

组合	说明
固定分配 + 局部置换	驻留集大小固定，缺页时只能在本进程内部换页
可变分配 + 局部置换	平时在本进程内部换页，OS 可根据缺页率调整驻留集大小
可变分配 + 全局置换	缺页时可从系统范围获取页框，进程页框数会变化

“固定分配 + 全局置换”为什么不可行？

全局置换可能让进程页框数变化，和固定分配矛盾

三种可行组合的差异：

策略	过程	主要问题
固定分配局部置换	每个进程页框数固定；缺页时从本进程页面中换出一页	初始页框数很难设得刚好
可变分配全局置换	缺页时优先给进程新页框；无空闲页框时可从全局选择未锁定页换出	一个进程频繁缺页可能挤压其他进程
可变分配局部置换	缺页时先在本进程内换页；OS 根据缺页率增减该进程页框数	需要持续监控缺页情况

固定分配局部置换中，OS 在进程开始运行前就确定页框数。运行中一旦缺页，只能在该进程自己的驻留集中选一页换出，所以它不会抢占其他进程的页框，但对初始分配数量很敏感。

可变分配全局置换中，每个进程页框数不固定；进程缺页时通常获得一个新页框；如果没有空闲页框，系统可从全局选择一个未锁定页面换出。它能快速照顾缺页进程，但可能让其他进程的驻留集变小。

可变分配局部置换中，每个进程页框数不固定；缺页时仍优先在本进程内部置换；OS 根据缺页率调整驻留集。缺页率过高，说明页框可能不足，可以增加页框；缺页率很低，说明分配可能偏多，可以回收部分页框。

页面置换

详见Page-Replacement-Algorithms

抖动与工作集

抖动也叫颠簸，指刚换出的页面很快又要换入，刚换入的页面很快又要换出，系统大量时间耗在页面调度上，真正执行进程的时间很少。

抖动的直接原因通常是：进程频繁访问的页面数大于分配给它的页框数。

工作集是某段时间窗口内进程实际访问过的页面集合，用于估计进程近期真正需要的页面范围。

驻留集大小不应小于工作集大小，否则进程会频繁缺页。但驻留集太大又会降低并发度。

页框回收

页框回收不一定要立刻把被换出的页面彻底覆盖。为了降低页面换入、换出的开销，系统可以使用页面缓冲算法。

页面缓冲算法的思想是：被置换出的页面先进入缓冲队列，页框暂时作为可用页框管理；如果该页很快又被访问，且页框内容还没有被新页面覆盖，就可以直接把它恢复回来，避免一次外存读入。

常见做法是维护两个队列：

队列	保存对象	处理方式
空闲页框队列	可直接分配的页框，可能仍保留旧页面内容	缺页时优先从这里取页框
修改页队列	被换出且修改位为 1 的页面	暂不立即写回，可集中批量写回外存

页面被换出时：

若页面未修改，外存中已有正确副本，不必写回；页框加入空闲页框队列。
若页面已修改，页框加入修改页队列，等待写回外存。
页表项状态位置为 0，使相关 TLB 项失效。
若该页在页框被复用前又被访问，可以直接从缓冲队列恢复映射。
若页框被分配给新页面，旧页面内容被覆盖；之后再访问旧页面，就必须从外存重新调入。

页面缓冲算法的效果有两点：

对刚被换出又马上访问的页面，可能避免一次外存读入。
对修改页，可以延迟并批量写回，减少零散 I/O。

Note

页面缓冲算法不改变“缺页时要选页换出”的事实。它优化的是换出后的页框回收和再次访问路径：被换出的页不是立刻彻底消失，而是在缓冲队列中保留一段时间。

# 内存映射文件