内存管理

• 1: 内存管理概念
• 2: 虚拟内存管理

# 内存管理

## 基础

- 基本概念：虚拟和逻辑地址，地址转换，内存共享，内存保护，内存分配和回收
- 连续分配管理方式
- 页式管理
- 段式管理
- 段页式管理

## 虚拟内存

- 基本概念
- 请求页式管理
- 页框分配
- 页置换算法
- 内存映射文件
- 虚拟存储器性能的影响因素和改进方法

1 - 内存管理概念

内存管理

内存管理（Memory Management） 是操作系统对 主存（内存） 进行统一管理的过程，其核心任务是：

为进程分配运行所需的内存空间，并负责回收、保护和管理这些空间。

例如，一个程序从磁盘启动时，操作系统需要：

1. 为程序分配一块内存空间；
2. 将程序代码、数据等装入内存；
3. 建立程序运行所需的地址映射关系；
4. 程序结束后回收所占用的内存空间。

随着多道程序设计的发展，内存管理不仅要解决 “有没有地方放” 的问题，还需要解决：

• 如何让多个进程同时共享有限的内存；
• 如何保证进程之间互不干扰（内存保护）；
• 如何提高内存利用率，减少碎片；
• 如何让程序认为自己拥有连续且足够大的内存空间（虚拟内存）。

因此，内存管理的核心就是：如何高效、安全地为进程组织和管理运行时所需的内存空间。

管理方式分类

操作系统中的各种内存管理方式并不是相互独立、一次性设计出来的，而是随着 多道程序设计、存储器容量和硬件地址转换能力的发展，逐步演进形成的。

其基本发展脉络可以概括为：

整个演进过程主要围绕两个目标展开：

1. 提高内存利用率

   • 允许更多程序同时驻留内存；
   • 减少内部碎片和外部碎片；
   • 允许进程离散地使用物理内存。

2. 增强内存管理能力

   • 实现进程隔离和内存保护；
   • 支持程序代码和数据的共享；
   • 保留程序本身的逻辑结构；
   • 支持虚拟内存。

从内存是否必须连续分配的角度看，内存管理方式大体可以分为两类：连续分配 和 离散分配。

所谓 连续分配，是指操作系统必须为一个进程分配一整段连续的内存区域。这类方式实现简单、地址转换开销较小，但灵活性不足。典型方式包括：

• 单一连续分配；
• 固定分区分配；
• 动态分区分配。

相比之下，离散分配 允许一个进程占用的物理内存空间彼此不连续，从而提高内存利用率和分配灵活性。典型方式包括：

• 页式管理；
• 段式管理；
• 段页式管理。

后文将沿着上述发展脉络，具体介绍各种内存管理方式的基本思想、解决的问题以及自身的局限性。

连续分配管理

连续分配（Contiguous Allocation） 是指：操作系统为每个进程分配一块连续的物理内存空间，进程在内存中的所有代码、数据、堆、栈等都必须存放在这一连续区域内。

由于整个进程必须连续存放，因此操作系统需要负责为进程寻找足够大的连续空闲区域，并维护这些空闲区域的分配和回收情况。

单一连续分配

在单一连续分配方式下，内存被划分为 系统区 和 用户区。

系统区供操作系统使用，用户区只装入一道用户程序，即整个用户内存空间都由该程序独占。系统区具体位于高地址还是低地址，取决于处理器和操作系统的设计。

单一连续分配是最早期、最简单的内存管理方式，适用于一次只运行一道用户程序的系统。

这种方式的优点包括：

• 实现简单；
• 管理开销小；
• 不会因为多个用户进程交替装入和退出而形成外部碎片。

其主要缺点包括：

• 一次只能运行一道用户程序；
• 当程序等待 I/O 时，CPU 可能长期空闲；
• 内存中未被当前程序使用的部分也无法供其他程序使用；
• CPU 利用率、内存利用率和系统吞吐量都很低。

单一连续分配的根本问题在于，它无法支持 多道程序并发驻留内存。

为了让一个程序等待 I/O 时，CPU 能够转而执行其他程序，操作系统开始在内存中同时保存多道程序，由此发展出了 固定分区分配。

固定分区分配

固定分区分配是最简单的一种 多道程序存储管理 方式。

它在系统启动或初始化时，将用户内存空间预先划分为若干个大小固定的分区，每个分区最多装入一道作业。

