JVM垃圾收集算法

垃圾收集算法

分代收集理论

根据对象存活周期的不同将内存分为几块，一般将java堆分为新生代和老年代，这样我们就可以根据各个年代的特点选择合适的垃圾收集算法。例如新生代中每次收集都有大量对象（99%）死去，所以可以选择复制算法，只要付出少量对象的复制成本就可以完成每次垃圾收集。而老年代的对象存活几率是比较高的，而且没有额外的空间对它进行分配担保，所以我们必须选择 “标记-清除” 或 “标记-整理” 算法进行垃圾收集

注意

注意：“标记-清除” 和 “标记-整理” 算法都会比复制算法慢十倍以上

标记复制算法

为了解决效率问题，”复制“ 算法算法出现了。它可以将内存划分为大小相同的两块，每次使用其中的一块。当这一块内存使用完之后，就将还存活的对象复制到另一块去，然后再把使用的空间一次清理掉，这样就使每次的内存回收都是对内存区间的一半进行回收。

标记清除算法

算法分为 “标记” 和 “清除” 阶段：标记存活的对象，统一回收未被标记的对象（一般选择这种）；也可以反过来；标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象。

提示

1、效率问题（如果需要标记的对象太多，效率不高）

2、空间问题（标记清除后会产生大量不连续的碎片）

标记整理算法

根据老年代特点特出的一种标记算法，标记过程仍然与 “标记-清除” 算法一样，但后续步骤不是直接对可回收对象回收，而是让所有存活的对象向一端移动，然后直接清理掉端边界以外的内存

垃圾收集底层算法实现

三色标记

在并发标记过程中，因为标记过程中应用程序线程还在跑，对象间的引用可能发生变化，多标和漏标的情况就有可能发生 。三色标记算法就是解决这种问题，把GCRoots可达性分析遍历对象过程中遇到的对象，按照 “是否访问过” 这个条件标记成以下三种颜色

  /**
   * 垃圾收集算法细节之三色标记
   * 为了简化例子，代码写法可能不规范，请忽略
   */
   public class ThreeColorRemark {

     public static void main(String[] args) {
         A a = new A();
         //开始做并发标记
         D d = a.b.d;   // 1.读
         a.b.d = null;  // 2.写
         a.d = d;       // 3.写
     }
   }

  class A {
      B b = new B();
      D d = null;
  }

  class B {
      C c = new C();
      D d = new D();
  }

  class C {
  }

  class D {
  }

• 黑色

  表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无需重新扫描一遍。黑色对象不可能直接（不经过灰色对象）指向某个白色对象

• 灰色

  表示对象已经被垃圾收集器访问过，但是这个对象上至少存在一个引用还没有被扫描过

• 白色

  表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达

多标-浮动垃圾

在并发标记过程中，如果由于方法运行结束导致部分局部变量（gcroot）被销毁，这个gcroot引用的对象之前又被扫描过（被标记为非垃圾对象），那么本轮GC不会回收这部分内存，这部分本应该回收但是没有回收到的内存，被称之为 “浮动垃圾” 。浮动垃圾并不会影响垃圾回收的正确性，只是需要等到下一次垃圾回收中才会被清除。 另外，针对并发标记（还有并发清理）开始后产生的新对象，通常的做法是直接全部当成黑色，本轮不会进行清除，这部分对象期间可能也会变为垃圾，这也算是浮动垃圾的一部分

漏标-读写屏障（并发标记阶段）

漏标会导致被引用的对象被当成垃圾误删除

增量更新（Incremental Update）

• 增量更新就是当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发标记结束后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次，这可简化理解为，黑色对象一旦插入了指向白色对象的引用之后，它就变回灰色对象了

读写快照（Snapshot At The Beginning，SATB）

• 原始快照就是当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次，这样就能扫描到白色的对象，将白色对象直接标记为黑色(目的就是让这种对象在本轮gc清理中能存活下来，待下一轮gc的时候重新扫描，这个对象也有可能是浮动垃圾)

• 写屏障

• - 写屏障实现增量更新 -  - 写屏障实现读写快照 - 

• 读屏障

• 

主流收集器算法实现

• 现代追踪式（可达性分析）的垃圾回收器几乎都借鉴了三色标记的算法思想，尽管实现的方式不尽相同：比如白色/黑色集合一般都不会出现（但是有其他体现颜色的地方）、灰色集合可以通过栈/队列/缓存日志等方式进行实现、遍历方式可以是广度/深度遍历等等

• 对于读写屏障，以Java HotSpot VM为例，其并发标记时对漏标的处理方案

  • CMS：写屏障 + 增量更新
  • G1，Shenandoah：写屏障 + SATB
  • ZGC：读屏障

• 为什么G1用SATB？CMS用增量更新？

  • SATB相对增量更新效率会高(当然SATB可能造成更多的浮动垃圾)，因为不需要在重新标记阶段再次深度扫描被删除引用对象，而CMS对增量引用的根对象会做深度扫描，G1因为很多对象都位于不同的region，CMS就一块老年代区域，重新深度扫描对象的话G1的代价会比CMS高，所以G1选择SATB不深度扫描对象，只是简单标记，等到下一轮GC再深度扫描。

记忆集与卡表

在新生代做GCRoots可达性扫描过程中可能会碰到跨代引用的对象，这种如果又去对老年代再去扫描效率太低了。 为此，在新生代可以引入记录集（Remember Set）的数据结构（记录从非收集区到收集区的指针集合），避免把整个老年代加入GCRoots扫描范围。事实上并不只是新生代、 老年代之间才有跨代引用的问题， 所有涉及部分区域收集（Partial GC） 行为的垃圾收集器， 典型的如G1、 ZGC和Shenandoah收集器， 都会面临相同的问题。 垃圾收集场景中，收集器只需通过记忆集判断出某一块非收集区域是否存在指向收集区域的指针即可，无需了解跨代引用指针的全部细节。 hotspot使用一种叫做“卡表”(Cardtable)的方式实现记忆集，也是目前最常用的一种方式。关于卡表与记忆集的关系， 可以类比为Java语言中HashMap与Map的关系。 卡表是使用一个字节数组实现：CARD_TABLE[ ]，每个元素对应着其标识的内存区域一块特定大小的内存块，称为“卡页”。 hotSpot使用的卡页（在老年代）是2^9大小，即512字节

• 卡表的维护

  • 卡表变脏上面已经说了，但是需要知道如何让卡表变脏，即发生引用字段赋值时，如何更新卡表对应的标识为1。 Hotspot使用写屏障维护卡表状态