e2hang/Operating-System

Fork 0

Files

e2hang 85262f0831 New Exam

2026-07-01 15:05:34 +08:00

38 KiB

Raw Permalink Blame History

第六章存储管理

一、知识讲解

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 数组实现：

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$。

步骤：

由程序确定逻辑地址 a；
越界检查：0 ≤ a ≤ l-1，否则越界中断；
物理地址 = 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 为越界异常。

步骤：

由程序确定逻辑地址 (p, d)；
查快表：用 p 查 TLB 得到页架号 f（命中则跳到第 6 步）；
越界检查：p 与 l 比较，若不满足 0 ≤ p ≤ l-1，则越界中断；
查页表：用 p 和页表首址 b 查页表，得页架号 f；
填快表：把 (p, f) 写入 TLB，若 TLB 已满则淘汰一项；
合成物理地址：把 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)。

地址映射过程：

由 p1 查外页表 → 得二级页表首址；
由 p2 查二级页表 → 得页架号 f；
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)；

工作原理：

由进程提供逻辑地址 (pid, p, d)；
在反置页表中查找表项，使 (pid, p) 匹配 → 得到对应的物理页框号 f；
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\}

步骤：

由程序确定逻辑地址 (s, d)；
查快表：用 s 查 TLB 得到 (b', l')（命中则跳到第 6 步）；
段号越界检查：s 与 l 比较，若不满足 0 ≤ s ≤ l-1，越界中断；
查段表：用 s 和 b 查段表，得 (b', l')；
填快表：把 (s, b', l') 写入 TLB；
段内越界检查：d 与 l' 比较，若不满足 0 ≤ d ≤ l'-1，越界中断；
合成物理地址：b' + d。

重点：

段式地址映射有两次越界检查：先检查段号，再检查段内地址；

每个段的长度可以不同，体现了程序员视角的程序结构；

分段便于共享（代码段、数据段）和保护（每段独立设权限）。

4. 段的共享

思想：把同一段装入物理内存一份，多个进程的段表项指向它。
实现：维护一个共享段表，记录 段名, 共享计数, 段长, 段首址, 其他；
进程段表 → 共享段表 → 共享段（多级间接）；
删除共享段：共享计数 -1，仅当计数为 0 时才真正释放。

UNIX 例子：正文段（text 段，多个进程共享同一份代码）：

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\}

步骤：

由程序确定逻辑地址 (s, p, d)；
查快表：用 (s, p) 查 TLB 得页架号 f（命中则跳到第 7 步）；
段号越界检查：s 与 l 比较，若不满足 0 ≤ s ≤ l-1，越界中断；
查段表：用 s 和 b 查段表得 (b', l')（页表首址、页表长）；
页号越界检查：p 与 l' 比较，若不满足 0 ≤ p ≤ l'-1，越界中断；
查页表：用 b' 和 p 查段内页表得页架号 f；
填快表：把 (s, p, f) 写入 TLB；
合成物理地址：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。

逻辑页号 p	0	1	2	3	4
页架号 f	3	5	1	—	7

p	0	1	2	3	4
f	5	8	12	—	20

p	0	1	2	3	…	15
f	2	5	8	14	…	31

考点 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）。

段号 s	段首址 b'	段长 l'
0	100K	30K
1	200K	20K
2	350K	50K
3	500K	40K

段号	段首址	段长
0	100	50
1	200	80
2	400	30
3	600	100

考点 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。

段号 s	页表首址 b'	页表长 l'
0	100	3
1	200	4
2	300	2

p	0	1	2	3
f	5	10	8	20

段号	页表长	页表首址
0	4	1000
1	3	2000
2	2	3000

p	0	1	2
f	5	7	12

考点 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 状态的进程。

附录：易错点提醒

页内偏移位数 ≠ 页号位数：一定要根据页大小 2^i 确定 i 是页内偏移位数，剩余位数才是页号。
越界条件是 ≤ l-1 而不是 ≤ l：在段号、页号、段内地址、逻辑地址判断时，都是"长度减 1"。
段内地址是"相对段首址"的偏移：物理地址 = 段首址 + 段内地址，不是简单相加两个绝对地址。
EAT 公式区分单级/多级页表：单级页表多 1 次内存访问；多级页表（k 级）多 k 次内存访问。
页式 vs. 段式的逻辑地址维度：页式逻辑地址虽然写成 (p, d)，但实际仍是一维线性地址的拆分；段式 (s, d) 是真正的二维。
共享段表的"共享计数"：用于决定是否能真正释放段，与"当前已装入内存的引用数"是两个不同概念（UNIX 中 x_count 与 x_ccount）。
快表的"命中"与"未命中"分支：地址映射题必须分两支写，命中时直接合并；未命中时先查页表/段表再合并，并要更新快表。
段页式只有两次越界：段号越界 + 页号越界；段内地址 d 是页内偏移，不需要再做越界检查。

38 KiB Raw Permalink Blame History Unescape Escape

第六章 存储管理

一、知识讲解

6.1 存储管理功能

1. 存储分配和去配

2. 存储共享

3. 存储保护

4. 存储扩充（虚拟存储）

5. 地址映射（地址翻译 / Address Translation）

6.2 内存资源管理

6.2.1 内存分区

6.2.2 内存分配

(1) 静态等长分区的分配（每"页"为单位）

(2) 动态异长分区的分配（每"区"为单位）

(3) UNIX 存储分配（FF 的经典实现）

6.2.3 碎片处理

6.3 存储管理方式

6.3.1 界地址管理方式

1. 基本原理

2. 所需表目

3. 所需寄存器

4. 地址映射

5. 双对界（Dual Bounds）

6. 交换技术（Swapping）

7. 覆盖技术（Overlay）

6.3.2 分页式存储管理（Paging）

1. 基本原理

2. 所需表目与寄存器

3. 地址映射（核心算法，必考）

4. 快表与有效访问时间（EAT）

5. 多级页表（Multi-Level Page Table）

6. 反置页表（Inverted Page Table）

6.3.3 分段式存储管理（Segmentation）

1. 基本原理

2. 所需表目与寄存器

3. 地址映射（核心算法，必考）

4. 段的共享

5. 段的保护

6.3.4 段页式存储管理（Segmentation with Paging）

1. 设计动机：段式 + 页式优点

2. 基本原理

3. 所需表目与寄存器

4. 地址映射（核心算法，必考）

6.3.5 四种管理方式对比总结（必考大题素材）

二、考点总结

考点 1：存储管理的五大功能

考点 2：内存分区方式

考点 3：位示图（Bit Map）

考点 4：动态异长分区的分配算法

考点 5：碎片与紧凑

考点 6：界地址（单一连续）管理

考点 7：交换与覆盖技术

考点 8：页式存储管理的基本原理

考点 9：页式地址变换（核心计算题，必考）

考点 10：快表与有效访问时间（EAT）

考点 11：多级页表

考点 12：反置页表

考点 13：段式存储管理基本原理

考点 14：段式地址变换（核心计算题，必考）

考点 15：段的共享与保护

考点 16：段页式存储管理原理

考点 17：段页式地址变换（核心计算题，必考）

考点 18：四种存储管理方式对比

考点 19：UNIX 存储分配（malloc/mfree）

考点 20：交换技术的策略

附录：易错点提醒

38 KiB

Raw Permalink Blame History

第六章存储管理