著名的三色标记法

一、前言

当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全程冻结用户线程的运行（STW）。

在根节点枚举这个步骤中，由于GC Roots相比起整个Java堆中全部的对象毕竟还算是极少数，且在各种优化技巧（如OopMap）的加持下，它带来的停顿已经是非常短暂且相对固定（不随堆容量而增长）的了。可从GC Roots再继续往下遍历对象图，这一步骤的停顿时间就必定会与Java堆容量直接成正比例关系了：堆越大，存储的对象越多，对象图结构越复杂，要标记更多对象而产生的停顿时间自然就更长。包含“标记”阶段是所有追踪式垃圾收集算法的共同特征，如果这个阶段会随着堆变大而等比例增加停顿时间，其影响就会波及几乎所有的垃圾收集器，同理可知，如果能够削减这部分停顿时间的话，那收益也将会是系统性的。

二、三色标记法

顾名思义，用三种颜色进行标记，其用在CMS垃圾回收器工作的并发标记阶段。

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

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

灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过，可以理解为正在搜索的对象。当垃圾回收线程从暂停中再次回来，不会扫描灰色对象，而是直接扫描灰色对象的引用。

简述三色标记法的遍历过程：

初始时，全部对象都是白色的
GC Roots直接引用的对象变成灰色
从灰色集合中获取元素：

3.1 将本对象直接引用的对象标记为灰色

3.2 将本对象标记为黑色
重复步骤3，直到灰色的对象集合变为空
结束后，仍然被标记为白色的对象就是不可达对象，视为垃圾对象

当Stop The Word时，对象间的引用是不会发生变化的，因为用户线程中断了，可以轻松完成标记，但是在并发标记的时候，标记期间用户线程还在跑，对象间的引用可能发生变化，多标和漏标的情况就可能会发生

多标(又叫浮动垃圾)

假设此时我们遍历到了D对象，此时D被标记成了灰色

此时线程发生B取消了对D的引用

这时候B->D的引用没了，D应该是白色，但是因为先前D已经被标记成灰色了，所以D对象仍然会被当成存活对象遍历下去。最终结果：这部分对象仍然会被标记为存活对象，本轮GC不会回收他们的内存。这部分因为并发而造成的本应该回收但是没有回收的对象被称为”浮动垃圾”，我们稍微一想也能想到，浮动垃圾不会影响应用程序的正确性，只需要等到下一轮GC到来就会被回收了。

另外的，针对并发标记开始后产生的新对象，通常做法是直接标记为黑色，本轮不进行清除，这些对象即使会变成垃圾对象，这也算浮动垃圾一部分。

漏标(读写屏障)

假设GC线程已经遍历到D对象，此时D被标记为灰色

但是此时有代码执行：

1
2
3

Object E = D.next;
D.next = null;
B.next = E;

此时D到E的引用消失，B生成了对E的引用。当GC线程继续时，因为D已经没有了对E的引用，所以不会遍历到E，E也就不会标志为灰色，同时B已经标志为黑色了，不会再被遍历，那么也就导致E一直是白色的，最后被当成垃圾处理，这显然与事实不符，E是可打的，但是因为并发的影响漏标了E，使得E被垃圾回收，明显影响了应用程序的正确性，这是不可接受的。

分析一下，漏标只有同时满足以下两个条件时才会发生：

灰色对象断开了白色对象的引用
黑色对象重新引用了该白色对象

从代码角度看：

1
2
3

Object E = D.next;
D.next = null;
B.next = E;

只要在上面三步中修改任意一步就可以将丢失的E记录下来，然后当作灰色对象继续遍历

根据以上思路有两种解决办法：

一、写屏障(阻止第二步和第三步)

1.写屏障 + SATB

当对象D的引用发生变化时，利用写屏障，将D原来的引用对象记录下来，这样可以尝试保留开始时的对象图，保证标记依然按照原本的路线走

2.写屏障 + 增量更新

当对象B的引用发生变化时，利用写屏障，将B新的引用对象E记录下来

即当有新的引用插入进来时，记录下新的引用

这种思路不要求保留原始对象图，而是针对新的引用记录下来等待遍历即增量更新

二、读屏障(阻止第一步)

读屏障针对第一步，当读取引用对象的时候，一律记录下来，显然这种方法非常保守，但是安全。

将记录下的引用遍历就是了

在现代的垃圾回收器当中可达性分析算法的垃圾回收器几乎都借鉴了三色标记法的思想。

在Java HotSpot VM中

CMS采用的是：写屏障 + 增量更新

G1采用的是：写屏障 + SATB