当存在空闲分区时，操作系统可以从外存的后备作业队列中选择一个能够放入该分区的作业，将其装入内存。这样，内存中便可以同时驻留多道程序。

固定分区可以采用两种划分方式：

• 分区大小相等：实现简单，但难以适应大小不同的程序；
• 分区大小不等：可以为不同大小的程序提供更多选择，但管理稍复杂。

为了方便管理，操作系统通常为固定分区建立一张 分区说明表。表中记录每个分区的：

• 起始地址；
• 分区大小；
• 当前状态；
• 已装入的作业或进程。

当有用户程序需要装入时，操作系统检索分区说明表，选择一个能够容纳该程序的空闲分区，并将其状态修改为“已分配”。

如果所有合适的分区都已被占用，即使内存中其他较小分区仍然空闲，该程序也无法装入。

固定分区分配首次实现了多道程序同时驻留内存，提高了 CPU 利用率和系统吞吐量，但它仍然存在明显问题：

1. 分区数量固定

   • 内存中能够同时驻留的进程数量受到分区数量限制。

2. 分区大小固定

   • 程序可能无法装入任何一个分区；
   • 较小的程序装入较大的分区时，会浪费分区内部的空间。

分区内部已经分配给某个进程、但没有被该进程实际使用的空间，称为 内部碎片。

固定分区的根本矛盾是：

分区大小是静态的，而程序所需内存大小是动态的。

为了解决固定分区尺寸僵化和内部碎片严重的问题，操作系统进一步提出了 动态分区分配。

动态分区分配

在 固定分区分配 中，用户内存被预先划分为若干大小固定的分区。

这种方式实现简单，但由于分区大小固定，而程序需要的内存大小各不相同，因此容易产生大量内部碎片。

为了解决固定分区“尺寸僵化、内存利用率低”的问题，操作系统引入了 动态分区分配。

动态分区分配的基本思想是：

不再预先划分固定大小的分区，而是在程序装入时，根据程序的实际需要，从空闲内存中动态划出一块大小合适的连续区域。

当进程请求内存时，操作系统从当前的空闲内存中划出一块连续区域分配给该进程。

当进程结束或主动释放内存时，该区域重新成为空闲内存，可供后续进程再次使用。

通过这种动态、按需分配的方式，内存可以从逻辑上划分为两类区域：

• 已分配区：正在被操作系统内核或进程占用的内存；
• 空闲区：当前尚未分配、可供后续进程使用的内存。

如下图所示，其中 内核内存（kernel memory） 和 进程内存（process memory） 属于已分配区域，其余部分为系统当前的空闲内存。

为了管理这些不断变化的空闲区域，操作系统通常维护一张 空闲分区表 或 空闲分区链表，用于记录每一块空闲内存的：

• 起始地址；
• 分区大小。

示意如下：

当进程申请内存时，操作系统会遍历空闲分区表，按照预定的 适应算法，例如首次适应、最佳适应等，从中选择一块满足需求的空闲区域，并完成内存分配。

不同适应算法选择空闲分区的方式不同，会影响查找效率、剩余空闲块的分布以及外部碎片的产生情况。

内存碎片

动态分区分配相比固定分区分配，可以根据进程的实际大小分配空间，因此大幅减少了固定分区中的内部碎片。

但是，它仍然无法避免 外部碎片。

下图以一个实例说明动态分区分配过程中内存碎片的产生过程：

由于各进程所需的内存大小不同，并且进程会不断装入和退出，因此内存中会逐渐形成许多彼此分散的小型空闲区域。

这些空闲区域虽然没有被任何进程占用，但由于它们彼此不连续，可能无法合并成一块足够大的连续空间。

所谓 外部碎片，是指位于已分配分区之间、不能满足当前连续内存申请的零散空闲空间。

例如，假设系统中存在三块空闲区域：

10 MB、20 MB、15 MB

此时空闲内存总量为 45 MB，但如果某个进程需要申请一块连续的 30 MB 内存，分配仍然会失败，因为不存在一块大小至少为 30 MB 的连续空闲区域。

因此，外部碎片的关键并不是空闲内存总量不足，而是：

空闲内存过于零散，不存在足够大的连续空间。

可以通过 紧凑（Compaction） 技术移动已分配分区，将零散的空闲空间合并为一块较大的连续区域。

