垃圾收集
垃圾收集（Garbage Collection）是一种自动内存管理机制，分配器自动回收程序不再使用的内存块。它对应于隐式分配器。
可达性分析：
- 从一组称为根集（root set） 的指针出发，进行图的遍历。
- 根集包括：栈中的局部变量、全局变量、寄存器中的指针等。
- 从根集不可达的堆块被视为垃圾，可以回收。
标记-清扫（Mark & Sweep）算法：
- 标记阶段：从根集出发，递归标记所有可达的已分配块。每个块头部通常有一位用于标记。
- 清扫阶段：遍历堆中所有块，将未标记的已分配块视为垃圾并回收（释放），同时清除标记位供下一轮使用。
与分配器的整合：
- 垃圾收集器通常建立在某种空闲链表分配器之上（如隐式空闲链表）。
- 垃圾收集器需要知道哪些是有效的指针（type tagging或保守式收集）。
保守式垃圾收集：
- C语言没有运行时类型信息，收集器无法准确判断一个整数的值是指针还是普通数据。
- 保守的做法是：将”看起来像指针”的值当作指针处理，不移动任何块。
- 优点是无需修改C编译器；缺点是有时无法回收本应回收的块。
链接到
- 上一个知识点：9.19 分离链表
- 下一个知识点：9.21 内存相关风险