---
title: "06-内存管理：从连续分配到虚拟内存"
aliases:
  - 内存管理
created: 2026-08-29
tags:
  - 基础与理论
  - 操作系统
  - "408"
---

# 内存管理：从连续分配到虚拟内存

> 本篇对应王道第三章（原 12 内存管理概念 + 13 虚拟内存管理合并）。前半解决"**内存怎么装**"（连续 → 分页 → 分段 → 段页式），后半解决"**装不下怎么办**"（虚拟内存与页面置换）。

## 一、内存管理的基本要求

内存容量再大也不可能装下所有进程的全部程序和数据，OS 必须对内存进行合理的划分和动态分配。五大功能：

- **分配与回收**：记录空闲空间和分配情况，回收结束进程的内存
- **地址转换**：逻辑地址 → 物理地址
- **内存扩充**：虚拟存储技术从逻辑上扩充
- **内存共享**：多个进程访问内存同一部分（受控访问）
- **存储保护**：各进程在各自空间内运行，互不干扰

### 程序怎么进内存：编译、链接、装入

源程序变成可执行程序的三步：**编译**（源代码 → 目标模块）→ **链接**（目标模块 + 库函数 → 完整装入模块）→ **装入**（装入模块 → 内存）。

![[image-70f9e389.png]]

**三种装入方式**：

| 方式 | 地址转换时机 | 特点 |
| --- | --- | --- |
| **绝对装入** | 编译时就知道放哪，直接生成绝对地址 | 只适用于**单道程序**，逻辑地址 = 物理地址 |
| **可重定位装入（静态重定位）** | **装入时一次完成**地址转换 | 作业一旦进内存**不能移动**、不能再申请空间 |
| **动态运行时装入（动态重定位）** | **推迟到真正执行时**才转换 | 需**重定位寄存器**（存起始位置）；程序可分散存放、可部分装入、便于共享——现代系统用这个 |

**三种链接方式**：**静态链接**（运行前链成整体，不再拆开）、**装入时动态链接**（边装入边链接，便于更新和共享）、**运行时动态链接**（用到才链接，加快装入、省内存——未用到的模块根本不调入）。

### 逻辑地址与物理地址

- **逻辑地址**（相对地址/虚拟地址空间）：编译后每个目标模块从 0 号单元开始编址，链接后构成统一的逻辑地址空间。**进程运行时看到和使用的都是逻辑地址**，不同进程可以有相同的逻辑地址（映射到主存不同位置）
- **物理地址**：内存中物理单元的集合，地址转换的终点

转换由 **MMU（内存管理部件）** 完成，页表由 OS 维护、处理器引用。

### 进程的内存映像

程序调入内存运行后就构成进程的内存映像：

![[image-d33fdb72.png]]

| 区域 | 内容 | 特点 |
| --- | --- | --- |
| **代码段** | 二进制代码（text、rodata、init） | **只读**，可多进程共享 |
| **数据段** | 全局/静态变量（data 已初始化、bss 未初始化） | 大小在调入时确定 |
| **堆** | malloc 动态分配的变量 | **向高地址增长**，运行时动态伸缩 |
| **栈** | 函数调用（返回地址、局部变量） | 从最大地址**向低增长**，调用则长、返回则缩 |
| **PCB** | 控制管理信息 | 放在**系统区** |

（这段和进程那章的"C 程序三段"闭环上了：正文段=代码+常量+已赋值全局，堆=malloc，栈=局部变量。）

### 内存保护

两种方法：

1. CPU 设一对**上、下限寄存器**，访问地址与两者比较判断越界
2. **重定位寄存器（基址）+ 界地址寄存器（限长）**：重定位寄存器存进程起始**物理地址**，界地址寄存器存进程最大**逻辑地址**；先比较（界地址寄存器管"**比**"），不越界再加基址（重定位寄存器管"**加**"）映射成物理地址

![[image-0bcc6352.png]]

加载这两个寄存器必须用**特权指令**——只有内核能改，用户程序不能。

### 内存共享

只有**只读区域**才适合共享。**可重入代码（纯代码）**：允许多进程同时访问、不允许任何进程修改；执行中可能改变的部分复制到各进程私有的局部数据区。