但是，紧凑需要移动大量内存数据，并修改相关地址，执行开销很高，而且要求程序能够进行动态重定位，因此并不是一种理想的根本解决方案。

动态分区的根本局限是：每个进程仍然必须占据一块连续的物理内存。

为彻底摆脱连续物理分配的限制，操作系统后来引入了 离散分配管理，允许一个进程的数据分散存放在多个不连续的物理区域中。

适应算法

内存空间中的空闲区域可能大小不一，并且分布在不同位置，操作系统使用 空闲分区表 或 空闲分区链表 记录这些空闲区域。

当进程申请一块新的连续内存时，操作系统必须从现有空闲区域中选择一块进行分配。

动态分区常见的分配策略主要包含四种：

• 首次适应（First Fit）
• 临近适应（Next Fit）
• 最佳适应（Best Fit）
• 最坏适应（Worst Fit）

• First Fit （首次适应）：从空闲分区表或空闲链表的开头开始查找，找到 第一个大小足以满足请求的空闲分区，将其分配给进程。

• Next Fit （临近适应）：从 上一次查找结束位置的下一个位置 开始查找，找到第一个大小足以满足请求的空闲分区。如果到达表尾仍未找到，则从表头继续循环查找，直到找到合适分区或者完整遍历一轮。

• Best Fit （最佳适应）：遍历全部空闲分区，在所有能够满足请求的分区中，选择 大小最小的空闲分区。对于本次请求而言，该分区的利用率最高，分配后剩余空间最小。

• Worst Fit （最坏适应）：遍历全部空闲分区，在所有能够满足请求的分区中，选择 大小最大的空闲分区。对于本次请求而言，该分区的利用率最低，但分配后剩余的空闲块通常仍然较大。

假设进程申请的内存大小为 $P$ ，空闲分区大小为 $F$ ，且 $F\ge P$ ，则该分区对于本次分配的利用率可以表示为：

• $F$ 越接近 $P$ ，利用率越高；
• $F$ 越大，利用率越低。

因此：

• 最佳适应选择满足条件的最小空闲块，即利用率最高的空闲块；
• 最坏适应选择满足条件的最大空闲块，即利用率最低的空闲块。

举个例子，假设空闲块序列为：

[8, 22, 20, 14, 10, 24]

进程请求大小为：

P = 16

四种分配算法会得到不同结果：

四种适应算法在该例子中的对比如下：

各算法的典型特点如下：

当动态分区中的某块内存被释放时，操作系统需要检查释放分区的前后是否存在相邻的空闲分区，并尽可能完成合并。

根据相邻情况，可以分为四种情况：

1. 前后都不是空闲分区
   • 将释放分区作为新的独立空闲分区插入空闲分区表。
2. 前面是空闲分区
   • 将释放分区与前面的空闲分区合并；
   • 前面空闲分区的起始地址不变；
   • 增大其分区大小。
3. 后面是空闲分区
   • 将释放分区与后面的空闲分区合并；
   • 合并后起始地址修改为释放分区的起始地址；
   • 增大分区大小。
4. 前后都是空闲分区
   • 将前方空闲分区、释放分区和后方空闲分区合并为一块；
   • 删除其中多余的空闲分区表项。

合并相邻空闲分区可以减少外部碎片，但无法从根本上消除动态分区必须连续分配的问题。

堆内存分配

动态分区分配最初用于操作系统直接在物理内存中，为进程划分连续空间。

随着分页和虚拟内存的引入，进程不再需要占据一整块连续的物理内存，因此传统动态分区分配不再是现代操作系统为进程分配物理内存的主要方式。

但是，动态分区所体现的思想——在一段连续地址空间内动态划分、分割、回收和合并内存块——仍然被现代进程的 堆内存分配器 所继承。

其发展关系可以概括为：

1. 早期操作系统
   • 动态分区用于在物理内存中为整个进程分配连续空间。
2. 引入分页与虚拟内存
   • 操作系统可以将进程的虚拟页面离散地映射到不同物理页框；
   • 整个进程不再需要占据连续物理空间。
3. 动态分区思想应用于堆管理
   • 用户态运行库在进程堆或内存映射区域中维护大小不同的内存块；
   • 根据程序请求动态分割和回收这些内存块。

参考 进程内存空间。

当程序调用 malloc 时，它通常是在向用户态内存分配器申请一块连续可用的 虚拟地址空间。

