Lecture 6：知识 - 内存管理基础

内存管理负责地址转换、保护、分配与回收。核心是区分逻辑地址与物理地址，并根据连续/非连续分配结构计算地址、碎片和表项。

6.1 地址与装入

• 按字节编址时一个地址对应 $1\text{ B}$；按字编址时一个地址对应一个字。MMU 负责虚实地址转换、保护等硬件支持。
• 逻辑地址（相对地址）由程序使用，物理地址（绝对地址）是实际内存单元地址。
• 取指令时，PC 给出待取指令的逻辑地址；执行指令需要读取或写入内存操作数时，相关有效地址也须转换。立即数直接包含在指令中，不要误认为每条指令都会再访问数据内存。
• 静态链接在运行前完成；装入时动态链接在装入内存时完成；运行时动态链接在首次需要模块时完成，便于共享和更新。

6.2 连续分配

• 单一连续分配：内存分系统区和用户区，用户区一次仅一个作业；简单但利用率低。
• 固定分区：预先分区，产生内部碎片；分区大小可相等或不等。
• 动态分区：按需建立分区，产生外部碎片；首次适应、最佳适应、最坏适应、邻近适应的区别在空闲分区检索策略。
• 内部碎片在已分配区域内部，例如固定分区分配了 $10\text{ MB}$ 而进程只用 $8\text{ MB}$；外部碎片是已分配区域之间零散、难以满足连续申请的空闲区，并不是外存碎片。分页主要留下末页的内部碎片，动态分区主要产生外部碎片。
• 紧凑可合并外部碎片但需动态重定位支持；内部碎片不能通过紧凑消除。
• 原资料提到的覆盖是让同一程序中不会同时执行的模块轮流占用同一块内存，以便程序总规模超过可用内存；交换是由 OS 把进程暂时换出到外存、需要时再换入。覆盖复用的是程序内部模块空间，交换移动的是进程驻留内容；二者均不等于把散落的空闲分区搬到一起的紧凑。

6.3 非连续分配

6.3.1 分页

逻辑地址由页号 $p$ 和页内偏移 $d$ 组成。若页大小为 $2^k$，低 $k$ 位为偏移；页表把页号映射为物理块号 $f$：

$$ \text{物理地址}=f\times\text{页大小}+d $$

• 页大小固定，消除外部碎片但最后一页可有内部碎片；每个虚页映射到一个物理页框，二者大小相同、编号不必相同。页表存放在内存，TLB（快表）缓存常用表项。
• 若进程大小对页长的余数可近似视为均匀分布，则末页内部碎片的平均值约为半页；这只是统计假设，不是每个进程都浪费半页。
• 二级/多级页表降低页表连续存储要求；反置页表按物理块建立，用进程号和页号检索。

6.3.2 分段与段页式

• 段按程序逻辑划分，地址为段号 + 段内偏移；段表含段长与基址，便于共享保护但有外部碎片。
• 段页式先按段、再按页，地址含段号、页号、页内偏移；兼顾逻辑分段和页式物理分配，访问通常需段表和页表两次映射。

6.4 保护与共享

• 重定位寄存器（基址）与界地址寄存器检查逻辑地址是否越界；越界产生异常而非普通用户程序自行处理。
• 分页可在页表项中设置读写执行、有效位等；分段可按段设置权限。共享代码段通常只读，多进程可映射同一物理页。

6.4.1 共享代码的空间计算

设 40 个用户同时运行同一文本编辑程序，每个进程包含 $160\text{ KB}$ 代码和 $40\text{ KB}$ 私有数据：

• 不共享时需 $40\times(160+40)=8000\text{ KB}$。
• 若 $160\text{ KB}$ 代码是只读可重入代码，只保留一份，则需 $160+40\times40=1760\text{ KB}$。
• 在页面大小为 $4\text{ KB}$ 的分页系统中，共享代码占 40 页；每个进程的页表各有 40 个表项指向相同代码页框，另有 10 个表项指向自己的私有数据页。
• 在分段系统中，每个进程只需一个段表项指向同一共享代码段，故共享关系更贴近程序的逻辑结构。
• 共享段在不同进程中可以有不同段号，只要各自段表项指向同一物理段即可；共享段的管理信息应记录引用它的进程数，最后一个引用撤销后才回收物理空间。共享只读代码与每个进程的私有可写数据应分开。

