Operating-System/Homework/07第七章 虚拟存储管理.md

# 第七章 虚拟存储管理

## 一、知识讲解

### 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)<fn≤2^i 的块组 i，不够就拆分更高块组；释放时检查伙伴条件（大小相同、物理连续、后块最后页框号+1 是 2^(i+1) 倍数）并合并。
- **考查方式**：计算题（分配/释放过程）、简答。
- **可能的题目**：
  1. **计算题**：伙伴堆中，已知初始空闲区 64 页框；依次 req(8)、req(8)、req(4)、rel(8)、rel(8)，画出每次操作后的空闲区状态。
     **解**：
     - 初始：64 页框空闲；
     - req(8)：从 64 中分出 8，余 56；56 又拆分（32+24→32+16+8）→ 空闲 {32,16,8}，分配 8；
     - req(8)：从 {32,16,8} 中分出 8 即可（取 16 拆分）→ 空闲 {32,16,8} 中已有 8，直接分配；
     - req(4)：从 {16} 拆分出 8，将 8 拆分出 4 → 空闲 {32,16,8,4} 中分配 4；
     - rel(8)：把 8 放回 → 若有伙伴则合并；空闲 {32,16,8,8,4} → 两 8 合并为 16 → {32,16,16,4}；
     - rel(8)：把 8 放回 → 空闲 {32,16,16,4,8} → 与原 16 合并？需要看伙伴关系。

### 考点 15：地址变换综合题（常考大题）

- **内容**：给定逻辑地址、页大小、页表内容、置换算法，求物理地址。
- **考查方式**：计算题（必考大题）。
- **可能的题目**：
  1. **2010 年考研题（PPT Slide 31-33）**：某虚拟页式系统，进程空间和内存空间都是 64KB，页长 1KB；某进程 6 个页（页号 0~5），分配 4 个页框，框号 5,12,8,3 装入页 0,2,3,5；280 时刻访问逻辑地址 13B7H。
     (1) 逻辑页号？
     (2) 若用 FIFO 置换，物理地址？
     (3) 若用 CLOCK 置换，物理地址？

     **解**：
     - (1) 13B7H = 0001 0011 1011 0111B；页长 1KB = 2^10 → 后 10 位是页内地址 0FB7H？不对，应该是最后 10 位：1011 0111 → 11 1011 0111B = 0 1110 1101 11 取后 10 位 = 11 1011 0111 = 0x3B7？等等，原题是"后 10 位为页内地址"。13B7H = 0001 0011 1011 0111B，共 16 位；前 6 位为页号 = 000100 = 4，后 10 位为页内地址 = 11 1011 0111 = 0x3B7。
     - 进程页号 0,1,2,3,4,5；当前内存中装入页 0,2,3,5（缺 1,4）；访问页 4 → 缺页。
     - (2) FIFO：原 4 个页框装入顺序未知，按 FIFO 淘汰最先进入的（假设是页 0）→ 淘汰页 0，页 4 装入框 5（替换页 0）。等等，按 PPT 答案："4 号页不在内存，发生缺页中断，按 FIFO 置换算法，应置换第 5 页，所得页框号 3"。
     - 物理地址：原页 0 的框号 5，页 5 的框号 3。FIFO 淘汰页 5（最后装入或最先装入的，需根据入队顺序），页 4 替换框 3，物理地址 = 00 0011 + 11 1011 0111 = 0000 1111 1011 0111B = 0FB7H。
     - (3) CLOCK：原页框 5（页 0）的访问位为 0（设初始 r=0），则淘汰页 0 → 页 4 装入框 5 → 物理地址 = 0001 0101 + 11 1011 0111 = 0001 0111 1011 0111B = 17B7H。

### 考点 16：缺页率计算综合题

- **内容**：给定访问序列、页框数、置换算法，求缺页次数和缺页率。
- **考查方式**：计算题。
- **可能的题目**：
  1. **例题**：引用串 1,2,3,4,1,2,5,1,2,3,4,5；3 个页框 FIFO 缺页率？
     **解**：参见 7.3.2 节，缺页 9 次，缺页率 = 9/12 = **75%**。

### 考点 17：有效访问时间（EAT）计算

