前言

内存管理要解决四个核心问题：如何为进程分配和回收空间，如何完成逻辑地址到物理地址的转换，如何阻止进程越界访问，以及如何利用虚拟内存让有限的物理内存运行更大的程序。

本章从连续分配开始，逐步过渡到分页、分段和段页式管理，最后进入虚拟内存、请求分页、页面置换与页面分配策略。理解这些内容的关键，是始终沿着“地址如何转换、页面是否在内存、内存不足时淘汰谁”这条主线思考。

一、内存基础与地址重定位

1. 内存、地址与程序运行

内存用于暂存正在运行的程序和数据。CPU 可以直接访问内存中的指令和数据，而程序在外存中时不能直接交给 CPU 执行，因此程序运行前需要先被装入内存。

内存由大量存储单元构成，每个存储单元都有唯一地址。计算机可以按字节编址，也可以按字编址：按字节编址时，一个地址对应 1 字节；按字编址时，一个地址对应 1 个机器字。

程序从源代码到运行通常经过三个环节：

1. 编译：把源代码翻译成目标模块。
2. 链接：把目标模块及所需库函数组合成完整的装入模块。
3. 装入：把装入模块放入内存，形成可供 CPU 访问的物理地址。

2. 逻辑地址与物理地址

程序编译、链接后形成的地址属于逻辑地址，也称相对地址；内存存储单元的真实地址属于物理地址，也称绝对地址。地址重定位就是把逻辑地址转换为物理地址。

三种装入方式的区别集中在“什么时候转换地址”：

装入方式	地址转换时机	主要特点
绝对装入	编译时	直接生成绝对地址，只适合地址位置预先确定的单道程序环境
可重定位装入	装入时	装入时一次性完成转换，程序运行后不能再移动
动态运行时装入	运行时	每次访问时进行转换，需要重定位寄存器支持，程序可在内存中移动

动态运行时装入把地址转换推迟到程序执行阶段，灵活性最高，也是现代操作系统采用的主要方式。

3. 内存管理的四项功能

操作系统的内存管理包括以下四项基本功能：

• 分配与回收：记录哪些空间已占用、哪些空间空闲，并在进程结束后回收内存。
• 地址转换：把进程使用的逻辑地址转换成物理地址。
• 空间扩充：借助虚拟内存，从逻辑上扩大用户可见的内存空间。
• 存储保护：保证各进程只访问自己的地址空间。

存储保护可以使用上下限寄存器检查物理地址是否越界，也可以使用重定位寄存器与界地址寄存器配合检查。后者先判断逻辑地址是否超过进程允许范围，再把合法逻辑地址与进程起始物理地址相加。

4. 进程的内存映像

以典型的 32 位 C 程序为例，进程地址空间通常包含只读代码与数据区、读写数据区、堆、共享库映射区、用户栈和内核区。

• 只读代码与数据区保存程序指令和只读常量。
• 读写数据区保存全局变量和静态变量。
• 堆由程序动态申请和释放，常见操作来自 malloc 和 free。
• 用户栈保存函数参数、局部变量、返回地址等调用信息。
• 共享库映射区保存被调用库函数的映射，例如 printf 所在的共享库。

堆通常向高地址方向增长，栈通常向低地址方向增长，两者之间保留可扩展空间。

二、连续分配管理

连续分配要求一个进程占用一整块连续的物理内存。随着多道程序的发展，连续分配经历了单一连续分配、固定分区分配和动态分区分配。

1. 三种连续分配方式

分配方式	分配规则	碎片情况	主要限制
单一连续分配	内存分为系统区和用户区，一个用户程序独占用户区	有内部碎片，无外部碎片	只能支持单道程序，利用率低
固定分区分配	预先把用户区划成若干固定分区，每个分区装一道作业	有内部碎片，无外部碎片	进程大小受最大分区限制
动态分区分配	根据进程大小动态建立分区	无内部碎片，有外部碎片	需要维护空闲分区并处理外部碎片

内部碎片位于已分配区域内部，是分给进程却没有使用的空间。外部碎片位于各个已分配区域之间，单个空闲区太小，无法满足新的连续分配请求。动态分区可以通过紧凑技术移动进程，把零散空闲区拼成大块连续空间，但移动与重定位会带来额外开销。

