追踪式垃圾回收

复习

• 引用计数：循环引用问题
• 图：用节点和边表示关系
• 语言运行时：负责内存管理

TL;DR

• 追踪式 GC 从“根”出发，找出所有还能到达的对象
• 到不了的对象就是垃圾，可以回收
• 常见做法分“标记”与“清除”两个阶段
• 它能处理引用计数搞不定的循环引用

正文

　　引用计数的死穴是循环引用。要解决它，就得换一种全局视角：不再只看“谁引用了谁”这个局部计数，而是从“程序现在还能触及哪些对象”出发。这就是追踪式垃圾回收（tracing GC）。

从“根”出发，看能到达谁

　　追踪式 GC 的思路是：

1. 找出所有根（root）——程序当前直接能访问到的地方，比如栈上的变量、全局变量
2. 从根出发，沿着引用关系一路“走”下去，把能到达的对象都标记为“活着”
3. 走不到的，就是垃圾，可以回收

　　注意第 2 步：“从根出发遍历所有能到达的对象”，本身就是一次图的遍历。 我们在数据结构部分学过的遍历，在这里派上了大用场。可达的活着，不可达的回收——一句话就是它的核心。

为什么它能解决循环引用

　　回头看看那个死结：A 和 B 互相引用，但再没有外部引用它们。

　　追踪式 GC 会怎么判断？它从根出发，发现根本走不到 A 和 B——因为没有任何根指向它们。于是它们被判定为“不可达”，即使它们彼此引用，也照样被回收。问题不在“有没有人引用它”，而在“根还能不能到达它”。 视角一换，死结就解开了。

标记与清除

　　最常见的实现叫标记—清除（mark and sweep）：

• 标记：从头遍历，把可达对象打上标记
• 清除：扫一遍内存，把没标记的对象回收掉

　　它的代价，是回收时往往要暂停程序（stop the world），集中做一轮标记和清除——这会带来可感知的卡顿。此外，回收后内存可能变得零碎，还需要“整理”或“复制”来改善（这些属于更细的取舍）。

　　追踪式 GC 用“运行时的停顿”，换来了对循环引用的正确处理和整体视角的简洁。 下一次，我们看看怎样把这种停顿变得更短、更聪明。

思考题 1

　　追踪式 GC 怎样判断一个对象是垃圾？

思考题 2

　　追踪式 GC 为什么能回收引用计数处理不了的循环引用？

小结

知识点

• 追踪式 GC 从根出发做可达性遍历
• 可达对象存活，不可达对象回收
• 标记—清除是常见实现
• 它能处理循环引用，代价是回收时可能暂停

参考资料

1. Wikipedia(zh)：追踪垃圾回收：基于可达性的垃圾回收
2. Wikipedia(zh)：标记-清除算法：先标记存活再清除垃圾

思考题答案（仅供参考）

思考题 1

　　它从根（栈上变量、全局变量等）出发，沿引用关系遍历，把能到达的对象标记为存活；那些从根出发无法到达的对象就是垃圾，可以被回收。

思考题 2

　　因为它判断的是“从根是否可达”，而不只看引用计数。循环引用的对象虽然彼此引用，但若没有任何根能到达它们，就会被判定为不可达而回收。所以它能解开引用计数的死结。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