算一笔账：40 个用户同时跑一个 160KB 代码 + 40KB 数据的编辑器——不共享要 40×200=8000KB；代码是纯代码共享一份的话只要 40×40+160=**1760KB**。而且**分段共享更简单**：分页系统每个进程要建 40 个页表项指向共享区，分段系统不管段多大只需**一个段表项**。

### 存储管理方式的演进

```
单一连续分配 → 固定分区 → 动态分区        （连续分配时代）
           ↘ 基本分页（提高利用率）↘ 基本分段（满足用户需求）↘ 段页式
```

## 二、连续分配管理方式

给用户程序分配一个**连续**的内存空间。

### 单一连续分配

内存分系统区（低地址，OS 专用）+ 用户区（仅一道用户程序独占）。优点：简单、**无外部碎片**、无需保护（永远只有一道程序）。缺点：只适用于单用户单任务；**有内部碎片**；利用率极低。

### 固定分区分配

用户空间划成若干**固定大小**分区，每区装一道作业。分区大小相等（简单但浪费）或不等（小/中/大搭配）。用**分区使用表**（始址、大小、状态）管理。

问题：程序太大放不进任何分区；程序小也要占一整区——**内部碎片**。无外部碎片，但利用率低。

### 动态分区分配

进程装入时**按实际需要**动态分配，分区大小数量都可变。

![[image-237110c0.png]]

随时间推移，内存中产生越来越多的小内存块——**外部碎片**（在所有分区的外部，与固定分区的内部碎片相对）。外部碎片可用**紧凑**技术克服（不时移动整理进程，需要动态重定位寄存器支持，费时）——类似 Windows 的磁盘碎片整理，只不过那是对外存的。

**内存回收四种情况**（回收区与插入点的前/后空闲分区的关系）：与前相邻 → 合并改前项大小；与后相邻 → 合并改后项始址和大小；前后都相邻 → 三者合并、取消后项；都不相邻 → 新建表项插入链。

### 四种顺序搜索算法（必背）

| 算法 | 排列方式 | 特点 |
| --- | --- | --- |
| **首次适应 First Fit** | 按地址**递增** | 找第一个够大的。**保留高地址大分区**利于大作业；低地址小碎片多、查找开销增。**综合性能最好、开销小，回收不必重新排序** |
| **邻近适应 Next Fit**（循环首次适应） | 同上，但从**上次结束位置**接着找 | 低/高地址分区被同等概率分配 → 高地址没有大分区可用，**通常比首次适应差** |
| **最佳适应 Best Fit** | 按**容量递增** | 找**最小**的够用分区。名字骗人——每次分配留下越来越多难以利用的小块，**外部碎片最多** |
| **最坏适应 Worst Fit** | 按**容量递减** | 找**最大**的分区切一块。看似不易产生碎片，但很快没有大分区可用，性能也差 |

### 基于索引搜索的分配算法（大中型系统）

空闲分区链太长时顺序搜索太慢，按**大小分类**建链 + 索引表管理：

- **快速适应**：按进程常用空间大小分类；分配时找能容纳的最小链取第一块。查找快、无内部碎片，但**回收合并复杂**
- **伙伴系统**：所有分区大小均为 **2 的 K 次幂**。要 n（2^(i-1) < n ≤ 2^i）就到 2^i 的链找；没有就把 2^(i+1) 的分区**等分成一对伙伴**，一个分配一个入链；回收时可能合并伙伴
- **哈希算法**：以分区大小为关键字建哈希表，直接定位分区链

连续分配的天花板：即使内存有超过 1GB 的空闲空间，但没有**连续**的 1GB，需要 1GB 的作业照样跑不了——这就引出了离散分配。

## 三、基本分页存储管理

**思想**：内存分成固定大小的**页框/页帧/物理块**；进程逻辑空间分成同样大小的**页/页面**；以页框为单位分配。进程只在最后一个不完整的块产生碎片，平均每个进程只产生**半页**的内部碎片（页内碎片）。

### 地址结构与页表