- **内容**：EAT = 命中时的访问时间 + 缺页率 × 缺页中断处理时间。
- **考查方式**：计算题（常考）。
- **可能的题目**：
  1. **PPT Slide 85 题**：请求分页系统中，页表保存在寄存器。若有可用空页/被置换页未修改，处理缺页中断需 8ms；若被置换页已修改，需 20ms（多写回外存时间）。一次内存存取 1ns。70% 被置换页被修改。为保证 EAT ≤ 12ns，求最大缺页率 p。
     **解**：设缺页率 p，平均缺页处理时间 = 0.7×20 + 0.3×8 = 14 + 2.4 = 16.4 ms = 16,400,000 ns。
     EAT = 1 + p × 16,400,000 ≤ 12
     p × 16,400,000 ≤ 11
     p ≤ 11/16,400,000 ≈ **6.7 × 10⁻⁷**（约百万分之 0.67）

  2. **PPT Slide 86 题**：LRU 请求分页系统，页面 4KB，内存访问 100ns/次，快表访问 20ns/次，缺页中断 25ms/次。30KB 进程进入系统，分配 3 块，访问序列 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1（20 次访问），快表命中率 20%。求平均有效访问时间。
     **解**：
     - 先算 LRU 缺页率：参见 7.3.3 节 LRU 示例，3 框 20 次访问中缺页 12 次 → 缺页率 p = 12/20 = 0.6；
     - 但本题中快表命中率 20%，意味着 80% 需访问内存页表；
     - 命中快表：20ns；
     - 未命中快表 + 命中内存页 + 命中内存数据：100ns + 100ns = 200ns；
     - 缺页时：缺页中断 25ms = 25,000,000 ns；
     - 平均：EAT = 0.2×20 + 0.8×200 + 0.6×25,000,000
            = 4 + 160 + 15,000,000
            ≈ **15,000,164 ns ≈ 15ms**（绝大多数时间花在缺页中断处理上）

### 考点 18：缺页率反馈模型（PFFB）

- **内容**：根据缺页率上下界阈值动态调整进程页框分配：缺页率高 → 加页框；缺页率低 → 减页框。
- **考查方式**：简答、选择。
- **可能的题目**：
  1. **选择题**：PFFB 模型调整页框数的依据是（ ）。A. 工作集大小 B. 缺页率 C. 进程优先级 D. 进程长度。**答案：B**。

### 考点 19：内存保护与越界/越权中断

- **内容**：段式有段号越界和段内偏移越界、越权中断；页式有页号越界；段页式综合。
- **考查方式**：选择、填空。
- **可能的题目**：
  1. **填空题**：段页式系统中可能发生的中断类型有 ____、____、____、____。
     **答案**：链接中断、缺页中断、越界中断（段号或页号）、越权中断。

### 考点 20：Windows Vista 段共享（原型页表）

- **内容**：共享页的页表项不直接指向物理页框，而是指向**原型页表**，原型页表项才指向物理页框。这样多个进程可共享同一物理页。
- **考查方式**：选择、简答。
- **可能的题目**：
  1. **简答题**：Windows Vista 中共享页的页表项为什么不直接指向物理页框？**答案**：通过原型页表实现共享。当物理页框号变化时（如换出换入），只需修改原型页表的对应项，所有引用该原型的进程页表项都自动跟随，避免每个进程都修改。

### 考点 21：Linux 虚拟存储特征

- **内容**：三级页表、请求调页、**无预调**、**无工作集**、kswapd 每秒运行一次保持空闲页、bdflush 周期性刷脏页。
- **考查方式**：填空、选择。
- **可能的题目**：
  1. **填空题**：Linux 的页守护进程是 ____，刷新守护进程是 ____，虚拟存储采用 ____（请调/预调），是否有工作集？____（有/无）。
     **答案**：kswapd、bdflush、请调、无。

---

## 附录：典型计算题汇总

### 计算题 1：FIFO + Belady 异常验证

**题目**：引用串 1,2,3,4,1,2,5,1,2,3,4,5，分别用 3 个和 4 个页框执行 FIFO，求缺页次数。

**解（参见 7.3.2）**：
- 3 框：缺页 9 次，缺页率 9/12；
- 4 框：缺页 10 次，缺页率 10/12；
- 页框多反而缺页多 → **Belady 异常**。

### 计算题 2：LRU 缺页率

**题目**：引用串 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%。

