Lecture 10–11: 动态存储管理（Dynamic Storage Management）
Lecture 10–11: 动态存储管理（Dynamic Storage Management）
概述
本讲研究”如何管理一块内存/存储区域以满足各种分配需求”——既适用于应用中的堆，也适用于操作系统与磁盘空间管理。核心挑战是不可预测性：不知道一个已分配块何时会被释放。我们从栈分配（LIFO，简单高效）讲到堆分配（任意顺序，困难），覆盖空闲链表（first fit/best fit）、slab 分配器、位图，以及存储回收的两种策略（引用计数与垃圾回收）。
核心概念与系统机制图解
动态存储的两个基本操作
allocate(size) → ptr 分配 size 字节, 返回指针
free(ptr) 释放之前分配的块
挑战: 不可预测——不知道分配出去的块多久后被释放 → 极难
栈分配（Stack Allocation，LIFO）
- 适用：分配/释放满足”后分配先释放”（LIFO）——可预测。
- 实现：一个栈指针。分配 = 调整指针；释放 = 指针调回去。极高效。
- 示例：过程调用（X 调 Y，Y 再调 Z）、树的遍历、表达式求值、递归下降解析。
- 特点：已分配空间连续、空闲空间连续、无碎片化。代价：要求可预测的 LIFO 模式。
堆分配（Heap Allocation）
- 适用：释放顺序不可预测（树、图、复杂数据结构）。
- 问题：内存被分割成已分配块与空闲块（洞/holes）——碎片化（fragmentation）。
- 目标：让”洞”的数量少、尺寸大。
空闲链表（Free List）策略
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│A1│ 洞 │A2│ 洞 │A3│ 洞 │A4 │ 洞 │ 已分配(Allocated)与洞(Free)交错
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
free list: 把所有洞串成链表
● First fit: 从链表头开始, 找到第一个足够大的洞
● Best fit : 扫描全链表, 返回最接近需求尺寸的洞, 剩余放回链表
● 释放时: 与相邻空闲块合并
问题: 洞会越切越碎(碎片化), 大分配失败或堆被迫增长, 扫描开销大
Slab 分配器
- 定义：把一块内存（slab）切成等大小的块；为每个常用分配尺寸准备一个池（pool），每个池有独立空闲链表。
size=8B池: ┌──┬──┬──┬──┬──┬──┬──┬──┐ free list size=16B池: ┌──┬──┬──┬──┬──┐ size=32B池: ┌──┬──┬──┐ 分配: 去对应尺寸的 slab 的空闲链表取一块; 池空则申请新 slab 切块 释放: 归还到所在 slab 的空闲链表; slab 全空可整体释放 - 优点：常见情形下分配/释放极快；操作系统广泛使用（内核对象池，如进程描述符按 struct 大小分池）。
- 缺点：内部碎片——slab 内未被使用的空间；分配尺寸频繁变化时尤其浪费。
位图（Bitmap）
- 定义：一个比特数组，每个比特表示一块固定大小内存（或磁盘块）的分配状态（0=空闲，1=已分配）。
- 适合管理固定大小块（slab 内部、磁盘块）；查找空闲块需扫描比特数组（文件系统讲座详述）。
存储回收（Reclamation）：何时能释放？
- 原则：只有”不再被访问”的内存才能释放；假设只有”有指针指向”的数据才可访问。
- 两个经典错误：
- 悬垂指针（Dangling Pointer）：释放太早——内存还在使用。
- 内存泄漏（Memory Leak）：没人释放——内存永远无法再用。
- 两种自动方案：
| 方案 | 机制 | 优点 | 缺点 |
|---|---|---|---|
| 引用计数 | 每个对象记录指向它的指针数，归零即释放 | 即时回收、实现简单（std::shared_ptr、文件系统 inode 链接数） | 无法处理循环引用（A 指 B、B 指 A，计数永不归零） |
| 垃圾回收（GC） | 不显式 free；GC 扫描找出所有”活”对象（从根可达），回收其余 | 无悬垂指针、可压缩内存消除碎片（Java/Go/JS） | 昂贵：占 10–20% CPU、2–5 倍内存超分配、回收时停顿 |
标记-清扫（Mark and Sweep）图解
Pass 1 (Mark): 从根(静态变量/局部变量)出发, 递归标记所有可达对象
Pass 2 (Sweep): 扫描所有对象, 把活对象拷贝到连续内存(可压缩), 更新指针, 释放其余
根 ──► A ──► B ──► C D(不可达→回收)
代码示例与系统调用解说
示例：悬垂指针 vs 引用计数（C++）
#include <memory>
#include <iostream>
struct Node { int val; };
int main() {
// --- 悬垂指针 ---
int* p = new int(42);
delete p; // 释放过早
std::cout << *p; // 未定义行为: 悬垂指针解引用
// --- 引用计数: std::shared_ptr ---
std::shared_ptr<Node> a = std::make_shared<Node>();
{
std::shared_ptr<Node> b = a; // 引用计数 1 → 2
// ... 使用 a/b ...
} // b 析构, 计数 2 → 1
// a 仍在, 对象存活
// a 离开作用域 → 计数 0 → 自动释放
return 0;
}
【代码做了什么？】 上半部分演示悬垂指针（释放后仍使用）；下半部分用 std::shared_ptr 让对象生命周期由引用计数自动管理。
【系统机制透视】
- 引用计数的开销：每次拷贝/析构智能指针都有原子加减；循环引用（如双向链表、父子互指）会导致计数永不归零 → 泄漏（C++ 需用
std::weak_ptr打破环，Python 需 GC 的循环检测器）。 - 与操作系统内存管理的关系：文件系统 inode 的
nlink（链接计数，Lecture 22）就是引用计数的经典系统级应用——目录条目全部删除后才真正释放文件数据。 - 堆管理的宏观流程：
malloc/new先查空闲链表/slab；堆空间不足时通过brk/mmap系统调用向 OS 申请扩大数据段/映射新区域（与 Lecture 9 的内存布局衔接）。
关键要点
- 栈分配（LIFO）简单高效零碎片，但要求可预测的分配顺序；堆分配支持任意顺序但面临碎片化。
- 空闲链表策略（first fit/best fit）简单但易碎片化、扫描开销大；slab 按尺寸分池大幅提速。
- 位图适合固定大小块的分配管理（也是磁盘空闲空间管理的基础）。
- 回收错误的两面：悬垂指针（过早释放）与内存泄漏（过晚释放）。
- 引用计数即时但怕环；GC 无悬垂但昂贵——系统设计需在两者间权衡。
常见陷阱与注意事项
- 释放后使用（use-after-free）：悬垂指针解引用是未定义行为，valgrind/ASan 可检测。
- 内存泄漏：忘 delete / 循环引用使 shared_ptr 计数不清零。
- 只 new 不 delete 的大循环：堆无限增长直至 OOM。
- 碎片化导致的大块分配失败：即使总空闲空间足够，也没有连续大块。
- slab 尺寸假设失效：分配尺寸分布变化时 slab 内部碎片激增。
思考题
- 问题：为什么栈分配没有碎片化而堆分配有？
- 答案：栈严格 LIFO，所有已分配空间与所有空闲空间各自连续；堆任意顺序分配/释放，空闲块与已分配块交错，形成大量小洞（碎片）。
- 问题：引用计数最大的缺陷是什么？给出一个例子。
- 答案：循环引用。两个对象互相持有对方指针时，各自计数都 ≥1，永不归零，内存泄漏。例如双向链表相邻节点互指、A 对象持有 B、B 持有 A。
- 问题：slab 分配器能消除碎片化吗？
- 答案：不能。它消除了”不同尺寸块交错”造成的搜索开销，但 slab 内未使用的空间（内部碎片）依然存在；分配尺寸变化频繁时浪费更明显。