垃圾收集算法

现代虚拟机的垃圾收集器大多基于分代收集理论，基于该理论，堆内存被划分出各种不同的区域，不同的区域有着不同的垃圾收集算法。

分代收集理论

分代收集理论建立在两个分代假说之上：

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

这两个分代假说共同奠定了多款常用的垃圾收集器的一致的设计原则：收集器应该将堆内存划分出不同的区域，然后将回收对象依据其年龄（一次垃圾回收，如果对象未被回收，则其年龄加一）分配到不同的区域进行存储。

显然，应该将大多数朝生夕死的对象集中在一起，在垃圾回收时只需关注如何保留少量存活的对象，而不是去标记那些大量将被回收的对象；将那些难以消亡的对象也集中在一起，减少对它们回收的频率。这样就有效的在时间和空间开销上做了权衡。

在堆内存划分出不同的区域之后，垃圾收集器才可以每次只回收其中某个区域的内存——因而才有了Minor GC、Major GC和Full GC回收类型的区分；针对不同区域也采用了适当的垃圾收集算法。

一切看似美好，但区域划分后会存在一个明显的问题：对象都不是孤立存在的，很可能存在跨代引用。

现代虚拟机一般都会将堆内存划分出新生代（Young Generation）和老年代（Old Generation）两个基本区域，对于新生代的回收称为Minor GC，但新生代的对象完全有可能被老年代所引用，同样，老年代的对象也完全有可能被新生代所引用，为了找出对应区域中的存活对象，不得不在固定的GC Roots之外，额外遍历老年代或新生代来确保可达性分析的正确性。遍历整个老年代所有对象的方案虽然理论上可行，但无疑会对内存回收带来很大的性能负担。于是有了第三个分代假说：

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

这个假说可以认为是前两个分代假说的推论：存在互相引用关系的两个对象，倾向于同时生存或同时死亡的。如果某个新生代对象存在跨代引用，由于老年代对象是难以消亡的，该引用会使新生代对象在被回收时存活下来，随后慢慢晋升至老年代，这时跨代引用就不存在了。

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

`GC`分类

新生代收集（Minor GC/Young GC）：对新生代收集。
老年代收集（Major GC/Old GC）：对老年代收集。目前只有CMS收集器会有单独收集老年代的行为。
混合收集（Mixed GC）：对整个新生代以及部分老年代收集。目前只有G1收集器会有这种行为。
整堆收集（Full GC）：对整个堆内存和方法区收集。

垃圾收集算法

标记-清除算法

该算法分为“标记”和“清除”两个阶段：首先使用可达性分析算法标记出所有需要回收的对象，标记完成后统一回收掉所有被标记的对象；也可以反过来，标记所有存活对象，统一回收未被标记的对象。

缺点：执行效率不稳定，如果堆中存在大量对象需要进行回收，则需要进行大量标记和清除的动作，执行效率随对象数量增长而降低；第二个是内存空间的碎片化问题，标记清除后会产生大量不连续的内存碎片。内存碎片太多会导致当需要分配大对象时无法找到连续的内存空间而不得不提前触发再一次的垃圾回收。

标记-复制算法

为了解决标记-清除算法在面对大量可回收对象时执行效率低的问题，有“大佬”提出了一种称为“半区复制”的垃圾收集算法：将可用内存按容量划分为大小相等的两块，每次只使用其中的一块，当这一块内存用完的时候才将其存活着的对象复制到另外一块内存上，然后再把已使用过的内存一次性清除。如果第一半内存中多数对象是存活的，那这种算法将会产生大量的内存间复制的开销，但对于多数对象是可回收状态时，算法就只需复制少量的存活对象，而且每次都是针对一半内存进行回收，内存碎片问题几乎不会出现。这种算法实现容易，执行效率也非常高，但其代价是可用内存缩小为了原来的一半。空间利用率太低。

现代虚拟机大多采用了该算法去回收新生代，有研究表明：新生代中朝生夕死的对象有98%都熬不过第一轮垃圾收集。因此并不需要将新生代划分为大小相等的两块，更好的做法是将新生代划分为一块较大的Eden区域和两块较小的Survivor空间，每次内存分配时只使用Eden区域和其中一块Survivor区域。当发生垃圾回收时，将Eden区和Survivor区存活的对象一次性复制到另一块Survivor区域上，然后直接回收掉Eden区和那块使用过的Survivor区。HotSpot虚拟机默认Eden和Survivor区域的大小比例是8 : 1，也就是说新生代中可用的内存空间为整个新生代的90%，这样空间利用率就达到了90%，虽然还有10%的另一块Survivor区域被浪费，但已经比较理想了。当然，任何人都不能保证研究在实际情况中的正确性，无法保证每次对新生代的回收都只有不多于10%的对象存活，于是存在一个兜底的安全设计：当另一块Survivor区域空间不足以容纳一次Young GC之后存活的对象时，就需要其它内存区域（大多指老年代）进行内存分配担保，将多余的存活对象直接复制到老年代。

标记整理

标记-复制算法在对象存活率较高时就会产生大量的内存间复制开销，优化过后的算法也需要浪费10%的空间，且需要其它空间进行内存分配担保。对于老年代来说，大部分对象都是难以消亡的，所以该算法并不适用于老年代。

针对老年代对象难以消亡的特征，有人提出了另一种有针对性的“标记-整理”算法，标记过程仍然采用的是可达性分析算法，但标记完成后并不是立刻进行回收，而是让所有存活对象都向内存空间一端移动，然后去清理边界以外的内存。

标记整理算法和标记清除算法的本质差异在于是否移动存活的对象，标记清除算法是不移动的，而标记整理算法是移动的。

是否移动存活对象是一个优缺点并存的风险决策。如果移动对象，尤其是在老年代这种每次回收都有大量对象存活的区域，移动存活对象并更新所有引用是一个极为负重的操作，而且这种移动对象操作必须全程暂停用户线程才能执行，这个暂停被称为Stop The World。如果不移动对象，那必然会造成内存碎片问题，而要解决内存碎片问题，就需要依赖更为复杂的内存分配器和内存访问器来解决，无疑加重了内存访问的负担，使程序的吞吐量降低。所以，无论是否移动对象都存在弊端，移动则出现Stop The World；不移动则可以忽略Stop The World的时间，但会产生内存碎片问题，且程序吞吐量降低。