回收动态分区时，需要检查回收区前后是否存在相邻空闲区。前后都相邻时合并三块；仅一侧相邻时合并两块；两侧都不相邻时新增一个空闲分区记录。

2. 动态分区分配算法

动态分区算法的差异体现在空闲分区的排列方式和查找起点。

算法	查找规则	空闲分区排列	主要特点
首次适应 First Fit	从低地址开始，选择第一个足够大的分区	按地址递增	开销较小，综合效果较好，能保留高地址大分区
最佳适应 Best Fit	选择能满足要求的最小分区	按容量递增	容易留下大量难以利用的小碎片，维护排序开销较大
最坏适应 Worst Fit	选择最大的空闲分区	按容量递减	剩余分区通常较大，但会快速消耗大分区
邻近适应 Next Fit	从上次查找结束处继续循环查找	按地址递增并形成循环结构	减少从低地址重复扫描的开销，但高地址大分区更容易被切分

四种算法中，首次适应结构简单、开销较小，并能较好地保留高地址的大分区，通常具有更稳定的综合表现。

三、基本分页存储管理

连续分配要求为进程找到整块空间，容易受到外部碎片影响。分页把进程和内存切成等大的小块，使进程能够离散地装入多个不相邻的物理区域。

1. 页、页框与页表

• 页面：进程逻辑地址空间中大小相等的分区。
• 页框：物理内存中与页面大小相等的分区，也称页帧、内存块或物理块。
• 页表：记录页面与页框之间映射关系的数据结构。

一个进程对应一张页表，每个页面对应一个页表项。页表项至少要记录页面所在的物理块号，页号可以根据页表项所在位置隐含得出。

分页消除了外部碎片，但进程最后一页可能没有装满，因此仍可能产生少量内部碎片。

2. 逻辑地址的拆分

分页系统把逻辑地址拆成页号 P 和页内偏移量 W。若页面大小为 L，逻辑地址为 A，则：

P = A / L 的整数部分
W = A % L

例如，页面大小为 1 KB，逻辑地址为 2500 B：

页号 P = 2500 / 1024 = 2
页内偏移量 W = 2500 % 1024 = 452

查页表得到第 2 页所在的物理块号后，再把该物理块的起始地址与 452 相加，即可得到最终物理地址。

当页面大小为 2 的整数次幂时，逻辑地址的低位可以直接作为页内偏移量，高位作为页号，硬件无需执行除法和取余运算。

3. 基本地址变换过程

页表寄存器 PTR 保存当前进程页表的起始地址和页表长度。进程未运行时，这些信息保存在 PCB 中；进程被调度运行时，操作系统把它们装入页表寄存器。

基本地址变换可拆成五步：

1. 根据逻辑地址得到页号和页内偏移量。
2. 将页号与页表长度比较，检查是否越界。页号从 0 开始，因此页号大于或等于页表长度时越界。
3. 用页表起始地址、页号和页表项长度定位对应页表项。
4. 从页表项中取出物理块号，与页内偏移量组合成物理地址。
5. 访问该物理地址对应的内存单元。

在没有快表的单级分页系统中，访问一个逻辑地址需要两次访存：第一次访问页表，第二次访问目标内存单元。

四、快表与多级页表

1. 快表为什么能加速地址转换

快表 TLB 是保存近期页表项副本的高速缓存。CPU 得到逻辑地址后，先用页号查询快表：

• 快表命中：直接取得物理块号，只需再访问一次目标内存。
• 快表未命中：访问内存中的页表取得物理块号，再访问目标内存，共需两次访存；取得的页表项还会复制到快表中。

TLB 只保存页表项副本，普通 Cache 还可以保存指令和数据副本，两者缓存的对象不同。

快表有效的基础是局部性原理。时间局部性表示刚访问过的指令或数据短时间内可能再次访问；空间局部性表示某个存储单元被访问后，其附近单元也可能很快被访问。

2. 两级页表解决什么问题

单级页表要求全部页表项连续存放。当进程地址空间很大时，页表本身也会很大，难以找到足够大的连续内存，并且进程短时间内只会使用少量页面，没有必要让整张页表常驻内存。

