说明：本文为个人学习笔记，内容参考王道《操作系统》网课与配套讲义，按个人理解整理总结，仅用于学习交流，如有疏漏欢迎指正。

内存空间的扩充

覆盖

为了解决程序大小超过物理内存总和的问题, 引入了覆盖技术

思想

• 将程序分为多个段(多个模块)
• 常用的段常驻内存, 不常用的段在需要时调入内存
• 内存中分为一个"固定区", 和若干个"覆盖区"

例子

注: 在计算机里，“透明”= 用户完全不用管，系统自动帮你做好。反过来，“不透明”= 用户必须手动操心、手动配置，系统不会自动帮你做。

为什么这叫 “不透明”？

• 现代虚拟内存（分页 / 分段）：程序员完全不用管内存，写代码时默认 “内存无限大”，系统自动帮你换入换出，这就是透明。
• 覆盖技术：程序员必须深度参与内存管理，从拆分段、设计覆盖区、声明结构，到保证调用逻辑，全要手动搞定，系统只负责执行你写的规则，不会帮你做任何决策。

交换

思想

内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

在进程因为内存紧张被调出的时候, 进程的PCB需要留在内存(进入挂起队列), 即常驻内存, 这是因为在PCB中可以记录进程被调出到外存的具体位置
暂时换出外存等待的进程状态为挂起状态

问题

1) 应该在外存的什么位置保存被换出的进程?

• 在支持对换功能的操作系统中，磁盘空间会被划分为文件区和对换区两个独立部分，二者的管理逻辑完全围绕各自的核心目标设计。
• 文件区主要用于存放各类持久化的用户文件与程序数据，核心追求是存储空间的利用率，因此采用离散分配的方式来减少空间浪费、提升存储效率
• 而对换区仅占用磁盘的一小部分空间，专门用于临时存放被换出内存的进程数据，由于对换的 I/O 速度直接影响系统的整体运行效率，所以对换区的管理以换入换出速度为核心目标，通常采用连续分配的方式来减少磁盘寻道时间、提升读写效率，最终实现对换区的 I/O 速度远快于文件区，保障进程调度的高效性。

2) 什么时候应该交换

交换通常发生在许多进程运行且内存吃紧时进行, 而系统负荷降低就暂停

3) 应该换出哪些进程

• 可优先换出阻塞进程
• 换出优先级低的进程
• 为了防止优先级低的进程在被调入内存后很快又被换出, 有的系统还会考虑进程在内存的驻留时间(PCB常驻内存, 并不会被换出外存)

虚拟存储技术

传统存储管理方式的特征和缺点

• 一次性: 作业必须一次性全部装入内存后才能开始运行, 这会造成两个问题 :
  • 作业很大时, 不能全部装入内存, 导致大作业无法运行
  • 当大量作业要求运行时, 由于内存无法容纳所有作业, 因此只有少量作业能运行, 导致多道程序并发度下降
• 驻留性: 一旦有作业被装入内存, 就会一直驻留在内存中, 直至作业运行结束. 事实上, 在一个时间段内, 只需要访问作业的一小部分数据即可正常运行, 这就会到时了内存中驻留大量的, 暂时用不到的数据, 造成内存资源浪费

虚拟内存的定义和特征

定义

• 程序装入时，仅将很快会用到的部分装入内存，暂时用不到的部分留在外存，程序即可开始执行。
• 程序执行中，若访问的信息不在内存，由操作系统将所需信息从外存调入内存，再继续执行。
• 若内存空间不足，由操作系统将内存中暂时用不到的信息换出到外存。
• 在操作系统管理下，用户看来有一个比实际内存大得多的内存，这就是虚拟内存。

特征

• 多次性：无需在作业运行时一次性全部装入内存，允许被分成多次调入内存。
• 对换性：在作业运行时无需一直常驻内存，允许在作业运行过程中，将作业换入、换出。
• 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际的容量。

如何实现虚拟内存技术

虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

传统非连续存储管理方式和虚拟内存的区别

• 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。 操作系统要提供请求调页(请求调段)功能
• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。操作系统要提供页面置换(或段置换)的功能

请求分页管理方式

请求分页管理方式是在基本分页存储管理方式的基础上进行拓展实现的

页表机制

缺页中断机构

1. 触发条件

在请求分页系统中，当要访问的页面不在内存时，会产生一个缺页中断，由操作系统的缺页中断处理程序处理。

2. 核心处理步骤