![[image-a325ee01.png]]

地址结构 = **页号 P + 页内偏移量 W**。32 位地址、页内 12 位 → 每页 4KB、最多 2^20 页。**地址结构决定了虚拟地址空间的寻址范围**。页面大小应是 2 的整数次幂且适中：太小 → 页表过长、转换开销大；太大 → 页内碎片多。

**页表**：每个进程一张，页号 → 物理块号的映射。页表项连续存放，**页号是隐含的、不占存储空间**。

![[image-37352012.png]]

### 基本地址变换机构

![[image-a076ed12.png]]

- **页表寄存器（PTR）**：存页表始址 F 和页表长度 M。进程未执行时存 PCB 里，被调度时才装入（寄存器贵，单 CPU 只设一个）
- 变换：逻辑地址 A → 页号 P = A / L，页内偏移 W = A % L → 越界检查（P ≥ M 则越界中断）→ 查页表得块号 b → 物理地址 E = b×L + W

![[image-6a6fbcbf.png]]

两个问题：① 每次访存都要地址转换，必须够快；② 页表不能太大，否则内存利用率低。下面两节分别对症下药。

### 快表 TLB：解决"转换慢"

页表全在内存 → 存一个数据**至少访存两次**（查页表 + 取数据），速度慢一半。解决：加一个**具有并行查找能力**的高速缓冲存储器——**快表（TLB，相联存储器）**，存放当前访问的若干页表项；内存中的页表相应叫**慢表**。

![[image-a9f040be.png]]

![[image-32bc0710.png]]

流程：先查快表，**命中**直接拼物理地址（一次访存）；**未命中**再查慢表，并把该表项**同时写入快表**（快表满则按某种算法替换）。

### 两级页表：解决"页表太大"

32 位系统、4KB 页、4B 页表项：页表项可达 2^20 个，页表本身要占 2^20×4B/4KB = **1K 个页**，而且要求**连续**——不切实际。

两个解法：① 页表所需的内存空间**离散分配**，用一张索引表记录各页表位置；② 只把需要的页表项调入内存（虚拟内存思想）。

方案①就是**给页表再建一层页表**——外层页表（页目录）：

![[image-33014067.png]]

![[image-cb833a8d.png]]

外层页表 1K 个表项正好占一页。新增**外层页表寄存器（页目录基址寄存器）**，变换时：页目录号 → 找页表始址 → 二级页号 → 找页表项 → 拼物理地址。**三次访存**（可以再用快表优化，关键字为段号+页号）。

64 位系统两级还不够（外层页表要 16384GB 连续内存），得**多级页表**——本质都是建立索引，避免存无用的页表项。

## 四、基本分段存储管理

**分页是从计算机角度设计的**（提高利用率，硬件机制实现，对用户透明）；**分段是为用户设计的**——方便编程、信息保护共享、动态增长、动态链接。

进程按**逻辑结构**划分为大小不等的段（主程序段、子程序段、栈段、数据段……），**每段从 0 编址、段内连续、段间不要求连续**。逻辑地址 = **段号 S + 段内偏移量 W**。

![[image-3284241f.png]]

⚠️ 分页的页号页内偏移对用户**透明**（一个整数除余即得）；分段的段号和偏移必须**用户显式提供**（编译程序完成）——这就是一维与二维的区别。

### 段表与地址变换

段表项记录**段始址 + 段长**（注意：比页表项多一个"长度"，因为段不等长）。

![[image-a4e9284f.png]]

变换：段号 S 与段表长度 M 比较（越界中断）→ 查段表得始址和段长 → 偏移量 W 与段长比较（越界中断）→ 物理地址 = 段始址 + W。

### 段的共享与保护

共享：每进程段表里放**一个段表项**指向同一物理段即可（分页要 N 个页表项）。纯代码（可重入代码）+ 各进程私有数据区。

保护：**存取控制** + **地址越界保护**（两次比较：段号 vs 段表长度；段内偏移 vs 段长）。分页只需判断页号越界——**页内偏移不可能越界**。

## 五、分页 vs 分段（必考对比）