两级页表先把页表分页，再建立页目录表记录各个二级页表的位置。逻辑地址相应地拆成一级页号、二级页号和页内偏移量。

没有快表时，两级页表访问一个逻辑地址需要三次访存：

1. 根据一级页号访问页目录表，找到二级页表。
2. 根据二级页号访问二级页表，找到物理块号。
3. 结合页内偏移量访问目标内存单元。

若两级页表仍然过大，还可以继续建立更多级页表。多级页表减少页表对连续内存的要求，也允许暂时不用的下级页表不驻留内存，但页表层级越多，未命中快表时的访存次数也越多。

五、分段与段页式管理

1. 基本分段存储管理

分段按照程序自身的逻辑关系划分地址空间，例如代码段、数据段和栈段。每个段从 0 开始编址，在物理内存中占据连续空间，不同段之间可以不相邻。

分段系统的逻辑地址由段号和段内地址组成。每个进程拥有一张段表，每个段表项记录段长和基址。地址转换时先检查段号是否越界，再检查段内地址是否超过段长，最后用基址加段内地址得到物理地址。

分页与分段可以从以下角度区分：

对比项	分页	分段
划分依据	系统按固定大小划分	按程序逻辑模块划分
地址空间	一维地址	段号与段内地址构成二维地址
大小	页面大小固定	段长不固定
用户可见性	对用户不可见	对用户可见
碎片	可能产生内部碎片	可能产生外部碎片
共享与保护	按页面处理不够直观	可按逻辑模块共享和保护

2. 段页式管理

段页式管理先按逻辑关系把进程分段，再把每一段划分成大小相等的页面，物理内存仍按页框分配。逻辑地址由段号、页号和页内偏移量组成。

每个进程先建立段表，段表项记录该段对应页表的长度和起始位置；每个段再建立页表，页表项记录页面所在的物理块号。

没有快表时，段页式系统通常需要三次访存：第一次查段表，第二次查页表，第三次访问目标内存。它兼顾了分段便于按逻辑模块共享、保护的特点，也保留了分页提高内存利用率的优势。

六、虚拟内存与请求分页

1. 从传统存储管理到虚拟内存

传统存储管理有两个明显限制：

• 一次性：作业必须全部装入内存后才能开始运行。
• 驻留性：作业装入后会一直驻留内存，直到运行结束。

局部性原理说明，进程在一段时间内通常只集中访问少量指令和数据。因此，可以先把即将使用的部分装入内存，把暂时不用的部分留在外存；运行中缺少哪一页，再由操作系统调入哪一页。

虚拟内存具有三个特征：

• 多次性：作业可以分多次调入内存。
• 对换性：作业运行期间可以在内存和外存之间换入、换出。
• 虚拟性：用户看到的逻辑内存容量可以大于实际物理内存。

虚拟内存的实现需要离散分配方式，以及请求调页和页面置换功能。

2. 请求分页的页表项

请求分页在基本分页的页表项上增加了若干信息：

字段	作用
状态位	标记页面当前是否在内存中
访问字段	记录页面近期访问情况，为置换算法提供依据
修改位	标记页面调入内存后是否被修改，决定淘汰时是否需要写回外存
外存地址	记录页面在外存中的位置，缺页时据此调入

3. 缺页中断处理流程

CPU 访问某一页时，如果页表项的状态位表明该页不在内存，就会产生缺页中断。缺页中断属于内中断，也称异常；一条指令执行期间可能触发多次缺页中断。

缺页处理过程如下：

1. 保护当前进程的执行现场，转入缺页中断处理程序。
2. 根据页表项中的外存地址定位目标页面。
3. 若存在空闲物理块，直接把页面调入该物理块。
4. 若没有空闲物理块，使用页面置换算法选择淘汰页。
5. 淘汰页被修改过时先写回外存，未修改时可直接覆盖。
6. 把目标页面调入内存，更新页表项；使用快表时还需同步相关快表项。
7. 恢复进程现场，重新执行被中断的指令。

七、页面置换算法

页面置换算法的目标是尽量降低缺页率，同时控制算法本身的实现开销。

1. OPT、FIFO、LRU 与 CLOCK