### 计算题 3：OPT 缺页率（理论下限）

**题目**：引用串 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，3 个页框，OPT。

**解（参考答案）**：

| 访问 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 框1 | 7 | 7 | 7 | 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 | 7 | 7 | 7 |
| 框3 |   |   | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 缺页? | × | × | × | × |   | × |   | × |   |   | × |   |   | × |   |   |   | × |   |   |

缺页 9 次，缺页率 9/20 = 45%（**最低**）。

### 计算题 4：Clock 算法

**题目**：8 个页框，r 位依次为 1,1,0,0,1,0,0,1（顺时针），访问新页，画 Clock 淘汰过程。

**解**：
1. 指针指向第一个 r=1 → 清 0，指针后移；
2. 第二个 r=1 → 清 0，指针后移；
3. 第三个 r=0 → **淘汰**。
- 共扫描 3 个位置才找到淘汰页。

### 计算题 5：改进 Clock 算法

**题目**：8 个页框 (r,m) 依次为 (1,1),(1,1),(1,0),(1,0),(1,0),(0,1),(0,1),(1,0)，访问新页，画改进 Clock 过程。

**解**：
1. **步骤 1**：从指针起找 (0,0)，没有；扫描一遍不修改 r；
2. **步骤 2**：再次扫描找 (0,1)，扫描过程中把所有 r=1 清 0；
   - 扫描 (1,1)→r 清 0 → (0,1)；
   - 扫描 (1,1)→r 清 0 → (0,1)（第二个）；
   - 扫描 (1,0)→r 清 0 → (0,0)；
   - 扫描 (1,0)→r 清 0 → (0,0)；
   - 扫描 (1,0)→r 清 0 → (0,0)；
   - 扫描到 (0,1) → **淘汰**（这是第 6 个位置）。
3. （步骤 3 在此例中不需要，步骤 2 已成功）

### 计算题 6：2010 考研题（地址变换）

参见考点 15。答案：
- (1) 逻辑页号 4；
- (2) FIFO 淘汰页 5，物理地址 0FB7H；
- (3) CLOCK 淘汰页 0，物理地址 17B7H。

### 计算题 7：有效访问时间

参见考点 17。答案：
- 题 1：p ≤ 6.7 × 10⁻⁷；
- 题 2：EAT ≈ 15,000,164 ns ≈ 15 ms。

### 计算题 8：工作集大小

**题目**：引用串 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6，Δ=5，求最近 5 次访问的工作集。

**解**：最近 5 次访问：3,2,1,2,3 → 涉及页面 {1,2,3}。**WS = {1,2,3}，大小 = 3**。

### 计算题 9：伙伴堆分配

**题目**：伙伴堆中空闲区大小 256 页框；依次 req(50), req(30), req(20)。

**解**：
- req(50)：2^5 < 50 ≤ 2^6 = 64，分配 64 页框；剩余 256-64=192 → 拆分为 128+64 → 128 入块组 7，64 已分配；
- req(30)：2^4 < 30 ≤ 2^5 = 32，从块组 7 拆出 64，64-32=32 入块组 5，分配 32 页框；
- req(20)：2^4 < 20 ≤ 2^5 = 32，从块组 5 分配 32 页框（块组 5 还有一块 32 即可）。
- 最终空闲区：块组 7 = 128 页框；块组 5 空（已分配）；其他为空。

---

**本章核心要点速记**：
1. 虚拟存储四大特征：**多次性、对换性、虚拟性、离散性**。
2. 缺页中断处理后**重新执行**该指令。
3. OPT **不可实现**但缺页率最低（理论基准）。
4. **FIFO 唯一可能 Belady 异常**；LRU/OPT/Clock 等都满足栈性质。
5. 改进 Clock 分 4 类页面、3 步扫描，**前 r 不清、后 r 清 0**。
6. 抖动 = 频繁缺页；工作集应能全部装入内存。
7. 动态链接用"间接字 + 链接位 L"，L=1 触发链接中断。
8. Linux 伙伴算法按 **2 的幂**组织；申请 fn 满足 2^(i-1)<fn≤2^i 时从块组 i 取。
9. Windows 共享用**原型页表**。
10. 有效访问时间 EAT = 1 + 缺页率 × 缺页中断开销（含置换、写回）。