常见的垃圾回收算法

分代收集理论

当前商业虚拟机的垃圾收集器，大多数都遵循了“分代收集”的理论进行设计，分代收集名为理论，实质是一套符合大多数程序运行实际情况的经验法则，它建立在两个分代假说之上：

1. 弱分代假说：绝大多数对象都是朝生夕灭的
2. 强分代假说：熬过越多次垃圾收集过程的对象就越难以消亡

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

但是，还存在一种情况，就是新生代的对象被老年代的对象引用了。为了找出这些对象，不得不遍历整个老年代。虽然理论上方案可行，但是会给回收带来很大的内存损耗。这时就需要对分代收集理论再加上一条经验法则：

1. 跨代引用假说：跨代引用相对于同代引用来说仅占极少数。

依据这条假说，我们就不应再为了少量的跨代引用去扫描整个老年代，也不必浪费空间专门记录每一个对象是否存在以及存在哪些跨代引用，只需在新生代上简历一个全局的数据结构（该结构被称为“记忆集”， Remembered Set），这个结构把老年代划分为若干小块，表示出老年代的哪一块内存会存在跨代引用。此后，当发生Minor GC时，只有包含了跨代引用的小块内存里的对象才会被加入到GC Roots进行扫描。虽然这种方法需要在对象改变引用关系时维护记录数据的正确定，会增加一些运行时的开销，但比起收集时扫描整个老年代来说认识划算的。

标记-清除

标记清除算法主要分为两个步骤：标记、清除

标记：标记存活的对象或者标记需要回收的对象

清除：回收未被标记的对象或者回收标记的对象

可参见下图

标记清除算法存在两个明显的缺点：

1. 执行效率不稳定，标记和清除两个过程的执行效率是和对象的数量成反比的；
2. 内存空间碎片化：会产生大量不连续的内存碎片，导致后期无法分配大对象的内存。

标记-整理

标记整理算法和标记清除算法差不多，不同的是，它的第二个步骤是把产生的内存碎片全部移到一起。

标记整理算法也存在比较明显的缺点：

1. 移动对象的时候会增加虚拟机停止的时间，也就是STW（Stop The World）的时间。

标记-复制

标记复制算法是为了解决标记清除算法面对大量可回收对象时执行效率低的问题。它把可用内存按照容量划分为大小相等的两块，每次只使用其中的一块。当一块的内存用完了，就将存活着的对象复制到另一块上面，然后把已经使用完的内存空间清空。

标记复制算法的缺点显而易见：

1. 它每次只能使用50%的内存空间，空间利用率太低

并发的可达性分析

标记阶段是所有追踪式垃圾收集算法的共同特征，如果这个阶段会随着堆变大而等比增加停顿时间的话，其影响就会波及几乎所有的垃圾收集器。同理，如果能够消减这部分停顿时间的话，那收益也将会是系统性的。

想解决或者降低用户线程的停顿，就要先搞清楚为什么必须在一个能保障一致性的快照上才能进行对象图的遍历？为了能够解释清楚这个额问题，我们引入三色标价作为工具辅助推导，把遍历对象图过程中遇到的对象，按照“是否访问过”这个条件标记成以下三种颜色：

• 白色：表示对象稍微被垃圾收集器访问过。显然，在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色对象，即代表不可达。
• 黑色：表示对象已经被垃圾收集器访问过，并且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过，它是安全存活的。如果有其他对象引用指向了黑色对象，无需重新扫描以便。黑色对象不可能直接（不经过灰色对象）指向某个白色对象。
• 灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少还存在一个引用还没有被扫描过。

对CMS收集器来说，用户线程和标记线程是同时工作的，那么可能存在两种情况：

1. 将原本已经消亡的对象标记为存活，虽然不是什么好事，但是可以接受
2. 将原来的存活对象误标识为已消亡，可以回收，那就是致命的问题。

下面几张图就演示了这种情况是如何发生的：

初始状态，只有GC Roots是黑色的。

扫描过程中，以灰色为波峰的波纹从黑向白推进

扫描顺利完成，此时黑色对象就是存活对象，白色对象就是已消亡可回收对象

在扫描的过程中，用户取消了灰色对象B到C的引用，同时又增加了A到C的引用。因为此时A已经完成扫描，是为黑色，所以A不会再次扫描，除了A之外，再也无其他对象指向C，C就成为了消失的对象。

此时，删除了灰色对象B到白色对象C的引用，新增了黑色对象A到白色对象D的引用。因为A对象不会再次扫描，没有其他对象指向C，此时，C和D对象就成了消失的对象。

对象消失的条件

Wilson于1994年从理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”问题。即原本应是黑色的对象被误标为白色：

• 赋值器插入了一条或多条从黑色对象到白色对象的引用；
• 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

因此，要解决并发扫描时的对象消失问题，只需要破坏这两个条件中的任意一个即可。由此分别产生了两种解决方案：增量更新和原始快照。

增量更新

增量更新破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，再扫描一次。这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。CMS是基于增量更新来做并发标记的。

原始快照

原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将会这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过引用关系中的灰色节点微耕，重新扫描一次，这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描的那一刻的对象图快照进行搜索。G1和Shenandoah使用原始快照来做并发标记的。

新生代分区

新生代内存区域是使用标记复制算法来回收内存的。但是它不是按照1：1的比例分成两块内存区域。而是分为了一块较大的Eden空间和两块较小的Survivor空间，比例是8：1：1.这样每次新生代就有90%的空间是可以使用的。

每次都会在Eden空间上分配内存，然后新生代回收的时候会把存活的对象（Eden区和其中一块Survivor区域，如果有存活对象的话）移动到其中的另一块Survivor空间上。

分配担保

大多数情况下，新生代98%的对象都是朝生夕死的，但是谁也不能保证，新生代每次回收的时候内存不超过新生代大小的10%。这个时候就要依赖于分配担保了。当Survivor区域的内存不够一次Monor GC之后存活的对象时，就需要依赖其他内存区域（实际上大多数是老年代）进行分配担保。

如果一块Survivor空间没有足够空间存放上一次新生代收集下来的存活对象，这些对象便将通过分配担保机制直接进入老年代。

名词解释

名词	释义	解释
MinorGC/Young GC	新生代收集	目标只是新生代的垃圾收集
Major GC/Old GC	老年代收集	目标只是老年代的垃圾收集。当前只有CMS收集器会有单独收集老年代的行为。另外，需要注意“Major GC”，有的资料上还指整堆收集
Mixed GC	混合收集	指目标时手记整个新生代及部分老年代的垃圾收集器。目前只有G1收集器会有这种行为。
Full GC	整堆收集	收集整个Java堆和方法区的垃圾收集。