虚拟内存管理

页框分配

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

驻留集

驻留集 是指当前在物理内存中实际驻留的进程页面的集合。驻留集大小 是表示这个集合中页面数量的指标，通常以页框（或页面框）的数量来度量。这个指标决定了进程可以直接访问的物理内存页面数量，以及在物理内存中保持的页面的范围。

驻留集大小 的合理设置对系统性能至关重要。若 驻留集大小 太小，进程可能经常发生页面置换，导致频繁的 缺页中断，从而降低性能。若 驻留集大小 太大，可能会浪费物理内存资源，并导致其他进程无法获得足够的内存。

抖动

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

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

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

内存分配策略

内存分配策略 包含 固定分配 和 可变分配 两种方式：

• 固定分配
  • 内存被划分为固定大小的区块。
  • 每个程序或进程被分配一个或多个这样的区块，不管它们实际上需要多少内存。
• 可变分配
  • 内存不是被划分为固定大小的区块，而是根据每个程序的需求动态分配。
  • 当一个程序请求内存时，操作系统查看可用内存并分配足够的连续空间给该程序，这个空间刚好满足其需求。

固定分配 中可以分为两种方式，一种是将内存分为若干大小相同的分区，另一种是将内存分为大小不同的分区。

可变分配 也包含两种分配方式，一种就是将 内存分为若干页面，然后根据进程的需求为其动态地分配内存页面。另一种思路与 动态分区分配 一致，在一块连续的内存上动态地申请连续的某个长度的存储空间。

内存置换策略

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

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

页置换算法

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

FIFO

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

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

在某些页面置换算法（特别是 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，则置换页面如下：

内存置换次数为 4，缺页率为 4/12 = 1/3

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 算法的例子：

加入内存系统中有 3 个页框，页面引用序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，则置换页面如下：

内存置换次数为 6，缺页率为 6/12 = 1/2

Clock

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

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

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

简单 Clock

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

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

• 0 表示该页面 未分配 或者 已分配但可以被替换
• 1 表示该页面 已分配 但 不可被替换

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

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

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

Clock 替换策略 如下：

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

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

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

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

简单 Clock 算法的例子：

加入内存系统中有 3 个页框，页面引用序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 2，内存页框初始状态为 -1:0, -1:0, -1:0（粗体表示时钟指针指向的位置，引号前面的 -1 表示当前页面为空，引号后面的表示引用位的值）

置换页面过程如下：

内存置换次数为 5，缺页率为 5/12

改进型 Clock

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

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

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

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

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

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

• 算法首先尝试寻找 (0, 0) 类型的页面，如果找到，则立即替换。
• 如果第一轮扫描没有找到 (0, 0) 类型的页面，则进行第二轮扫描，寻找 (0, 1) 类型的页面。
• 如果前两轮都没有找到，那么会将所有访问位设置为 0 然后重复前两轮扫描。

LFU

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

基本步骤：

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

内存映射文件

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

映射过程 如下：

• 进程调用 mmap，指定要映射的文件、偏移量、长度以及访问权限（如读、写）。
• 操作系统在进程的虚拟地址空间中分配一段连续的虚拟内存，并建立虚拟地址与文件内容的映射关系。
• 当进程访问这部分虚拟地址时，操作系统通过分页机制将文件内容加载到物理内存，并同步更新文件内容到磁盘。

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

常规文件操作（如使用 read 或 write 系统调用）依赖页缓存机制来提高效率并保护磁盘，但这引入了 两次数据拷贝 的过程：

1. 从磁盘到页缓存：当进程发起读文件请求时，内核通过文件的 inode 查找文件内容。如果文件页不在页缓存中，内核会从磁盘将数据拷贝到内核空间的页缓存中。
2. 从页缓存到用户主存：页缓存位于内核空间，用户进程无法直接访问。因此，内核需要将页缓存中的数据再次拷贝到用户进程的内存空间（用户主存）。写操作类似，用户进程的写缓冲区先拷贝到内核空间的页缓存，再延迟写回磁盘。

这两次数据拷贝（磁盘 → 页缓存 → 用户主存）增加了系统开销，尤其是在处理大文件或高频 I/O 操作时，效率较低。

mmap 通过将文件直接映射到进程的虚拟地址空间，消除了从页缓存到用户主存的拷贝步骤，仅需一次数据拷贝：

• 从磁盘到用户主存：当进程访问映射的虚拟地址时，操作系统通过分页机制按需从磁盘加载文件内容到物理内存，并将其映射到进程的虚拟地址空间。进程可以直接操作这部分内存，无需额外的内核到用户空间的拷贝。
• 写操作同步：对于可写映射，进程对映射内存的修改会由操作系统自动同步到磁盘（或通过 msync 显式同步），无需用户态到内核态的缓冲区拷贝。

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

• 减少数据拷贝：mmap 只需要从磁盘到物理内存的一次拷贝，消除了页缓存到用户主存的额外拷贝，降低了 CPU 和内存开销。
• 高效内存访问：文件内容直接映射到虚拟地址空间，进程像操作内存一样读写文件，简化了编程模型并提高了性能。
• 延迟加载：mmap 支持按需加载，只有实际访问的文件页面才会被加载到内存，优化了内存使用效率。
• 支持进程间通信：多个进程可以映射同一文件，共享内存区域，实现高效的数据共享。