[数据结构与算法]垃圾收集算法以及GC过程

概述

??Java语言不同于C、C++，程序员不需要对无用的对象（内存）手动进行回收，JVM虚拟机通过垃圾回收机制自动对无用内存进行回收。而任何一个垃圾收集器都需要解决3个问题：

1. 哪些内存需要回收
2. 什么时候进行回收
3. 如何进行回收

如何判定垃圾

??一开始碰到这个问题的时候，脑海马上浮现出的思路是：一个对象是否判定为“垃圾”，主要是需要判定该对象是否有被其他对象引用，可以考虑在对象被引用的时候对其进行标记，失效的时候再将其设置为失效。从结论上看，很明显，这个没经过推敲的方案漏洞百出，不过却有点引用计数法的味道。

• 引用计数法

??引用计数法的大体思路如下：给对象添加一个引用计数器，每当有一个地方引用这个对象时，就将计数器加一；当引用失效时，计数器就减一，当计数器为0时候，说明这个对象不能再被使用，可以进行回收。

??引用计数法比较好理解，但是它却有一个很大的问题：难以解决循环引用的问题。比如在函数内部创建A和B对象，A对象引用B对象，B对象引用A对象，当函数退出后，这两个对象已经不能被访问，但是按照引用计数法，这两个对象又互相引用，这样计数器就不会被减为0，也就永远不会被回收。

• 可达性分析算法

??可达性分析算法是通过“GC Roots”为起点，从这个节点开始向下搜索，搜索走过的路径称为引用链，当一个对象到GC Roots没有任何引用链相连时，则认为这个对象不可达，即需要进行回收。

??在JAVA中，可以称为GC Roots的对象包括：虚拟机栈本地变量表引用的对象（包括局部变量）、静态变量、常量、本地方法栈JNI中引用的对象。（可以看我的另一篇文章《JVM运行时数据区》）

??当我们用可达性分析算法分析上述的循环引用场景时，会发现由于用可达性分析算法，A对象和B对象即使相互引用，但是当方法退出后，栈帧也相应的销毁，本地变量表也就同步销毁，因此将没有任何GC Roots可以指向A或者B对象，A和B对象都将被判定为“垃圾”回收。

垃圾收集算法

??我喜欢在了解前先进行简单的思考，看到这个马上想到的就是：可以先通过可达性分析找到需要回收的对象，然后再进行回收即可。其实这也是“标记-清除”算法的基本思路。

• 标记清除

??标记清除算法可以分为“标记”和“清除”两部分，首先标记出可以进行回收的对象，标记完成后再进行统一回收。该算法存在两个问题，效率不足且容易产生大量内存碎片。

• 复制算法

??复制算法是将内存分为大小相等的两块，每次只使用其中的一块，当这块内存用完时，就将还存活的对象复制到另一块内存，然后再将这块内存空间一次性清理掉，这种算法的优点在于不需要考虑内存碎片等情况，但是如果都使用这种算法，那么内存的使用率将只有原来的一半，代价有点大，而且在对象存活率较高的情况下，效率体现不出来。

??虽然复制算法有明显的缺陷，但是主流的虚拟机都是采用这个算法回收新生代。因为新生代的对象大部分都是“朝生夕死”的，也就是说实际存活的对象并不会有一半，因此并不需要按照1：1的比例进行内存划分，而是将新生代分为Eden和两块相同大小的Survivor区，比例一般是8：1：1，每次使用Eden和其中一块Survivor，回收的时候将存活的对象复制到另一块Survivor区（空间不足则存放到老年代），之后清理掉Eden区和使用过的Survivor区，也就是说新生代内存空间会造成一块Survivor区内存的浪费，如果比例是8：1：1，则新生代会有10%的内存空间是不可分配的，只能用于回收。

• 标记整理

??由于复制算法的缺陷也是明显的，不适用与大量存活对象的场景，而且复制算法在回收的时候可能存在Survivor区没有足够的空间存放Eden区中存活的对象（总不能丢弃吧），此时这些对象就需要有额外空间进行存放，对于新生代可以将这类对象存放到老年代，而老年代如果使用该算法，要么进行1：1内存分配（浪费50%的空间），否则就需要额外空间进行存放，而新的这块额外空间又需要进行回收。。。显然，复制算法并不适用与老年代。

??由于老年代的特殊性，引出了“标记-整理”算法，标记与“标记-清除”算法一样，不同的地方在于清理过程，“标记-清除”算法是直接进行清理，而“标记-整理”是先将存活对象整理到一端，然后直接清理掉边界以外的内存。

• 分代收集算法

??分代收集算法并不是一个独立的算法，其实就是依据对象存活周期的特点将对象分为新生代和老年代，然后采用各自合适的算法，常规的方式是新生代采用复制算法，老年代采用“标记-清除”或者“标记整理”算法。

内存分配与回收策略

• Eden区分配

