第五章存储器管理

5.1 程序的装入和链接

装入方式

方式	特点	适用
绝对装入	编译时产生绝对地址	单道程序
可重定位装入（静态重定位）	装入时一次性修改全部地址	装入后不能移动
动态运行时装入（动态重定位）	运行时借助重定位寄存器转换地址	地址可延迟到执行时变换，支持紧凑

链接方式

方式	说明
静态链接	装入前将所有模块链接成完整可执行文件
装入时动态链接	装入内存时边装入边链接
运行时动态链接	运行到某模块时才链接（最灵活,节省内存）

5.2 连续分配方式

方式	说明	碎片
单一连续分配	内存分为系统区+用户区,一次只一个程序	有内碎片
固定分区分配	预先分为若干固定大小分区	内碎片（分区内浪费）
动态分区分配	按需分配大小	外碎片（分区间浪费），可通过紧凑解决

动态分区分配算法⭐

算法	策略	空闲分区排列	优缺点
首次适应FF	从头找第一个够大的	地址递增	保留大分区,但低址碎片多
循环首次适应NF	从上次找到的位置继续	循环	分布均匀,但大分区缺乏
最佳适应BF	找最小的够用分区	容量递增	碎片最小但太小无法用
最坏适应WF	找最大的分区	容量递减	碎片概率小,但大分区缺乏

动态分区分配的改进算法

快速适应：按常用空间大小分类，设索引表管理
伙伴系统：分区大小为 $2^k$ ，分割/合并都是二分
哈希算法：以空闲分区大小为关键字建哈希表

5.3 分页存储管理方式（⭐⭐⭐）

基本概念

页面（页）：进程地址空间分成的固定大小区域（如4KB）
物理块（页框/帧）：内存空间分成的同大小区域
页内碎片（内碎片）：最后一页装不满一块

地址计算公式⭐

$P = INT\left[\frac{A}{L}\right] \quad d = A \mod L$

其中 $A$ = 逻辑地址， $L$ = 页面大小， $P$ = 页号， $d$ = 页内偏移

页表

每个进程一张页表
作用：页号 → 物理块号 的映射
页表寄存器PTR：存放页表起始地址和页表长度

地址变换过程（基本分页）

从逻辑地址取出页号P和页内偏移d
页号P与页表长度比较 → 若P ≥ 页表长度则越界中断
页表起始地址 + P × 页表项长度 → 找到页表项 → 取物理块号b
物理地址 = b × L + d（即块号拼接页内偏移）

基本分页：访问一个数据需要2次访存（1次查页表+1次读数据）

快表TLB⭐

引入TLB后：先查TLB(命中则1次访存)，未命中则查页表(2次访存)并更新TLB。

$EAT = h\,(t_{TLB}+t_m) + (1-h)\,(t_{TLB}+2t_m)$

其中 $h$ = TLB命中率， $t_{TLB}$ = TLB访问时间， $t_m$ = 内存访问时间。

等价写法： $EAT = 2t_m + t_{TLB} - h\,t_m$ 。

两级页表

32位地址空间，4KB页面 → 页表项1M个 → 页表占4MB → 不现实
解决：对页表也分页！
逻辑地址：|外层页号P1(10位)|外层页内地址P2(10位)|页内偏移d(12位)|
需要3次访存（访问外层页表→访问页表→访问数据）

多级页表

64位系统需要更多级（如x86-64用4级页表）
每增加一级多一次访存

反置页表

按物理块号而非页号组织：每个物理块对应一个表项
表项内容：页号 + 进程标识符PID
减少页表内存占用
可用哈希加速检索

5.4 分段存储管理方式

分段的引入目的

方便编程（逻辑分段）
信息共享（以段为单位共享）
信息保护
动态链接
动态增长

分段的基本原理

作业地址空间分为若干段，每段有段名和段长
逻辑地址：|段号S|段内地址d|（二维地址）
段表项：段号 + 段长 + 基址（起始地址）

段的地址变换

段号S与段表长度比较 → 若S ≥ TL则越界中断
由段表找到段表项 → 取段长和起始地址
段内地址d与段长比较 → 若d ≥ SL则越界中断（⭐两次越界检查！）
物理地址 = 起始地址 + d

分页 vs 分段（⭐⭐⭐必考）

比较项	分页	分段
目的	系统管理的需要,提高内存利用率	用户的需要,满足编程和使用
单位性质	页是信息的物理单位	段是信息的逻辑单位
大小	固定,由系统/硬件决定	不固定,由用户程序决定
地址维度	一维（页号+偏移自动划分,用户不可见）	二维（需给出段名和段内地址）
碎片	内碎片	外碎片

可重入代码（纯代码）

允许多个进程同时访问的代码
不允许任何修改
可修改的部分放在各进程的局部数据区

5.5 段页式存储管理方式

先分段,每段再分页
逻辑地址：|段号S|段内页号P|页内偏移d|
段表项：页表起始地址 + 页表长度
需要3次访存（段表→页表→数据）
实际中加TLB减少访存次数

5.6 IA-32/x86-64内存管理

IA-32

分段+分页：CPU生成逻辑地址→分段单元→线性地址→分页单元→物理地址
Linux在IA-32上仅最低限度使用段
4KB页使用二级页表（10+10+12）
PAE扩展为三级页表,支持36位物理地址(64GB)

x86-64

四级页表,48位虚地址,支持52位物理地址
页面大小可为4KB/2MB/1GB

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q26/Q27、2010Q28/Q29、2016Q28、2019Q31、2024Q25/Q27、2025Q22
优质例题：已知逻辑地址长度、页大小、页表项大小，求页号位数/页内偏移位数/页表占用空间。
最短解题模板：
1. 先拆位：偏移位数 = $\log_2(页大小)$ 。
2. 页号位数 = 逻辑地址位数 - 偏移位数。
3. 页表空间 = 页数 × 页表项大小，注意单位统一（B/KB）。

⚡ 秒杀版口令卡（10秒回忆）

口令：先偏移后页号，最后算页表。
口令：页号=高位，页内偏移=低位。
口令：所有计算先统一单位。

第五章 存储器管理