虚拟内存管理

真题练习

页式虚拟存储的细节都在 组成原理章节，对于本节，重点掌握 页框分配的几个概念 以及几种 页面置换算法 的细节。

页框分配

在 虚拟内存管理 中，页框分配 是操作系统为进程分配物理内存（页框）的过程。 它直接影响着系统的性能，因为分配的页框数量会影响进程的 缺页率 和系统的整体吞吐量。

驻留集

驻留集（Resident Set） 是指某个进程在执行过程中，当前实际存放在物理内存中的页面集合。换句话说，它反映了该进程在某一时刻真正占用并可直接访问的物理页。由于进程的地址空间往往远大于物理内存，操作系统通过 虚拟存储管理 来实现“用部分物理内存支撑完整逻辑地址空间”，而驻留集正是这个机制下进程能够被立即访问的 物理页子集。

驻留集大小（Resident Set Size, RSS） 则是度量该集合规模的指标，通常以页框（page frame）的数量来表示。它决定了进程可直接利用的物理内存范围，从而影响其运行效率。

合理设置驻留集大小对于系统性能至关重要：

• 过小：如果驻留集太小，进程运行时所需的工作集页面无法完全驻留，会频繁发生页面置换，导致 缺页中断 激增，系统性能显著下降。
• 过大：如果驻留集太大，则会占用过多物理内存，可能挤压其他进程的生存空间，降低系统整体吞吐率。

因此，操作系统往往需要通过 页面置换算法 或 局部/全局分配策略 来动态调整驻留集大小，以在单个进程性能与系统整体资源利用之间取得平衡。

抖动

抖动（Thrashing）是指操作系统中频繁发生的页面置换现象，即刚被换出的页面马上又要被换入内存，刚被换入的页面马上又要被换出外存，导致系统大部分时间都用于页面的换入换出，而真正用于进程运行的时间很少。

当系统为一个进程分配的物理内存不足以满足其 工作集（当前活跃的页面集合）的需求时，就会频繁发生 缺页中断。操作系统必须不停地从磁盘读取所需的页面到内存中，同时写出其他页面以释放空间。因为磁盘访问速度远慢于内存访问，这种频繁的磁盘 I/O 活动显著减慢了系统性能。

抖动 的直接后果是 CPU 使用率 下降，因为 CPU 在等待必要的页面从磁盘加载时处于空闲状态。系统资源被过多地用于管理内存和磁盘之间的数据交换，而非执行用户程序。抖动 严重时，系统的 吞吐量 下降，响应时间增加，用户和应用程序都会感受到系统变得迟钝和无响应。

内存分配策略

这里的 固定分配 与 可变分配 描述的是“一个进程拥有的页框数是否会在运行期间改变”，不是固定分区/动态分区，也不是页框本身大小是否相同。请求分页系统中的页和页框大小始终相等。

分配策略	页框所有权	缺页时的变化	典型边界
固定分配	进程运行前获得固定数量的页框	只能在已分配页框内置换，页框总数不变	只能与局部置换组合
可变分配	进程拥有的页框数可随缺页率或系统负载调整	可增加或减少驻留集	可与局部置换或全局置换组合

内存置换策略

当我们谈论 内存置换策略时，一般都是建立在 页式虚拟存储管理 基础之上的。在 连续分配（分区管理） 中是不存在“页面置换”概念的，在 段式存储管理 中可以有段置换，但考研语境通常默认讨论页式系统。

内存置换策略 分为 局部置换 和 全局置换 两种。

• 局部置换 策略是指在选择要换出的页面时，仅限于该进程自身所拥有的内存页面范围内进行选择。也就是说，一个进程的 缺页 不会影响到其他进程的内存页面。
• 全局置换 策略是指在选择要换出的页面时，可以在整个系统的内存页面范围内进行选择。也就是说，一个进程的 缺页 可能会导致其他进程的内存页面被换出。

注意

内存分配和置换策略的组合

在系统实现时，可以选择一种 内存分配策略 和 内存置换策略 进行组合。

需要注意的是，不存在 固定分配全局置换 这种组合。因为 固定分配 表示进程所占用的内存空间是恒定的，而 全局置换 表示进程可以侵占其他进程的内存空间，这一特性与 固定分配 的语义相违背，所以不存在这种组合。

页置换算法

在操作系统中，进程运行时，如果它要访问的页面不在内存中，就会产生 缺页中断。这时，操作系统需要从磁盘中将该页面调入内存。但如果此时内存已满，操作系统就需要选择一个页面将其移出内存，以便为新页面腾出空间。这个选择要移出哪个页面的算法，就叫做 页面置换算法。

FIFO

