虚拟内存管理

页框分配

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

驻留集大小

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

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

抖动

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

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

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

内存分配策略

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

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

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

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

内存置换策略

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

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

全局置换策略是指在选择要换出的页面时，可以在整个系统的内存页面范围内进行选择。 也就是说，一个进程的缺页可能会导致其他进程的内存页面被换出。

页置换算法

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

FIFO

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

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 页面在三分钟前被使用过。 那么在这种情况下，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是一种内存映射文件的方法，即将一个文件映射到进程的地址空间， 实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对映关系。

• mmap 允许将文件映射到进程的虚拟地址空间，使文件的内容可以像内存一样直接访问，而不需要显式的读取或写入文件。
• 这意味着当你修改映射到内存中的文件内容时，实际上是在修改物理存储设备上的文件。因此，内存映射文件对于高性能 I/O 操作非常有用，因为可以避免显式的 I/O 操作。

以下内容为扩展内容，了解即可，基本不会考察。

常规文件操作需要从磁盘到页缓存再到用户主存的两次数据拷贝。而mmap操控文件，只需要从磁盘到用户主存的一次数据拷贝过程。

若要理解上述差别，首先需要了解常规文件的系统操作：

1. 进程发起读文件请求。
2. 内核通过查找进程文件符表，从而找到文件的 inode。
3. 在 inode 中查找要请求的文件页是否已经缓存在页缓存中。如果存在，则直接返回这片文件页的内容。
4. 如果不存在，则通过inode定位到文件磁盘地址，将数据从磁盘复制到页缓存。之后再次发起读页面过程，进而将页缓存中的数据发给用户进程。

总结来说，常规文件操作为了提高读写效率和保护磁盘，使用了页缓存机制。这样造成读文件时需要先将文件页从磁盘拷贝到页缓存中，由于页缓存处在内核空间，不能被用户进程直接寻址，所以还需要将页缓存中数据页再次拷贝到内存对应的用户空间中。这样，通过了两次数据拷贝过程，才能完成进程对文件内容的获取任务。写操作也是一样，待写入的buffer在内核空间不能直接访问，必须要先拷贝至内核空间对应的主存，再写回磁盘中（延迟写回），也是需要两次数据拷贝。

而使用mmap操作文件中，创建新的虚拟内存区域和建立文件磁盘地址和虚拟内存区域映射这两步，没有任何文件拷贝操作。而之后访问数据时发现内存中并无数据而发起的缺页异常过程，可以通过已经建立好的映射关系，只使用一次数据拷贝，就从磁盘中将数据传入内存的用户空间中，供进程使用。