---

垃圾收集算法

JVM在生成了一个对象之后,对于那些标记为"死亡"的对象就要进行回收处理.从判定对象是否"死亡"的角度出发,垃圾回收算法可以分为"引用计数垃圾回收" 和 “追踪垃圾回收(Tracing GC)”.但是之前我们也了解到,绝大多数JVM中没有采用引用计数算法来判定一个对象是否死亡.所以JVM主要采用的是追踪垃圾回收算法.,但是由于追踪垃圾回收算法遵循"分代回收"理论进行设计.所以对分代假说进行了解是很有必要的.

1.分代收集理论

在JVM中大部分的对象都是朝生夕灭,但是如果一个对象"熬过"了多次垃圾收集还存活下来,那么就说明它越难消亡.所以JVM中将堆中的对象分为两类:新生代对象和老年代对象.并将堆分为两个区域来分别存放两类对象.新生代(Young Generation和老年代(Old Generation).而根据不同的区域.GC可以根据两个部分的不同特点来分别进行收集.但是如果只是简单地将堆内存看成两个分割的部分的话就可能产生问题.
比如说,来一次只针对新生代的MinorGC的话,如果新生代中的对象被老年代中的对象引用 既 跨代引用(但是这是非常罕见的),那么就不得不在固定的GC Roots之外,对整个老年代进行搜索来验证可达性分析的正确性.因为如果一个新生代对象产生了跨代引用,由于老年代对象是难以销毁的,所以新生代对象也会变得难以销毁.

对此我们也有一个解决方案.那就是在新生代区域建立一个全局的数据结构(记忆集),来将老年代分为几个部分,并记录老年代的哪些部分会产生跨代引用,那么此后进行MinorGC的时候就会将老年代中产生跨代引用的部分也加入到可达性分析中.

GC可以进行针对不同区域的垃圾收集.

• Minor GC/Young GC(新生代收集):针对新生代进行收集.
• Major GC/Old GC(老年代收集):只针对老年代进行收集,目前只有CMS收集器会有这样的行为.
• Mixed GC(混合收集):收集整个新生代和部分老年代,目前只有G1收集器才有这样的行为
• Full GC(整堆收集):收集整个java堆和方法区

2.标记-清除算法(Mark-Sweep)

标记清除算法是最早出现,也是最基础的GC算法.人如其名,这种算法分为两步:标记(Mark) 和 清除(Sweep).首先标记出所有需要清除的对象,然后统一回收被标记的对象.这种算法简单而且易于理解.但是存在很多缺点:

• 大多数情况下效率低:因为java堆中大部分的对象都是朝生夕灭需要进行收集.所以要进行大量的标记和清除.需要清除的对象越多,效率越低
• 产生内存空间的碎片化问题:对堆内存中空间进行收集后,会产生大量不连续的空间(碎片化).这样就会导致今后如果要分配一个大的对象,堆中总内存空间是足够的,但是由于碎片化,没有足够大的连续空间来进行分配.

标记清除算法示意图:

3.标记-复制(Mark-Copying)—适用于新生代

标记复制算法简称复制算法.

3.1初始阶段

研究人员针对标记-消除算法碎片化的缺点.研究出另一种算法—半区复制(Semispace Copying),半区复制算法将内存区域对半分.其中一半用于分配内存.另一半则用于存放存活的对象.

半区复制的具体操作是:将一个半区内进行GC后存活的对象复制到另一半区并顺序排列.如果内存大部分对象都会被回收的话,那么只需要复制少部分的对象即可.

所以这种算法适合新生代.但是这种算法有一种致命的缺点:空间浪费实在是太大了,50%的空间都无法用来分配内存.那么有没有什么改进手段呢?

3.2优化

基于半区复制算法和新生代朝生夕灭的特点,研究人员提出来一种更为优化的算法.称为"Appel回收".那么它是怎么进行优化的呢?想一想,既然新生代绝大多数对象都会很快被回收,那么需要使用一半的空间来存放存活的对象吗?.

所以Appel回收的具体策略是:将新生代不再简单粗暴地分成两个相等的区域,而是分成了一块较大的Eden空间(80%)和两块较小的Survivor(共20%)空间.每次分配时只使用Eden和一块Survivor空间.发生垃圾回收的时候,将已分配空间中仍然存活的对象一次性的复制到另外的一块Survivor空间上.这样只有一个Survivor区域(10%)会被浪费.

Appel算法示意图:

但是这样也可能会出现一点小问题:虽说新生代对象有98%都熬不过第一轮垃圾收集(IBM研究得出),但是谁都没有办法百分百保证,每次回收只有不超过10%对象存活,如果出现了存活对象内存大于Survivor区域,Survivor区域不够放怎么办呢?Appel算法提供了一个安全保障:但Survivor空间不够存放一次Minor回收后存活的对象,那么会去依赖于其他的内存区域(实际上,大多数情况都是老年代)进行分配担保(Handle Promotion)

4.标记-整理算法(Mark-Compact)适用于老年代

标记-复制算法很适合存活对象非常少的新生代区域.但是在老年代就不再适用了.所有针对老年代的存完特性.1974年研究人员提出来一种针对性的算法—“标记-整理算法(Mark-Compact)”.

标记整理算法的标记过程和标记清除算法是一样的.但是后续步骤不是直接进行回收.而是将所有存活后的对象向内存的一段移动,然后将存活边界以外的所有对象都清除掉.算法示意图如下:

标记-清除算法和标记-整理算法本质上的差异就在于前者是一种非移动式的回收算法,而后者是移动式的.是否移动存活后对象是一项优缺点并存的风险决策.因为移动对象尤其是老年代大量的对象是一种极为负重的操作.

4.2另一种思考方式

此外,还有一种"和稀泥式"的解决方案:就是让虚拟机大部分时间都采用标记清除算法,暂时容忍内存碎片的存在,直到内存中的碎片化程度已经达到影响对象的内存分配时,再采用标记整理算法来对空间碎片进行一次整理.