FIFO（First-In-First-Out）是最简单的页面置换算法。它总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面。

FIFO 的实现方法是把调入内存的页面按先后顺序放入队列中，当需要置换页面时，选择队头的页面即可。

Belady 异常

在某些页面置换算法（特别是 FIFO，先入先出算法）中，增加页面的数量反而导致页面错误（page fault）次数增加，这种情况违背了直觉，因为通常认为更多的内存框架应该减少页面错误，这种异常情况叫做 Belady 异常。

举个实际例子，假设页面访问序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。

• 使用 3 个页面框架，FIFO 算法可能产生 9 次页面错误。
• 使用 4 个页面框架，FIFO 算法可能产生 10 次页面错误。 这种页面错误次数随着框架增加而增加的现象就是 Belady 异常。

所以这也是 FIFO 算法的缺点，使用其他算法可以解决这个问题。

OPT

OPT（Optimal）页面置换算法，也称为最佳页面置换算法，是一种理论算法，其目标是在给定页框数和引用序列下使缺页次数最少。

OPT 假设能够预知未来的页面访问序列。发生缺页且页框已满时，它淘汰 从当前时刻向后、下一次访问距离最远 的页面；以后不再访问的页面可优先淘汰。

但这在实际情况下是不可能的，因而 OPT 算法通常用于理论研究和性能评估，以作为其他页面置换算法的性能上限的比较基准。

举个 实际例子 来说明一下 OPT 页面置换算法的运行过程：

假如系统中有 3 个页框，页面引用序列为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，则轨迹如下：

当前引用	引用后内存状态	淘汰页	命中/缺页
7	7	—	缺页
0	7, 0	—	缺页
1	7, 0, 1	—	缺页
2	2, 0, 1	7	缺页
0	2, 0, 1	—	命中
3	2, 0, 3	1	缺页
0	2, 0, 3	—	命中
4	2, 4, 3	0	缺页
2	2, 4, 3	—	命中
3	2, 4, 3	—	命中
0	2, 0, 3	4	缺页
2	2, 0, 3	—	命中

装满 3 个空页框后发生 4 次页面置换，整个引用串发生 7 次缺页，所以缺页率为

LRU

LRU（Least Recently Used）基于最近的页面访问历史来决定哪个页面应该被置换出内存。

LRU 算法是基于时间局部性思想：如果一个页面在最近被使用的话，那么这个页面在将来很可能被再次使用。 所以 LRU 算法会选择 最近一直没有被使用的页面 进行替换。

如果内存中包含 3 个页面，A 页面在 1 分钟前被使用过，B 页面在 2 分钟前被使用过，C 页面在 3 分钟前被使用过。 那么在这种情况下，LRU 算法会优先替换 C 页面，因为该页面上次使用的时间距离现在最远。

我们可以使用一个队列来保存内存中的页面，最近被使用过 的页面放在 队列尾部，表示这些页面不会优先被替换。最近没使用过 的页面会放在 队列头部，表示这些页面会优先被替换。基于这种思路，LRU 算法可以用如下过程进行描述：

假设内存中 Mem 最多可以容纳 N 个页面（将其看成一个长度最大为 N 的队列），当访问一个页面 P 时：

• 如果 P 在队列中出现
  • 将 P 移动到队列末尾
• 如果 P 不在队列中
  • 如果队列没有满的话，将 P 加入队列末尾
  • 如果队列满的话，将队列头部的页面淘汰，并且将 P 加入队列末尾

举个例子，在下图中，当进程访问 C 页面时，发现 C 页面出现在其驻留集中，所以需要将 C 移动到队列尾部，这样刚刚访问过的 C 页面的淘汰优先级就会降到最低。

LRU 的 执行流程 可以通过以下流程图理解：

---

LRU 算法的例子：

假如系统中有 3 个页框，页面引用序列仍为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2。下表中的内存状态按“左侧最久未使用、右侧最近使用”排列：

当前引用	引用后内存状态	淘汰页	命中/缺页
7	7	—	缺页
0	7, 0	—	缺页
1	7, 0, 1	—	缺页
2	0, 1, 2	7	缺页
0	1, 2, 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	缺页
2	3, 0, 2	—	命中

装满 3 个空页框后发生 6 次页面置换，整个引用串发生 9 次缺页，所以缺页率为

Clock

根据 LRU 代码实现 可知，用代码实现一个高效的 LRU 算法需要用到一个散列表和一个基于链表的队列，这从软件层面实现不算特别复杂，但若是要用硬件实现相应的逻辑则不大容易。

Clock 算法的提出是为了解决 LRU 算法在硬件实现上的复杂性，该算法流程相比 LRU 更加简单，可以更高效地使用硬件电路进行实现。

