3.4 虚拟内存管理

局部性原理与虚拟内存的特征；请求分页的页表项、缺页中断与地址变换；页框分配策略与调入策略；OPT、FIFO、LRU、CLOCK 与改进型 CLOCK 页面置换算法，Belady 异常；抖动与工作集；内存映射文件；影响虚拟存储器性能的因素。

虚拟内存的基本概念

前面介绍的存储管理方式都要求一个作业全部装入内存后才能运行（一次性），而且作业装入后一直驻留在内存中直到运行结束（驻留性）。这使得大作业无法运行，也限制了能同时运行的作业数。

局部性原理说明，程序在一段时间内只访问很小的一部分代码和数据：

• 时间局部性：如果某条指令（或数据）被访问过，不久以后它很可能再次被访问，典型原因是程序中存在大量循环；
• 空间局部性：一旦程序访问了某个存储单元，不久以后其附近的存储单元也很可能被访问，因为指令通常顺序执行、数据一般以数组等形式连续存放。

因此程序不必全部装入内存：装入程序时只装入一部分，其余部分留在外存；执行过程中访问的信息不在内存时，由操作系统把它调入内存；内存空间不足时，把暂时不用的内容换出到外存。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

• 虚拟内存的特征：多次性（作业分多次调入内存）、对换性（作业运行时可以换入、换出）、虚拟性（从逻辑上扩充了内存容量）；
• 虚拟内存的实际容量 ≤ 内存容量 + 外存容量，最大容量 ≤ 计算机地址位数能表示的范围；
• 虚拟内存的实现需要建立在离散分配的基础上，有请求分页、请求分段、请求段页式三种方式，都需要一定容量的内存和外存、页表（段表）机制、中断机构和地址变换机构的支持。

请求分页管理

请求分页在基本分页的基础上，增加了请求调页和页面置换功能。

页表项

• 状态位 P（有效位）：该页是否已调入内存，供程序访问时参考；
• 访问字段 A：该页在一段时间内被访问的次数，或最近多久未被访问，供置换算法选择换出页面时参考；
• 修改位 M：该页调入内存后是否被修改过，未修改的页换出时不必写回外存；
• 外存地址：该页在外存上的地址，供调入该页时参考。

缺页中断与地址变换

访问的页面不在内存时，产生一个缺页中断，请求操作系统把所缺的页调入内存。此时缺页的进程阻塞；若内存中有空闲块，则分配一个块，把页调入并修改页表；若没有空闲块，则按置换算法淘汰某页（若被淘汰页修改过，还要先写回外存）。调页完成后，进程被唤醒，重新执行产生缺页的那条指令。

缺页中断与一般中断相比：它是在指令执行期间（而不是一条指令执行完后）产生和处理的，属于内中断（故障）；一条指令在执行期间可能产生多次缺页中断（如指令本身和它的操作数都跨页）。

地址变换时，先查快表（TLB）：命中则直接得到物理块号；未命中则查内存中的页表，若页在内存中则得到物理块号并把该表项写入快表；若页不在内存，则产生缺页中断。

页框分配

驻留集与分配策略

给一个进程分配的物理页框的集合称为该进程的驻留集。驻留集越小，驻留在内存中的进程越多，但每个进程的缺页率会升高；驻留集超过一定大小后，再增加页框对缺页率的改善并不明显。

• 固定分配局部置换：为每个进程分配一定数目的物理块，在运行期间不变；缺页时只能从该进程在内存中的页面中选出一页换出。难以确定应为每个进程分配多少块；
• 可变分配全局置换：先为每个进程分配一定数目的物理块，操作系统保留若干空闲块；进程缺页时从空闲块中分配一块，没有空闲块时可以选择任何进程的一页换出，这样被选中进程的物理块会减少，缺页率会增加；
• 可变分配局部置换：缺页时只允许从该进程自己的页面中选一页换出；如果进程频繁缺页，系统再为它分配若干物理块，反之则减少分配给它的物理块。

（固定分配全局置换不存在：全局置换意味着一个进程的块数会改变。）

调入策略与调入来源

• 何时调入：预调页策略——根据局部性原理，一次调入若干相邻的页，常用于进程首次调入；请求调页策略——进程运行中需要访问的页不在内存时才调入，每次只调入一页，I/O 开销较大；
• 从何处调入：外存分为存放文件的文件区和存放对换页面的对换区，对换区采用连续分配，I/O 速度比文件区快。系统拥有足够的对换区空间时，可以全部从对换区调入（进程运行前把与进程有关的文件从文件区复制到对换区）；否则，不会被修改的文件直接从文件区调入，可能被修改的部分换出时写到对换区，以后再从对换区调入。UNIX 方式：与进程有关的文件放在文件区，未运行过的页面从文件区调入，曾经运行过又被换出的页面从对换区调入。

页面置换算法

选择调出页面的算法称为页面置换算法，好的算法应有较低的页面更换频率。

Belady 异常：当分配给进程的物理块数增加时，缺页次数不减反增。只有 FIFO 算法可能出现 Belady 异常，LRU 和 OPT 不会（它们属于「栈式算法」）。

抖动与工作集

抖动（颠簸）是指刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出，频繁的页面调度使进程把大部分时间都花在换页上。产生抖动的主要原因是：系统中同时运行的进程太多，分配给每个进程的物理块太少，不能满足进程正常运行的基本要求。

工作集是指在某段时间间隔内进程要访问的页面集合。用一个大小为 Δ 的窗口来确定：在时刻 t，工作集 W(t, Δ) 就是最近 Δ 次访问所涉及的页面集合。例如访问序列为 … 2 6 1 5 7 7 7 7 5 1 时，若 Δ = 5，则在最后时刻的工作集为 {1, 5, 7}。

工作集反映了进程在接下来一段时间内很可能频繁访问的页面集合，因此驻留集的大小不应小于工作集的大小，否则进程在运行过程中将频繁缺页。操作系统可以跟踪每个进程的工作集，并为它分配大于工作集的物理块；若还有空闲块，则可以再调入一个进程；若所有进程的工作集之和超过了可用物理块数，就暂停一个进程，把它的页面调出，从而防止抖动。

内存映射文件

内存映射文件是操作系统向应用程序提供的一个系统调用，它允许进程把一个文件的内容映射到自己虚拟地址空间的一部分。此后进程像访问内存一样访问文件：访问到尚未调入的部分时，产生缺页，由操作系统从文件中把对应的页读入；进程关闭文件时，操作系统把修改过的页写回文件。

多个进程可以把同一个文件映射到各自的虚拟地址空间中（映射到同一组物理页框），从而实现共享内存；进程对这些页的修改，其他进程立即可见。

影响虚拟存储器性能的因素

缺页率是影响虚拟存储器性能的主要因素，而缺页率又受以下因素影响：

• 页面大小：页面较大则缺页率较低，但页内碎片增加、每次换页的开销变大；页面较小可以减少碎片，但页表变长，缺页可能增多；
• 分配给进程的物理块数：块数越多，缺页率越低，但超过一定数目后效果不明显；
• 页面置换算法：好的算法（如 LRU）可以显著降低缺页率；
• 程序的编写方法：程序的局部性越好，缺页率越低。例如数组按行存放时，按行访问比按列访问缺页少得多。

写回外存的频率也影响性能：换出已修改的页面要写回磁盘，可以先把它们挂在已修改换出页面的链表上，积累到一定数目后再成批写回，减少 I/O 次数。

即时练习