GC一探究竟（二）

1.前言

在上一篇博客中介绍了关于GC的一些对象回收判断以及简单介绍了方法区的回收，但你们有没有想过，内存的垃圾是如何收集的。因此，本文将讲述几种常见的垃圾收集算法。

2. 标记-清除算法

2.1 原理

该算法分为标记，和清除两个过程，其中，标记过程便是使用可达性分析算法，从GC Roots开始遍历，在可达对象中的对象头进行标记。而在清除过程，在堆内存中从头到尾进行线性遍历，清除不可达对象。同时，还需要将存活对象的标记清除掉，以便为下一次GC操作做好准备 。

2.2 优点

对于存活对象多的情况下，可以减少对象的移动（相对于下面的复制算法），提高效率。

2.3 缺点

• 标记和清除过程，是两个遍历的过程，两次遍历，效率不高
• 很明显，当我们清除之后，会产生大量的不连续内存，存在过多的不连续内存，会导致在给大对象分配的内存空间的时候，会因为内存不足而频繁的进行GC操作，降低程序效率

3. 复制算法

3.1 原理

image

复制算法的原理便是把一整块的空间分为两块，每次只使用一块，当一块使用完之后，可将不回收的对象复制到另一块上，然后将旧的一块的内存全部清空。

具体：当有效内存空间耗尽时，JVM将暂停程序运行，开启复制算法GC线程。接下来GC线程会将活动区间内的存活对象，全部复制到空闲区间，且严格按照内存地址依次排列，与此同时，GC线程将更新存活对象的内存引用地址指向新的内存地址。

3.2 优点

• 对比标记-清除算法，采用复制算法，明显可以减少大量的不连续内存空间。
• 对比标记-清除算法，可提高效率，不用两次遍历，只需一次遍历，复制完之后，便可以清除旧空间内存。

3.3 缺点

• 很明显，需要分出一半的空间进行复制用，会损失一半的内存，是典型的空间换时间的实现。
• 相对于一些存活对象很多的情况下，则需要复制的对象过多，将会降低效率，因此它适用于存活量少的区域回收内存。

3.4 应用举例

堆中的新生代区（后面会讲）中的98%的对象都是”朝生夕死“的，因此特别适合用复制算法回收，而且由于存货量很少，不需要划出一半的内存用做保留区。而是划出一块较大的Eden和两块较小的Survivor空间，在HotSpot中，Eden：Survivor=8:1。

当回收的时候，将Eden和Survivor中的存活对象复制到另一个Survivor中，然后回收掉它们的全部内存，之后那块Survivor就作为保留区用。

但是，这样算下来，堆中新生代的10%内存会被浪费，也即是用来存放每次回收存活对象的内存之后新生代的10%。我们无法保证每次回收都只有不多于10%的对象存活。当Survivor空间不够用的时候，需要依赖其他内存（这里指老年代）进行分配担保，也即不够存放的那些对象将直接通过分配担保机制进入老年代。（分配担保，后面会讲）

4. 标记-整理算法

4.1 原理

image

标记-整理算法分为标记和整理两个阶段，标记过程就是和标记-清除过程是一致的，而标记之后，后续的步骤并不是直接清理可回收对象，而是让所有存活的对象都向一端移动，然后直接清除掉端边界以外的内存。

4.2整理过程

由标记-整理算法可以很清楚的知道，标记-整理算法的整理过程的工作便是，移动存活对象和更改所有指向被移动对象的指针。

4.1.1 整理顺序

• 任意顺序：对象的移动方式和它们初始的对象排列和引用关系无关
• 线性顺序：将具有关联关系的对象排列在一起
• 滑动顺序：整理之后的对象顺序与原先的不变

现在大多数的垃圾收集算法都是按照任意顺序或滑动顺序去实现的。

4.1.2 双指针算法

双指针算法属于任意顺序的整理算法，适用于固定大小对象的区域。

1. 过程原理

需要访问两次堆内存

• 第一次：将内存尾部的可达对象移动到头部的空闲区域
• 第二次：修改可达对象的引用，指向引用的新地址

2.第一次遍历

原理：在内存区域的头部有个free指针，尾部有个scan指针，free指针向后遍历，直到找寻到第一个空闲区域（没有标记为可达对象的区域），此时scan指针向前遍历，直到找寻到第一个存活对象，将存活对象移动到free指针下的空闲区域，并且把移动的位置记录在原先的位置上（用于第二次遍历的时候，修改引用）。重复以上操作，直到free指针和scan指针重复。结束第一次遍历。

3. 第二次遍历

第二次的遍历目的在于修改被移动的对象的引用，更新为移动之后的位置。因此需要从GC Roots开始进行遍历，如果发现引用指向的地址指针是在第一次遍历之后的指针后面的，则说明该对象已经被移动，则取出其储存的新位置的指针，修改其引用，重复操作，直到遍历结束。

4.1.3 Lisp 2 整理算法

Lisp2算法是属于滑动顺序的一种，应用更为广泛，对比双指针算法，它可以处理不同大小的对象。它的缺陷在于，需要每个对象头部额外增加一个完整的域(forwardingAddress)来记录转发地址。

1. 过程原理

• 第一次遍历将所有存活对象的 forwardingAddress 域指向最后要移动到的地址。
• 第二次遍历将所有指向存活对象的引用都修改为相应对象的 forwardingAddress。
• 第三次遍历将所有存活对象转移到 forwardingAddress 中。

2. 第一次遍历

• 设置两个指针在内存区域的头部，分别是free指针和scan指针，free指针指向的区域代表的是后面遍历的第一个存活对象所存储的地址，scan指针用于遍历后面的存活对象。
• 如图所示，scan指针向后移动，访问到的第一个存活对象是B，因此，需要在B对象记录的转发地址是free指向的地址，即0。此时free需要将指针后移，而后移的距离便是B对象的内存大小，作为下个存活对象的转发地址，接下来便是scan指针继续向后遍历，寻找存活对象。
• 继续重复过程，直到遍历到内存区域尾部。

3. 第二次遍历

第二次遍历是修改所有的存活对象的引用

• 修改GC Roots对象的引用，如，根对象1引用对象B，由于对象B的迁移地址是0，因此，根对象1中对对象B的引用就要改为其转发地址
• 同理，修改其他根对象
• 通过scan指针遍历堆内存，更新所有的可达对象对其引用对象的引用为其引用对象的迁移地址。比如说，对于可达对象B， 它引用了对象D，D的迁移地址是2，那么B直接将其对D对象的引用重新指向2这个位置。
• 第二次遍历结束后的对象之间的引用关系。

4. 第三次遍历

5300ad940cf2a3dc99ddf4c4.png

第三次遍历则是根据可达对象的迁移地址去移动可达对象，比如说可达对象B，它的迁移地址是0，那么就将其移动到位置0，同时去除可达对象的标记，以便下次垃圾收集。

5. 分代收集算法

根据对象的存活周期的不同将内存划分为几块。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用“标记-清理”或“标记-整理”算法来进行回收。

6.总结

• 前三个算法都是基于根搜索算法去判断一个对象是否应该被回收，分代收集算法其实就是前三个算法的一个有机结合。
• 在GC线程开启时， 或者说GC过程开始时候，都要暂停应用程序（stop the world）。

欢迎关注本人博客：https://allen-yu.com/