此外，Clock 算法的目的与 LRU 算法类似：保证最近刚访问过的页面可以在将来尽量晚被淘汰。

简单 Clock

CLOCK 算法的核心思想是使用一个类似时钟的数据结构，以跟踪每个页面的访问状态。

页面的访问状态用一个比特位（访问位）来表示：

• 0 表示该页最近未被访问，本轮扫描可作为淘汰候选；空页框也可视为可直接使用。
• 1 表示该页最近被访问，扫描到它时先把引用位清为 0，并给予一次“第二次机会”；它不是永久不可替换。

初始情况下进程的所有页面都未被分配，所有页面的访问位都为 0。

当一个新页面被添加时，时钟中的指针会不断旋转，直到找到一个访问位为 0 的页面将其替换。若当前页面的访问位为 1，则将其设置为 0，并移动到下一个位置进行查找。

---

在实际的 Clock 算法实现中，我们需要使用一种可以循环遍历的数据结构来模拟时钟结构。常用的选择是数组或循环链表。数组和链表中的每个元素都需要记录 访问位 和 页面号。

Clock 替换策略 如下：

假设内存最多可以容纳 N 个页面，我们可以用一个长度为 N 的数组来作为数据结构模拟时钟，当访问一个页面 P 时：

• 如果 P 在数组中 出现
  • 将 P 的引用标记为 1
• 如果 P 不在数组中，判断指针指向的页面访问位的数值
  • 如果访问位为 0，则替换该页面，并将指针移动到下一个位置
  • 如果访问位为 1，将该页面的访问位置为 0，将指针移动到下一个位置继续判定

注意

访问位 也叫做 引用位，注意一下这两种表述表示同一个含义。

Clock 替换策略可以通过以下流程图理解：

以下图为例，当首先访问页面 A、B、C 时，可以找到访问位为 0 的页面，直接替换页面；接下来访问页面 D，由于此时页面已满且访问位都为 1，指针会移动一个循环并且将所有页面的访问位都设置为 0，最后替换页面 A；然后访问页面 C 时，发现页面 C 已经存在，将对应的访问位设置为 1，指针位置不动；最后访问页面 E，发现指针指向的页面 B 访问位为 0，替换该页面，然后将指针后移一个位置。

那么 Clock 算法是如何保证最近访问过的页面尽量晚被淘汰呢？这主要包含两点：

1. 若访问的页面在时钟中存在，则将该页面的访问位设置为 1，这可以保证这个页面尽量晚被淘汰。
2. 若访问的是新页面（在时钟中不存在），找到一个可替换的页面，将新页面加载到这个位置，并将新页面的访问位设置为 1，这可以保证新页面尽量晚被淘汰。

---

简单 Clock 算法的例子：

假如系统中有 3 个页框，页面引用序列为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，内存页框初始状态为 -:0, -:0, -:0。粗体表示指针指向的位置，冒号前是页面号，冒号后是引用位。

置换页面过程如下：

当前引用	引用后页框状态	淘汰页	命中/缺页
7	7:1 -:0 -:0	—	缺页
0	7:1 0:1 -:0	—	缺页
1	7:1 0:1 1:1	—	缺页
2	2:1 0:0 1:0	7	缺页
0	2:1 0:1 1:0	—	命中
3	2:1 0:0 3:1	1	缺页
0	2:1 0:1 3:1	—	命中
4	4:1 0:0 3:0	2	缺页
2	4:1 2:1 3:0	0	缺页
3	4:1 2:1 3:1	—	命中
0	4:0 2:0 0:1	3	缺页
2	4:0 2:1 0:1	—	命中

装满 3 个空页框后发生 5 次页面置换，整个引用串发生 8 次缺页，所以缺页率为

改进型 Clock

简单 Clock 算法仅使用一个“访问位”来记录页面是否被访问过。当发生缺页中断时，算法从时钟指针的当前位置开始扫描内存中的页面，寻找第一个访问位为 0 的页面进行淘汰。这种算法虽然实现简单，但存在一个明显的缺陷：它没有考虑页面是否被 修改 过。

注意

如果一个页面被修改过，那么在淘汰它之前，需要将它写回磁盘，这会增加 I/O 操作的开销。而如果一个页面没有被修改过，那么可以直接淘汰它，无需进行额外的 I/O 操作。

为了解决 简单 Clock 算法的缺陷，改进型 Clock 算法引入了“修改位”的概念。每个页面都有两个状态位：

• 访问位（R）：表示页面是否被访问过。
• 修改位（M）：表示页面是否被修改过。

根据这两个状态位，页面可以按照 淘汰优先级 分为四种类型：