1. 进程阻塞：产生缺页中断后，当前缺页的进程会被阻塞，放入阻塞队列，等待调页完成。
2. 调页与内存分配：
   • ✅ 内存有空闲块：为进程分配一个空闲块，将所缺页面从外存装入该块，修改页表对应项（更新内存块号、状态位为 1）。
   • ❌ 内存无空闲块：通过页面置换算法选择一个页面淘汰：
     • 若被淘汰页面被修改过：必须将其写回外存，再调入新页面。
     • 若被淘汰页面未修改：直接覆盖，无需写回外存，节省 I/O 开销。
3. 进程唤醒：调页完成后，唤醒被阻塞的进程，将其放回就绪队列，等待 CPU 调度继续执行。

属性

缺页中断是因为当前执行的指令想要访问的目标页面未被调入内存而产生的, 因此属于内中断
一条指令在执行期间, 可能产生多次缺页中断
(例如: 将逻辑地址A中的数据复制到逻辑地址B, 而AB属于不同的页面, AB都不在内存中, 则可能产生两次中断)

地址变换机构

• 新增步骤1 : 请求调页(查到页表项时进行判断, 判断页面是否在内存中)
• 新增步骤2 : 页面置换(需要调入页面, 但没有空闲内存块时, 需要换出某一些页面来腾出内存空间)
• 新增步骤3 : 需要修改请求页表中新增的表项

页面置换算法

最佳置换算法(OPT)

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

注意 : 缺页时未必发生页面置换

问题

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

先进先出置换算法(FIFO)

每次选择淘汰的页面是最早进入内存的页面

最佳最久未使用置换算法(LRU)

每次淘汰的页面是最近最久未使用的页面

时钟置换算法(CLOCK)

核心设计

• 为每个页面设置一个访问位，内存中的页面通过链接指针连成一个循环队列。
• 页面被访问时，访问位置为1。

淘汰页面的扫描规则

1. 第一轮扫描：
   • 遇到访问位为0的页面：直接选择该页面淘汰。
   • 遇到访问位为1的页面：将其置为0，暂不淘汰，继续检查下一个页面。
2. 特殊情况处理：
   • 若第一轮扫描中所有页面访问位都是1，则将所有页面的访问位依次置为0后，进行第二轮扫描。
   • 第二轮扫描中一定会有访问位为 0 的页面，因此简单 CLOCK 算法选择淘汰页面最多经过两轮扫描。

改进型时钟置换算法

一、算法核心思想

1. 简单时钟算法的局限

简单 CLOCK 仅考虑访问位（页面最近是否被访问），完全忽略页面的修改状态，导致可能频繁淘汰已修改页面，产生大量磁盘 I/O 开销。

2. 改进的核心逻辑

在访问位的基础上，新增修改位作为淘汰依据：

• 淘汰未修改页面（修改位 = 0）：无需执行 I/O 写回外存，开销极低
• 淘汰已修改页面（修改位 = 1）：必须执行 I/O 写回外存，开销极高
• 核心原则：其他条件相同时，优先淘汰未修改的页面，最大程度减少 I/O 操作

3. 页面状态表示

用 (访问位A, 修改位M) 表示页面状态：

二、完整算法规则（最多 4 轮扫描）

将所有可置换页面排成循环队列，按以下顺序扫描，找到符合条件的页面立即淘汰：

第 1 轮扫描（找最优：(0, 0)）

• 目标：从当前位置开始，查找第一个 (0, 0) 的页面
• 操作：不修改任何标志位，找到直接淘汰；若未找到，进入第 2 轮

第 2 轮扫描（找次优：(0, 1)）

• 目标：重新扫描，查找第一个 (0, 1) 的页面
• 操作：将所有扫描过的页面访问位 A 置为 0，找到直接淘汰；若未找到，进入第 3 轮

第 3 轮扫描（重置后再找 (0, 0)）

• 目标：重新扫描，查找第一个 (0, 0) 的页面
• 操作：不修改任何标志位，找到直接淘汰；若未找到，进入第 4 轮

第 4 轮扫描（最终找 (0, 1)）

• 目标：重新扫描，查找第一个 (0, 1) 的页面
• 操作：找到直接淘汰
• 兜底保证：第 2 轮已将所有页面 A 置为 0，因此第 3/4 轮必然能找到符合条件的页面，算法最多执行 4 轮扫描

小结

页面分配策略

驻留集

1. 定义

驻留集：请求分页存储管理中, 给进程分配的物理块的集合，即进程当前在内存中的页面集合。

2. 核心特性

在虚拟存储系统中，驻留集大小 < 进程总大小（按需调页，无需一次性装入全部页面）。

3. 驻留集大小的影响

页面分配策略

1. 固定分配

• 规则：操作系统为每个进程分配固定数目的物理块，进程运行期间驻留集大小不再改变。
• 特点：分配简单，但无法根据进程运行状态动态调整，灵活性差。

