第五章：内存管理
5.1 内存管理的基本概念
内存管理是OS对内存空间的分配和回收。好比图书馆的阅览室管理员——不同的读者（进程）需要不同的区域（内存空间），管理员要合理分配座位，还要记录谁占了哪儿。
5.1.1 逻辑地址与物理地址
| 地址类型 | 定义 | 来源 |
|---|---|---|
| 逻辑地址（虚拟地址） | CPU生成的地址 | 编译后的程序 |
| 物理地址 | 内存单元的真实地址 | 地址转换后 |
地址转换：程序中的逻辑地址 → OS/硬件转换为物理地址。
5.1.2 程序的装入和链接
链接方式：
- 静态链接：在程序运行前将所有目标模块链接成一个完整的可执行文件。
- 装入时动态链接：装入内存时边装入边链接。
- 运行时动态链接：运行时需要某模块时才链接（节省内存，常用）。
装入方式：
- 绝对装入：程序中的地址就是物理地址（只适合单道程序环境）。
- 可重定位装入：装入时一次性将逻辑地址转换为物理地址（静态重定位）。
- 动态运行时装入：运行时每访问一次地址就转换一次（动态重定位，需要MMU硬件支持——现代OS标准）。
💡 记忆技巧：三种装入方式的区别在于"什么时候转换地址"——绝对装入（编译时）、可重定位装入（装入时）、动态运行时装入（运行时）。
5.2 连续分配管理方式
5.2.1 单一连续分配
内存分为系统区和用户区，用户区一次只给一道程序用。早期单道批处理使用。简单但浪费严重。
5.2.2 固定分区分配
内存划分为固定大小的区域，每个分区可装一道作业。分为分区大小相等和分区大小不等。
- 优点：实现简单。
- 缺点：分区内碎片（内部碎片——分区没装满的部分），分区数量固定，多道程度受限。
5.2.3 动态分区分配
不再预分固定区域，而是根据进程需求动态划分。随着进程的创建和终止，内存会产生外部碎片（各分区之间的空隙）。
解决外部碎片：紧凑技术（移动进程内容，使其连续排列）——代价高（需要动态重定位支持）。
📌 408考点提示：内部碎片（固定分区有）vs 外部碎片（动态分区有）是常见选择题。
5.3 动态分区分配算法
| 算法 | 策略 | 优点 | 缺点 |
|---|---|---|---|
| 首次适应（FF） | 从低地址开始找第一个满足的分区 | 简单、速度快 | 低地址留下小碎片 |
| 最佳适应（BF） | 找到满足要求的最小分区 | 保留大分区 | 产生很多小碎片 |
| 最坏适应（WF） | 找到最大的分区 | 减少小碎片产生 | 大分区很快被切小 |
| 邻近适应（NF） | 从上次分配位置继续找 | 不用每次从头扫描 | 高地址也产生碎片 |
📌 408考点提示：四种算法的对比选择题常见。首次适应（FF）是实际系统中使用最广泛的算法。
5.4 非连续分配管理方式
5.4.1 基本分页存储管理
基本思想：把逻辑地址空间分成大小相等的页（Page），物理内存分成同样大小的页框/页帧（Page Frame），通过页表实现映射。
页表：记录逻辑页号→物理页框号的映射关系。每个进程有自己的页表。
地址转换过程：
- 逻辑地址 = 页号 + 页内偏移
- 查页表：页号 → 页框号
- 物理地址 = 页框号 × 页大小 + 页内偏移
计算示例：
- 逻辑地址32位，页大小4KB（2^12）→ 页号20位，页内偏移12位
- 页表项4字节 → 页表大小 = 2^20 × 4B = 4MB
快表（TLB——Translation Lookaside Buffer）：
- 页表在内存中，每次访问内存都要查页表（多一次内存访问）。
- TLB是CPU中的高速缓存（类似Cache），存储最近使用的页表项。
- 引入TLB后：先在TLB中查找 → 找到（TLB命中）直接转换；找不到再到内存查页表。
有效访问时间（EAT）计算：
- 设TLB命中率 = a，TLB访问时间 = t，内存访问时间 = m
- TLB命中时：t + m（查TLB + 访问内存）
- TLB未命中时：t + 2m（查TLB + 查页表 + 访问内存——实际上查页表也需要一次内存访问）
- EAT = a × (t + m) + (1-a) × (t + 2m) = t + m + (1-a) × m
5.4.2 基本分段存储管理
基本思想：程序按逻辑分段（如主程序段、数据段、栈段），每段有自己的名字和长度。
段表：记录段号→基址+段长。
地址转换：逻辑地址（段号+段内地址）→ 查段表 → 基址+段内地址 → 物理地址。
分段vs分页：
| 对比 | 分页 | 分段 |
|---|---|---|
| 目的 | 提高内存利用率（消除外部碎片） | 满足编程逻辑（模块化） |
| 大小 | 固定（由OS决定） | 可变（由程序决定） |
| 地址空间 | 一维（线性地址） | 二维（段号+段内地址） |
| 用户可见性 | 用户不可见 | 用户可见（编程时考虑分段） |
| 共享 | 较难 | 容易（按段共享） |
5.4.3 段页式管理
结合了分页和分段：先分段，每段内再分页。
- 逻辑地址 = 段号 + 段内页号 + 页内偏移
- 需要段表（段号→页表地址）和页表（页号→页框号）
- 地址转换：段表→页表→物理地址（三次内存访问，但TLB可以加速）
5.5 虚拟内存
5.5.1 局部性原理
虚拟内存的理论基础是局部性原理：
- 时间局部性：刚访问过的地址很可能再次被访问（循环）。
- 空间局部性：刚访问过的地址附近的地址很可能被访问（顺序执行）。
5.5.2 虚拟内存的概念
虚拟内存：将程序的一部分装入内存，其余部分放在磁盘上。程序可以使用比物理内存更大的地址空间。
实现方式：
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
虚拟内存的特征：
- 多次性：作业分多次调入内存。
- 对换性：作业可以在内存和磁盘间对换。
- 虚拟性：逻辑上扩充内存容量。
5.5.3 请求分页管理方式
页表机制：在基本分页页表的基础上增加状态位（是否在内存）、访问字段（记录访问次数/时间）、修改位（是否被修改）、外存地址。
缺页中断：当访问的页不在内存时，CPU触发缺页中断——从磁盘将页调入内存。缺页中断属于内中断/异常中的故障（fault）。
地址变换过程：
- 访问逻辑地址，解析页号+偏移。
- 查TLB：命中→得到页框号→拼成物理地址→访问数据。
- TLB未命中：查内存中的页表——如果该页在内存中，更新TLB，访问数据。
- 如果该页不在内存中：触发缺页中断→从磁盘调入→更新页表和TLB→重执行指令。
📌 408考点提示：请求分页的地址转换过程（含TLB和缺页中断处理）是综合题的常见素材。
5.5.4 页面置换算法
当内存已满而需要调入新页时，必须置换某个页面。
| 算法 | 策略 | 是否可能产生Belady异常 | 评价 |
|---|---|---|---|
| OPT（最佳置换） | 置换未来最长时间不再访问的页 | 否 | 理论最优，无法实现 |
| FIFO（先进先出） | 置换最先进入内存的页 | 是 | 简单但性能差 |
| LRU（最近最久未使用） | 置换最长时间未使用的页 | 否 | 性能好，但需硬件支持 |
| CLOCK（NRU——最近未使用） | 扫描页的访问位，第一轮找0，第二轮清0重找 | 否 | 近似LRU，常用 |
⚠️ 易错点：
- FIFO的Belady异常：分配的页面增多，缺页率反而上升。只有FIFO有此问题。
- LRU需要硬件计数器或栈支持，实现成本高。
- CLOCK算法（NRU） 是LRU的近似实现——给每个页一个访问位，循环扫描。
缺页率计算：缺页次数 / 总访问次数。
💡 记忆技巧：OPT=预知未来（不能实现），FIFO=先进先出（像排队），LRU=看过去（最久没用过），CLOCK=转圈检查（像钟表扫描）。
5.6 页面分配策略
5.6.1 分配策略
| 策略 | 物理块数量 | 置换范围 |
|---|---|---|
| 固定分配局部置换 | 固定 | 只能置换自己的页 |
| 可变分配全局置换 | 可变 | 可从全局空闲中取 |
| 可变分配局部置换 | 可变（可增减） | 只能置换自己的页 |
5.6.2 工作集与抖动
- 工作集：进程在一段时间内频繁访问的页面集合。
- 抖动（颠簸）：分配给进程的物理块太少，导致频繁缺页——CPU忙于换页，利用率急剧下降。
解决方法：采用工作集模型——确保分配给进程的物理块数 ≥ 工作集大小。
5.7 内存映射文件
内存映射文件（Memory-Mapped File）：将磁盘文件映射到虚拟地址空间的一个区域。访问该区域就像访问内存一样——由OS在背后自动处理换页。
优点：统一了文件访问和内存访问；多个进程可以共享同一映射。
示例题
示例1（地址转换）：页面大小为4KB，某页表内容如下。逻辑地址为：0x2A3C，求物理地址。
假定页表：页号0→页框号3, 页号1→页框号7, 页号2→页框号1, 页号3→页框号5
解：页面大小4KB=2^12，所以页内偏移占12位。 0x2A3C = 0010 1010 0011 1100（二进制） 高20位（这里简化为高4位示意）为页号=2（0x2），低12位为页内偏移=0xA3C 查页表：页号2→页框号1 物理地址 = 1 × 4096 + 0xA3C = 4096 + 2620 = 0x1A3C 实际物理地址 = 0x1000 + 0xA3C = 0x1A3C
示例2（页面置换——LRU）：页面访问序列：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2，分配3个页框。求LRU的缺页次数。
解（手动模拟）：
| 步 | 访问 | 页框1 | 页框2 | 页框3 | 是否缺页 |
|---|---|---|---|---|---|
| 1 | 7 | 7 | - | - | 缺 |
| 2 | 0 | 7 | 0 | - | 缺 |
| 3 | 1 | 7 | 0 | 1 | 缺 |
| 4 | 2 | 2 | 0 | 1 | 缺（替换7——最久未用） |
| 5 | 0 | 2 | 0 | 1 | 已存在，不换 |
| 6 | 3 | 2 | 0 | 3 | 缺（替换1——最久未用） |
| 7 | 0 | 2 | 0 | 3 | 已存在 |
| 8 | 4 | 4 | 0 | 3 | 缺（替换2——最久未用） |
| 9 | 2 | 4 | 0 | 2 | 缺（替换3） |
| 10 | 3 | 4 | 3 | 2 | 缺（替换0——最久未用） |
| 11 | 0 | 0 | 3 | 2 | 缺（替换4） |
| 12 | 3 | 0 | 3 | 2 | 已存在 |
| 13 | 2 | 0 | 3 | 2 | 已存在 |
| 14 | 1 | 0 | 1 | 2 | 缺（替换3——最久未用） |
| 15 | 2 | 0 | 1 | 2 | 已存在 |
缺页次数：10次。缺页率 = 10/15 ≈ 66.7%
示例3（有效访问时间计算）：TLB命中率98%，TLB访问时间10ns，内存访问时间100ns。求有效访问时间（假设TLB未命中时访问页表需一次内存访问）。
解：EAT = 0.98 × (10 + 100) + 0.02 × (10 + 100 + 100) = 0.98 × 110 + 0.02 × 210 = 107.8 + 4.2 = 112 ns
对比无TLB的情况：每次访问需查页表（100ns）+ 访问数据（100ns）= 200ns，TLB使性能提升了约44%。
本章小结
内存管理是操作系统的核心功能之一。重点掌握：逻辑地址到物理地址的转换（分页/分段/段页式）、连续分配算法的对比、页面置换算法的缺页率计算（OPT/FIFO/LRU/CLOCK）、虚拟内存的概念和工作原理。地址转换计算和缺页率模拟是408的常见考题，需要多练习。