762 lines
38 KiB
Markdown
762 lines
38 KiB
Markdown
# 第六章 存储管理
|
||
|
||
## 一、知识讲解
|
||
|
||
### 6.1 存储管理功能
|
||
|
||
操作系统的**存储管理**（Storage Management / Memory Management）是 OS 的核心功能之一，主要解决"**多道程序如何共享有限的内存空间**"以及"**程序如何使用比实际内存更大的地址空间**"两大问题。本章围绕"功能—资源管理方式—管理方式（页/段）"三条线索展开。
|
||
|
||
存储管理的主要功能可以归纳为以下五项：
|
||
|
||
#### 1. 存储分配和去配
|
||
- **对象**：内存与外存（采用相同的方法统一管理）。
|
||
- **时刻**：在进程创建、撤销、换入换出（swapping）、进程长度变化（如栈溢出、execl 调用）时进行。
|
||
- 何时分配、何时去配，由 OS 根据内存使用情况自动决定。
|
||
|
||
#### 2. 存储共享
|
||
- **目的**：节省内存（同一份代码/数据只保留一份）；支持进程间通信。
|
||
- **内容**：可共享代码（reentrant code，可重入代码）、可共享数据。
|
||
|
||
#### 3. 存储保护
|
||
- **目的**：保证多道程序互不干扰，防止一个进程访问另一个进程的内存或破坏 OS 内核。
|
||
- **手段**：
|
||
- **防止地址越界**：访问的物理地址必须在该进程所属内存区域内；
|
||
- **防止操作越权**：对共享数据/代码只能做许可的操作（如只读不可写）。
|
||
|
||
#### 4. 存储扩充（虚拟存储）
|
||
- 借助**内存与外存的结合**，向用户提供一个**速度接近内存、容量相当于外存**的虚拟存储体系。
|
||
- 实现机制：覆盖（overlay）、交换（swapping）、虚拟存储（虚拟页/虚拟段，详见第七章）。
|
||
|
||
#### 5. 地址映射（地址翻译 / Address Translation）
|
||
- **任务**：把程序中使用的**逻辑地址（相对地址、虚地址）**转换为内存中的**物理地址（绝对地址、实地址）**。
|
||
- **硬件支持**：
|
||
- **基址寄存器（Base Register）**：保存当前运行进程的起始物理地址；
|
||
- **限长寄存器（Limit Register）**：保存当前运行进程的长度；
|
||
- **快表（TLB，Translation Lookaside Buffer）**：缓存最近使用的页/段表项，加速地址映射；
|
||
- 地址映射过程由硬件（MMU，Memory Management Unit）自动完成；
|
||
- 当地址映射**不能正常完成**（如越界）时，硬件产生**越界中断（地址错）**，交由 OS 处理。
|
||
|
||
> **重点提示**：基址寄存器 + 限长寄存器 + 快表 是实现地址映射的经典硬件组合，是后续页式/段式管理的物理基础。
|
||
|
||
---
|
||
|
||
### 6.2 内存资源管理
|
||
|
||
本节讨论操作系统如何描述和分配"空闲内存"，分为**内存分区方式**和**内存分配算法**两大部分。
|
||
|
||
#### 6.2.1 内存分区
|
||
|
||
按"分区时刻"和"分区大小"两个维度组合，可以得到 4 种分区方案：
|
||
|
||
| 分区时刻 \ 大小 | 等长分区 | 异长分区 |
|
||
|:---:|:---:|:---:|
|
||
| **静态分区** | 静态等长（页式、段页式基础） | 静态异长 |
|
||
| **动态分区** | 动态等长 | 动态异长（段式、界地址） |
|
||
|
||
- **静态分区**：系统在**初始化时**就把内存划分好，运行期间不再改变。
|
||
- **动态分区**：根据进程申请**临时划分**内存区域。
|
||
- **等长分区**：每个分区大小相同（典型为 $2^i$）；便于位示图管理，适合分页。
|
||
- **异长分区**：每个分区大小不同；按程序大小划分，适合分段。
|
||
|
||
通常的工程做法：
|
||
- **静态 + 等长** → 页式、段页式
|
||
- **动态 + 异长** → 段式、界地址管理
|
||
|
||
#### 6.2.2 内存分配
|
||
|
||
##### (1) 静态等长分区的分配（每"页"为单位）
|
||
|
||
管理"哪些页框被占用、哪些页框空闲"的数据结构有三种：
|
||
|
||
| 数据结构 | 特点 | 适用 |
|
||
|:---:|:---|:---:|
|
||
| **位示图（Bit Map / 位视图）** | 用一个 bit 代表一页状态：0 表空闲，1 表占用。分配时从头找第一个 0 改为 1；去配时把对应位置 0。 | 多单元管理（每个 bit 都需维护） |
|
||
| **空闲页面表** | 只记录连续空闲页的首地址与长度，可分配**连续多页**（如 DMA 要求）。 | 需分配连续页面 |
|
||
| **空闲页面链** | 用链表把空闲页串起来，**节省空间**（不需为已分配页维护信息）。 | 不适合管理外存 |
|
||
|
||
**位示图例**：内存共 $2^n$ 页，每页 $2^i$ 字节，则位示图占用 $2^n$ 位（共 $2^{n-i}$ 个机器字）。
|
||
|
||
##### (2) 动态异长分区的分配（每"区"为单位）
|
||
|
||
空闲区数据结构：按"首址递增"排列的表，每条记录为 `(首址, 长度)`，`长度=0` 表示表尾。
|
||
|
||
**经典算法对比**（必考）：
|
||
|
||
| 算法 | 选取策略 | 优点 | 缺点 |
|
||
|:---|:---|:---|:---|
|
||
| **最先适应 FF (First Fit)** | 取第一个能满足的空闲区 | 尽量使用低地址空间，保留高地址大空闲区 | 可能把大空闲区"切碎"，产生碎片 |
|
||
| **下次适应 NF (Next Fit)** | 从上次分配位置的**下一个**开始循环查找 | 查找开销小，空闲区分布更均匀 | 仍可能切碎大空闲区 |
|
||
| **最佳适应 BF (Best Fit)** | 取**最小**能满足的空闲区 | 保留大空闲区 | 容易留下大量**小碎片** |
|
||
| **最坏适应 WF (Worst Fit)** | 取**最大**的空闲区 | 防止形成小碎片 | 把大空闲区切碎，大作业难以装入 |
|
||
|
||
> **关键提示**：
|
||
> - 内存中**地址一定按首址递增**排列，这是所有算法的公共前提；
|
||
> - "最佳适应"中"最佳"指"**浪费最小**"，并非"最优整体效果"；
|
||
> - 例：空闲区序列 `[12k, 32k, 80k, 4k]`，申请 30K 时
|
||
> - FF：取 32K，剩余 2K（第一个能放下的）；
|
||
> - BF：取 32K，留下 2K 碎片（最小的能放下的）；
|
||
> - WF：取 80K，剩余 50K（最大的能放下的）。
|
||
|
||
##### (3) UNIX 存储分配（FF 的经典实现）
|
||
|
||
UNIX 使用结构体 `map` 数组实现：
|
||
```c
|
||
struct map { char *m_size; char *m_addr; };
|
||
struct map coremap[CMAPSIZ]; // 内存分配
|
||
struct map swapmap[SMAPSIZ]; // 交换区分配
|
||
```
|
||
|
||
`malloc(mp, size)` 沿链表找第一个 `m_size >= size` 的块，从中切出 size 部分，更新表项；`mfree(mp, size, aa)` 在去配时做**相邻合并**（与前/与后/前后合并），避免碎片扩散。这是理解**首次适应 + 空闲区合并**的最经典 C 代码示例，考试可作简答题。
|
||
|
||
#### 6.2.3 碎片处理
|
||
|
||
- **碎片（Fragment）**：不能被任何进程利用的零碎空闲区。
|
||
- **内部碎片**：分配单元（如一页）内未被进程完全使用的部分；
|
||
- **外部碎片**：分散在已分配区之间的零碎空闲区。
|
||
- **紧凑（Compaction）**：通过**移动已分配区**使所有空闲区连成一片。
|
||
- **代价**：开销极大（需要重定位所有进程、修改所有基址），实际中很少采用；
|
||
- 仅在动态分区方式下讨论。
|
||
|
||
---
|
||
|
||
### 6.3 存储管理方式
|
||
|
||
存储管理的**四种核心方式**：
|
||
|
||
| 方式 | 地址结构 | 内存划分 | 进程划分 | 主要优点 | 主要缺点 |
|
||
|:---|:---:|:---:|:---:|:---|:---|
|
||
| **界地址管理** | 一维 | 动态异长 | 一个连续区 | 简单 | 碎片、外部碎片 |
|
||
| **页式管理** | 一维 | 静态等长（页框） | 静态等长（页面） | 无外部碎片 | 内部碎片、地址二维分裂 |
|
||
| **段式管理** | 二维 | 动态异长 | 若干段 | 便于共享、保护 | 外部碎片 |
|
||
| **段页式管理** | 二维 | 静态等长 | 段→页 | 兼顾段式优点 + 无外部碎片 | 复杂、开销大 |
|
||
|
||
> **对比要点**：页式的逻辑地址与物理地址都是一维的（页号+页内偏移），而段式的逻辑地址是二维的（段号+段内偏移），物理地址仍是一维的（基址+偏移）。
|
||
|
||
---
|
||
|
||
### 6.3.1 界地址管理方式
|
||
|
||
#### 1. 基本原理
|
||
- **内存划分**：**动态异长**（每个进程占一段连续内存）。
|
||
- **进程空间划分**：一个进程一个连续区域，逻辑地址 `0 ~ l-1`（`l` 为进程长度）。
|
||
- **进程空间与内存空间对应**：进程可被装入到内存中的任意起始地址 `b`，**支持重定位**。
|
||
|
||
#### 2. 所需表目
|
||
- **内存分配表**：记录在 PCB 中（含基址 `b`、限长 `l`）。
|
||
- **空闲区域表**：系统级，数组 `array of (addr, size)`。
|
||
|
||
#### 3. 所需寄存器
|
||
- **基址寄存器 b**：当前运行进程的起始物理地址；
|
||
- **限长寄存器 l**：当前运行进程的长度。
|
||
|
||
#### 4. 地址映射
|
||
|
||
**映射函数**：$\sigma: a \mapsto b+a$，但需先做越界检查 $0 \le a \le l-1$。
|
||
|
||
**步骤**：
|
||
1. 由程序确定逻辑地址 `a`；
|
||
2. 越界检查：`0 ≤ a ≤ l-1`，否则越界中断；
|
||
3. 物理地址 `= b + a`。
|
||
|
||
> **重要**：界地址方式是后续页式、段式的"雏形"，理解其寄存器机制对掌握后面内容至关重要。
|
||
|
||
#### 5. 双对界（Dual Bounds）
|
||
|
||
经典 UNIX 将进程空间分为 **I 空间（指令空间）和 D 空间（数据空间）**，各用一对界（基址 + 限长）：
|
||
- **代码 (I 空间)**：一对界；
|
||
- **数据 (D 空间)**：一对界。
|
||
|
||
硬件能识别逻辑地址所属空间（取指 vs. 读写数据），并使用对应的映射寄存器。**优点**：同一进程内指令和数据可以独立重定位，方便代码共享。
|
||
|
||
#### 6. 交换技术（Swapping）
|
||
|
||
- **定义**：进程在**内存与外存之间**的动态调度，用于缓解内存不足。
|
||
- **工作过程**：
|
||
- 当外存有可运行进程时，系统尝试将其调入内存；
|
||
- 当内存紧张时，把暂时不可运行的进程移出到外存。
|
||
- **UNIX sched 进程（#0）原则**：
|
||
1. 内存有空间 → 直接移入；
|
||
2. 不够 → 移出处于 SWAIT、SSTOP 状态的进程；
|
||
3. 还不够 → 移出 SSLEEP、SRUN 状态进程，但需满足条件：**在外时间 ≥ 3 秒且在内时间 ≥ 2 秒**（避免频繁颠簸）。
|
||
- **重定位（Relocation）**：被换出的进程再次装入内存时，**位置可能不同**，因此程序必须与内存位置无关——即**可重定位程序（浮动程序）**。由 0 起始编址的程序天然支持重定位。
|
||
|
||
#### 7. 覆盖技术（Overlay）
|
||
|
||
- **定义**：把**大程序装入较小进程空间**的技术。
|
||
- **做法**：
|
||
- 静态装入**全局代码和数据**到内存；
|
||
- 其余部分按调用关系**动态装入**；
|
||
- **后装入的成分可重复使用先装入成分使用的存储区**（覆盖先装入的成分）。
|
||
- **示例**：编译器有 `Pass1/Pass2/Pass3/Pass4`，其中 `Pass1` 30KB、`Pass2` 50KB、`Pass3` 40KB、`Pass4` 25KB，加上公共例程、符号表、覆盖驱动程序，可全部放进 50KB 覆盖区。
|
||
- 覆盖与交换的区别：覆盖由**程序员**控制，交换由**操作系统**自动调度。
|
||
|
||
---
|
||
|
||
### 6.3.2 分页式存储管理（Paging）
|
||
|
||
#### 1. 基本原理
|
||
|
||
页式管理是**最重要的存储管理方式**之一，必须彻底掌握。
|
||
|
||
**内存划分**：
|
||
- 静态等长分区，每区称为一个**页框（Page Frame）**，大小为 $2^i$ 字节。
|
||
- 第 0 页框首址为 0，第 1 页框首址为 $2^i$，……，第 $k$ 页框首址为 $k \times 2^i$。
|
||
- **物理地址** = 页架首址 + 页内偏移 = `页架号 × 2^i + 页内地址`。
|
||
- 若地址总线为 `n` 位，则页架号占 `n-i` 位，页内地址占 `i` 位。
|
||
|
||
**进程空间划分**：
|
||
- 静态等长分区，每区称为一个**页面（Page）**，大小为 $2^i$ 字节（与页框相同）。
|
||
- **逻辑地址** = 逻辑页首址 + 页内偏移 = `逻辑页号 × 2^i + 页内地址`。
|
||
- 逻辑地址结构：(p, d)，其中 p 为逻辑页号，d 为页内偏移。
|
||
|
||
**对应关系**：
|
||
- **页表（Page Table）**：每个进程一个，记录每个逻辑页对应的物理页框号 f。
|
||
- 第 0 页 → f₀，第 1 页 → f₁，……
|
||
|
||
#### 2. 所需表目与寄存器
|
||
|
||
| 项目 | 数量 | 说明 |
|
||
|:---|:---:|:---|
|
||
| **页表** | 每进程一个 | 记录 `逻辑页号 → 页架号` 的映射 |
|
||
| **总页表** | 系统一个 | 反映物理页框的占用情况 |
|
||
| **页表首址寄存器 b** | 系统一个 | 当前运行进程的页表起始地址 |
|
||
| **页表长度寄存器 l** | 系统一个 | 当前运行进程的页表长度（页数） |
|
||
| **快表 TLB** | 系统一组 | 缓存最近使用过的 `(逻辑页号 → 页架号)` |
|
||
|
||
#### 3. 地址映射（核心算法，必考）
|
||
|
||
**映射函数**：$\sigma: (p, d) \mapsto (f, d) \cup \{\Omega\}$，其中 $\Omega$ 为越界异常。
|
||
|
||
**步骤**：
|
||
1. 由程序确定逻辑地址 `(p, d)`；
|
||
2. **查快表**：用 `p` 查 TLB 得到页架号 `f`（命中则跳到第 6 步）；
|
||
3. **越界检查**：`p` 与 `l` 比较，若不满足 `0 ≤ p ≤ l-1`，则越界中断；
|
||
4. **查页表**：用 `p` 和页表首址 `b` 查页表，得页架号 `f`；
|
||
5. **填快表**：把 `(p, f)` 写入 TLB，若 TLB 已满则淘汰一项；
|
||
6. **合成物理地址**：把 `f`（页架号）与 `d`（页内偏移）合并为物理地址 `(f, d)`。
|
||
|
||
> **重点**：
|
||
> - 整个映射过程由硬件（MMU）自动完成；
|
||
> - 越界、缺页等异常由硬件产生中断，OS 介入处理；
|
||
> - 页表项至少包含：页架号、有效位（V）、访问位（A）、修改位（M）、保护位。
|
||
|
||
#### 4. 快表与有效访问时间（EAT）
|
||
|
||
**有效访问时间（Effective Access Time）公式**（必考）：
|
||
|
||
$$
|
||
EAT = h \times (t_{TLB} + t_{mem}) + (1-h) \times (t_{TLB} + 2 \times t_{mem})
|
||
$$
|
||
|
||
其中 `h` 为快表命中率。
|
||
|
||
**例题**：设 `t_TLB = 20ns`，`t_mem = 100ns`，命中率 `h = 98%`，求 EAT：
|
||
$$
|
||
EAT = 0.98 \times (20 + 100) + 0.02 \times (20 + 200) = 117.6 + 4.4 = 122 \text{ ns}
|
||
$$
|
||
|
||
#### 5. 多级页表（Multi-Level Page Table）
|
||
|
||
**提出背景**：
|
||
- 内存空间成倍增长，进程虚拟空间也成倍增加；
|
||
- 32 位地址空间、页长 4KB（页内偏移占 12 位）→ 页号占 20 位 → 单级页表最多 $2^{20}$ 个表项（约 4MB），需要**连续大内存**；
|
||
- 多线程设计使进程虚拟空间出现大量**空洞（hole）**，如栈的预留空间并不需要分配物理页框，但单级页表仍要为它们保留表项，浪费内存。
|
||
|
||
**解决方案**：**二级或多级页表**。
|
||
- 外页表（顶级页表）的表项指向一个二级页表；
|
||
- **只有真正使用的逻辑页面才有对应的二级页表**；
|
||
- 访问 hole 时，OS 才会动态建立相应的内页表。
|
||
|
||
**典型 32 位二级分页**：
|
||
- 页内偏移 = 12 位；
|
||
- 逻辑页号 = 20 位，再分为 **外页号 p1（10 位）+ 内页号 p2（10 位）**；
|
||
- 逻辑地址结构：`(p1, p2, d)`。
|
||
|
||
**地址映射过程**：
|
||
1. 由 `p1` 查外页表 → 得二级页表首址；
|
||
2. 由 `p2` 查二级页表 → 得页架号 `f`；
|
||
3. `f` 与 `d` 合并 → 物理地址 `(f, d)`。
|
||
|
||
> **开销**：相比单级页表，每访问一次内存需要访问外页表 + 二级页表 + 数据，共 **3 次内存访问**（算上 TLB 可优化）。
|
||
|
||
**多级页表的 EAT（以 4 级页表为例）**：
|
||
|
||
$$
|
||
EAT = h \times (t_{TLB} + t_{mem}) + (1-h) \times (t_{TLB} + 5 \times t_{mem})
|
||
$$
|
||
|
||
例：`h=98%, t_TLB=20ns, t_mem=100ns`：
|
||
$$
|
||
EAT = 0.98 \times 120 + 0.02 \times 520 = 117.6 + 10.4 = 128 \text{ ns}
|
||
$$
|
||
|
||
#### 6. 反置页表（Inverted Page Table）
|
||
|
||
**传统页表的问题**：
|
||
- 面向进程空间：每个进程一个页表，每个逻辑页一项；
|
||
- 当进程空间很大时（如 64 位），页表占用空间巨大。
|
||
|
||
**反置页表思路**：
|
||
- 面向**物理内存空间**：每个物理页框对应一个表项；
|
||
- 表项大小固定（与内存大小成正比，与进程数无关）；
|
||
- 表项内容：(进程号 pid, 逻辑页号 p)；
|
||
|
||
**工作原理**：
|
||
1. 由进程提供逻辑地址 `(pid, p, d)`；
|
||
2. 在反置页表中查找表项，使 `(pid, p)` 匹配 → 得到对应的物理页框号 `f`；
|
||
3. `f` 与 `d` 合并 → 物理地址 `(f, d)`。
|
||
|
||
**性能问题与优化**：
|
||
- 查找反置页表平均需要扫描表长度的一半，速度慢；
|
||
- **散列（Hash）**：先对 `(pid, p)` 做散列，在散列表中定位；为解决冲突加入**冲突计数**；
|
||
- **进一步优化**：在散列表前再加快表（TLB）缓存。
|
||
|
||
---
|
||
|
||
### 6.3.3 分段式存储管理（Segmentation）
|
||
|
||
#### 1. 基本原理
|
||
|
||
- **内存划分**：**动态异长**，每区一段；
|
||
- **进程空间划分**：**若干段**，每段一个程序单位（如主程序、子程序、数据、栈等）；
|
||
- **对应关系**：每段可装入内存中的任意连续区域；
|
||
- **逻辑地址** = `(段号 s, 段内地址 d)`，是**二维地址**；
|
||
- **物理地址** = 段首址 + 段内偏移 = `b' + d`。
|
||
|
||
> **示例**（PPT 例）：一个进程分为 `main / X / Y / D` 四段，逻辑地址 `调用 x 段 e`、`访问 d 段 a`，每段大小不同（80K/40K/20K/60K），在内存中可装入不同位置。
|
||
|
||
#### 2. 所需表目与寄存器
|
||
|
||
| 项目 | 数量 | 说明 |
|
||
|:---|:---:|:---|
|
||
| **段表** | 每进程一个 | 记录 `(段号 → 段首址 b', 段长度 l')` |
|
||
| **空闲表** | 系统一个 | `array of (addr, size)` |
|
||
| **段表首址寄存器 b** | 系统一个 | 当前进程段表首址 |
|
||
| **段表长度寄存器 l** | 系统一个 | 当前进程段数 |
|
||
| **快表 TLB** | 系统一组 | 缓存 `(段号 → 段首址, 段长)` |
|
||
|
||
#### 3. 地址映射（核心算法，必考）
|
||
|
||
**映射函数**：$\sigma: (s, d) \mapsto (b'+d) \cup \{\Omega\}$
|
||
|
||
**步骤**：
|
||
1. 由程序确定逻辑地址 `(s, d)`；
|
||
2. **查快表**：用 `s` 查 TLB 得到 `(b', l')`（命中则跳到第 6 步）；
|
||
3. **段号越界检查**：`s` 与 `l` 比较，若不满足 `0 ≤ s ≤ l-1`，越界中断；
|
||
4. **查段表**：用 `s` 和 `b` 查段表，得 `(b', l')`；
|
||
5. **填快表**：把 `(s, b', l')` 写入 TLB；
|
||
6. **段内越界检查**：`d` 与 `l'` 比较，若不满足 `0 ≤ d ≤ l'-1`，越界中断；
|
||
7. **合成物理地址**：`b' + d`。
|
||
|
||
> **重点**：
|
||
> - 段式地址映射有**两次越界检查**：先检查段号，再检查段内地址；
|
||
> - 每个段的长度可以不同，体现了**程序员视角**的程序结构；
|
||
> - 分段便于**共享**（代码段、数据段）和**保护**（每段独立设权限）。
|
||
|
||
#### 4. 段的共享
|
||
|
||
- **思想**：把同一段装入物理内存**一份**，多个进程的段表项指向它。
|
||
- **实现**：维护一个**共享段表**，记录 `段名, 共享计数, 段长, 段首址, 其他`；
|
||
- **进程段表 → 共享段表 → 共享段**（多级间接）；
|
||
- **删除共享段**：共享计数 -1，仅当计数为 0 时才真正释放。
|
||
|
||
**UNIX 例子**：正文段（text 段，多个进程共享同一份代码）：
|
||
```c
|
||
struct text {
|
||
int x_daddr; // disk address
|
||
int x_caddr; // core address, if loaded
|
||
int x_size; // size (×64)
|
||
int *x_iptr; // inode pointer
|
||
char x_count; // reference count
|
||
char x_ccount; // number of loaded reference
|
||
} text[NTEXT];
|
||
```
|
||
- `x_count`：被多少进程引用（共享计数）；
|
||
- `x_ccount`：已被装入内存的引用数；
|
||
- `p_textp`：进程 PCB 中的指针，指向所属的 text 结构。
|
||
|
||
#### 5. 段的保护
|
||
|
||
段表中增加**访问权限字段** `(R, W, E)`：
|
||
- `R`：可读；
|
||
- `W`：可写；
|
||
- `E`：可执行；
|
||
- 三者组合为 3 位编码（如 `101` 表示可读可执行不可写）。
|
||
|
||
快表中也需要保存访问权限（共享段表入口包含权限）。
|
||
|
||
---
|
||
|
||
### 6.3.4 段页式存储管理（Segmentation with Paging）
|
||
|
||
#### 1. 设计动机：段式 + 页式优点
|
||
|
||
| 维度 | 段式优点 | 页式优点 | 段页式结合 |
|
||
|:---|:---|:---|:---|
|
||
| 共享 | 便于共享 | 较难 | 段级共享 |
|
||
| 保护 | 便于按段保护 | 较粗 | 段级保护 |
|
||
| 碎片 | 外部碎片 | **无外部碎片** | 无外部碎片 |
|
||
| 程序员视角 | 接近程序结构 | 一维平铺 | 段间逻辑 + 段内分页 |
|
||
|
||
> **核心思想**：**段间是逻辑的，段内是物理的**。每个进程包含若干段，每段包含若干页。
|
||
|
||
#### 2. 基本原理
|
||
|
||
**内存划分**：
|
||
- 同页式，**静态等长**，每区 $2^i$ 字节，称为一个**页框**。
|
||
- **物理地址** = `(页架号 f, 页内地址 d)`。
|
||
|
||
**进程空间划分**：
|
||
- 一个进程包含**若干段**；
|
||
- 每个段包含**若干页**。
|
||
- **逻辑地址** = `(段号 s, 逻辑页号 p, 页内地址 d)`，三维地址（三元组）。
|
||
|
||
#### 3. 所需表目与寄存器
|
||
|
||
| 项目 | 数量 | 说明 |
|
||
|:---|:---:|:---|
|
||
| **段表** | 每进程一个 | 记录 `(段号 → 页表首址 b', 页表长 l')` |
|
||
| **页表** | 每段一个 | 记录 `(逻辑页号 → 页架号 f)` |
|
||
| **总页表** | 系统一个 | 反映物理页框占用 |
|
||
| **段表首址寄存器 b** | 系统一个 | 当前进程段表首址 |
|
||
| **段表长度寄存器 l** | 系统一个 | 当前进程段数 |
|
||
| **快表 TLB** | 系统一组 | 缓存 `(段号, 逻辑页号 → 页架号)`（快段表 + 快页表合一） |
|
||
|
||
#### 4. 地址映射（核心算法，必考）
|
||
|
||
**映射函数**：$\sigma: (s, p, d) \mapsto (f, d) \cup \{\Omega\}$
|
||
|
||
**步骤**：
|
||
1. 由程序确定逻辑地址 `(s, p, d)`；
|
||
2. **查快表**：用 `(s, p)` 查 TLB 得页架号 `f`（命中则跳到第 7 步）；
|
||
3. **段号越界检查**：`s` 与 `l` 比较，若不满足 `0 ≤ s ≤ l-1`，越界中断；
|
||
4. **查段表**：用 `s` 和 `b` 查段表得 `(b', l')`（页表首址、页表长）；
|
||
5. **页号越界检查**：`p` 与 `l'` 比较，若不满足 `0 ≤ p ≤ l'-1`，越界中断；
|
||
6. **查页表**：用 `b'` 和 `p` 查段内页表得页架号 `f`；
|
||
7. **填快表**：把 `(s, p, f)` 写入 TLB；
|
||
8. **合成物理地址**：`f` 与 `d` 合并得物理地址 `(f, d)`。
|
||
|
||
> **重点**：
|
||
> - 段页式有**两次越界检查**（段号 + 页号），没有段内偏移检查（页内偏移由硬件自动处理）；
|
||
> - 一次逻辑地址访问最多需要 **3 次内存访问**（段表 + 页表 + 数据）+ 1 次 TLB 访问；
|
||
> - 引入快表后命中率 90% 以上时性能仍可接受。
|
||
|
||
---
|
||
|
||
### 6.3.5 四种管理方式对比总结（必考大题素材）
|
||
|
||
| 对比项 | 界地址 | 页式 | 段式 | 段页式 |
|
||
|:---|:---:|:---:|:---:|:---:|
|
||
| 内存划分 | 动态异长 | 静态等长 | 动态异长 | 静态等长 |
|
||
| 进程划分 | 一段 | 若干页 | 若干段 | 段→页 |
|
||
| 逻辑地址 | 一维 (a) | 一维 (p, d) | 二维 (s, d) | 三维 (s, p, d) |
|
||
| 物理地址 | b + a | (f, d) | b' + d | (f, d) |
|
||
| 主要表 | 内存分配表 | 页表 | 段表 | 段表+页表 |
|
||
| 越界次数 | 1 | 1 | 2 | 2 |
|
||
| 外部碎片 | 有 | 无 | 有 | 无 |
|
||
| 内部碎片 | 无 | 有（最后一页） | 无 | 有 |
|
||
| 共享粒度 | 无 | 难（按页） | 易（按段） | 易（按段） |
|
||
| 保护粒度 | 粗 | 中 | 细 | 细 |
|
||
|
||
---
|
||
|
||
## 二、考点总结
|
||
|
||
### 考点 1：存储管理的五大功能
|
||
- **内容**：存储分配与去配、存储共享、存储保护、存储扩充、地址映射。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. 简述存储管理的功能。
|
||
**答**：① 存储分配与去配；② 存储共享；③ 存储保护（防越界、防越权）；④ 存储扩充（虚拟存储）；⑤ 地址映射（逻辑地址→物理地址）。
|
||
2. 地址映射的硬件支持包括哪三部分？
|
||
**答**：基址寄存器、限长寄存器、快表（TLB）。
|
||
|
||
### 考点 2：内存分区方式
|
||
- **内容**：静态/动态 × 等长/异长 = 4 种组合；常用方式：静态+等长（页式、段页式）、动态+异长（段式、界地址）。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. 段式存储管理采用的内存划分方式是？
|
||
**答**：动态异长分区。
|
||
|
||
### 考点 3：位示图（Bit Map）
|
||
- **内容**：用 1 个 bit 代表 1 页；0 表示空闲，1 表示占用；分配从头找第一个 0 改为 1；去配置 0。
|
||
- **考查方式**：选择、填空、计算。
|
||
- **可能的题目**：
|
||
1. 32 位地址空间，页长 4KB，位示图占用多少字节？
|
||
**答**：总页数 $= 2^{32}/2^{12} = 2^{20}$，位示图 $= 2^{20}$ 位 $= 2^{17}$ 字节 $= 128$ KB。
|
||
|
||
### 考点 4：动态异长分区的分配算法
|
||
- **内容**：FF（最先适应）、NF（下次适应）、BF（最佳适应）、WF（最坏适应）。重点比较优缺点。
|
||
- **考查方式**：选择、填空、简答、应用题。
|
||
- **可能的题目**：
|
||
1. 在 FF、BF、WF 算法下，已知空闲区 `[12K, 32K, 80K, 4K]`，申请 30K，各选择哪个区？
|
||
**答**：FF → 32K（首个能放下）；BF → 32K（最小能放下）；WF → 80K（最大能放下）。
|
||
2. 最佳适应算法的主要缺点是什么？
|
||
**答**：容易产生大量小碎片（外部碎片）。
|
||
|
||
### 考点 5：碎片与紧凑
|
||
- **内容**：外部碎片、内部碎片；紧凑（compaction）= 移动已分配区使空闲区连续；开销大。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. 页式存储管理存在哪类碎片？段式存储管理存在哪类碎片？
|
||
**答**：页式主要存在**内部碎片**；段式主要存在**外部碎片**。
|
||
|
||
### 考点 6：界地址（单一连续）管理
|
||
- **内容**：基址寄存器 + 限长寄存器；映射 `a → b+a`；越界检查 `0 ≤ a ≤ l-1`；双对界（I 空间 + D 空间）。
|
||
- **考查方式**：选择、填空、计算。
|
||
- **可能的题目**：
|
||
1. 进程的逻辑地址空间为 0~999，基址寄存器 b=2000，则逻辑地址 500 对应的物理地址是？
|
||
**答**：物理地址 `= b + a = 2000 + 500 = 2500`。
|
||
|
||
### 考点 7：交换与覆盖技术
|
||
- **内容**：交换（swapping）= OS 自动在内外存间调入调出进程；覆盖（overlay）= 程序员手动复用内存；可重定位程序与浮动程序。
|
||
- **考查方式**：选择、简答。
|
||
- **可能的题目**：
|
||
1. 覆盖技术与交换技术的主要区别是什么？
|
||
**答**：覆盖由程序员手动控制，常用于同一进程内的代码复用；交换由 OS 自动调度，用于缓解内存不足，调入/调出整个进程。
|
||
2. 进程被换出后再装入内存的位置可能与原位置不同，这要求程序具有什么特性？
|
||
**答**：可重定位（浮动）特性，即由 0 起始编址、与物理位置无关。
|
||
|
||
### 考点 8：页式存储管理的基本原理
|
||
- **内容**：内存和进程都按 $2^i$ 静态等长划分；逻辑地址 = `(p, d)`；物理地址 = `(f, d)`；页表项 = 页架号。
|
||
- **考查方式**：选择、填空、计算。
|
||
- **可能的题目**：
|
||
1. 某系统页面大小为 4KB，逻辑地址 32 位，则页号占多少位？
|
||
**答**：页内偏移占 12 位（$2^{12}=4096$），所以页号占 $32-12 = 20$ 位。
|
||
2. 页表的作用是什么？每个进程有几个页表？
|
||
**答**：记录本进程逻辑页到物理页框的映射；每个进程一个页表。
|
||
|
||
### 考点 9：页式地址变换（核心计算题，必考）
|
||
- **内容**：地址映射步骤 + 越界检查 + 快表 + 页表合并。
|
||
- **考查方式**：**计算大题**。
|
||
- **可能的题目**：
|
||
|
||
**例题 1**：某系统采用页式存储管理，页面大小为 1KB，进程页表长度 `l = 5`，页表首址 `b = 200`，页表内容为：
|
||
|
||
| 逻辑页号 p | 0 | 1 | 2 | 3 | 4 |
|
||
|:---:|:---:|:---:|:---:|:---:|:---:|
|
||
| 页架号 f | 3 | 5 | 1 | — | 7 |
|
||
|
||
求逻辑地址 `0 1011 1010`（即十进制 218）对应的物理地址（设快表为空）。
|
||
|
||
**答**：
|
||
- 逻辑地址 = `(p=0, d=218)`（高 5 位是页号？不，重新看题：设页长 1KB = $2^{10}$，则页内偏移占 10 位）；
|
||
- 逻辑地址二进制需 15 位（假设进程空间 32KB），p=逻辑地址高 5 位，d=低 10 位；
|
||
- 解法：把 218 写成二进制得到 `p` 与 `d`；查页表得页架号 `f`；物理地址 = `f × 1024 + d`。
|
||
- 若 `p=0`，查表得 `f=3`，物理地址 `= 3 × 1024 + 218 = 3072 + 218 = 3290`。
|
||
|
||
**例题 2**：设进程页表长 `l=5`，页表首址 `b=200`。已知页表内容：
|
||
|
||
| p | 0 | 1 | 2 | 3 | 4 |
|
||
|:---:|:---:|:---:|:---:|:---:|:---:|
|
||
| f | 5 | 8 | 12 | — | 20 |
|
||
|
||
给出逻辑地址 `0AC5H`（十六进制），求物理地址（设页内偏移 10 位，快表空）。
|
||
|
||
**答**：
|
||
- 0AC5H = `0000 1010 1100 0101` 共 16 位；
|
||
- 高 6 位为页号 `p=000010=2`，低 10 位为页内偏移 `d=10 1100 0101 = 0x2C5 = 709`；
|
||
- 查页表：`p=2 → f=12`；
|
||
- 物理地址 = `12 × 1024 + 709 = 12288 + 709 = 12997 = 0x32C5H`。
|
||
|
||
**例题 3**：系统页面大小为 4KB，进程 A 的逻辑地址空间为 64KB，页表如下：
|
||
|
||
| p | 0 | 1 | 2 | 3 | … | 15 |
|
||
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|
||
| f | 2 | 5 | 8 | 14 | … | 31 |
|
||
|
||
求逻辑地址 `0x3245` 的物理地址。
|
||
|
||
**答**：
|
||
- 4KB = $2^{12}$，页内偏移 12 位；64KB = $2^{16}$，逻辑地址 16 位，页号占 4 位；
|
||
- `0x3245 = 0011 0010 0100 0101`；
|
||
- 页号 `p = 0011 = 3`，页内偏移 `d = 0010 0100 0101 = 0x245 = 581`；
|
||
- 查页表：`p=3 → f=14`；
|
||
- 物理地址 = `14 × 4096 + 581 = 57344 + 581 = 57925 = 0xE245`。
|
||
|
||
### 考点 10：快表与有效访问时间（EAT）
|
||
- **内容**：EAT 公式：$EAT = h(t_{TLB}+t_{mem}) + (1-h)(t_{TLB} + 2t_{mem})$。
|
||
- **考查方式**：计算题。
|
||
- **可能的题目**：
|
||
1. 已知 `t_TLB = 20ns`，`t_mem = 100ns`，命中率 `h = 90%`，求 EAT。
|
||
**答**：`EAT = 0.9 × 120 + 0.1 × 220 = 108 + 22 = 130 ns`。
|
||
2. 4 级页表的 EAT 公式是什么？
|
||
**答**：`EAT = h(t_{TLB}+t_{mem}) + (1-h)(t_{TLB} + 5t_{mem})`。
|
||
|
||
### 考点 11：多级页表
|
||
- **内容**：单级页表在 32/64 位系统下太大且浪费；多级页表 + 稀疏分配；32 位常用二级页表 `(p1, p2, d)`，其中 `p1, p2` 各 10 位，`d` 占 12 位。
|
||
- **考查方式**：选择、简答、计算。
|
||
- **可能的题目**：
|
||
1. 为什么要使用多级页表？
|
||
**答**：① 单级页表占用连续大内存，多级页表按需分配；② 进程虚拟地址空间存在大量空洞（hole），单级页表会浪费内存。
|
||
2. 32 位系统，页长 4KB，二级页表中 `p1`, `p2`, `d` 各占多少位？
|
||
**答**：`d` 占 12 位，剩余 20 位分给 `p1`, `p2`，各 10 位。
|
||
|
||
### 考点 12：反置页表
|
||
- **内容**：面向物理内存，大小固定；用 `(pid, p)` 散列查找；为加速引入散列表 + TLB。
|
||
- **考查方式**：选择、简答。
|
||
- **可能的题目**：
|
||
1. 反置页表相对传统页表的优势是什么？
|
||
**答**：表大小只与物理内存大小成正比，与进程数、进程虚拟地址空间大小无关。
|
||
2. 反置页表的主要问题是什么？如何解决？
|
||
**答**：查找慢（线性扫描）；解决：① 散列技术；② 加 TLB 缓存。
|
||
|
||
### 考点 13：段式存储管理基本原理
|
||
- **内容**：内存动态异长；进程分若干段；逻辑地址 `(s, d)`；段表含 `(段首址 b', 段长 l')`。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. 段式存储管理的逻辑地址是几维？页式呢？
|
||
**答**：段式是**二维**（段号, 段内地址）；页式是**一维**（页号, 页内地址合并）。
|
||
2. 段式存储管理需要几次越界检查？检查什么？
|
||
**答**：两次：① 段号 `0 ≤ s ≤ l-1`；② 段内地址 `0 ≤ d ≤ l'-1`。
|
||
|
||
### 考点 14：段式地址变换（核心计算题，必考）
|
||
- **考查方式**：**计算大题**。
|
||
- **可能的题目**：
|
||
|
||
**例题 1**：某系统采用段式存储管理，段表首址寄存器 `b`，段表长度 `l = 4`。段表内容：
|
||
|
||
| 段号 s | 段首址 b' | 段长 l' |
|
||
|:---:|:---:|:---:|
|
||
| 0 | 100K | 30K |
|
||
| 1 | 200K | 20K |
|
||
| 2 | 350K | 50K |
|
||
| 3 | 500K | 40K |
|
||
|
||
求逻辑地址 `(s=1, d=15K)` 对应的物理地址。
|
||
|
||
**答**：
|
||
- 段号 `s=1 < l=4`，不越界；
|
||
- 查段表得 `b'=200K, l'=20K`；
|
||
- 段内地址 `d=15K ≤ l'=20K`，不越界；
|
||
- 物理地址 = `b' + d = 200K + 15K = 215K`。
|
||
|
||
**例题 2**：同上系统，求逻辑地址 `(s=2, d=60K)` 的物理地址，并说明是否有异常。
|
||
|
||
**答**：
|
||
- 段号 `s=2 < l=4`，段号不越界；
|
||
- 查段表得 `b'=350K, l'=50K`；
|
||
- 段内地址 `d=60K > l'=50K`，**段内越界**，产生越界中断。
|
||
|
||
**例题 3**：某段式系统中，段表项为 `(段号, 段首址, 段长)`，已知某进程段表：
|
||
|
||
| 段号 | 段首址 | 段长 |
|
||
|:---:|:---:|:---:|
|
||
| 0 | 100 | 50 |
|
||
| 1 | 200 | 80 |
|
||
| 2 | 400 | 30 |
|
||
| 3 | 600 | 100 |
|
||
|
||
求逻辑地址 `(0, 30)`, `(1, 90)`, `(2, 20)`, `(3, 100)` 对应的物理地址，指出越界情况。
|
||
|
||
**答**：
|
||
- `(0, 30)`：`b'+d = 100+30 = 130`（段号 0<4，段内 30≤50，正常）。
|
||
- `(1, 90)`：`b'=200, l'=80`，段内 90>80，**段内越界**。
|
||
- `(2, 20)`：`b'+d = 400+20 = 420`（正常）。
|
||
- `(3, 100)`：`b'=600, l'=100`，段内 100>100，**段内越界**（应满足 `0 ≤ d ≤ l'-1`）。
|
||
|
||
### 考点 15：段的共享与保护
|
||
- **内容**：共享段表 `(段名, 共享计数, 段长, 段首址, ...)`；进程段表 → 共享段表 → 共享段；UNIX text 段引用计数 `x_count, x_ccount`。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. 共享段表中的"共享计数"有什么作用？
|
||
**答**：记录有多少进程正在使用该段；删除共享段时仅当计数为 0 时才真正释放。
|
||
2. 段保护如何在段表中实现？
|
||
**答**：在段表项中增加访问权限字段（R, W, E），如 `101` 表示可读可执行不可写。
|
||
|
||
### 考点 16：段页式存储管理原理
|
||
- **内容**：内存静态等长；进程分若干段，每段分若干页；逻辑地址 `(s, p, d)`；段表+页表；快表存 `(s, p, f)`。
|
||
- **考查方式**：选择、填空、简答、计算。
|
||
- **可能的题目**：
|
||
1. 段页式存储管理中逻辑地址由哪三部分组成？
|
||
**答**：段号 s、逻辑页号 p、页内地址 d。
|
||
2. 段页式存储管理中需要进行几次越界检查？
|
||
**答**：两次：段号越界（`0 ≤ s ≤ l-1`）和页号越界（`0 ≤ p ≤ l'-1`）。
|
||
|
||
### 考点 17：段页式地址变换（核心计算题，必考）
|
||
- **考查方式**：**计算大题**。
|
||
- **可能的题目**：
|
||
|
||
**例题 1**：某段页式系统，段表长度 `l=3`，段表首址 `b`，段表内容：
|
||
|
||
| 段号 s | 页表首址 b' | 页表长 l' |
|
||
|:---:|:---:|:---:|
|
||
| 0 | 100 | 3 |
|
||
| 1 | 200 | 4 |
|
||
| 2 | 300 | 2 |
|
||
|
||
段 1 的页表内容：
|
||
|
||
| p | 0 | 1 | 2 | 3 |
|
||
|:---:|:---:|:---:|:---:|:---:|
|
||
| f | 5 | 10 | 8 | 20 |
|
||
|
||
求逻辑地址 `(s=1, p=2, d=750)` 对应的物理地址（页长 1KB，快表空）。
|
||
|
||
**答**：
|
||
- 段号 `s=1 < l=3`，不越界；
|
||
- 查段表 `s=1` → 页表首址 `b'=200`, 页表长 `l'=4`；
|
||
- 页号 `p=2 < l'=4`，不越界；
|
||
- 查页表 `p=2 → f=8`；
|
||
- 物理地址 = `f × 1024 + d = 8 × 1024 + 750 = 8942`。
|
||
|
||
**例题 2**：某段页式系统，页面大小 4KB，某进程的段表：
|
||
|
||
| 段号 | 页表长 | 页表首址 |
|
||
|:---:|:---:|:---:|
|
||
| 0 | 4 | 1000 |
|
||
| 1 | 3 | 2000 |
|
||
| 2 | 2 | 3000 |
|
||
|
||
段 1 的页表：
|
||
|
||
| p | 0 | 1 | 2 |
|
||
|:---:|:---:|:---:|:---:|
|
||
| f | 5 | 7 | 12 |
|
||
|
||
求逻辑地址 `(1, 2, 0x123)` 对应的物理地址。
|
||
|
||
**答**：
|
||
- 段号 `s=1 < l=3`，不越界；
|
||
- 查段表 `s=1` → 页表首址 `b'=2000`, 页表长 `l'=3`；
|
||
- 页号 `p=2 < l'=3`，不越界；
|
||
- 查页表 `p=2 → f=12`；
|
||
- 物理地址 = `f × 4096 + d = 12 × 4096 + 0x123 = 49152 + 291 = 49443 = 0xC123`。
|
||
|
||
### 考点 18：四种存储管理方式对比
|
||
- **内容**：界地址、页式、段式、段页式在地址结构、内存划分、碎片、共享、保护的对比。
|
||
- **考查方式**：**简答 / 大题**。
|
||
- **可能的题目**：
|
||
1. 试比较页式管理和段式管理的优缺点。
|
||
**答**：
|
||
- **页式**：内存静态等长，**无外部碎片**，但有内部碎片；逻辑地址一维；不便于按逻辑单位共享和保护。
|
||
- **段式**：内存动态异长，**便于按段共享和保护**，符合程序员视角；逻辑地址二维；有外部碎片。
|
||
2. 为什么说段页式管理结合了段式和页式的优点？
|
||
**答**：段页式在段间保留**段式**的逻辑结构和共享保护粒度，在段内采用**页式**消除外部碎片，因此兼顾两者优点。
|
||
|
||
### 考点 19：UNIX 存储分配（malloc/mfree）
|
||
- **内容**：`map` 结构 + `malloc` 切块 + `mfree` 相邻合并（前合并、后合并、前后合并）。
|
||
- **考查方式**：填空、简答（理解算法即可）。
|
||
- **可能的题目**：
|
||
1. `mfree` 在去配时考虑哪三种合并情况？
|
||
**答**：① 与前一个空闲区合并；② 与后一个空闲区合并；③ 同时与前后合并。
|
||
|
||
### 考点 20：交换技术的策略
|
||
- **内容**：UNIX sched 进程的交换优先级：① 外存 SRUN 进程优先移入；② 内存空间不足先移出 SWAIT/SSTOP；③ 仍不够时移出 SSLEEP/SRUN，但需满足"在外 ≥3 秒、在内 ≥2 秒"的条件（防止颠簸）。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. UNIX 系统在内存紧张时优先移出哪些状态的进程？
|
||
**答**：先移出 SWAIT、SSTOP 状态的进程；其次在满足时间条件的前提下移出 SSLEEP、SRUN 状态的进程。
|
||
|
||
---
|
||
|
||
## 附录：易错点提醒
|
||
|
||
1. **页内偏移位数 ≠ 页号位数**：一定要根据页大小 $2^i$ 确定 `i` 是页内偏移位数，剩余位数才是页号。
|
||
2. **越界条件是 `≤ l-1` 而不是 `≤ l`**：在段号、页号、段内地址、逻辑地址判断时，都是"长度减 1"。
|
||
3. **段内地址是"相对段首址"的偏移**：物理地址 = 段首址 + 段内地址，不是简单相加两个绝对地址。
|
||
4. **EAT 公式区分单级/多级页表**：单级页表多 1 次内存访问；多级页表（k 级）多 k 次内存访问。
|
||
5. **页式 vs. 段式的逻辑地址维度**：页式逻辑地址虽然写成 `(p, d)`，但实际仍是一维线性地址的拆分；段式 `(s, d)` 是真正的二维。
|
||
6. **共享段表的"共享计数"**：用于决定是否能真正释放段，与"当前已装入内存的引用数"是两个不同概念（UNIX 中 `x_count` 与 `x_ccount`）。
|
||
7. **快表的"命中"与"未命中"分支**：地址映射题必须分两支写，命中时直接合并；未命中时先查页表/段表再合并，并要更新快表。
|
||
8. **段页式只有两次越界**：段号越界 + 页号越界；段内地址 d 是页内偏移，不需要再做越界检查。 |