2. 可变分配

• 规则：先为每个进程分配一定数目的物理块，运行期间可根据缺页情况动态增加 / 减少物理块，驻留集大小可变。
• 特点：灵活性高，可根据进程需求动态调整，更合理利用内存。

页面置换策略

1. 局部置换

• 规则：发生缺页时，只能从当前进程自己的物理块中选择页面淘汰，不影响其他进程。
• 特点：各进程独立，不会抢占其他进程内存，系统更稳定，但无法全局优化内存分配。

2. 全局置换

• 规则：发生缺页时，可使用系统空闲块，也可淘汰其他进程持有的物理块，分配给缺页进程。
• 特点：可全局动态调整内存分配，内存利用率更高，但可能导致进程驻留集被抢占，稳定性弱于局部置换。
• 关键结论：全局置换会改变进程的物理块数量，因此无法与固定分配搭配使用（固定分配要求驻留集大小不变）。

分配与置换的组合可行性

不可行原因

固定分配要求进程驻留集大小固定，而全局置换会淘汰其他进程的物理块，必然改变当前进程的物理块数量，因此两者无法结合。

页面分配 & 置换策略 三种组合方案

固定分配局部置换

1. 核心规则

• 分配：系统为每个进程分配固定数量的物理块，整个运行期间驻留集大小完全不变。
• 置换：进程缺页时，只能从自身内存中的页面里选一页换出，再调入新页面。
• 物理块确定方式：根据进程大小、优先级、程序员指定参数等确定初始分配量。

2. 优缺点

✅ 优点：实现简单，各进程内存隔离，不会互相抢占
❌ 缺点：初始分配量难以确定：分配太少会频繁缺页，分配太多浪费内存；无法根据进程运行状态动态调整

可变分配全局置换

1. 核心规则

• 分配：初始为每个进程分配一定物理块，系统维护空闲物理块队列。
  • 进程缺页时，优先从空闲队列取块分配，驻留集增大；
  • 无空闲块时，从系统中任意未锁定的页面（任意进程）淘汰，将该块分配给缺页进程。
• 置换：全局范围，可淘汰任何进程的页面，被淘汰进程的物理块数减少、缺页率上升。

2. 关键特性

• 只要缺页就优先分配新物理块，仅当空闲块耗尽时才触发置换
• 是最容易实现的分配置换策略，内存利用率高
• 缺点：可能出现 “进程被频繁抢占物理块，缺页率飙升” 的情况，稳定性弱

方案 3：可变分配局部置换

1. 核心规则

• 分配：初始为每个进程分配一定物理块，根据缺页率动态调整：
  • 进程频繁缺页 → 额外多分配物理块，直到缺页率降至合理水平；
  • 进程缺页率极低 → 适当回收部分物理块，减少驻留集大小。
• 置换：进程缺页时，仅能从自身内存页面中淘汰，不影响其他进程。

2. 优缺点

✅ 优点：性能最优，兼顾灵活性与稳定性，可动态适配进程需求，避免全局抢占
❌ 缺点：实现复杂度最高，需要实时监控各进程缺页率，算法开销大

何时调入页面

1. 预调页策略（运行前调入）

核心逻辑

基于局部性原理，预测不久之后可能访问到的页面，一次性提前调入若干相邻页面，而非缺页时才调入。

优缺点

✅ 优点：若预测准确，可大幅减少缺页次数，提升效率，比单次调页更高效。
❌ 缺点：预测成功率仅约 50%，若提前调入的页面大多未被访问，会造成严重的 I/O 和内存浪费。

适用场景

• 主要用于进程的首次调入阶段
• 通常由程序员指定需要优先调入的程序部分，而非系统盲目预测

2. 请求调页策略（运行时调入）

核心逻辑

进程在运行期间发生缺页时，才将所缺的页面调入内存，是虚拟内存的基础调页方式。

优缺点

✅ 优点：调入的页面100% 会被访问，不会造成无效 I/O，内存利用率高。
❌ 缺点：每次只能调入一页，每次调页都需磁盘 I/O 操作，I/O 开销较大，频繁缺页时性能下降明显。

适用场景

• 进程运行过程中的常规调页，是请求分页系统的默认调页方式

从何处调入页面

1. 方案一：系统有足够对换区空间

核心逻辑

• 页面调入 / 调出全程在「内存 ↔ 对换区」之间进行
• 进程运行前，先把进程相关的全部数据从文件区复制到对换区
• 后续所有缺页调入、页面置换，都直接在对换区操作

优缺点

✅ 优点：对换区连续分配、读写速度快，页面调入 / 调出效率最高
❌ 缺点：需要占用大量对换区空间，对磁盘空间要求高