6.5 图示补全：装入、地址绑定与连续分配

6.5.1 编译、链接与装入

程序生命周期要按输入语言区分：高级语言源程序由编译器翻译，编译器可以先生成汇编代码，也可以直接生成目标代码；若生成汇编代码，再由汇编器产生含机器指令的可重定位目标文件。链接器把一个或多个目标文件与库合并、解析符号并重定位，生成可执行文件；装入器再把可执行映像映射到内存并开始运行。链接方式：

• 静态链接：运行前把所需目标模块与库连接为一个可执行文件。
• 装入时动态链接：模块装入内存时边装入边链接。
• 运行时动态链接：程序执行中首次需要某模块时才链接/装入，便于共享、更新和按需使用。

地址绑定的时机要分清：编译时已知装入位置可生成绝对地址；装入时把相对地址一次性改为物理地址，称静态重定位；运行时由 MMU 的重定位（基址）寄存器动态把逻辑地址映射为物理地址，程序可在内存中移动。

进程内存映像通常包括只读代码段、已初始化数据段、bss（未初始化或初始化为零的全局/静态数据）、堆（向高地址动态扩展）和栈（函数调用使用，通常向低地址增长）。只读纯代码可被多个进程共享；堆和栈是各进程私有的。

6.5.2 基址/界址保护

连续分配下，CPU 先比较逻辑地址是否小于界址（限长）寄存器；越界则产生地址异常，未越界才计算：

$$ \text{物理地址}=\text{基址（重定位寄存器）}+\text{逻辑地址} $$

基址寄存器保存进程起始物理地址，界址寄存器保存其最大逻辑地址范围；二者只能由内核用特权指令装载。越界异常与用户态试图执行特权指令造成的特权异常都属于硬件保护机制。

另一种连续分配保护方式是用物理地址上、下界寄存器直接检查目标物理地址是否落在本进程区间内。它与上面的“逻辑地址先和限长比较，再加基址”是两种检查口径；若区间采用左闭右开表示，合法条件分别是 $\text{下界}\le\text{物理地址}<\text{上界}$ 和 $0\le\text{逻辑地址}<\text{限长}$，不要把最大合法地址与区间长度混为一谈。

6.5.3 分区与空闲区管理

• 固定分区使用分区说明表，按分区大小或状态分配；实现简单、无外部碎片，但会因作业小于分区而产生内部碎片。
• 动态分区用空闲分区表或空闲分区链管理；分配时可把大空闲区切成“已分配部分 + 剩余空闲部分”。回收时应与相邻的前/后空闲区合并，前后都相邻时三者合并。
• 回收区有四种相邻情况：只邻前空闲区则扩展前区；只邻后空闲区则把后区起址前移并增大其长度；同时邻前、后空闲区则三者合并并删去一个表项；两侧均不邻空闲区则新增表项。是否“相邻”按内存地址区间判断，不能按空闲表项在表中的排列位置判断。
• 首次适应按地址递增找第一个足够大的空闲区，通常综合效果较好；邻近适应从上次查找位置继续；最佳适应选最小可满足分区，易产生很多小碎片；最坏适应选最大空闲区，可能过快耗尽大分区。紧凑（compaction）把已分配区搬到一起以合并外部碎片，代价大且需动态重定位支持。
• 快速适应按常用大小维护多条空闲链，索引表帮助定位合适的链；它是查找和组织空闲区的方法，本身不决定碎片类型。若整块交付大于请求量的大小类，会有内部浪费；若切分并保留余块，则可避免这部分内部碎片。还可用空闲区大小作键建立哈希索引，加快寻找对应链。
• 伙伴系统按 $2$ 的幂次分块，申请时从足够大的块反复二分；回收时仅同一父块分出的两个伙伴均空闲才可合并，不能只凭等大、相邻就合并。它便于合并与查找，但按幂次向上取整可能产生内部碎片。
• 原 PDF 还介绍了内核对象的 slab 分配器：按对象类型或大小设置缓存，在 slab 中复用等大小对象，以减少重复初始化和分配成本。slab 并非原页所写的“SLABS / Simplified Lease Allocator”缩写；固定大小对象槽也可能有块内浪费，不能笼统称为零碎片。