当程序调用 free 时，分配器会将对应内存块标记为空闲，并可能与相邻空闲块合并。

堆内存分配器通常维护空闲块列表、大小分类链表或更复杂的数据结构。

当程序申请内存时，分配器会：

1. 寻找足够大的空闲块；
2. 必要时将较大的空闲块分割；
3. 将其中一部分返回给程序；
4. 保留剩余部分供后续分配。

当程序释放内存时，分配器会：

1. 将对应块标记为空闲；
2. 尝试与相邻空闲块合并；
3. 在适当条件下，将部分大块内存归还给操作系统。

需要注意的是，malloc 并不一定在每次调用时都直接向操作系统申请物理页。用户态分配器通常会先从已经获得的堆空间或内存映射区域中进行二次分配。

伙伴算法

伙伴算法（Buddy Algorithm）是一种按照 $2$ 的幂次管理内存块的分配方法。

它将可管理的内存划分为大小为：1 KB、2 KB、4 KB、8 KB、……

等 $2$ 的幂次大小的块。

当需要分配内存时，算法会寻找能够满足请求的最小块。如果没有合适大小的空闲块，就将更大的块不断一分为二，直到得到所需大小的块。

当内存被释放时，算法会检查对应的伙伴块是否也处于空闲状态。如果伙伴块空闲，则将两者合并为更大的块，并继续向上尝试合并。

内存分配过程

假设需要分配大小为 $S$ 的内存，算法首先找到满足下式的最小块大小：

其中 $n$ 应理解为使块大小满足要求的整数阶数，实际系统中的最小块大小不一定是 1 字节。

分配过程如下：

• 如果对应阶数的空闲链表中存在空闲块，则直接分配；
• 如果不存在，则向更高阶空闲链表查找更大的块；
• 找到更大的块后，将其平均分割为两个大小相同的伙伴块；
• 如果分割后的块仍然过大，则继续分割；
• 最终分配其中一个满足请求的块，其余块加入对应阶数的空闲链表。

下图展示了一个使用伙伴算法的内存分配实例：

伙伴算法分配的块大小必须为 $2$ 的幂，因此当请求大小不是 $2$ 的幂时，会向上取整到最近的块大小。

例如，请求 6 KB 时，可能需要分配一个 8 KB 的块，其中未使用的 2 KB 构成 内部碎片。

内存释放过程

释放一块内存时，算法会检查其伙伴块是否也处于空闲状态。

伙伴块需要同时满足以下条件：

• 与当前块大小相同；
• 地址满足伙伴关系；
• 两者由同一个更大的父块分割而来。

如果伙伴块空闲，则：

1. 将当前块与伙伴块合并为一个更大的块；
2. 将合并后的块加入更高一级的空闲链表；
3. 继续检查新块的伙伴是否也处于空闲状态；
4. 重复合并，直到伙伴不空闲或已经达到最大块大小。

伙伴关系

伙伴块的地址满足特定关系。

假设所管理内存区域的起始地址为 0，当前块大小为 $2^n$ ，则起始地址为 $A$ 的块，其伙伴地址为：

其中 $\oplus$ 表示按位异或。

例如，块大小为 8，即 $2^3$ ，则：

• 地址 0 的伙伴为 8
• 地址 8 的伙伴为 0
• 地址 16 的伙伴为 24
• 地址 24 的伙伴为 16

通过异或运算，系统可以快速定位某个内存块对应的伙伴块。

伙伴算法的主要特点是：

• 分割和合并速度快；
• 可以快速找到伙伴；
• 能够缓解外部碎片；
• 但会由于按 $2$ 的幂向上取整而产生一定的内部碎片。

现代操作系统内核常使用伙伴算法管理物理页框，而在更小对象的分配中，还会结合 Slab、SLUB 等分配器。

离散分配管理

连续分配方式要求整个进程或进程中的某个逻辑区域占据连续内存，因此容易受到外部碎片的限制。

离散分配的关键思想是：

将一个进程拆分成多个较小的单位，分别存放到不同的物理内存区域中，再通过地址映射结构将它们组织为完整的进程地址空间。

按照划分单位的不同，离散分配主要包括：

• 页式管理：按照固定大小的页划分；
• 段式管理：按照程序的逻辑结构划分；
• 段页式管理：先分段，再对每个段分页。

