所有的 GC 算法其存在形式可以归结为追踪(Tracing)和引用计数(Reference Counting)这两种形式的混合运用。
- 追踪式 GC:从根对象出发,根据对象之间的引用信息,一步步推进直到扫描完毕整个堆并确定需要保留的对象,从而回收所有可回收的对象。
- 引用计数式 GC:每个对象自身包含一个被引用的计数器,当计数器归零时自动得到回收。因为此方法缺陷较多,在追求高性能时通常不被应用。
目前比较常见的 GC 实现方式包括:
- 追踪式,分为多种不同类型,例如:
- 标记清扫:从根对象出发,将确定存活的对象进行标记,并清扫可以回收的对象。
- 标记整理:为了解决内存碎片问题而提出,在标记过程中,将对象尽可能整理到一块连续的内存上。
- 增量式:将标记与清扫的过程分批执行,每次执行很小的部分,从而增量的推进垃圾回收,达到近似实时、几乎无停顿的目的。
- 增量整理:在增量式的基础上,增加对对象的整理过程。
- 分代式:将对象根据存活时间的长短进行分类,存活时间小于某个值的为年轻代,存活时间大于某个值的为老年代,永远不会参与回收的对象为永久代。并根据分代假设(如果一个对象存活时间不长则倾向于被回收,如果一个对象已经存活很长时间则倾向于存活更长时间)对对象进行回收。
引用计数:根据对象自身的引用计数来回收,当引用计数归零时立即回收。
追踪式 GC
引用计数式 GC
垃圾回收统一定理
虽然在实践中我们有追踪式和引用计数式两种 GC 的形式,但在理论上我们能够对其进行统一描述, 这就是垃圾回收统一定理(Unified Theory of GC) [Bacon et al. 2004]。
内存中对象及其指针所组成了一个对象图,我们不妨令所有对象组成的集合为 $V$, 设指针所指链接对象的多重集为 $E$。由于我们不应该释放一个会在未来会被使用的对象, 如果我们不对任何赋值器进行分析而是进行保守地估计,则如果从栈或寄存器出发存在到达对象的路径, 则该对象将在未来被使用,记这些路径的起始对象组成的集合为根集合 $R$。则对象的引用计数 $\rho (v)$(其中 $v\in V$)可以由下述的递归定点表示进行计算:
\rho (v) = |[v: v\in R]| + |[(w, v) : (w,v) \in E \land \rho(w) > 0]|
TODO: 将 追踪式和引用计数式 GC 用定点表示进行描述
TODO: 讨论统一定理的指导意义进一步阅读的参考文献
[Bacon et al. 2004] Bacon, David F., Perry Cheng, and V. T. Rajan. “A unified theory of garbage collection.” ACM SIGPLAN Notices 39.10 (2004): 50-68.