6.6 图示补全：分页、快表、分段与段页式

6.6.1 基本分页地址转换

页大小为 $L$，逻辑地址为 $A$：

$$ p=\left\lfloor A/L\right\rfloor,\quad d=A\bmod L,\quad \text{物理地址}=f\times L+d $$

其中 $p$ 是页号、$d$ 是页内偏移、$f$ 是页表项给出的物理块号。若页表长度 $M$ 表示表项数、页号从 $0$ 开始，则合法页号为 $0\le p<M$；通过页表基址寄存器定位表项，按该系统的存在位和权限规则检查后，才取 $f$ 与偏移拼接/相加。页大小为 $2^k$ 时，低 $k$ 位就是页内偏移。

例如 4 KB 页面使偏移占 12 位，逻辑地址 0x00401000 和 0x0040104A 的高 20 位都是 0x00401，故属同一虚页；偏移分别为 0x000、0x04A。页表本体在内存中，进程切换时可由 PCB 中保存的页表相关信息恢复页表基址寄存器，不能把整个页表误当成放在 PCB 里。

页表项必须能表示物理块号；具体设计还可设置存在/有效、读写执行权限、访问、修改（脏）等控制位，不能把这些位一概视为所有基本分页系统的固定格式。页号通常由页表项在表中的位置隐含，不必在每项中重复存储。例如主存 4 GB、页大小 4 KB 时共有 $2^{20}$ 个物理块，块号至少 20 bit，加入所需控制信息后常向上取整到若干字节。

发生合法缺页时，处理流程包括取得可用页框、建立页号到页框号的映射并更新页表；有文件或交换区后备的页需要调入，首次访问的匿名页则可分配并清零，无须读磁盘。若有空闲页框，不必先置换内存中的页。

6.6.2 TLB（快表）与多级页表

TLB 是关联查找的页表项高速缓存，不是普通 Cache 的同义词。访问逻辑地址时先查 TLB：

• 快表命中：得到页框号后访问目标内存单元，通常只需一次主存访问。
• 快表未命中：先访问主存中的页表，再访问目标内存，共两次主存访问，并将该页表项调入快表（必要时替换旧项）。

TLB 未命中不等于缺页：前者只表示地址翻译缓存里没有该表项；若主存页表项有效，查表后照常访问数据。只有所需页面当前不在主存等情况，才进入缺页处理。上述“一次/两次访存”均以不发生缺页、忽略 Cache 等其他层次为前提。

若 TLB 查找时间为 $t$、一次主存访问时间为 $m$、命中率为 $h$，忽略其他开销时：

$$ EAT=h(t+m)+(1-h)(t+2m) $$

单级页表很大时会要求连续的大块内存。二级/多级页表把页表再分页：每张下级表通常设计为恰占一页，外层表也须按系统设计妥善容纳；优点是只为用到的地址空间建立下级表、降低连续空间要求，缺点是 TLB 未命中时每增加一级就多一次查表访问。例如二级页表无 TLB 命中、无缺页时需访问页目录、二级页表和目标单元，共三次主存访问。反置页表按物理页框建立，需用进程号和页号检索。

6.6.3 分段与段页式转换

分段地址为 $(s,w)$：若段表长度 $M$ 表示表项数，则先检查 $0\le s<M$；再取段表项的段基址和段长，检查 $0\le w<\text{段长}$，最后：

$$ \text{物理地址}=\text{段基址}+w $$

各段从段内偏移 $0$ 独立编址。若段号和段内偏移各占 16 位，则最多可编码 $2^{16}$ 个段，每段的可表示偏移范围为 $0$～$2^{16}-1$，即最大可表示段长为 $2^{16}\text{ B}=64\text{ KB}$；实际段长仍由对应段表项限制。

