垃圾收集算法

3.3 垃圾收集算法

从如何判定对象消亡的角度出发， 垃圾收集算法可以划分为”引用计数式垃圾收集“（Reference Counting GC）和”追踪式垃圾收集“（Tracing GC）两大类，这两类被称为”直接垃圾收集“和”间接垃圾收集“。

3.3.1 当代收集理论

目前商业虚拟机大多遵循了“分代收集”（Generational Collection）的理论进行设计，其是一种经验法则，建立在两个分代假说之上：

• 弱分代假说（Weak Generational Hypothesis）：绝大多数对象都是朝生夕灭的。
• 强分代假说（Strong Generational Hypothesis）：熬过越多次垃圾收集过程的对象就是越难以消灭。

这两个假说共同奠定了常用垃圾收集器的一致设计原则：收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄（年龄既熬过垃圾收集过程的次数）分配到不同的区域之中存储。

将朝生夕灭的对象集中放在一起，每次回收时只关注如何保留少量存活而不是去标记那些大量将要被回收的对象，就能以较低代价回收到大量的空间；

如果剩下的都是难以消亡的对象，那把它们集中放在一块，VM便可以用较低的频率来回收这个区域，这兼顾了垃圾收集的时间开销和内存的空间有效利用。

在Java堆划分出不同的区域之后，因而才有了“Minor GC”，“Major GC”，“Full GC”这样的回收类型的划分；也才能够针对不同的区域安排与里面存储对象的存亡特征相匹配的垃圾收集算法——“标记—复制算法”，“标记—清除算法”，“标记—整理算法”等针对性的垃圾收集算法。

VM设计者一般会把Java堆划分为新生代（Young Generation）和老年代（Old Generation）两个区域。顾名思义，在新生代中，每次垃圾收集时都大批对象死去，而每次回收后存活的少量对象，将会逐步晋升到老年代中存放。

分代收集并非只是简单划分一下内存区域那么容易，它至少存在一个明显的困难：对象不是孤立的，对象之间会存在跨代引用。为了解决这个问题，就需要对分代收集理论添加第三条经验法则：

• 跨代引用假说(Intergenerational reference hypothesis)：跨代引用相对于同代引用仅占极少数。存在互相引用关系的两个对象，是应该倾向于同时生存或同时死亡的。

依据这条假说，就不在需要为了少量的跨代引用去扫描整个老年代，也不必浪费空间专门记录 每一个对象是否存在及存在哪些跨代引用，只需在新生代上建立一个全局的数据结构（记忆集，Remembered Set），这个结构把老年代划分成若干小块，标识出老年代的哪一块内存会存在跨代引用。

术语定义：

• 部分收集（Partial GC）：指目标不是完整收集整个Java堆的垃圾收集，其中又分为：
  • 新生代收集（Minor GC/Yound GC）：指目标只是新生代的垃圾收集
  • 老年代收集（Major GC/Old GC）：指目标只是老年代的垃圾收集。目前只有CMS收集器会有单独收集老年代的行为。
  • 混合收集（Mixed GC）：指目标是收集整个新生代以及部分老年代的垃圾收集。目前只有G1收集器会有这种行为。
• 整堆收集（Full GC）：收集整个Java堆和方法区的垃圾收集

3.3.2 标记-清除算法

“标记-清除”（Mark-Sweep）算法，如其名字一样，分为“标记”，“清除”两部分：首先标记出所有需要回收的对象，在标记完成后，统一回收掉所有被标记的对象，也可以反过来，标记存活的对象，统一回收未被标记的对象。

标记过程就是对象是否属于垃圾的判定过程。

它是最基础的收集算法，后续算法大多基于其改进。它的主要缺点有两个：

• 执行效率不稳定，需要回收的对象多与少会影响
• 内存空间的碎片化

3.3.3 标记-复制算法

标记-复制算法被简称为复制算法，其是为了解决标记-清除算法面对大量可回收对象时执行效率低的问题。

所谓复制算法，就是把内存分为2块等同大小的内存空间（A和B），使用A进行内存的使用，当A部分的内存不足以分配对象而引起内存回收时，就会把存活的对象从A内存块放到B内存块中，后把A内存块中的对象全部清除，在B内存块中使用，当B内存不足以分配内存时，就会把B中存活的对象放到A内存块中，然后把B中对象全部清除，如此循环。

使用这种方式可以避免出现空间碎片（内存中不连续的空间），不过会浪费一半的内存，降低空间的使用率。

这样实现简单，运行高效，不过其缺陷也明显，就是将可用内存缩小了一半。在新生代垃圾收集中使用较多。

3.3.4 标记-整理算法

复制算法在对象存活率较高时就要进行较多的复制操作，效率会降低。

针对老年代对象的死亡特征，于1974年提出的“标记-整理”（Mark-Compact）算法，其中的标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活对象都向内存空间一端移动，然后直接清理到边界以外的内存。

标记-清除算法与标记-整理算法的本质差异在于前者是一种非移动式的回收算法，后者是移动式的。

是否移动回收后的存活对象是一项两难选择：

• 移动：移动存活对象并更新所有引用这些对象的地方是极为负重的操作，而且这种对象移动操作必须全程暂停用户应用程序才能进行。
• 不移动：散布于堆中的存活对象导致的空间碎片化就只能依赖于更复杂的内存分配器和内存访问来解决。

基于以上两点，移动则内存回收时更复杂，不移动则内存分配时更复杂。

从垃圾收集的停顿时间来看，不移动对象停顿时间会更短，甚至不需要停顿，但从整个程序的吞吐量来看，移动对象会更划算。

还有一种“和稀泥”式的方案，既平时用标记-清除算法，暂时容忍内存碎片的存在，直到内存空间的碎片化程度已经大到影响对象分配时，再采用标记-整理算法收集一次，获得规整的内存空间。