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