| | 分页 | 分段 |
| --- | --- | --- |
| 单位本质 | **信息的物理单位** | **信息的逻辑单位** |
| 目的 | 提高内存利用率（系统需要） | 满足用户需求（方便编程、共享、保护） |
| 可见性 | 对用户**不可见**，系统行为 | 对用户**可见**，用户按逻辑划分 |
| 大小 | **固定**，由系统决定 | **不固定**，取决于程序 |
| 地址空间 | **一维**（一个整数除余即得页号+偏移） | **二维**（必须显式给段号+偏移） |
| 碎片 | 页内碎片（内部），无外部碎片 | 段内碎片（内部），无外部碎片（段间空隙可整段利用） |
| 共享保护 | 麻烦（N 个页表项） | 简单（1 个段表项） |

## 六、段页式存储管理

先分段（逻辑结构、共享保护），**段内再分页**（内存按页框分配）——两种方式取长补短。

![[image-e95da528.png]]

逻辑地址 = **段号 + 页号 + 页内偏移**三段。每个进程一张段表（段表项：段号、页表长度、**页表始址**），**每段一张页表**（页表项：页号、块号）。

⚠️ **每个进程的段表只有一个，页表可能有多个**。地址变换：段表查页表始址 → 页表查块号 → 拼物理地址，**三次访存**（同样可用快表加速，关键字 = 段号+页号）。段页式的地址空间是**二维**的。

## 七、虚拟内存：装不下怎么办

### 传统方式的两个死穴

之前所有管理方式都有两个共同特征，也是两个共同问题：

1. **一次性**：作业必须一次性全部装入才能运行——作业太大装不下就**跑不了**；大量作业要求运行时只能少数先跑，**并发度下降**
2. **驻留性**：装入后就一直驻留到结束——大量暂时不用的程序数据占着内存，要跑的作业又进不来

### 局部性原理

虚拟内存的依据是**局部性原理**（快表、页高速缓存都靠它）：

- **时间局部性**：某条指令/数据被执行（访问）过，不久后可能再次执行——源于**循环**
- **空间局部性**：访问了某个存储单元，附近的单元也将被访问——指令顺序存放顺序执行、数据以数组/表形式簇聚存储

### 虚拟存储器

基于局部性：**装入时只装当前要用的少数页面**，其余留在外存即可启动；执行中访问的信息不在内存 → 由 OS 调入（**请求调页**）；内存不够 → 暂时不用的换出（**页面置换**）。用户感觉有一个比实际大得多的存储器——**虚拟存储器**。容量大只是**错觉，是虚的**。

三个特征：

- **多次性**：分多次调入（**最重要的特征**，与一次性的根本区别）
- **对换性**：运行中可换入换出（虚拟存储器正常运行的表现）
- **虚拟性**：逻辑上扩充容量（**最重要的目标**）

**实现前提：必须建立在离散分配之上**（连续分配做不到逻辑扩充）。三种实现：请求分页、请求分段、请求段页式。硬件支持：一定容量内存+外存、页表机制、**缺页中断机构**、地址变换机构。

### 请求分页：页表多了四个字段

![[image-e7fc8f73.png]]

| 字段 | 作用 |
| --- | --- |
| **状态位 P** | 该页是否已调入内存 |
| **访问字段 A** | 一段时间内被访问次数/多久未被访问——置换算法的参考 |
| **修改位 M** | 调入后是否被修改——决定换出时**要不要写回外存** |
| **外存地址** | 该页在外存的存放地址（物理块号） |

### 缺页中断

访问的页面不在内存 → 产生**缺页中断**，进程阻塞入阻塞队列，调页完成后再唤醒。内存有空闲页框就装入并改页表；没有则按置换算法淘汰一页——**被淘汰页若被修改过还要写回外存**（没改过不用写，直接覆盖）。

与一般中断的两个区别：

- 在**指令执行期间**产生和处理（一条指令执行中），属于**内部异常**
- **一条指令执行期间可能产生多次缺页中断**（如 copy 指令跨页）

### 请求分页的地址变换流程

![[image-b311eb03.png]]

