GC垃圾收集算法详解
一、垃圾标记算法
1、对象存活判断
只有对堆内存上对象进行标记出哪些是存活的，哪些是死亡（不再被其他存活对象引用）对象。被标记为死亡的对象在GC时被回收。
判断对象存活主要有两种方式
（1）引用计数（java未选择，python选择）
每个对象保存一个整型的引用计数器属性，用于记录对象被引用的情况。
算法思想：
对于一个对象A，只要有任何对象引用了A，则A的引用计数加1，当引用失效，此时引用计数器减1。一旦引用计数器值为0，则可以被回收。
优点：
实现简单，垃圾对象便于辨识，判定效率高，回收没有延迟
缺点：
1）需要单独的字段存储计数器，这样的做法增加了存储空间的开销
2）每次都需要更新计数器，增加了更新时间开销
3）无法处理循环引用，这也是java回收器没有使用的主要原因。
举例，循环引用如下图所示，p变量使用完后指向null，理论上来说之前指向的对象要被回收，但是由于存在循环引用，导致rc最后都为1，无法回收。
注意：python使用了引用计数，python解决循环引用主要有两方面
1）手动解除
2）使用弱引用。
（2）可达性分析（根搜索算法，追踪性垃圾收集算法）（java和c#选择此算法）
算法思想：
1）以根对象集合（GC Roots）为起点，按照从上到下的方式搜索被根对象集合所连接的目标对象是否可达。
2）内存中存活的对象都被根对象集合直接或者间接连接着，搜索所走过的路径称为引用链。
3）如果目标对象没有任何引用链相连，则不可达，意味着该对象已经死亡，标记为垃圾。
GC Roots
1）虚拟机中引用的对象
各个线程被调用的方法中使用的参数，局部变量等
2）本地方法栈内的JNI引用的对象
3）方法区类静态属性引用的对象（jdk7后再堆中）
java类的引用类型静态变量
4）方法区中常量引用的对象（jdk7后String Table移入堆中）
5）被同步锁持有的对象
6）虚拟机内部的引用
Class对象，异常对象，系统类加载器等
注意：
1）GC Roots除了上面提到的，用户在选择垃圾收集器回收内存区域时，有可能有其他对象临时加入到GC Roots中，比如分代收集，局部收集器等。原因是，在垃圾回收时，收集的区域内的对象有可能被其他区域的对象引用，这是为了保证可达性分析的准确性。
2）如果使用可达性分析来判断内存对象是否可以被回收，那么必须保障一致性的快照中进行，如果没有快照，则准确性无法满足。所以这也是导致GC的Stop the world的原因。即使CMS收集器号称几乎不会停顿，但是在枚举根节点时也是要停顿的。
二、垃圾清除算法
当成功区分内存存活对象和死亡对象后，GC下面开始执行垃圾回收，释放无用的对象所占用的内存空间，以便有足够的可用内存空间为新对象分配
1、标记清除
当堆中有效内存空间被耗尽时，就会停止整个程序，然后进行两项工作，第一是标记，第二是清除
算法原理
（1）标记
从根节点开始遍历，标记所有被引用的对象，一般是对象的Header中记录为可达对象
（2）清除
对堆内存从头到尾进行线性遍历，如果发现某个对象在Header中没有标记为可达对象，则将其回收。
这里的清除并不是正真的置空，而是把清除的对象地址保存在空闲列表中，下次有新对象分配内存时如果空闲列表空间够用就分配。
、
缺点：
（1）效率不高
（2）GC时需要停止整个程序，用户体验差
（3）清理后的内存不是连续的，会产生内存碎片，需要维护一个内存空闲列表
2、复制算法
算法思想
将活着的内存空间分为两块，每次只使用其中一块，在垃圾回收时，将正在使用的活对象复制到未被使用的内存块中，之后清除正在使用的内存块中的所有对象，交换两个内存的角色，最后完成垃圾回收。
‘优点
（1）没有标记-清除过程，实现简单，效率高
（2）内存空间是连续的，不会产生碎片
缺点
（1）需要两倍的内存
（2）对于G1分拆大量region的GC，复制而不移动，意味着GC需要维持region之间的对象引用关系，不管是内存占用或者时间开销也不小。
总结：该算法适合活对象较少的场景
3、标记-压缩算法
复制算法的高效建立在存活对象少，垃圾对象多的场景，所以，复制算法适合新生代。但是在老年代，大部分对象都是活对对象，此时使用复制算法就不太好了。
算法原理
（1）从根节点开始标记所以被引用的对象
（2）将所有存活对象压缩到内存一端，按顺序存放
（3）清理空余空间
标记压缩与标记清除区别，标记-清除是非移动式回收算法，标记-压缩是移动式回收。
优点
（1）jvm在分配对象内存时不需要维护空闲列表了，而维护一个起始地址
（2）没有复制算法的两倍内存问题
缺点
（1）效率低于复制算法
（2）移动对象，如果该对象被其他对象引用，还需要调整引用地址
（3）移动中，需要暂停用户线程
三、分代收集算法
在hotSpot中，GC所使用的内存回收算法必须结合年轻代和老年代各自的特点
1、年轻代
内存区域小于老年代，对象是朝生夕死，回收频繁，使用复制算法速度最快，年轻代的survivor的设计使用了复制算法。
2、老年代
内存区域大，对象生命周期长，回收频率低于年轻代，适合使用标记-清理，标记压缩算法
四、增量收集和分区算法
标记清除，标记压缩，复制算法，都会停止用户线程，为了解决暂停用户线程的问题，即产生了实时垃圾回收的算法的诞生。
1、增量收集
算法思想
如果一次性将所有的垃圾进行处理，需要造成系统的长时间停顿，那么就可以让垃圾收集线程和应用程序线程交替执行，每次垃圾收集线程只收集一小片区域的内存空间，接着切换应用程序线程，依次反复，直到垃圾收集完成。
其实，增量收集算法通过分阶段完成（标记清除、标记压缩、复制）的工作。
缺点
使用这种方式，垃圾回收是间断性的执行，用户停顿时间减少了，但是会出现垃圾回收线程和用户线程频繁切换，造成上下文切换的消耗，使得垃圾回收总体成本上升，造成系统吞吐量下降
2、分区算法
堆空间越大，GC时间越长，用户停顿时间越长。为了解决这个问题，出现了分区算法
算法思想
将一大块内存分割成多个小块（region），根据目标停顿时间，合理的回收若干个小区间，从而减少一次GC所产生的停顿。每个小区间是独立使用，独立回收。