算法	淘汰规则	特点
OPT	淘汰未来最长时间不再访问的页面	缺页率最低，但无法预知未来页面序列，不能在实际系统中实现
FIFO	淘汰最早进入内存的页面	实现简单，但性能较差，可能出现 Belady 异常
LRU	淘汰最近最久没有访问的页面	符合局部性原理，性能较好，但需要硬件支持，开销较大
CLOCK	循环检查访问位，优先淘汰访问位为 0 的页面	性能与开销较均衡

Belady 异常是指给进程增加物理块后，缺页次数反而上升。在以上算法中，FIFO 可能出现该现象。

2. CLOCK 算法

简单 CLOCK 为每个页面设置访问位，并把所有页面组织成循环队列。页面被访问后，访问位置为 1。需要淘汰页面时，从指针当前位置开始扫描：

• 访问位为 0：淘汰该页面。
• 访问位为 1：把访问位改为 0，跳过该页面并继续扫描。

如果第一轮所有访问位都是 1，它们会被依次清零，第二轮一定能够找到访问位为 0 的页面。因此简单 CLOCK 最多扫描两轮。

改进型 CLOCK 同时考虑访问位 A 和修改位 M，优先级从高到低为：

1. 第一轮查找 (A=0, M=0)，不修改访问位。
2. 第二轮查找 (A=0, M=1)，并把经过页面的访问位清零。
3. 第三轮再次查找 (A=0, M=0)。
4. 第四轮再次查找 (A=0, M=1)。

未修改页面不需要写回外存，因此优先淘汰 (0,0) 页面可以减少磁盘 I/O。

八、页面分配、抖动与工作集

1. 驻留集与分配策略

驻留集是请求分页系统分配给进程的物理块集合。驻留集过小会导致频繁缺页，过大又会降低可并发运行的进程数量。

页面分配和置换可组合成三种常见策略：

• 固定分配、局部置换：驻留集大小固定，缺页时只能淘汰本进程的页面。
• 可变分配、全局置换：驻留集大小可变，可从系统空闲块或其他进程中取得物理块。
• 可变分配、局部置换：仍只淘汰本进程页面，但系统会根据缺页率增减该进程的物理块。

固定分配与全局置换无法合理组合：固定分配要求进程运行期间物理块数量不变，而全局置换可能改变不同进程拥有的物理块数量。

2. 何时调页

预调页策略在进程运行前预测即将访问的页面并提前调入，适合首次调入，但预测不准确时会浪费 I/O。请求调页策略等到真正缺页时才调入，调入页面一定会被访问，但每次缺页都需要一次磁盘 I/O。

3. 抖动与工作集

刚换出的页面马上又要换入，刚换入的页面很快又被换出，这种频繁调页现象称为抖动或颠簸。主要原因是进程频繁访问的页面数超过了它可用的物理块数。

工作集是在某段时间窗口内，进程实际访问过的页面集合。操作系统可以根据工作集大小调整驻留集，使进程保留当前阶段经常访问的页面。一般应让驻留集能够覆盖工作集，否则缺页率会显著升高。

九、内存映射文件

内存映射文件通过系统调用把文件映射到进程的虚拟地址空间。映射完成后，程序可以像访问内存一样读写文件内容，文件数据的调入、写回与解除映射由操作系统负责。

内存映射文件有两个重要作用：

• 简化文件访问，程序无需反复显式调用 read、write 和 seek 来移动数据。
• 允许多个进程映射同一文件，借助共享页面交换数据。

进程关闭文件或解除映射时，操作系统会把被修改的数据写回磁盘。具体写回时机仍由操作系统的缓存与同步策略决定。

十、总结

内存管理的演进始终围绕空间利用率和地址转换展开：连续分配实现简单，但会受到碎片和连续空间限制；分页通过页表完成离散分配，快表与多级页表分别改善地址转换速度和页表空间问题；分段强调程序的逻辑结构，段页式结合了分段与分页的特点；虚拟内存再借助缺页中断、页面置换和工作集，让有限物理内存承载更大的进程地址空间。

复习时可以固定沿着三步判断：先确定逻辑地址怎样拆分，再判断目标页是否已在内存，最后分析内存不足时采用哪种置换和分配
策略。这样能够把分页、虚拟内存和页面置换算法串成同一条完整链路。

参考资料

• 王道考研操作系统第三章：内存管理