CMS和G1的漏标问题解决及三色标记算法图解

三色标记算法：GCRoot如果想查找到存活对象，会根据可达分析算法分析，遍历整个引用链 ,按照是否访问过该对象分成三种不同的颜色盒子（容器）：白色、灰色、黑色盒子。

白色：本对象没有被访问过 （没有被GCRoot扫描过，有可能是为垃圾对象）；
灰色：本对象已经被访问过（被GCRoot扫描过），且本对象中的属性没有被GCRoot扫描，该对象就是为灰色对象；如果该对象的属性被扫描的情况下，从灰色变为黑色。
黑色：本对象已经被访问过（被GCRoot扫描过），且本对象中的属性已经被GCRoot扫描过，该对象就是为黑色对象。

三色标记算法原理

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

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

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

d、在白色盒子剩下的对象都是为没有被GCRoot关联的对象，可能会被垃圾回收机制清理。
e、下次GCRoot起点从灰色节点开始计算

三色标记算法缺陷：在并发标记阶段的时候，因为用户线程与GC线程同时运行，有可能会产生多标或者漏标；
多标--多标记（浮动垃圾）
漏标--漏标记

浮动垃圾

1.并发标记：用户与GC线程同时运行，假设现在扫描到C对象，B对象变为黑色，用户线程执行C的属性E=null,GC线程扫描C对象引用链，认为E对象是为可达对象，但是C对象根本没有引入到E对象，E对象应该是为垃圾对象，这种问题，可以在重新标记阶段(修正)修复。
2.并发清除阶段：用户与GC线程同时运行，会产生新的对象但是没有及时被GC清理。 只能在下一次GC清理垃圾的修复。

漏标问题

1.用户线程先执行C的E属性=null；GC线程的GcRoot就扫描不到E。Gc就认为E对象就是为垃圾对象，不可达对象。
2.用户线有执行B.E属性=E；E对象就是应该是为可达对象。
3.因为GCRoot是从C开始，不会从黑色的B开始，就会导致漏标的情况发生。

漏标的问题满足两个条件：
1.至少有一个黑色对象指向了白色对象
2.所有灰色对象扫描完整个链时，删除之前所有白色对象。

1.CMS如何解决漏标问题---写屏障+增量更新方式

满足一个条件（灰色对象与白色对象断开连接），在并发标记阶段当我们黑色对象（B）引用关联白色对象（E），记录下B黑色对象。
在重新标记阶段（所有用户线程暂停），有将B对象变为灰色对象将整个引用链全部扫描。
缺点：遍历B整个链的效率非常低，有可能会导致用户线程等待的时间非常长。

2.G1如何解决漏标问题---原始快照方式

在C断开E的时候，会记录原始快照，在重新标记阶段的时候以白色对象变为灰色为起始点扫描整个链，本次GC是不会被清理。
好处：如果假设B（黑色对象）引入该白色对象的时候，无需做任何遍历效率是非常高。
缺点：如果假设B（黑色对象） 没有引入该白色对象的时候，该白色对象在本次GC继续存活，只能放在下一次GC在做并发标记的时候清理。
tips:以浮动垃圾（占内存空间）换让我们用户线程能够暂停的时间更加短。

总结：
CMS收集器解决漏标问题：增量方式 如果现在B（黑色）对象引入白色对象，写屏障。
好处：避免浮动垃圾，缺点扫描整个引用链效率比较低。
G1收集器解决漏标问题：原始快照方式。
好处：效率非常高，无需扫描整个引用链，缺点：可能会产生浮动垃圾。