第 13 讲：地址空间、装入与分区管理

内存管理的核心矛盾是：程序想要一块连续、独立、从固定地址开始的空间，而物理内存不仅容量有限，还要被多个程序共享。从分区到分页的每一步，都在放松“逻辑地址必须等于物理地址”这个限制。

先分清四种地址

  • 符号地址：源码中的变量名、函数名；
  • 相对/逻辑地址：编译与链接后，相对于某个逻辑空间的地址；
  • 虚拟地址：CPU 执行指令时发出、尚需地址转换的地址；
  • 物理地址：经 MMU 等机制转换后真正访问存储器的地址。

在没有虚拟存储的早期系统中，逻辑地址和物理地址可能很早就被绑定；现代系统将最后的转换推迟到每次访存。

程序如何从源码进内存

编译—汇编—链接—装入

program.c ─编译器→ program.s ─汇编器→ program.o
                                                     ├─链接器→ ELF 可执行文件
library.o / extras.o ─────────────────────┘
ELF ─装载器→ 进程虚拟地址空间 → CPU 从入口点执行

单个 .o 文件编译时不知道外部函数最终地址，因此会留下：

  • 符号表：某个函数或全局变量叫什么；
  • 重定位项：哪条指令或数据里的地址等链接时回填。

链接器合并各节，解析符号，按架构规则计算重定位值，生成 ELF。课件用 MIPS jal 指令和 R_MIPS_26 重定位展示了这个过程：调用地址不是编译时凭空知道的，而是符号定义与调用点被链接器对上后计算出来的。

节与段不是一件事

ELF 节（section）更偏向链接视角，段（segment）更偏向装载视角：

  • .text 保存代码，通常可读可执行；
  • .data 保存已初始化的可写静态数据；
  • .bss 表示未初始化/零初始化数据，只需在文件中记录所需内存大小，不必真存一大片零；
  • 装载器按 program header 把若干节归并为可映射段，建立权限不同的虚拟内存区域。

execve 装载时会检查 ELF 魔数和格式，为可装载段建立映射，准备参数、环境与用户栈，然后将用户 PC 设为 ELF 入口。入口通常先进 C 运行时启动代码，再由它调用 main，不是内核直接找 main。

进程运行时的地址空间还会出现堆、栈、共享库和内核保留区。堆通常随动态分配增长，栈随函数调用保存返回地址、局部变量以及初始参数/环境；它们是运行时的虚拟区域，不必在 ELF 文件中逐字节保存。ELF 的 section header 主要服务链接/分析，装载器真正按 program header 中的可装入 segment 建立映射。

地址绑定的三个时机

时机含义代价
编译时直接生成绝对地址装入位置不能改
装入时生成可重定位代码，装入器一次修改运行后不能随意移动
运行时每次访存都经硬件动态转换需要 MMU，但最灵活

最简单的动态重定位可用基址寄存实现：

physical=base+logical.\text{physical}=\text{base}+\text{logical}.

再用界限寄存检查 0≤logical<limit0\le \text{logical}<\text{limit}，同时完成重定位和保护。

连续分配：固定分区

固定分区在启动时就把内存切成若干块，一个进程占一块。

  • 实现和回收都简单；
  • 能同时驻留的进程数不超过分区数；
  • 进程比分区小时，分区内剩下的空间不能给别人，形成内部碎片。

单一公共队列能灵活地选任意大小足够的空分区；每个分区自己一条队列更直接，但可能出现某队很长而其他分区闲置。

动态分区与空闲链表

动态分区按请求大小临时切分内存，避免大块内部浪费，但进程反复进出后会留下许多不连续小孔，形成外部碎片。

空闲状态可以用位图或链表管理：

  • 位图空间开销与分配单元数有关，操作简单；
  • 链表只记连续区段，容易合并相邻空闲块，但查找依赖链长。

回收一块时必须检查上、下物理相邻区：都空闲就三块合并；只有一边空闲就两块合并；都不空闲才新建一个空闲项。

四种顺序搜索算法

设按地址排列的空闲块是 [100,500,200,300,600][100,500,200,300,600] KiB，请求为 212 KiB：

算法选择主要考虑
First Fit500从头搜，选第一个够大的
Next Fit从上次结束位置继续减少低地址重复搜索
Best Fit300选最小的足够块
Worst Fit600选最大块，希望剩余仍可用

Best Fit 看似最省，却容易不断留下极小碎片；Worst Fit 会快速切碎珍贵的大空闲块；First Fit 简单且常有不错的综合效果，但低地址区可能被反复切割。没有一个名字上“最佳”就对所有工作负载最佳的算法。

课件还介绍了按大小分类建立多条空闲链的 Quick Fit/分类搜索：申请时可直接去相应大小桶取块，避免从长链逐项扫描；代价是桶的划分、跨桶选择和相邻空闲块合并更复杂。顺序搜索优化查找成本，分类索引则用更多元数据换更快的常见大小分配。

伙伴系统

伙伴系统只提供 2k2^k 大小的块。若请求 70 KiB，需要一块 128 KiB：

  1. 找到一块 128 KiB；若没有，就把 256 KiB 块对半拆分；
  2. 返回其中一半，另一半是它的“伙伴”；
  3. 释放时，若同阶伙伴也空闲，两者合并成 256 KiB，再向上尝试。

伙伴地址可由块起始地址的对应位翻转快速求得，所以拆分和合并高效；代价是向上取整带来内部碎片。

紧凑、覆盖与交换

  • 紧凑（compaction）：移动已分配区，把分散小孔拼成大空闲区。需要动态重定位，拷贝代价大。
  • 覆盖（overlay）：由程序员/链接结构将不会同时执行的模块放在同一内存区。减少单个程序所需内存，但编程负担重。
  • 交换（swapping）：OS 把暂时不运行的整个进程或其大部分移到外存，腾出内存，以后再调回。

覆盖解决“一个程序太大”，交换解决“多个进程合起来太大”。虚拟内存后来把调度粒度细化到页，才不必每次搬整个进程。

给分区计算题的检查顺序

  1. 先画出按地址排列的空闲块，不要只记大小；
  2. 每次分配后立即更新起址和剩余大小；
  3. Next Fit 要标上上次搜索停止位置；
  4. 回收时先按物理地址合并邻居，再执行后续分配；
  5. 分清“总空闲量足够但无连续大块”的外部碎片，与“分配块内未用”的内部碎片。

评论