• (0, 0)：最近既没有被访问，也没有被修改。
• (0, 1)：最近没有被访问，但是被修改了。
• (1, 0)：最近被访问了，但是没有被修改。
• (1, 1)：最近被访问了，也被修改了。

当访问一个新页面时，改进型 Clock 算法的运行过程如下：

• 第一轮从指针处扫描 (0, 0)，不修改引用位；找到就立即替换。
• 若未找到，第二轮扫描 (0, 1)，并把沿途页面的访问位 $R$ 清为 0。
• 若仍未找到，第三、四轮按同样顺序再次查找 (0, 0) 与 (0, 1)；经过第二轮清零后必能选出受害页。淘汰优先级为 $(0,0)>(0,1)>(1,0)>(1,1)$。

LFU

LFU（Least Frequently Used）算法的核心思想是：当主存没有足够的空间加载新的页面时，系统会选择那些在 过去使用次数最少的页面 进行置换。

基本步骤：

1. 初始化：当一个页面首次加载到内存中时，为其分配一个计数器并将其设置为 1（表示该页面被访问过一次）。
2. 页面命中：如果要访问的页面已经在内存中，则增加该页面的访问计数。
3. 页面置换：当需要为新的页面腾出空间时（也就是说，当内存中的页面已满并且需要加载一个新页面时），系统会查看所有当前在内存中的页面的访问计数，选择访问次数最少的那个页面进行置换。

内存映射文件

内存映射文件 通过 mmap 系统调用，将文件的全部或部分内容 映射到进程的虚拟地址空间。映射后，文件内容可以像操作普通内存一样被直接读写，而无需通过显式的文件 I/O 操作（如 read 或 write）。操作系统负责将虚拟地址的访问转换为对底层物理存储设备（通常是磁盘）的操作。

映射过程 如下：

• 进程调用 mmap，指定要映射的文件、偏移量、长度以及访问权限（如读、写）。
• 操作系统在进程的虚拟地址空间中分配一段连续的虚拟内存，并建立虚拟地址与文件内容的映射关系。
• 当进程访问尚未驻留的映射页时，会触发缺页处理；内核把对应文件页装入页缓存所使用的物理页框，并让进程页表映射这些页框。写入是否回写原文件取决于映射类型：共享映射与私有映射的语义不同。

那么 mmap 相对于常规文件的优势在哪里呢？（了解）

常规文件操作（如使用 read 或 write 系统调用）通常依赖页缓存。以缓存未命中的 read 为例，数据路径包含一次设备到内存的传输，以及一次内存到内存的复制：

1. 存储设备 → 页缓存页框：内核根据文件元数据定位数据；文件页不在页缓存时，由设备控制器/DMA 等把数据传入承载页缓存的物理页框。这是 I/O 数据传输，不应简单理解成 CPU 执行的一次普通内存复制。
2. 页缓存 → 用户缓冲区：read 再把所需字节从页缓存复制到调用者提供的用户缓冲区。write 的方向相反，先把用户缓冲区内容复制进页缓存，再由内核按写回策略持久化。

其中可由 mmap 避免的主要是 页缓存与用户缓冲区之间的额外内存复制；设备到物理内存的数据传输仍然存在。

mmap 通过把承载文件页的页缓存页框直接映射到进程虚拟地址空间，消除了 read/write 路径中页缓存与单独用户缓冲区之间的那次复制：

• 按需映射页缓存页框：进程首次访问尚未驻留的文件页时，操作系统按需把数据从存储设备传入物理内存，再建立页表映射。进程随后直接访问该物理页框，无需再复制到另一份用户缓冲区。
• 共享映射（如 MAP_SHARED）：对映射页的修改会成为文件页缓存中的脏数据，可由内核延迟写回；需要明确完成同步时使用 msync，而持久性还要结合系统提供的同步语义判断。
• 私有映射（如 MAP_PRIVATE）：写入通常触发写时复制，修改只对当前进程私有，不会自动回写原文件。

通过以上讲解可知，mmap 具备以下优势：

• 减少数据拷贝：mmap 复用页缓存所占的物理页框，消除了页缓存到独立用户缓冲区的额外复制，因而可降低 CPU 和内存带宽开销。
• 高效内存访问：文件内容直接映射到虚拟地址空间，进程像操作内存一样读写文件，简化了编程模型并提高了性能。
• 延迟加载：mmap 支持按需加载，只有实际访问的文件页面才会被加载到内存，优化了内存使用效率。
• 支持进程间通信：多个进程使用共享映射映射同一文件区域时，可以通过这些共享物理页交换数据；仍需同步机制协调并发访问。