1. 查**快表** → 命中：取块号（写指令置修改位）
2. 未命中查**页表** → 找到：取块号并写入快表
3. 页表也没有 → **缺页中断处理**：调页入内存，更新页表和快表
4. 块号 + 页内偏移 → 物理地址 → 访存

### 页框分配

**驻留集**：给一个进程分配的页框集合。太小 → 缺页率高、CPU 忙于处理缺页；太大 → 超过一定数目后再加改善不明显，浪费内存、并发度下降。

三种分配+置换组合策略：

| 策略 | 置换范围 | 特点 |
| --- | --- | --- |
| **固定分配全局置换** | — | **不存在**！固定了还给全局抢，矛盾 |
| **固定分配局部置换** | 只从自己的页面里换 | 难以确定该给多少 |
| **可变分配全局置换** | 空闲队列取 + 可以抢别的进程的 | 灵活但盲目加块，伤并发度 |
| **可变分配局部置换** | 只换自己的；缺页频繁就加块，缺页率特别低就减块 | 兼顾，但要更复杂的实现 |

物理块分配算法（固定分配时）：平均分配、按比例分配、优先权分配（重要紧迫的进程多分）。

**调页时机**：**预调页**（预测要用的页预先调入，成功率约 50%，主要用于进程首次装入）；**请求调页**（缺了才调，一定被访问、易实现，主流方案，缺点是每次一页、磁盘 IO 开销大）。

**从哪调入**：外存分文件区（离散分配）和对换区（连续分配，IO 更快）——① 对换区够 → 全从对换区调（相关文件先复制过去）；② 对换区不够 → 不会被修改的从文件区调（换出时直接丢弃），可能修改的换出时放对换区；③ UNIX 方式 → 没跑过的从文件区调，跑过被换出的从对换区调，共享页已被调入就不用再调。

## 八、页面置换算法

内存满了，淘汰谁？目标：**最低缺页率**（换入换出要磁盘 IO，开销大）。

### OPT：最佳置换（不可实现）

淘汰**以后永不使用**或**最长时间不再被访问**的页。理论最优、**无法实现**（无法预知未来），但用来**评价其他算法**。

![[image-a33fb8e2.png]]

引用串 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1、三块：缺页 9 次、置换 6 次。

⚠️ "最长时间不被访问"和"以后被访问次数最少"是**不同概念**，别混。

### FIFO：先进先出

淘汰**最早进入内存**的页。队列实现、简单，但不利用局部性，性能差——同一例子置换 12 次，比 OPT 多一倍。

![[image-15812a46.png]]

**Belady 异常**：分配的物理块**增多，缺页次数不减反增**（3 块 9 次 → 4 块 10 次）。

![[image-854db26d.png]]

**只有 FIFO 会出现 Belady 异常**——LRU 和 OPT 永远不会（它们是堆栈类算法）。

### LRU：最近最久未使用

淘汰**最近最长时间未使用**的页——过去不用的，将来大概率也不用。

![[image-52358aad.png]]

**LRU 是"向前看"的**（根据过去），**OPT 是"向后看"的**（根据未来）——两者前几步可能巧合相同，但无必然联系。性能接近 OPT，但需要寄存器和栈的硬件支持，**开销大**。

### CLOCK：时钟置换（NRU）

用小开销逼近 LRU。给每页一个**访问位**（装入或被访问置 1），页面链成**循环队列**，配一个替换指针：

- 扫描：访问位 = 1 → 置 0，跳过（**给它第二次机会**）；访问位 = 0 → 淘汰它
- 又称 **NRU（最近未用）算法**

![[image-93872fd2.png]]

![[image-048fb188.png]]

### 改进型 CLOCK：把修改代价也算进去

换出修改过的页要写回磁盘——**代价更大**。用（访问位 A，修改位 M）组合分四类：

| 类别 | A | M | 说明 |
| --- | --- | --- | --- |
| 1 类 | 0 | 0 | 最近未访问且未修改——**最佳淘汰页** |
| 2 类 | 0 | 1 | 最近未访问但已修改——次佳 |
| 3 类 | 1 | 0 | 最近访问过未修改——可能再用 |
| 4 类 | 1 | 1 | 最近访问过且已修改——可能再用 |