页式管理

页式管理的地址翻译、页表结构、TLB、缺页异常、页面置换和请求分页等细节，详见 组成原理中的对应章节。

本节重点介绍页式管理为什么出现，以及它与段式管理、段页式管理之间的区别。

动态分区虽然可以根据程序大小按需划分内存，但每个进程仍必须占据一整块连续的物理内存，因此容易受到外部碎片的限制。

页式管理的核心思想是：

将进程拆分为固定大小的页，使一个进程可以离散地存放在多个不连续的物理页框中。

页式管理通常进行如下划分：

• 将进程的虚拟地址空间划分为若干固定大小的 页（Page）；
• 将物理内存划分为与页大小相同的 页框 或 物理块（Frame）；
• 通过 页表 记录虚拟页号到物理页框号的映射关系。

由于页和页框大小相同，进程的任意虚拟页都可以装入任意空闲页框。

因此，进程在虚拟地址空间中看起来仍然是连续的，但其实际使用的物理页框可以分散在内存的不同位置。

页式管理带来的关键变化是：

连续分配：整个进程必须放入一块连续物理内存

页式管理：每个页单独分配页框，各页框可以彼此不连续

页式管理的主要优点包括：

• 不要求整个进程占据连续物理内存；
• 基本消除了动态分区中的外部碎片；
• 便于实现虚拟内存；
• 便于按照页面设置访问权限；
• 便于在进程之间共享某些页面。

页式管理的主要缺点包括：

• 页是由系统按照固定大小机械划分的，不反映程序的逻辑结构；
• 页表会占用额外内存；
• 地址翻译会带来额外开销；
• 进程最后一个页面通常无法被完全利用，因此仍可能存在少量内部碎片。

段式管理

段式管理并不是页式管理的简单升级，而是从另一个角度解决内存管理问题。

二者关注的核心问题不同：

页式管理：关注物理内存的分配效率，按照固定大小机械分页

段式管理：关注程序本身的逻辑结构，按照代码、数据、栈等逻辑单位分段

段式内存管理将程序按照逻辑功能划分为多个长度可变的 段（Segment），例如：

• 代码段；
• 数据段；
• 堆段；
• 栈段；
• 不同模块或过程对应的段。

每个段在逻辑上表示程序中的一个相对独立的组成部分。

段式管理的主要优点是能够反映程序的逻辑结构，因此更便于按照逻辑单位实现：

• 内存保护；
• 代码和数据共享；
• 模块化编程；
• 段的独立增长。

例如，可以将代码段设置为只读和可执行，将数据段设置为可读写，也可以让多个进程共享同一个只读代码段。

在早期 x86 体系结构中，分段机制是一种重要的地址管理和保护手段。8086 使用段寄存器与偏移量形成地址，但其分段机制与现代操作系统教材中抽象的段式存储管理并不完全等价，需要结合具体体系结构理解。

下文介绍段式内存管理中的三个关键概念：段、段表 和 地址翻译。

段概念

段是按照程序的逻辑结构划分的地址空间单位。

其主要特点包括：

• 每个段都有明确的逻辑含义，例如代码段、数据段或堆栈段；
• 不同段的长度可以不同；
• 同一个段内部的地址是连续的；
• 不同段可以放在彼此不连续的物理内存区域；
• 每个段可以设置独立的访问权限。

段式管理中的逻辑地址通常表示为：

段号用于确定访问哪个段，段内偏移表示访问该段中的哪个位置。

段表

每个进程拥有一张段表。

段表中的每个段表项通常记录：

• 段基址：该段在物理内存中的起始地址；
• 段长：该段的长度；
• 访问权限：例如可读、可写、可执行；
• 其他状态信息。

当程序使用段号和段内偏移访问内存时，处理器首先根据段号查找段表项，取得段基址和段长。

虽然一个进程的不同段可以离散地放置在物理内存中，但在纯段式管理中，每一个段内部通常仍然需要占据一块连续的物理内存。

因此，段式管理仍然可能产生 外部碎片。

地址翻译

假设逻辑地址由段号 $S$ 和段内偏移 $W$ 组成：

段式地址翻译过程如下：

1. 检查段号是否越界

   • 使用段号 $S$ 与段表长度进行比较；
   • 如果段号超出当前进程段表范围，则产生异常。

