垃圾回收统一理论

所有的 GC 算法其存在形式可以归结为追踪（Tracing）和引用计数（Reference Counting）这两种形式的混合运用。

• 追踪式 GC：从根对象出发，根据对象之间的引用信息，一步步推进直到扫描完毕整个堆并确定需要保留的对象，从而回收所有可回收的对象。

• 引用计数式 GC：每个对象自身包含一个被引用的计数器，当计数器归零时自动得到回收。因为此方法缺陷较多，在追求高性能时通常不被应用。

目前比较常见的 GC 实现方式包括：

• 追踪式，分为多种不同类型，例如：
  • 标记清扫：从根对象出发，将确定存活的对象进行标记，并清扫可以回收的对象。
  • 标记整理：为了解决内存碎片问题而提出，在标记过程中，将对象尽可能整理到一块连续的内存上。
  • 增量式：将标记与清扫的过程分批执行，每次执行很小的部分，从而增量的推进垃圾回收，达到近似实时、几乎无停顿的目的。
  • 增量整理：在增量式的基础上，增加对对象的整理过程。
  • 分代式：将对象根据存活时间的长短进行分类，存活时间小于某个值的为年轻代，存活时间大于某个值的为老年代，永远不会参与回收的对象为永久代。并根据分代假设（如果一个对象存活时间不长则倾向于被回收，如果一个对象已经存活很长时间则倾向于存活更长时间）对对象进行回收。
• 引用计数：根据对象自身的引用计数来回收，当引用计数归零时立即回收。

追踪式 GC

TODO:

引用计数式 GC

TODO:

垃圾回收统一定理

虽然在实践中我们有追踪式和引用计数式两种 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.