最基础的收集算法 —— 标记/清除算法

       之所以说标记/清除算法是几种GC算法中最基础的算法，是因为后续的收集算法都是基于这种思路并对其不足进行改进而得到的。标记/清除算法的基本思想就跟它的名字一样，分为“标记”和“清除”两个阶段：首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象。

       标记阶段：标记的过程其实就是前面介绍的可达性分析算法的过程，遍历所有的GC Roots对象，对从GC Roots对象可达的对象都打上一个标识，一般是在对象的header中，将其记录为可达对象；

       清除阶段：清除的过程是对堆内存进行遍历，如果发现某个对象没有被标记为可达对象（通过读取对象header信息），则将其回收。

       上图是标记/清除算法的示意图，在标记阶段，从对象GC Root 1可以访问到B对象，从B对象又可以访问到E对象，因此从GC Root 1到B、E都是可达的，同理，对象F、G、J、K都是可达对象；到了清除阶段，所有不可达对象都会被回收。

       在垃圾收集器进行GC时，必须停止所有Java执行线程（也称"Stop The World"），原因是在标记阶段进行可达性分析时，不可以出现分析过程中对象引用关系还在不断变化的情况，否则的话可达性分析结果的准确性就无法得到保证。在等待标记清除结束后，应用线程才会恢复运行。

       前面刚提过，后续的收集算法是在标记/清除算法的基础上进行改进而来的，那也就是说标记/清除算法有它的不足。其实了解了它的原理，其缺点也就不难看出了。

       1、效率问题。标记和清除两个阶段的效率都不高，因为这两个阶段都需要遍历内存中的对象，很多时候内存中的对象实例数量是非常庞大的，这无疑很耗费时间，而且GC时需要停止应用程序，这会导致非常差的用户体验。

       2、空间问题。标记清除之后会产生大量不连续的内存碎片（从上图可以看出），内存空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾回收动作。

       既然标记/清除算法有这么多的缺点，那它还有存在的意义吗？别急，一个算法有缺陷，人们肯定会想办法去完善它，接下来的两个算法就是在标记/清除算法的基础上完善而来的。

复制算法

       为了解决效率问题，复制算法出现了。复制算法的原理是：将可用内存按容量划分为大小相等的两块，每次使用其中的一块。当这一块的内存用完了，就将还存活的对象复制到另一块内存上，然后把这一块内存所有的对象一次性清理掉。用图说明如下：

       回收前：

       回收后：

        复制算法每次都是对整个半区进行内存回收，这样就减少了标记对象遍历的时间，在清除使用区域对象时，不用进行遍历，直接清空整个区域内存，而且在将存活对象复制到保留区域时也是按地址顺序存储的，这样就解决了内存碎片的问题，在分配对象内存时不用考虑内存碎片等复杂问题，只需要按顺序分配内存即可。

       复制算法简单高效，优化了标记/清除算法的效率低、内存碎片多的问题。但是它的缺点也很明显：

       1、将内存缩小为原来的一半，浪费了一半的内存空间，代价太高；

       2、如果对象的存活率很高，极端一点的情况假设对象存活率为100%，那么我们需要将所有存活的对象复制一遍，耗费的时间代价也是不可忽视的。

       基于以上复制算法的缺点，由于新生代中的对象几乎都是“朝生夕死”的（达到98%），现在的商业虚拟机都采用复制算法来回收新生代。由于新生代的对象存活率低，所以并不需要按照1：1的比例来划分内存空间，而是将内存分为一块较大的Eden空间和两块较小的From Survivor空间、To Survivor空间，三者的比例为8：1：1。每次使用Eden和From Survivor区域，To Survivor作为保留空间。GC开始时，对象只会存在于Eden区和From Survivor区，To Survivor区是空的。GC进行时，Eden区中所有存活的对象都会被复制到To Survivor区，而在From Survivor区中，仍存活的对象会根据它们的年龄值决定去向，年龄值达到年龄阀值（默认为15，新生代中的对象每熬过一轮垃圾回收，年龄值就加1）的对象会被移到老年代中，没有达到阀值的对象会被复制到To Survivor区。接着清空Eden区和From Survivor区，新生代中存活的对象都在To Survivor区。接着， From Survivor区和To Survivor区会交换它们的角色，也就是新的To Survivor区就是上次GC清空的From Survivor区，新的From Survivor区就是上次GC的To Survivor区，总之，不管怎样都会保证To Survivor区在一轮GC后是空的。GC时当To Survivor区没有足够的空间存放上一次新生代收集下来的存活对象时，需要依赖老年代进行分配担保，将这些对象存放在老年代中。