扫描逻辑：第一轮找 1 类（**不改访问位**）；没有 → 第二轮找 2 类（**顺路把扫描过的访问位清 0**）；还没有 → 把所有访问位复 0 后重复前两轮——一定能找到。

好处：减少磁盘 IO；代价：可能要扫好几轮，算法本身开销增加。

**页面置换的总原则**：尽可能保留访问过的页面，淘汰未访问过的；同样未访问的，优先淘汰**未修改**的（写回省了）。

## 九、抖动、工作集与性能

### 抖动（颠簸）

刚换出的页马上又要用，刚换入的马上又要换出——**频繁的页面调度**。根本原因：**分配给进程的物理块太少**，满足不了正常运行的基本要求，进程大部分时间花在换入换出上，CPU 利用率急剧下降趋于零。

### 工作集

某段时间间隔内，进程要访问的**页面集合**，由时间 t 和窗口尺寸 Δ 确定。

![[image-72108765.png]]

窗口设 5，t1 时刻工作集 {2,3,5}，t2 时刻 {1,2,3,4}。**驻留集大小不能小于工作集**，否则频繁缺页。

### 内存映射文件

OS 提供的系统调用，在**磁盘文件与进程虚拟地址空间之间建立映射**：把文件当内存中的大字符数组读写，不用文件 IO；读写由 OS 透明完成；只在访问页面时才逐页读入，退出/关闭映射时改动过的页面才写回。多个进程映射同一个文件 → **共享内存通信**（各自虚拟地址独立，OS 用页表映射到相同物理内存）。

好处：编程简单（像访问内存一样读写文件）；方便多进程共享文件。

### 影响缺页率的因素

- **页面大小**：大 → 缺页率低但页内碎片大；小 → 碎片小但页表长、页数多
- **物理块数**：越多缺页率越低，超过某数目后改善不明显
- **置换算法**：LRU、CLOCK 好于 FIFO
- **写回频率**：建"已修改换出页面链表"，攒一批再统一写回，减少磁盘 IO；期间再被访问可直接从链表取回，连读入都省了
- **程序局部化程度**：按行存储就按行访问，别按列访问（数组遍历顺序送命题）

### 地址翻译综合题

TLB → 页表 → Cache → 主存 → 外存，一套组合拳：虚拟地址拆成 TLB 标记 + 组索引 + 页内偏移；查 TLB 不中查页表得物理页号，拼出物理地址；物理地址再拆成 Cache 标记 + 组索引 + 块偏移查 Cache。**查找顺序：TLB → 页表 → Cache/主存 → 外存**，务必掌握。

## 十、盲点总复习

1. 静态重定位装入后程序**不能移动**；动态重定位才能支持紧凑、离散分配
2. 内存保护：重定位寄存器管"**加**"，界地址寄存器管"**比**"；加载它们要**特权指令**
3. 首次适应综合性能最好；最佳适应外部碎片**最多**（名字反着记）
4. 页表项连续存放 → 页号隐含不占空间；页表寄存器平时在 PCB 里，调度时才装入
5. 快表是**相联存储器**（并行查找）；两级页表三次访存；段页式也是三次访存
6. 分页一维、分段二维——能否用一个整数除余得到段号/页号是判断标准
7. 段表项 = 始址 + **段长**；页表项 = 块号（长度隐含）；**分页无外部碎片**（页内碎片），分段无外部碎片（段内可整段换入换出思路）
8. 缺页中断是**内中断**，指令执行**期间**产生，一条指令可多次缺页
9. 淘汰页**未修改不写回**，修改过才写——改进 CLOCK 的出发点
10. **只有 FIFO 有 Belady 异常**；LRU/OPT 是堆栈类算法，永远不会
11. 抖动根因 = 物理块太少；驻留集 ≥ 工作集才不频繁缺页
12. 数组按行存储就按行遍历——程序局部化程度直接影响缺页率

---

内存管好了，接下来管文件 → [[07-文件管理]]

⬅️ 🏠 [[00-操作系统总览]] ➡️ [[07-文件管理]]