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

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

一、内存管理的基本要求

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

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

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

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

三种装入方式：

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

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

逻辑地址与物理地址

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

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

进程的内存映像

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

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

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

内存保护

两种方法：

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

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

内存共享

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

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

存储管理方式的演进

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

二、连续分配管理方式

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

单一连续分配

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

固定分区分配

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

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

动态分区分配

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

随时间推移，内存中产生越来越多的小内存块——外部碎片（在所有分区的外部，与固定分区的内部碎片相对）。外部碎片可用紧凑技术克服（不时移动整理进程，需要动态重定位寄存器支持，费时）——类似 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 的作业照样跑不了——这就引出了离散分配。

三、基本分页存储管理

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

地址结构与页表

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

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

基本地址变换机构

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

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

快表 TLB：解决"转换慢"

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

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

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

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

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

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

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

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

四、基本分段存储管理

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

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

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

段表与地址变换

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

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

段的共享与保护

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

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

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

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

六、段页式存储管理

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

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

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

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

传统方式的两个死穴

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

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

局部性原理

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

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

虚拟存储器

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

三个特征：

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

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

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

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

缺页中断

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

与一般中断的两个区别：

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

请求分页的地址变换流程

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

页框分配

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

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

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

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

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

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

八、页面置换算法

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

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

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

引用串 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 多一倍。

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

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

LRU：最近最久未使用

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

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

CLOCK：时钟置换（NRU）

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

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

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

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

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

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

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

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

九、抖动、工作集与性能

抖动（颠簸）

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

工作集

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

窗口设 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/主存 → 外存，务必掌握。

十、盲点总复习

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

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

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