三色标记算法

三色标记算法：是指利用可达性分析算法，对象被GC线程扫描标记的状态，解决GC漏标的问题
黑色：根对象，或者该对象与它的子对象都被扫描过
灰色：对象本身被扫描，但是还有没扫描该对象的子对象。
白色：未被扫描的对象，如果扫描完成所有对象之后，最终为白色的为不可达对象，即垃圾对象。

GC 线程和业务线程同时工作，在并发标记中，三色标记算法会存在两个缺陷：多标（浮动垃圾）、漏标。
1、多标（浮动垃圾）
1、浮动垃圾：是指那些已经是垃圾的对象，却在一次GC回收过程中存活了下来
产生浮动垃圾的过程：
    第一步：GC 线程： A 已经完全标记，B 已经完成自身标记，正在标记C；
    第二步：业务线程：将A -> B 的引用失效；
    第三步：GC 线程： 因为B自身已经扫描完成，所以感知不到 A -> B 的引用失效，待把C、D标记完成后，将B设置为黑色。
    其实B、C、D都已经是垃圾对象，但是本次三色标记被标记成了黑色，黑色代表存活对象，所以本次GC不会将B、C、D回收掉，B、C、D就是浮动垃圾。
浮动垃圾影响：对GC的影响并不是很大，只不过是让垃圾对象多存活一段时间，在下次GC的时候，一定会将这些浮动垃圾清理掉，因此JVM里并没有针对浮动垃圾做任何操作。
2、漏标
漏标：是指那些本该存活的对象，在一次GC回收过程中却被当做垃圾对象回收了
  产生漏标需要两个必要条件，缺一不可：
  1、黑色对象 -> 白色对象建立链接
  2、灰色对象 -> 白色对象引用断开
产生漏标的过程：
第一步：GC 线程：A 已经完全标记，B 已经完成自身标记，正在标记 C
第二步：业务线程：A -> D 新建了引用关系，同时 B -> D 的引用失效
第三步：GC 线程：因为A已经扫描完成，所以未感知到 A -> D 的建立引用，认为没有任何引用指向D，D漏标被回收
漏标影响：会造成非常严重的问题，如图所示，当顺着 A -> D 的指针，去找B对象，结果发现B对象不存在返回NULL，这不就是NullPointerException吗

有两种方案解决漏标：
1、黑色对象 -> 白色对象建立链接时，通过写屏障将黑色对象标记为灰色，灰色对象需要重新标记，这种方法叫 Incremental-Update（增量更新）；
2、灰色对象 -> 白色对象引用断开，先将该引用原始快照保存下来，等到重新标记阶段将该引用取出来，重新扫描白色对象是否被引用，
1、GMS 避免漏标的方法叫做增量更新：
1、GC线程： A 已经完全标记，B 已经完成自身标记，正在标记C
2、业务线程：A -> D 新建了引用关系，利用写屏障将A重新标记为灰色
           （注意：这里的写屏障，并不是指内存屏障，是指类似切面编程的理念，不改变原有逻辑的情况下，将A标记为灰色）
3、GC线程： A 变为灰色，需要重新标记     

2、G1 避免漏标的方法叫做 SATB（Snapshot-At-The-Beginning）：
1、GC线程：A 已经完全标记，B 已经完成自身标记，正在标记C
2、业务线程：同时 B -> D 引用断开，利用写屏障将 B -> D 的引用原始快照记录下来
3、在重新标记阶段，将B -> D 的引用原始快照拿出来，重新扫描D是否被引用。
为什么G1会选择SATB来解决漏标问题呢，我们知道：当灰色对象-> 白色对象引用消失时，该引用原始快照会被记录下来，下次扫描时会拿到该引用，
检查白色对象是否有引用指向它，这是时候配合RSet，无需遍历整个堆，只需要遍历当前Region，和当前Region的Rset指向的那些Region区域，
即可知道有没有引用指向它，时间开销极小。