2. 查找段表项

   • 根据段表基址和段号找到对应段表项；
   • 读取该段的段基址和段长。

3. 检查段内偏移是否越界

   • 比较段内偏移 $W$ 与段长；
   • 如果 $W$ 不在合法范围内，则产生段越界异常。

4. 计算物理地址

   • 如果访问合法，则：

段式管理适合按照逻辑单位进行保护和共享，但存在两个主要问题：

• 每个段的长度可变，内存分配和回收较复杂；
• 每个段内部仍需连续存放，因此会产生外部碎片。

为了同时获得分段的逻辑组织能力和分页的离散分配能力，可以将两者结合，形成 段页式管理。

段页式管理

段页式管理（Paged Segmentation）是一种将 段式管理 与 页式管理 相结合的内存管理方式。

分页和分段各自解决的问题不同：

段页式管理的基本思想是：

先按照程序的逻辑结构分段，再将每一个段划分为固定大小的页。

其划分过程可以表示为：

程序
├── 代码段
│   ├── 第 0 页
│   ├── 第 1 页
│   └── ...
├── 数据段
│   ├── 第 0 页
│   ├── 第 1 页
│   └── ...
└── 栈段
    ├── 第 0 页
    ├── 第 1 页
    └── ...

操作系统首先通过 段表 管理各个逻辑段。

每个段表项不再直接给出整个段在物理内存中的起始地址，而是记录该段对应的：

• 页表起始地址；
• 段长或页表长度；
• 访问权限等信息。

在每个段内部，再通过独立的页表完成虚拟页到物理页框的映射。

在段页式管理中，虚拟地址通常被划分为三个部分：

• 段号（Segment Number）；
• 段内页号（Page Number）；
• 页内偏移（Offset）。

逻辑地址可以表示为：

地址翻译过程如下：

1. 根据虚拟地址中的 段号 查找段表；
2. 从段表项中取得该段页表的起始地址；
3. 根据 页号 查找该段对应的页表；
4. 从页表项中取得物理页框号；
5. 将物理页框号与 页内偏移 组合，得到最终物理地址。

段页式管理在逻辑上采用分段，在物理内存分配上采用分页：

逻辑组织：分段

物理分配：分页

它的主要优点包括：

• 保留程序的逻辑结构；
• 便于按照段进行共享和保护；
• 每个段内部可以离散地使用物理页框；
• 基本消除了纯段式管理中的外部碎片；
• 可以支持虚拟内存。

其主要缺点包括：

• 地址翻译过程更复杂；
• 需要同时维护段表和多个页表；
• 一次地址翻译可能涉及多次访存；
• 页表和段表都会占用额外内存。

虚拟存储器

虚拟存储器（Virtual Memory）并不是一种与分页、分段并列的地址空间划分方式，而是在这些基本内存管理方式之上进一步发展出来的 存储管理机制。

它的基本思想是：

程序运行时不必将全部内容一次性装入内存，只需装入当前需要使用的部分；其余内容暂时保存在外存中，并在访问时由操作系统按需调入。

虚拟存储器利用了程序执行过程中的 局部性原理：

• 在一段时间内，程序通常只会集中访问少量代码和数据；
• 暂时没有被访问的部分没有必要一直占用物理内存；
• 只要将当前需要的部分保存在内存中，程序就可以继续运行。

因此，一个程序的地址空间可以大于实际分配给它的物理内存，甚至可以大于整个物理内存的容量。

页式虚拟存储涉及的页表结构、TLB、缺页异常、请求调页和页面置换算法等硬件与操作系统协同细节，统一放在 组成原理章节 中展开。

最后总结一下内存管理的发展历史：

2 - 虚拟内存管理

页框分配

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

驻留集

驻留集（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，则置换页面如下：

内存置换次数为 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 的 执行流程 可以通过以下流程图理解：

LRU 算法的例子：

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

整个过程中，共发生 9 次缺页：

• 前 3 次缺页（访问页面 7、0、1）时，内存中仍有空闲页框，因此只需将页面装入内存，不发生页面置换。
• 后 6 次缺页（访问页面 2、3、4、2、3、0）时，内存已满，需要按照 LRU 算法进行页面置换。

因此：

• 页面置换次数：6 次
• 缺页次数：9 次
• 缺页率： $\frac{9}{12}=\frac{3}{4}=75\%$

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 替换策略可以通过以下流程图理解：

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