算法简介

• 三色标记算法是一种并行的垃圾标记算法，可以在用户线程执行时并行发的进行垃圾标记操作，减少程序的STW时间，增强用户的体验，在Java中，常见的CMS，G1，ZGC等垃圾回收器就是使用了该算法进行垃圾标记

• 三色标记算法的三色即为对象的状态：

  • 白色：表示对象尚未被垃圾收集器访问过
  • 灰色：表示对象自身被检查了，成员没被检查完
  • 黑色：表示对象自身和成员都被检查完了

• 三色标记算法的优缺点

  • 优点：可以异步执行，减少GC的STW时间
  • 缺点：会造成漏标和错标的问题

算法执行过程

1. 在初始阶段的时候，所有的对象都是存放在白色容器中

   

2. 初始标记阶段，GCRoot标记直接关联对象置为灰色

   

3. 并发标记阶段，扫描整个引用链，有子节点的话，则当前节点变为黑色，子节点变为灰色

   

4. 重复并发标记阶段，直至灰色对象没有其它子节点引用时结束

   

5. 扫描完成，此时黑色对象就是存活的对象，白色对象就是已消亡可回收的对象

算法缺陷

• 浮动垃圾 ：并发标记的过程中，若一个已经被标记成黑色或者灰色的对象，突然变成了垃圾，由于不会再对黑色标记过的对象重新扫描,所以不会被发现，那么这个对象不是白色的但是不会被清除，重新标记也不能从GC Root中去找到，所以成为了浮动垃圾，浮动垃圾对系统的影响不大，留给下一次GC进行处理即可
• 漏标 ： 并发标记的过程中，一个业务线程将一个未被扫描过的白色对象断开引用成为垃圾（删除引用），同时黑色对象引用了该对象（增加引用）（这两部可以不分先后顺序）；因为黑色对象的含义为其属性都已经被标记过了，重新标记也不会从黑色对象中去找，导致该对象被程序所需要，却又要被GC回收，此问题会导致系统出现问题，而CMS与G1，两种回收器在使用三色标记法时，都采取了一些措施来应对这些问题，CMS对增加引用环节进行处理（Increment Update），G1则对删除引用环节进行处理(SATB)

解决方案

• CMS：写屏障 + 增量更新

• G1、Shenandoah：写屏障 + 原始快照

• ZGC：读屏障

• 原始快照相对增量更新来说效率更高（当然原始快照可能造成更多的浮动垃圾），因为不需要在重新标记阶段再次深度扫描被删除引用对象。

• 而 CMS 对增量引用的根对象会做深度扫描，G1 因为很多对象都位于不同的 region，CMS 就一块老年代区域，重新深度扫描对象的话 G1 的代价会比 CMS 高，所以 G1 选择原始快照不深度扫描对象，只是简单标记，等到下一轮 GC 再深度扫描

• 而 ZGC 有一个标志性的设计是它采用的染色指针技术，染色指针可以大幅减少在垃圾收集过程中内存屏障的使用数量，设置内存屏障，尤其是写屏障的目的通常是为了记录对象引用的变动情况，如果讲这些信息直接维护在指针中，显然可以省去一些专门的记录操作。而 ZGC 没有使用写屏障，只使用了读屏障，显然对性能大有裨益的

参考文档

• https://www.jianshu.com/p/e2e8f7a35445
• https://www.jianshu.com/p/bbc10c98d0d6
• https://www.cnblogs.com/Courage129/p/14385571.html