垃圾回收算法详谈

目录

• 分代收集理论
• 标记-清除算法
• 标记-复制算法
• 标记-整理算法

分代收集理论

现在大多数的经典垃圾收集器，都遵循分代垃圾回收，就是将内存分为新生代和旧生代进行分代收回。这样的设计是建立在三种假说上

弱分代假说：绝大数的对象都是朝生夕灭的

强分代假说：熬过越多次的垃圾收集过程的对象就越难消亡

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

根据前两条的假说，就不难理解分代垃圾设计的原因。如果一个区域的对象都是朝生夕灭的话，那么把他们集中在一起，每次都关注如何保留少量的存活对象而不是去标记那些要消亡的对象，就能以较小的代价回收大量的垃圾。而如果多次进行垃圾回收却仍未消亡的对象，那么也将它们集中在一个区域进行管理，在这个区域用比较低的频率进行垃圾回收。这样就能同时兼顾时间消耗和内存的利用。

根据这两条假说，设计者至少会将内存划分为两个区域，一个是新生代，用于存储一开始创建的对象，它们绝大数都逃不了一轮垃圾回收，一个是老年代，存储经过多次垃圾回收后仍存活的对象。但是，分代收集并不是简单的将区域划为为两块那么简单。这是因为对象之间不是孤立的，它们跨代引用。对于跨代引用，假如新生代的对象被老年代的对象引用。那么每次进行垃圾收集时，还需要遍历老年代的对象来找出新生代里存活对象，反之亦然。这样对性能是极大的消耗。因此这就需要第三条假说。依据这样的假说，我们就不需要为少量的引用去扫描整个老年代，只需要在新生代设计一个全局的数据结构，标记老年代哪块内存引用新生代的对象，在进行新生代垃圾回收时只扫描那一块的内存。

标记-清除算法

最早的也是最基础的垃圾回收算法。说它基础是因为后续的垃圾回收算法都是以这个为基础的。该算法分别两个步骤，为标记和清除步骤。标记阶段可以标记存活的对象，那么清除阶段就清除未标记的对象。也能标记未存活的对象，清除阶段就清除已标记的对象。

这个算法有两个缺点。第一个是效率不稳定。如果堆中存在大量的对象，那么标记和清除的效率就很低。也就是说，它的效率会随着对象的增长而减低。第二个缺点就是它会产生大量的内存碎片，内存碎片太多会导致大的对象找不到连续的足够的内存而不得不提前进行新一轮的垃圾回收。

标记-复制算法

标记复制算法是将内存分为两半，每次只使用一块。当其中一块满了后，触发垃圾回收。它将内存里的存活的对象复制到新的一块内存上，然后把原有的那一半内存整块清除。由于每次清除的都是整块对象，所以也没有内存碎片问题，简单高效，速度也很快。不足的之处是需要浪费一半的内存。

现在的虚拟机的新生代大多采用这种算法。由于新生代的每次都能回收98%的垃圾，因此它们并不需要按照1比1的比例划分新生代的。

新生代按照8:1:1的比例划分为Eden区，和两块Survivor区。每次只是用一块Eden和一块Survivor区。进行垃圾回收时，将存活的对象复制到另一块Survivor区，然后清除整块Eden区和被使用的Survivor区。这样只有10%的新生代会被浪费。

标记-整理算法

老年代不适用与标记复制，因为老年代的对象大多数存活，那么需要复制比较多的对象从而导致效率降低，并且对象多，需要额外浪费比较多的内存空间。

针对老年代的对象存亡特性，出现了标记整理算法。标记过程和标记清除算法一样，后续的过程是先将所有的存活对象往内存一一端移动，然后再清除掉边界外所有的内存。

标记整理和标记清除的本地区别就是标记整理是移动式的，标记清除是非移动式的。它们各有利弊。

标记整理的优点当然就是不会产生内存碎片。缺点则是在移动对象时，会产生STW（stop the world），就是用户的程序都会暂停。

从停顿时间上来看，标记整理延迟长，标记清除延迟短。但从吞吐量上，标记整理吞吐量比标记清除大。有些关注吞吐量的垃圾收集器是基于标记整理的。有些关注延迟的垃圾收集器是标记清除的。

当然也有些垃圾收集器两者皆有。一开始采用标记清除，当碎片太多时换成标记整理