# 第七章 虚拟存储管理 ## 一、知识讲解 ### 7.0 章节定位与学习目标 本章是存储管理的"高潮章节"——在前一章基本分页/分段的基础上，把"一次性、驻留性"的常规存储管理扩展为"部分装入、按需调入"的**虚拟存储**。它要解决的核心问题是：**当程序比内存还大、或者多道程序并发占用内存导致内存不足时，怎么办？** 需要掌握的关键词：**局部性原理、虚拟存储器特征、缺页中断、请求分页地址变换、OPT、FIFO、Belady 异常、LRU、栈性质、NUR/Clock、改进 Clock、LFU、MFU、抖动、工作集、驻留集、请求调页/预调页、全局置换/局部置换、动态链接、共享段表、伙伴算法**。 --- ### 7.1 外存资源管理 #### 7.1.1 外存空间的划分与基本单位 **外存（磁盘）按"块"（block）管理**：块长度静态等长，为 2 的幂（2^i 字节）。**块既是外存分配的基本单位，也是 I/O 传输的基本单位**。这一点非常重要，与内存以"页"为单位完全对称：内存管理单位是页，外存管理单位是块，二者大小可以相等（如都为 4KB），也可以不等（一般块 = 多个页）。 **为什么块长必须是 2 的幂？** 出于效率考虑： 1. 便于按位运算定位（地址/块长 即为块号，可用移位实现）； 2. 便于伙伴（Buddy）算法对半分割、合并； 3. 与内存分页的页大小易于对齐。 #### 7.1.2 外存空间的分配方式 外存空间的组织有三种典型方式： | 方式 | 原理 | 优缺点 | |------|------|--------| | **空闲块链** | 把所有空闲块用链表串起来 | 简单，但分配/释放需遍历链表，**慢** | | **空闲块表**（UNIX） | 系统维护一张"空闲块号表"，记录连续空闲区段 | 速度较快，是 UNIX 成组链接法的思想 | | **字位映像图**（位图法） | 外存按块编号，每块对应一位，0=空闲 1=占用 | 查找空闲块快速，可一次找多个连续块 | 外存区域按用途划分： - **Swap 空间（交换区）**：存放被换出的页面，访问频率高，要求读写快； - **File 空间（文件区）**：存放文件，访问频率相对低，要求空间利用率高； - **输入井/输出井**：用于批处理系统中作业的输入/输出缓冲。 > **易考点**：外存块长的取值、字位映像图的"1 位对应一块"。 #### 7.1.3 进程与外存的对应关系 按进程运行时组织方式不同，进程在外存的存放方式有 4 种： | 方式 | 内存单位 | 外存单位 | 适用 | |------|---------|---------|------| | **界地址（连续）** | 连续区 | 一组/两组连续块 | 简单存储管理 | | **页式** | 一页 | 一块 | 虚拟页式 | | **段式** | 一段（变长） | 若干连续块 | 虚拟段式 | | **段页式** | 一页 | 一块 | 虚拟段页式 | > **双对界**：每个进程在外存中占两段连续区（用户区 + 交换区副本），便于成批换入换出。 --- ### 7.2 虚拟存储系统概述 #### 7.2.1 为什么要虚拟存储 **没有虚拟存储的两大问题**： 1. **不能运行比内存大的程序**：单道程序年代，一旦程序超过内存容量就无法运行； 2. **进程全部装入内存会浪费空间**：**程序运行时具有局部性**，一个进程某一时刻真正使用的页面只占其全部页面的一小部分，把整个进程都装入内存意味着大部分页面"白占"。 **局部性原理（Locality Principle）** 是虚拟存储的根基： - **时间局部性**：某指令/数据被访问后，短时间内很可能再次被访问（如循环体、热点数据）； - **空间局部性**：某存储单元被访问后，其相邻单元短期内很可能被访问（如顺序执行、数组顺序访问）。 由于局部性的存在，**单控制流进程**只需把"当前活跃"的一小部分装入内存即可运行；**多控制流进程**（如多线程）则需要更多活跃页面。 #### 7.2.2 虚拟存储的定义与特征 **虚拟存储器**：是指具有**请求调入**和**置换**功能，能从**逻辑上**对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和决定，运行速度接近内存，成本接近外存。 **虚拟存储的四大特征**（背诵）： 1. **多次性**（最重要）：一个作业被分成多次调入内存运行（不是一次性装入）； 2. **对换性**：作业在运行过程中可以换入/换出内存； 3. **虚拟性**：从逻辑上扩充内存容量，使用户看到的内存比实际大； 4. **离散性**：进程的多个页面在外存/内存可以离散存放（这要求分页或分段管理才能实现）。 > **易错点**：虚拟性的前提是离散性 —— 没有离散分配，虚拟存储无法实现。 #### 7.2.3 虚拟页式存储管理基本原理 这是最常见的虚拟存储实现方式。 **进程运行前**：全部页面装入外存，部分活跃页面装入内存。 **进程运行时**：若访问的页面不在内存 → 触发**缺页中断（Page Fault）**，由中断处理程序完成： 1. 保存现场； 2. 在外存找到该页地址； 3. 在内存找一个空闲页框；若无空闲，按置换算法选一页淘汰； 4. 若被淘汰页"脏"（被修改过），需先写回外存； 5. 把所需页面读入内存； 6. 修改该进程的页表和系统的总页表（标记该页在内存、更新页框号等）； 7. 重新执行被中断的指令（**重新启动**而非"继续执行"是缺页中断的特色）。 **为什么缺页中断要"重新启动指令"而不是"返回下一条指令"？** 因为缺页中断发生时，该指令可能还未执行完（例如取操作数阶段发现数据页不在内存），必须重新执行该指令才能拿到正确数据。 #### 7.2.4 虚拟页式地址映射（重点） 地址变换流程（结合快表/页表）： ``` 逻辑地址 (p, d) │ ▼ 查快表（TLB）得 f ├─ 命中 ──→ f+d 得物理地址 [硬件完成] └─ 未命中 ─→ 由 (b, p) 查页表得 f ├─ 页在内存 ─→ 修改快表（如快表满则淘汰一项），f+d 得物理地址 └─ 缺页 ─→ 缺页中断处理（见上） ※ p 越界 → 越界中断 ``` **关键点**： - **快表（TLB, Translation Lookaside Buffer）**：一种特殊的高速缓存，存放最近使用的页表项（p → f 的映射）。命中时硬件直接合成物理地址，**极快**；未命中才访问内存中的页表（慢）。 - 快表一般采用**组相联或全相联**，容量小（几十到几百项），查找由硬件并行完成。 - 一次地址变换可能触发**两次内存访问**（访问页表 + 访问数据），故引入快表。 #### 7.2.5 页表与快表的改进 **页表项** 应包含： - 页框号 f - 访问权限 {r, w, e} - 修改标志（脏位）0/1 - 有效位（在内存？）、访问位等 **快表项** 应包含：逻辑页号 p、页框号 f、访问权限、修改标志等。 #### 7.2.6 内存页框分配策略（静态） | 策略 | 公式/方法 | 优缺点 | |------|----------|--------| | **平均分配** | m 个页框 / n 个进程 = m/n 个 | 简单但不考虑进程实际需要 | | **按进程长度比例** | a_i = (s_i / S) × m | 较合理，但忽略优先级 | | **按进程优先级比例** | a_i = (priority_i / ΣP) × m | 体现优先级 | | **按长度与优先级综合** | 加权 | 最灵活 | **静态策略的缺陷**：不能反映（1）程序结构（如有些程序天然就是局部性差）；（2）程序在不同时刻的行为特性（同一进程在不同阶段访问的页面集不同）。所以实际操作中多用**动态分配**（基于工作集或缺页率反馈）。 #### 7.2.7 外存块的分配策略 | 策略 | 含义 | 优点 | 缺点 | |------|------|------|------| | **静态分配** | 外存长期保持进程全部页面 | 淘汰时若未修改可直接丢弃，**快** | 外存浪费 | | **动态分配** | 外存仅保存进程不在内存的部分页面 | 外存**省** | 淘汰时若被修改必须写回，**慢** | > **易考点**：静态/动态分配 vs 静态/动态页面调入，二者不要混淆！ #### 7.2.8 页面调入时机 | 方式 | 触发时机 | 优点 | 缺点 | |------|---------|------|------| | **请求调页（Demand Paging）** | 缺页中断发生时才调入 | 按需调入，外存访问次数少 | 缺页时进程必须等待 I/O | | **预调页（Prepaging）** | 根据程序顺序行为提前调入即将访问的页 | 缺页率可能降低 | 预测不一定准，调入的页可能根本不用 | **预调页必须辅以请调**：因为预调预测不可能 100% 准确，必须用请求调页作为兜底，否则一旦预测失败将持续缺页。 --- ### 7.3 页面置换算法（核心考点） **目标**：**最低的缺页率（page fault rate）**。当内存已无空闲页框时，按某种规则选一页淘汰。 > **置换算法同时适用于：页淘汰、段淘汰、快表淘汰**。三处的淘汰策略可以独立选择。 #### 7.3.1 OPT（最佳置换算法，Optimal） **原理**：淘汰**将来最长时间以后才被使用**的页面（或者"以后永远不再被使用"的页面）。 **优缺点**： - 优点：**缺页率最低**，可作为衡量其他算法优劣的基准； - 缺点：**不可实现** —— 因为操作系统无法预知进程未来的访问序列。这是最常考的一句话："OPT 缺页率最低，但不能实现，只能作为理论基准"。 **OPT 缺页率计算**： 设引用串：6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 6, 0, 1，分配 3 个页框。 | 访问 | 6 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 6 | 0 | 1 | |------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 框1 | 6 | 6 | 6 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 框2 | | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 6 | 6 | 6 | | 框3 | | | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | | 缺页? | × | × | × | × | | × | | × | | | × | | | × | | | | × | | | 缺页次数 = 9，缺页率 = 9/20 = **45%**。 OPT 每次淘汰"未来最远才用到的页面"：访问 2 时淘汰 1（1 在未来位置 13 出现，距离 11）；访问 3 时淘汰 6（6 未来在位置 17 才出现，最远）等等。 #### 7.3.2 FIFO（先进先出） **原理**：淘汰**最早调入内存**的页面（认为是"最旧"的页面）。实现简单，用一个**队列**记录调入顺序即可。 **依据**：先调入的页面可能已经用完了。 **缺点**： - **Belady 异常**（必考）：分配的页框数增加，缺页次数反而可能不减反增（违反常识）； - 没有考虑页面的使用情况，可能淘汰仍在使用的页面。 **Belady 异常示例**： 引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 | 内存=3 框 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 | |----------|---|---|---|---|---|---|---|---|---|---|---|---| | 框1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 | | 框2 | | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | | 框3 | | | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | | 缺页? | × | × | × | × | × | × | × | | | × | × | × | 缺页次数 = **9**，缺页率 = 9/12。 | 内存=4 框 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 | |----------|---|---|---|---|---|---|---|---|---|---|---|---| | 框1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 4 | | 框2 | | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | | 框3 | | | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | | 框4 | | | | 4 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 | | 缺页? | × | × | × | × | | | × | × | × | × | × | × | 缺页次数 = **10**，缺页率 = 10/12。 **结论**：4 框比 3 框的缺页率反而更高（10/12 > 9/12），这就是 **Belady 异常**。 > **重要结论**：FIFO 是**唯一**会出现 Belady 异常的常用置换算法；OPT、LRU、Clock 等都满足"栈性质"（stack property），即分配的页框越多缺页率不会上升。 #### 7.3.3 LRU（最近最少使用） **原理**：淘汰**最近一次访问距当前时间最长**的页面。即"过去最久没用的页面，未来也最可能不被用"。 **实现**：用**栈（stack）**。当一个页面被访问时，将其从栈中取出（如果存在），再压到栈顶。**栈顶是最新访问的，栈底是 LRU 页**（即下一次该被淘汰的）。 **性质**：LRU 满足**栈性质（Stack Property）**：n 个页框的 LRU 内存内容是 n+1 个页框 LRU 内存内容的子集。即增加页框数，缺页率**不会上升**。 **LRU 缺页率计算**： 引用串：6, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 6, 0, 1，分配 3 个页框。 | 访问 | 6 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 6 | 0 | 1 | |------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 框1 | 6 | 6 | 6 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 6 | 6 | 6 | | 框2 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | | 框3 | | | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | | 缺页? | × | × | × | × | | × | | × | × | × | × | | | × | | × | | × | | × | 缺页次数 = **12**，缺页率 = 12/20 = **60%**。 > **注意**：LRU 在本例中缺页率反而比 OPT 高（12 > 9），但比 FIFO 通常更低。LRU 缺页率与 OPT 缺页率之间的差，可以衡量算法与最优算法的差距。 #### 7.3.4 NUR / Clock（最近未用） LRU 思想很好，但需要维护精确的时间戳，开销太大。**NUR（Not Used Recently）** 是 LRU 的**近似**： **原理**：为每页增加一个访问位（引用位）r。访问该页时置 r=1；系统**定时**（如每次时钟中断）将所有 r 清 0。淘汰时选择 r=0 的页淘汰。 **Clock 算法（时钟算法，又称 Second Chance 的变种）**： 将所有页框组织成一个**环形链表**（钟面），有一个**指针**指向当前位置。需要淘汰时： 1. 从指针所指位置开始检查； 2. 若当前页面 r=0 → 直接淘汰； 3. 若 r=1 → 置 r=0，指针顺时针移动到下一页； 4. 重复 2-3 直到找到一个 r=0 的页面。 **Clock 与 Second Chance 的区别**：两者淘汰效果基本相同，但 Clock 算法直接利用**页表中的引用位**，外加一个指针，无需额外链表，**速度更快、节省空间**。 **Clock 算法执行示意**（访问第 18 页，指针最初指向框 12 即页 6，r=1）： | 步骤 | 指针位置 | 该页 r 值 | 处理 | |------|---------|-----------|------| | 初始 | 框 12（页 6, r=1） | 1 | r 清 0，指针移到框 23 | | | 框 23（页 3, r=1） | 1 | r 清 0，指针移到框 51 | | | 框 51（页 4, r=0） | 0 | **淘汰页 4** | #### 7.3.5 改进的 Clock 算法 **进一步考虑修改位 m**（脏位，标识页面是否被修改过），形成 4 类页面： | r | m | 类别 | 处理 | |---|---|------|------| | 0 | 0 | **最佳淘汰页** | 最近未访问且未修改，直接淘汰（无需写回） | | 0 | 1 | 次佳 | 最近未访问但被修改，淘汰前需写回 | | 1 | 0 | 较差不淘汰 | 最近访问但未修改 | | 1 | 1 | 最差不淘汰 | 最近访问且被修改 | **改进 Clock 算法分 4 轮扫描**（PPT 给出 3 步流程）： - **步骤 1**：从指针当前位置开始扫描，**找第一个 r=0 且 m=0 的页面**，淘汰；本次扫描**不修改任何 r 位**。 - **步骤 2**：若步骤 1 失败，再次从原位置扫描，**找第一个 r=0 且 m=1 的页面**；同时**将扫描过的页面的 r 位清 0**。 - **步骤 3**：若步骤 2 失败，指针回到原位置；由于步骤 2 已经把所有 r=1 的页面置 0，重新执行步骤 1 必能找到 r=0,m=0 的页面；若仍找不到则再次执行步骤 2，**此次一定成功**。 > **最优性证明**：经过两轮扫描，所有 r=1 的页面 r 都已被清 0，第 3 轮必然能找到 r=0,m=0 或 r=0,m=1 的页面。 #### 7.3.6 LFU（最不经常使用） **原理**：淘汰**访问次数最少**的页面。依据是"活跃访问页面访问次数应该较大"。 **实现**：每页一个计数器，调入时清 0，访问时增 1；淘汰选计数器最小者。 **缺点**： 1. 前期使用多但之后不再使用的页面（如初始化代码）计数器很大，难换出； 2. 刚调入的新页面计数器小，可能被错误换出。 #### 7.3.7 MFU（最经常使用） **原理**：淘汰**访问次数最多**的页面。依据是"已经用得最多的页面可能已经用完了"。 **缺点**：有些程序段（系统库、错误处理代码）在整个程序运行中都要使用，MFU 会错误地淘汰它们。 #### 7.3.8 二次机会（Second Chance） **原理**：淘汰**装入最久且最近未被访问**的页面。即在 FIFO 队列的基础上检查访问位：若队首页 r=0 则淘汰；若 r=1 则清 0 并放到队尾（相当于给它"第二次机会"）。 **与 Clock 的关系**：本质相同，区别仅在数据结构 —— Second Chance 用链表（额外空间、摘/入链慢），Clock 用环形 + 指针（直接用页表 r 位，省空间、速度快）。 #### 7.3.9 各种置换算法对比表 | 算法 | 思路 | 缺页率 | 实现难度 | 备注 | |------|------|--------|---------|------| | OPT | 淘汰未来最远才用 | 最低（基准） | 不可能实现 | 理论参考 | | FIFO | 淘汰最早调入 | 较高 | 极简（队列） | Belady 异常 | | LRU | 淘汰最近最久未用 | 接近 OPT | 较高（栈/时间戳） | 满足栈性质 | | Clock | NUR + 环形指针 | 接近 LRU | 中 | 实用 | | 改进 Clock | Clock + 脏位 | 优于 Clock | 中 | 实用 | | LFU | 淘汰访问最少 | 不稳定 | 中 | 计数器 | | MFU | 淘汰访问最多 | 差 | 中 | 几乎不用 | --- ### 7.4 抖动（Thrashing）与工作集 #### 7.4.1 抖动现象 **定义**：如果一个进程在运行中**频繁地发生缺页**，以致于大部分 CPU 时间都用于处理缺页中断而非执行用户指令，则称该进程处于**抖动（颠簸）状态**。 **形象描述**：页面在内存与外存之间来回频繁换入换出，看似在"剧烈抖动"，但实际有效工作几乎为零。 **原因**： 1. **分给进程的物理页框过少**（小于其工作集），导致频繁缺页； 2. **置换算法不合理**，例如 FIFO； 3. 多个进程竞争内存（多道程序度过高），总内存需求超出物理内存。 **处理方法**： 1. 增加分给进程的物理页框数； 2. 改进置换算法（如用 LRU/Clock 替代 FIFO）； 3. 降低多道程度，挂起部分进程。 **思考题**（PPT Slide 34）："在某些虚拟页式存储管理系统中，内存中总保持一个空闲的物理页架，这样做有什么好处？" > **答**：保证缺页中断处理时立即有空闲页框可用，无需临时置换，缩短缺页中断处理时间；同时降低抖动概率。但代价是内存少了一个可用页框，相当于"预留应急资源"。 #### 7.4.2 工作集模型（Working Set Model） **工作集定义**：进程在某段时间内所访问页面的集合，记为 WS(t, Δ)，其中： - **t**：当前时刻； - **Δ（窗口尺寸）**：考察的时间窗口长度（用访问次数或时间衡量）。 例如引用串 … 2 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 …，取 Δ=10，最近 10 次访问涉及 {5,7,1,6,2}，则 WS(t,Δ) = {5,7,1,6,2}。 **Denning 原则**：**为使程序有效运行，工作集应能全部装入内存**。若分配给进程的页框数 < 工作集大小，则必然频繁缺页（即抖动）。 **工作集与 Δ 的关系**： - Δ 太小：活动页面不能全部装入，缺页率高； - Δ 太大：内存浪费，且反应迟钝； - 经验值（Madnick & Donovan）：**Δ ≈ 10000 次访内**。 **工作集大小估算**（PPT Slide 38 给出的递推公式）： $$\tau_{n+1} = \alpha \cdot W_n + (1 - \alpha) \cdot \tau_n$$ 其中： - W_n = 第 n 个 Δ 周期内实际工作集大小； - τ_n = 第 n 个 Δ 周期工作集估算值； - α 通常取 0.5。 **实现**：在页表中增加"访问位"。Δ 开始时全部清 0；Δ 期间访问置 1；Δ 结束时访问位为 1 的页面即为该 Δ 周期的工作集。 #### 7.4.3 缺页率反馈模型（PFFB） **原理**：根据缺页率动态调整分配给进程的页框数。 - 缺页率 ≥ 上界阈值 → 内存页面少 → **增加**页框； - 缺页率 ≤ 下界阈值 → 内存页面多 → **减少**页框。 **缺页率公式**： $$\text{缺页率} = \frac{\text{缺页次数}}{\text{访问内存总次数}}$$ 这是另一种动态控制内存分配的方法（与工作集异曲同工，工作集是基于"过去一段时间活跃页面"，PFFB 是基于"最近缺页频率"）。 --- ### 7.5 虚拟段式存储系统 #### 7.5.1 基本思想 与虚拟页式类似，但基本单位是**段**（变长）。进程运行前全部装入外存，部分装入内存；访问不在内存的段时，发生**缺段中断**。 #### 7.5.2 地址映射 ``` 逻辑地址 (s, d) │ ▼ 查快表得 (b', l') ├─ 命中 ──→ 0≤d≤l'-1 越界检查 → b'+d 得物理地址 └─ 未命中 ─→ 由 (b, s) 查段表得 (b', l') ├─ 段在内存 ──→ 修改快表 └─ 缺段 ──→ 缺段中断：紧凑够?→紧凑;→选段淘汰→写回→读入→修改段表和快表 ※ s 越界 → 越界中断 ``` **注意**：虚拟段式要解决"变长段调入"的复杂问题 —— 当内存剩余空间不够装入新段时，可能需要**紧凑（compaction）** 操作，把分散的空闲区合并成连续大区。这与虚拟页式"固定大小页框"截然不同，是虚拟段式实现起来更复杂的主要原因。 #### 7.5.3 动态链接（Dynamic Linking） | 类型 | 时机 | 由谁完成 | |------|------|---------| | **静态链接** | 装入/运行前 | 链接程序（linker） | | **动态链接** | 运行时 | 操作系统 | **静态链接的缺点**： 1. 链接时间长； 2. 目标代码长（即使不用的段也被链入）； 3. 不使用的链接段占据空间。 **动态链接的实现**（Multics 为例）： - **段名-段号对照表**：每进程一个，记录"符号名 → 段号"； - **符号表**：每段一个，记录段内"符号 → 段内地址"； - **段形式**：符号表 + 目标代码（或数据）。 执行时遇到间接寻址指令且链接位 L=1，触发**链接中断**： 1. 由 D 取出符号地址； 2. 查段名-段号对照表： - 已分配段号 → 取段号查段表 → 找段内地址 → 填入 (段号,段内地址) → D，置 L=0（链接完成）； - 未分配段号 → 从外存/文件读入该段 → 分配段号 → 填写对照表 → 重新进入步骤 2。 #### 7.5.4 动态链接与共享的矛盾 **矛盾点**： - **动态链接**：要修改代码（修改间接字 D 和 L 位）； - **段的共享**：要求代码是**纯代码（pure code）**，即代码执行过程中不会被修改。 **解决方法**：把共享段拆成**纯段**（共享）和**杂段**（私有）。纯段用于共享执行；杂段存放可变数据（如全局变量），每个进程一份。 --- ### 7.6 虚拟段页式存储系统 #### 7.6.1 为什么要段页式 段式便于动态链接、共享、动态增长；页式便于内存管理、无外碎片。把两者结合：**先分段再分页**，就是段页式 —— 兼顾段式的灵活和页式的简洁。 #### 7.6.2 所需数据结构 | 表 | 数量 | 内容 | |----|------|------| | **段表** | 每进程 1 个 | 段号 → (页表长度, 页表首址) 等 | | **页表** | 每段 1 个 | 逻辑页号 → 页框号 | | **共享段表** | 系统 1 个 | 段名、(页表长度, 页表首址)、扩充标志、共享计数 | | **段名-段号对照表** | 每进程 1 个 | 段名 → 段号 | #### 7.6.3 寄存器 - 段表长度寄存器 l（保存当前进程段表长度） - 段表首址寄存器 b（保存当前进程段表首址） - 快表（TLB） #### 7.6.4 地址映射 逻辑地址 (s, p, d) → 物理地址 (f, d) ``` (s, p, d) │ ▼ 查快表 (s, p) → f ├─ 命中 ──→ 形成物理地址 (f, d) └─ 未命中 ─→ 由 (s, b) 查段表 → (b', l') ├─ 0≤s≤l-1 越界检查 ─→ 不通过：越界中断 └─ 通过 → 由 (b', p) 查页表 ├─ 0≤p≤l'-1 越界检查 ─→ 不通过：越界中断（可扩展则扩展该段） ├─ 页在内存 → (s,p,f) 入快表 └─ 缺页 → 缺页中断 ※ 间接寻址且 L=1 → 链接中断 ※ 访问权限不匹配 → 越权中断 ``` #### 7.6.5 中断类型 | 中断 | 处理 | |------|------| | **链接中断** | 见 7.5.3；共享段时共享计数加 1 | | **缺页中断** | 调入页 → 更新页表/总页表 | | **越界中断（段号）** | 错误处理 | | **越界中断（页号）** | 若可扩展则扩展该段（增页）并修改页表/段表；否则错误处理 | | **越权中断** | 错误处理 | #### 7.6.6 各种虚拟存储管理比较 | 特性 | 虚拟页式 | 虚拟段式 | 虚拟段页式 | |------|---------|---------|-----------| | 地址空间 | 一维 | 二维 | 二维 | | 存储分配 | 简单 | 复杂 | 简单 | | 存储碎片 | 无 | 有（外碎片） | 无 | | 存储共享 | 不便 | 方便 | 方便 | | 存储保护 | 不便 | 方便 | 方便 | | 动态扩充 | 不可 | 可以 | 可以 | | 动态连接 | 不可 | 可以 | 可以 | --- ### 7.7 Linux 存储管理（系统举例） #### 7.7.1 物理存储管理 - **三级页表**：页目录 → 页中间目录 → 页表 → 页内偏移； - **伙伴堆算法（Buddy Heap）**：管理空闲物理页框。 #### 7.7.2 虚拟存储管理 - 请求调页（demand paging）； - **无预调**（no pre-paging）； - **无工作集**（no working set）； - **页守护进程 kswapd**：每秒运行一次，保持内存中有足够的空闲页； - **刷新守护进程 bdflush**：周期性唤醒，将脏页写回磁盘。 #### 7.7.3 Buddy Heap 伙伴堆算法（必考） **核心思想**：把内存按 2 的幂次大小组织成块组。 - 块组 i：由 2^i 个连续页框组成的空闲区； - 共 10 个块组（i = 0,1,…,9），对应 1,2,4,…,512 个页框； - 每个块组维护一个空闲链表和一个**位图**。 **分配算法**（申请 fn 个页框）： 1. 找到满足 2^(i-1) < fn ≤ 2^i 的块组 i； 2. 若块组 i 有空闲块 → 直接分配一个； 3. 否则找更高块组 j（2^j ≥ 2^i），将 2^j 拆成 2^i + 2^(j-i)（按 2 的整数次幂拆分）； 4. 修改位图。 **释放算法**： 1. 释放 2^i 个页框； 2. 检查相邻块是否是**伙伴**（buddy）： - 两块大小相同（都是 2^i 个页框）； - 物理地址连续； - 后一块的最后页框编号 + 1 是 2^(i+1) 的整数倍； 3. 若伙伴也空闲 → 合并为 2^(i+1) 大块；递归向上合并； 4. 修改位图。 **位图规则**（PPT Slide 71）： - 一对 buddy 中：若一个空闲、另一个全部或部分占用 → 位图位置 1； - 若都空闲或都被全部或部分占用 → 位图位置 0。 **内部碎片问题**：申请 17 个页框时按 Buddy 算法要分配 32 个页框，浪费 15 个页框。Linux 用 **slab 分配器**（second memory allocator）将剩余小空闲块单独管理；**vmalloc**（third memory allocator）用于分配物理不连续的内存。 #### 7.7.4 分配示例 申请 fn=3，2^1 < 3 ≤ 2^2，所以在块组 2 分配 4 个页框（页框 8,9,10,11）。 --- ### 7.8 Windows Vista 存储管理（系统举例） #### 7.8.1 进程地址空间 - 32 位虚拟地址，寻址 4GB； - 用户空间：低地址 2GB； - 系统空间：高地址 2GB。 #### 7.8.2 存储管理方式：虚拟页式 - **页面尺寸**：4KB ~ 64KB； - **可交换页面**：用户空间所有页均可换出；系统空间部分页（如 DLL）也可换出； - **页表结构**：二级页表（页目录 + 页表）。 32 位地址划分： ``` | PDE (10位) | PTE (10位) | d (12位) | ``` #### 7.8.3 存储共享及保护 - **原型页表（Prototype Page Table）**：用于共享页。共享页的页表项不直接指向物理页框，而是指向原型页表，原型页表的表项才指向实际物理页框。 - **保护单位**：以页为单位。访问类型有只读、读写、执行、不可操作、写时复制（copy-on-write）等。 #### 7.8.4 内存优先级与页面调度 内存按 0~7 优先级组织： - 高优先级：进程工作集，活跃使用； - 低优先级：待机列表（standby list）、已修改页列表等。 **进程虚拟页面状态**： | 状态 | 含义 | |------|------| | **闲置（free）** | 未分配内存；访问将导致缺页 | | **预定（reserved）** | 已分配但不可立即使用；需解除预订才能用 | | **确认（committed）** | 已分配且可访问 | --- ## 二、考点总结 ### 考点 1：虚拟存储器的定义与四大特征 - **内容**：虚拟存储器是具有请求调入和置换功能，能从逻辑上扩充内存容量的存储系统。四大特征：**多次性、对换性、虚拟性、离散性**。 - **考查方式**：选择、填空、简答。 - **可能的题目**： 1. **选择题**：虚拟存储器的特征不包括（ ）。A. 多次性 B. 对换性 C. 一次性 D. 离散性。**答案：C**（一次性是常规存储管理的特征，与虚拟存储的多次性对立）。 2. **简答题**：为什么离散性是虚拟性的前提？**答案**：因为只有离散分配（分页/分段），进程的多个页面才可能不连续地放在内存和外存，从而实现部分装入；如果必须连续分配，则装入部分页面到不连续区域是做不到的。 ### 考点 2：缺页中断与一般中断的区别 - **内容**：缺页中断发生在执行指令过程中（如取操作数/取指令阶段），由硬件陷入 OS 缺页中断处理程序；处理完成后必须**重新执行该指令**（不是返回下一条）。一般中断处理完返回下一条指令即可。 - **考查方式**：选择、简答。 - **可能的题目**： 1. **选择题**：缺页中断处理完成后应（ ）。A. 返回下一条指令 B. 重新执行被中断指令 C. 终止进程 D. 跳过本指令。**答案：B**。 ### 考点 3：OPT 算法（最佳置换） - **内容**：淘汰将来最长时间以后才被使用的页面。**不可实现**，但缺页率最低，常作为基准。 - **考查方式**：计算题、简答。 - **可能的题目**： 1. **计算题**：引用串 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，分配 4 个页框，用 OPT 计算缺页次数。 **解**：访问 7,0,1,2 → 缺页 4 次（填满）；访问 0 命中；访问 3 → 淘汰未来最远才用的：未来用到 4、2、3、0、3、2、1、2、0、1、7、0、1，位置 17 才出现 7，最远。等等。最优淘汰策略下缺页次数约为 6~8 次（具体需逐步推算）。 ### 考点 4：FIFO 算法与 Belady 异常 - **内容**：FIFO 用队列实现，淘汰最早调入的页面。**唯一**会出现 Belady 异常（页框增加、缺页不减反增）。 - **考查方式**：计算题（必考）、简答。 - **可能的题目**： 1. **计算题**：引用串 1,2,3,4,1,2,5,1,2,3,4,5，FIFO、3 框和 4 框的缺页率。 **解**：参见 7.3.2 节，3 框缺页 9 次（9/12），4 框缺页 10 次（10/12），出现 Belady 异常。 2. **简答题**：哪些置换算法不会出现 Belady 异常？为什么？ **答案**：OPT、LRU、Clock 等都满足**栈性质**（n 框内容 ⊆ n+1 框内容），增加页框只会减少缺页。**FIFO 是唯一常见会 Belady 异常的算法**。 ### 考点 5：LRU 算法与栈性质 - **内容**：LRU 淘汰最近最久未访问的页面。用栈实现，栈顶最新、栈底最久。**满足栈性质**，无 Belady 异常。 - **考查方式**：计算题、简答。 - **可能的题目**： 1. **计算题**：引用串 6,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,6,0,1，3 框，LRU 缺页率。 **解**：参见 7.3.3 节，缺页 12 次，缺页率 12/20 = 60%。 ### 考点 6：Clock 算法 - **内容**：用页表引用位 r + 环形指针实现。r=0 淘汰；r=1 清 0 后移指针。 - **考查方式**：分析题、计算题。 - **可能的题目**： 1. **分析题**：给定 8 个页框的 r 位状态，画出连续 3 次缺页的 Clock 淘汰过程。 **解**：从指针所指位置开始，按顺时针方向扫描；遇到 r=1 清 0 后跳过；遇到 r=0 直接淘汰。详细过程参见 7.3.4 节示例。 ### 考点 7：改进 Clock 算法（4 类页面、3 步扫描） - **内容**：考虑访问位 r 和修改位 m，分 4 类：最佳 (0,0)、次佳 (0,1)、较佳 (1,0)、最差 (1,1)。3 步流程：先找 (0,0) 不改 r；再找 (0,1) 清 r；最后回到起点必找到。 - **考查方式**：分析题。 - **可能的题目**： 1. **分析题**：8 个页框，r、m 状态给定，访问新页，画出改进 Clock 淘汰过程。 **解**：参见 7.3.5 节三步流程。 ### 考点 8：LFU 与 MFU - **内容**：LFU 淘汰访问次数最少的；MFU 淘汰访问次数最多的。LFU 缺点是前期热点页难换出、新页易被错误淘汰；MFU 缺点是会误淘汰全程使用的代码。 - **考查方式**：选择、简答。 - **可能的题目**： 1. **选择题**：下列说法正确的是（ ）。A. LFU 不会淘汰刚开始使用的页 B. MFU 适用于全程都用的代码 C. LFU 用计数器实现 D. MFU 是最优置换算法。**答案：C**。 ### 考点 9：抖动（Thrashing） - **内容**：频繁缺页导致 CPU 时间大量浪费在中断处理上的现象。原因：页框过少、置换算法差、多道度过高。处理：增加页框、改进算法、降低多道度。 - **考查方式**：选择、简答。 - **可能的题目**： 1. **简答题**：系统出现抖动时有哪些处理方法？**答案**：① 增加物理页框数（或减少进程数）；② 改用更优置换算法（如 LRU）；③ 利用工作集模型给活跃进程分配足够页框；④ 挂起部分进程；⑤ 调度时优先调度缺页率低的进程。 ### 考点 10：工作集模型 - **内容**：WS(t,Δ) 是进程在 [t-Δ, t] 期间访问的页面集合。**Denning 原则：工作集应能全部装入内存**。Δ 经验值约 10000 次访内。 - **考查方式**：选择、计算（工作集大小估算）。 - **可能的题目**： 1. **计算题**：引用串 … 2 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 …，Δ=10，求当前工作集。 **解**：最近 10 次访问：7,7,7,7,5,1,6,2,2,1 → 涉及页面 {1,2,5,6,7}。**WS = {1,2,5,6,7}，大小 = 5**。 ### 考点 11：请求调页 vs 预调页 - **内容**：请求调页（demand paging）在缺页时调入；预调页（prepaging）在缺页前提前调入。预调必须辅以请调（兜底）。 - **考查方式**：选择、简答。 - **可能的题目**： 1. **简答题**：为什么预调页必须辅以请求调页？**答案**：预调基于对未来的预测，而预测不可能 100% 准确；一旦预测错误（如调入的页实际不被访问）就会浪费 I/O，且真正要用到的页还是得靠请求调入，故二者必须配合。 ### 考点 12：动态链接 vs 静态链接 - **内容**：静态链接由 linker 在运行前完成，缺点是慢、长、不必要的段被链入；动态链接由 OS 在运行时完成，可节省空间、按需链接，但实现复杂、需"链接中断"处理。 - **考查方式**：选择、简答。 - **可能的题目**： 1. **简答题**：动态链接与段的共享有什么矛盾？如何解决？**答案**：矛盾是动态链接会修改代码中的间接字（修改是杂段），而共享要求纯代码。解决方法是把共享段拆为纯段（共享执行）和杂段（私有数据，每进程一份）。 ### 考点 13：虚拟段式 vs 虚拟页式 vs 虚拟段页式比较 - **内容**：参见 7.6.6 节对比表。 - **考查方式**：选择、简答。 - **可能的题目**： 1. **选择题**：便于动态连接和共享的虚拟存储管理方式是（ ）。A. 虚拟页式 B. 虚拟段式 C. 虚拟段页式 D. 以上都不能。**答案：B、C**。 2. **简答题**：虚拟段页式相比虚拟段式和虚拟页式各有什么优点？**答案**：相比虚拟段式 —— 无外碎片、内存管理简单；相比虚拟页式 —— 便于动态链接、共享、动态扩充。 ### 考点 14：Linux 伙伴算法（Buddy Heap） - **内容**：按 2 的幂组织空闲块组。分配时找满足 2^(i-1)