??大部分情况下对象都是在Eden区进行分配，只有部分小对象会依据逃逸分析判定，进而会在栈上进行分配，逃逸分析可以通过-XX:-DoEscapeAnalysis进行关闭。

• 大对象直接进入老年代

??前面有说到复制算法的缺点，对于大量存活对象不适用，因此如果在Eden区创建了大对象，而这个大对象暂时又“死不了”，如果这类对象比较多，将会导致Eden区还有不少空间时就提前触发了Minor GC，并反复对其进行复制，严重影响垃圾收集效率以及应用性能。因此可以通过-XX:PretenureSizeThreshold参数进行调优，让大于这个参数的对象直接进入老年代，减少Eden区域和Survivor区进行大量内存复制。

• 长期存活对象进入老年代

??该策略是分代收集理论的基本要求，为的是将长期存活的对象从新生代移动到老年代。为了制定“长期”的标准，虚拟机引入了年龄机制，对象在经过一次Minor GC后（新生代垃圾收集），年龄会加1，当年龄增长到一定程度（默认为15岁），则会移动到老年代，可以通过参数-XX:MaxTenuringThreshold设置。

• 动态年龄判断

??对象并不是必须达到年龄限制才会从新生代移动到老年代，当Survivor空间中有相同年龄对象的大小总和大于Survivor空间的一半，则大于或等于该年龄的对象就会进入老年代。比如设定年龄有1，2，3，……，n，n+1，……，如果在Survivor区中年龄为n的对象占一半以上，那么年龄为n,n+1,……的所有对象则会直接进入老年代。

• 空间分配担保

??在发生Minor GC的时候，如果老年代最大可用的连续空间大于新生代所有对象总空间，则执行Minor GC；当不满足且开启了-XX:-HandlePromotionFailur允许担保参数，那么就会接着判断老年代最大可用连续空间是否大于历史转移到老年代的对象的平均值，如果大于，则触发Minor GC，如果小于或者-XX:-HandlePromotionFailur为关闭状态，则会触发Full GC。

??空间担保机制是一种“预判”机制，既然是预判就不一定正确，在上述情况下，即使Minor GG触发后可能还是需要触发Full GC，相当于白白绕了一圈，又回到Full GC，但是即使如此，担保参数大部分情况下还是打开的，因为这样可以避免Full GC过于频繁。

GC

??GC有分为Minor GC和Full GC，Minor GC 指的是新生代进行垃圾回收的过程，而Full GC会回收老年代也会回收新生代。 一般情况下（部分小对象可能在栈上进行分配），对象是在Eden区进行分配，当Eden区没有足够空间进行分配时，则会执行Minor GC。Minor GC是比较频繁的，但是执行效率比较快，而Full GC回收较慢，而且会发生STW（部分垃圾收集器有进行优化，比如CMS），所以当我们发现频繁出现Full GC时，可以考虑扩大内存，或者通过调整新生代大小/比例等达到优化的目的。

• GC过程

??依据上面的垃圾收集算法以及内存分配策略，我们总结下GC回收的过程。

1. 当Eden区没有足够的内存分配时，则首先对“空间分配担保”机制进行判断，当该机制允许触发Minor GC时，则触发Minor GC。如果不允许，则触发Full GC。刚开始一般老年代最大可用的连续空间是大于新生代所有对象总空间的，所以会触发Minor GC。
2. 当触发Minor GC时，虚拟机会标记Eden区以及其中一个使用的Survivor0区（第一次两个都为空,所有不会触发“长期存活对象进入老年代机制”以及“动态年龄判断机制”），之后采用复制算法将存活的对象从Eden区和Survivor0复制到Survivor1区，不够存放的对象则直接放到老年代中，之后清空Eden区和Survivor0区。
3. 当程序继续运行时，则会再次出现Eden区没有足够的内存进行分配，则继续执行步骤1，当允许触发Minor GC时，此时由于Survivor区不为空，则需要判定是否满足“长期存活”或者“动态年龄判断机制”，如果满足，则直接进入老年代，如果不满足，则同样采用复制算法进行回收，不同的是此时是将Eden区和Survivor1区中存活的对象复制到Survivor0区，之后清空Eden区和Survivor1区。
4. 以此类推，由于复制算法必须保证其中一个Survivor区为空，所以每次触发Minor GC后，空闲的Survivor区将从Survivor0区切换到Survivor1区，或者从Survivor1区切换到Survivor2区。
5. Full GC的触发主要是为了回收老年代，其触发条件为当老年代没有足够的空间进行分配或者虚拟机认为老年代没有足够的空间进行分配时（空间担保机制）。场景主要有三种：一是当对象大小满足“大对象直接进入老年代”规则，而此时老年代又没有足够的空间进行分配时，则会触发Full GC；二是当触发Minor GC之后，仍然没有足够的空间进行对象分配时，则会触发Full GC。三是当“空间担保机制”判定需要进行Full GC时，即会触发Full GC。