2. 方案二：系统缺少足够对换区空间

核心逻辑

• 按页面是否会被修改，区分处理：
  1. 不会被修改的页面（如程序代码页）：直接从文件区调入内存；换出时无需写回磁盘（文件区已有原始副本），下次需要直接从文件区调入
  2. 可能被修改的页面（如数据页）：首次从文件区调入；换出时必须写回对换区，后续调入从对换区读取

优缺点

✅ 优点：节省对换区空间，适合对换区容量有限的系统
❌ 缺点：文件区读写速度慢，未修改页面的调入效率低于对换区

3. 方案三：UNIX 经典方式

核心逻辑

• 进程运行前，所有数据全部存放在文件区
• 未使用过的页面：直接从文件区调入内存
• 已使用过 / 被修改的页面：换出时写回对换区，后续需要时从对换区调入

特点

• 兼顾了空间节省与效率：未修改页面直接用文件区，节省对换区；修改页面用对换区，保证后续调入速度
• 是实际操作系统（如 UNIX/Linux）的主流实现方案

抖动/颠簸

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动（颠簸）。

产生抖动的主要原因是：进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）。

工作集

在某段时间间隔（窗口尺寸 ）里，进程实际访问页面的集合

工作集的计算方法

核心规则

• 以窗口尺寸为时间范围，统计该时间段内进程访问过的去重页面集合，即为当前时刻的工作集。
• 工作集大小 ≤ 窗口尺寸（若窗口内有重复访问的页面，去重后数量会小于窗口尺寸）。

示例

（窗口尺寸 = 4，访问序列：24, 15, 18, 23, 24, 17, 18, 24, 18, 17, 17, 15）

• 第 1 个窗口（访问前 4 个页面）：{24,15,18,23} → 工作集大小 = 4
• 后续窗口（如访问到第 7 个页面时）：窗口内页面为{24,17,18,24} → 去重后{18,24,17} → 工作集大小 = 3

作用

• 指导内存分配，避免抖动

  操作系统统计进程的工作集大小，为进程分配不小于工作集大小的物理块（驻留集大小 ≥ 工作集大小）：

  • 若驻留集 < 工作集：进程会频繁缺页，引发抖动（颠簸），系统性能暴跌；
  • 若驻留集 ≥ 工作集：进程缺页率大幅降低，可流畅运行，无抖动风险。

• 优化页面置换算法

  基于局部性原理，进程近期访问的页面（工作集）与未来访问的页面高度相关，因此置换时可优先淘汰不在工作集中的页面，大幅减少缺页次数。

内存映射文件

传统文件访问方式

• open 系统调用：打开文件
• seek 系统调用：将读写指针移到某个位置
• read 系统调用：从读写指针所指位置读入若干数据（从磁盘读入内存）
• write 系统调用：将内存中的指定数据，写回磁盘（根据读写指针确定要写回什么位置）

内存映射文件访问方式

• open 系统调用: 打开文件
• mmap系统调用: 将文件映射到进程的虚拟地址空间 (会给程序员返回一个指针, 指向映射的区域的起始地址 )
  • 接着就可以用访问内存的方式去访问这个指针后面的区域(起始地址➕偏移量)
  • 文件的读入写出由操作系统自动完成 (因为操作系统只是建立文件数据和内存之间的映射, 没有把数据读入内存, 相当于缺页的状态)
  • 进程关闭文件后, 操作系统会自动将文件被修改过的数据写回磁盘

实现文件数据的共享

多个进程可以映射同一个文件, 实现共享

总结

覆盖（Overlay）：把程序分成常驻的“固定区”和按需装入的“覆盖区”，解决“大程序装不下内存”；缺点是不透明，需要程序员手动设计与管理装入/覆盖关系。 交换（Swapping）：内存紧张时把进程整体换出到外存、再换入；PCB常驻内存以记录外存位置。换出位置通常区分文件区/对换区，优先换出阻塞或低优先级进程。 虚拟内存（Virtual Memory）：基于局部性原理实现“按需调页/置换”，具备多次性、对换性、虚拟性；核心机制是页表 + 缺页中断 + 页面置换算法（OPT 理论最优、FIFO 简单、LRU 更贴近局部性、CLOCK 及改进 CLOCK 用访问位/修改位折中性能与开销）。 分配与抖动：驻留集太小会缺页频繁并引发抖动；用工作集估计活跃页面集合，指导分配使驻留集 ≥ 工作集以降低缺页率。 mmap 内存映射文件：把文件映射到虚拟地址空间，像访问内存一样访问文件；实际读写由 OS 通过缺页调入/写回自动完成，并支持多进程共享同一文件数据。