分页以固定大小页面提高物理内存利用率，页号和偏移可由一个线性地址拆出，面向系统；分段以程序逻辑模块划分，段号和段内偏移须作为两个分量表达，便于用户理解、共享和保护，但有外部碎片。每段内部连续，段与段之间可不相邻。段页式先检查段号，再由段表取得该段页表的位置和页数，检查页号后查页表，与页内偏移形成物理地址；地址字段为段号、页号、页内偏移。若还需按真实段长保护，末页的偏移也应满足 $\text{页号}\times\text{页大小}+\text{页内偏移}<\text{段长}$，仅检查页号不足以识别末页的未用尾部。

6.6.4 基本分页数值例题

若页大小为 $1\text{ KB}=1024\text{ B}$，逻辑地址 $A=2500$ 所在的页 $2$ 被装入物理块 $8$：

$$ p=\left\lfloor\frac{2500}{1024}\right\rfloor=2,\qquad d=2500\bmod1024=452 $$

$$ E=8\times1024+452=8192+452=8644 $$

原 PDF 第 23 页中间一步写成了 8×1024=8196，这是算术笔误；最终地址 8644 是正确的，块起始地址应为 8192。

若物理内存为 $4\text{ GB}=2^{32}\text{ B}$、页大小为 $4\text{ KB}=2^{12}\text{ B}$，则共有 $2^{20}$ 个页框。仅表示页框号至少需要 20 bit，即至少 3 B；实际页表项还要容纳有效位、权限位、访问位、修改位等信息，工程实现常向上取整为 4 B 或更大。

6.6.5 TLB 与多级页表数值例题

若一次 TLB 查询耗时 $1\ \mu s$，一次主存访问耗时 $100\ \mu s$，TLB 命中率为 $90%$，并采用“先查 TLB，再访问主存”的串行模型：

$$ EAT=0.9\times(1+100)+0.1\times(1+100+100)=111\ \mu s $$

对于 32 位字节地址、$4\text{ KB}$ 页面、4 B 页表项：页内偏移占 12 bit，虚页号占 20 bit，共 $2^{20}$ 个页表项；单级页表大小为 $2^{20}\times4\text{ B}=4\text{ MB}$，要占 $4\text{ MB}/4\text{ KB}=1024$ 个页框。二级页表可把每 1024 个表项分为一组，使每张下级页表恰占一页。

若页大小为 $2^{10}\text{ B}$、页表项为 2 B，一张下级页表可容纳 $2^{10}/2=2^9$ 个表项。逻辑地址空间共有 $2^{16}$ 页时，页目录至少需要：

$$ \frac{2^{16}}{2^9}=2^7=128 $$

个目录项。

再看 PDF 的二级页表示例：32 位逻辑地址被拆成 10 bit 页目录号 + 10 bit 二级页号 + 12 bit 页内偏移。页目录号 0 指向物理块 3 中的二级页表，二级页号 1 对应的数据页在物理块 4。对地址

(0000000000, 0000000001, 111111111111)

页内偏移的 12 个二进制位全为 1，因此偏移是 $2^{12}-1=4095$，正确物理地址为：

$$ 4\times4096+4095=20479=\mathtt{0x4FFF} $$

原 PDF 第 31 页把 12 个 1 误算为 1023，继而得到 17407；那相当于只按 10 位偏移计算，与题中 12 位偏移字段矛盾，不能照抄。

6.6.6 分段越界例题

若段 2 的基址为 $8\text{ KB}=8192$、段长为 500，访问段内偏移 100 合法，物理地址为 $8192+100=8292$。

另一例中段 2 的段长为 300、基址为 4000，逻辑地址为 $(2,400)$。地址转换必须先比较偏移和段长；因 $400\ge300$，立即产生越界异常，不能把二者相加得到 4400。若段不在内存，应触发调入相关处理；若访问方式违反读写权限，则属于权限异常，这两类情况不要与越界混淆。

相关知识

• 科目导航：操作系统导航
• 阅读顺序：上一篇：死锁 · 下一篇：虚拟内存管理
• 关联专题：主存储器

6.7 本节复盘

• 绝对/静态重定位/动态重定位按地址绑定时机区分。
• 连续分配重点是内外碎片；分页消除外部碎片，分段保留逻辑结构，段页式二者结合。
• 地址计算先拆字段、检查段号或页号，再查相应表项并核对存在、权限和段内边界；确认合法后才组成物理地址并访问内存。