标记/整理算法

       复制算法在对象存活率较高时要进行较多的复制操作，效率会变得很低，更关键的是，如果不想浪费50%的内存空间，就需要有额外的内存空间进行分配担保，以应对内存中对象100%存活的极端情况，因此，在老年代中由于对象的存活率非常高，复制算法就不合适了。根据老年代的特点，高人们提出了另一种算法：标记/整理算法。从名字上看，这种算法与标记/清除算法很像，事实上，标记/整理算法的标记过程任然与标记/清除算法一样，但后续步骤不是直接对可回收对象进行回收，而是让所有存活的对象都向一端移动，然后直接清理掉端边线以外的内存。

       回收前：

       回收后：

       可以看到，回收后可回收对象被清理掉了，存活的对象按规则排列存放在内存中。这样一来，当我们给新对象分配内存时，jvm只需要持有内存的起始地址即可。标记/整理算法不仅弥补了标记/清除算法存在内存碎片的问题，也消除了复制算法内存减半的高额代价，可谓一举两得。但任何算法都有缺点，就像人无完人，标记/整理算法的缺点就是效率也不高，不仅要标记存活对象，还要整理所有存活对象的引用地址，在效率上不如复制算法。

       弄清了以上三种算法的原理，下面我们来从几个方面对这几种算法做一个简单排行。

效率：复制算法 > 标记/整理算法 > 标记/清除算法（标记/清除算法有内存碎片问题，给大对象分配内存时可能会触发新一轮垃圾回收）

内存整齐率：复制算法 = 标记/整理算法 > 标记/清除算法

内存利用率：标记/整理算法 = 标记/清除算法 > 复制算法

       从上面简单的评估可以看出，标记/清除算法已经比较落后了，但是吃水不忘挖井人，它是后面几种算法的前辈、是基础，在某些场景下它也有用武之地。

终极算法 —— 分代收集算法

       当前商业虚拟机都采用分代收集算法，说它是终极算法，是因为它结合了前几种算法的优点，将算法组合使用进行垃圾回收，与其说它是一种新的算法，不如说它是对前几种算法的实际应用。分代收集算法的思想是按对象的存活周期不同将内存划分为几块，一般是把Java堆分为新生代和老年代（还有一个永久代，是HotSpot特有的实现，其他的虚拟机实现没有这一概念，永久代的收集效果很差，一般很少对永久代进行垃圾回收），这样就可以根据各个年代的特点采用最合适的收集算法。

       新生代：朝生夕灭，存活时间很短。

       老年代：经过多次Minor GC而存活下来，存活周期长。

       在新生代中每次垃圾回收都发现有大量的对象死去，只有少量存活，因此采用复制算法回收新生代，只需要付出少量对象的复制成本就可以完成收集；而老年代中对象的存活率高，不适合采用复制算法，而且如果老年代采用复制算法，它是没有额外的空间进行分配担保的，因此必须使用标记/清理算法或者标记/整理算法来进行回收。

       总结一下就是，分代收集算法的原理是采用复制算法来收集新生代，采用标记/清理算法或者标记/整理算法收集老年代。

       以上内容介绍了几种收集算法的原理、优缺点以及使用场景，它们的共同点是：当GC线程启动时（即进行垃圾收集），应用程序都要暂停（Stop The World）。理解了这些知识，为我们研究垃圾收集器的运行原理打下了基础。以上是我个人学习的一点总结，欢迎交流学习