三色标记算法
写在前面
本文是对 JVM 三色标记 增量更新 原始快照 一文的镜像转载，仅供个人备份查阅使用
三色标记法
1.1 基本算法
要找出存活对象，根据可达性分析，从GC Roots开始进行遍历访问，可达的则为存活对象：
最终结果：A/D/E/F/G 可达
我们把遍历对象图过程中遇到的对象，按“是否访问过”这个条件标记成以下三种颜色：
- 白色：尚未访问过。
- 黑色：本对象已访问过，而且本对象 引用到 的其他对象 也全部访问过了。
- 灰色：本对象已访问过，但是本对象 引用到 的其他对象 尚未全部访问完。全部访问后，会转换为黑色。
三色标记遍历过程
假设现在有白、灰、黑三个集合（表示当前对象的颜色），其遍历访问过程为：
- 初始时，所有对象都在 【白色集合】中；
- 将
GC Roots直接引用到的对象 挪到 【灰色集合】中； - 从灰色集合中获取对象： 3.1. 将本对象 引用到的 其他对象 全部挪到 【灰色集合】中； 3.2. 将本对象 挪到 【黑色集合】里面。
- 重复步骤3，直至【灰色集合】为空时结束。
- 结束后，仍在【白色集合】的对象即为
GC Roots不可达，可以进行回收。
注：如果标记结束后对象仍为白色，意味着已经“找不到”该对象在哪了，不可能会再被重新引用。
当Stop The World （以下简称 STW）时，对象间的引用 是不会发生变化的，可以轻松完成标记。
而当需要支持并发标记时，即标记期间应用线程还在继续跑，对象间的引用可能发生变化，多标和漏标的情况就有可能发生。
- 浮动垃圾(多标)：将原本应该被清除的对象，误标记为存活对象。后果是垃圾回收不彻底，不过影响不大，可以在下个周期被回收；
- 对象消失(漏标)：将原本应该存活的对象，误标记为需要清理的对象。后果很严重，影响程序运行，是不可容忍的。
能不能在并发标记期间，将用户线程对引用关系的修改都保存起来？并发标记完成后，再将这些保存的修改过程，重新进行标记和调整？能，CMS
就是这么干的。它将并发标记期间引用发生变化的对象都暂存起来，并发标记完成后，再重新对这些暂存的对象重新进行一次标记
。虽然重新标记的过程是需要 STW 的，但是重新标记的对象数量远远小于并发标记阶段的对象数量，因此停顿时间也是短暂且相对固定的，因此这个方法可行！
1.2 多标-浮动垃圾
假设已经遍历到E（变为灰色了），此时应用执行了 objD.fieldE = null ：
D > E 的引用断开
此刻之后，对象E/F/G是“应该”被回收的。然而因为E已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即
本轮GC不会回收这部分内存。
这部分本应该回收 但是 没有回收到的内存，被称之为“浮动垃圾”。浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除。
另外，针对并发标记开始后的新对象，通常的做法是直接全部当成黑色，本轮不会进行清除。这部分对象期间可能会变为垃圾，这也算是浮动垃圾的一部分。
1.3 漏标(对象消失)-读写屏障
假设GC线程已经遍历到E（变为灰色了），此时应用线程先执行了：
var G = objE.fieldG;
objE.fieldG = null; // 灰色E 断开引用 白色G
objD.fieldG = G; // 黑色D 引用 白色G
E > G` 断开，`D`引用 `G
此时切回GC线程继续跑，因为E已经没有对G的引用了，所以不会将G放到灰色集合；尽管因为D重新引用了G，但因为D已经是黑色
**了，不会再重新做遍历处理。
最终导致的结果是：G会一直停留在白色集合中，最后被当作垃圾进行清除。这直接影响到了应用程序的正确性**，是不可接受的。
漏标必须要同时满足以下两个条件：
- 赋值器插入了一条或者多条从黑色对象到白色对象的新引用；
- 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。
这两个条件必须全部满足，才会出现对象消失的问题。那么我们只需要对上面条件进行破坏，破坏其中的任意一个，都可以防止对象消失问题的产生。这样就产生了两种解决方案：
- 增量更新：
Incremental Update。 - 原始快照：
Snapshot At The Beginning，SATB。
增量更新破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用时，就将这个新加入的引用记录下来，待并发标记完成后，重新对这种新增的引用记录进行扫描；
原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，也是将这个记录下来，并发标记完成后，对该记录进行重新扫描。
HotSpot 虚拟机中，不管是新增还是删除，这种记录的操作都是通过写屏障实现的。我们可以将写屏障理解为 JVM
对引用修改操作的一层 AOP，注意它与内存屏障是两个不同的东西。
增量更新与原始快照在 HotSpot 中都有实际应用，其中增量更新用在 CMS 中，原始快照用在了 G1、Shenandoah 等回收器中。
增量更新
增量更新破坏的是第一个条件，在新增一条引用时，将该记录保存。实际的实现中，通常是将引用相关的节点进行重新标记。考虑下图中的例子：
上面就是一次引用关系修改导致的对象消失问题。增量更新进行的处理，就是将由 A 到 C
的这条新增的引用关系进行保存。首先看下 Dijkstra 等人提出的方式：
write_barrier(obj, field, newobj) {
if (newobj.mark == FALSE) {
newobj.mark = TRUE;
push(newobj, $mark_stack);
}
*field = newobj;
}
如果新引用的对象 newobj 没有被标记，那么就将其标记后堆到标记栈里。换句话说， 如果 newobj 是白色对象，就把它涂成灰色。这样操作后的结果如下图所示：
此时 C 被涂成了灰色，它将在后续被重新扫描，阻止了对象消失。
Steele 提出了一种更严厉的方法，它相比 Dijkstra 的方法，可以减少错误标记的对象数量。
write_barrier(obj, field, newobj) {
if($gc_phase == GC_MARK && obj.mark == TRUE && newobj.mark == FALSE) {
obj.mark = FALSE;
push(obj, $mark_stack);
}
*field = newobj;
}
如果在标记过程中发出引用的对象是黑色对象，且新的引用的目标对象为灰色或白色，那么我们就把发出引用的对象涂成灰色。这样操作后的结果如下图：
此时 A 由原来的黑色变成了灰色，将在后续被重新扫描。
原始快照 SATB
原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，并发扫描结束后，在将这些记录重新扫描一次。
write_barrier(obj, field, newobj) {
oldobj = *field;
if(gc_phase == GC_MARK && oldobj.mark == FALSE) {
oldobj.mark = TRUE;
push(oldobj, $mark_stack);
}
*field = newobj;
}
当 GC 进入到标记阶段且 oldobj 没被标记时，则标记 oldobj
，并将其记录。也就是说，在标记阶段中如果指针更新前引用的 oldobj 是白色对象，就将其涂成灰色。
上图依旧是对象消失的例子。a 到 b 中，产生了一条由 A 到 C 的引用关系，这里并没有像增量更新那样将 A 或者 C
标为灰色，相反原始快照中允许出现从黑色指向白色的引用。而在从 b 到 c 中，删除了由 B 到 C
的引用关系。这时候就需要进行处理，将 C 涂为灰色。
1.4 三色标记法与现代垃圾回收器
现代追踪式（可达性分析）的垃圾回收器几乎都借鉴了三色标记的算法思想，尽管实现的方式不尽相同：比如白色/黑色集合一般都不会出现（但是有其他体现颜色的地方）、灰色集合可以通过栈/队列/缓存日志等方式进行实现、遍历方式可以是广度/深度遍历等等。
对于读写屏障，以Java HotSpot VM为例，其并发标记时对漏标的处理方案如下：
- CMS：写屏障 + 增量更新
- G1：写屏障 + SATB（原始快照）
- ZGC：读屏障
工程实现中，读写屏障还有其他功能，比如写屏障可以用于记录跨代/区引用的变化，读屏障可以用于支持移动对象的并发执行等。功能之外，还有性能的考虑，所以对于选择哪种，每款垃圾回收器都有自己的想法。
值得注意的是，CMS中使用的增量更新，在重新标记阶段，除了需要遍历 写屏障的记录，还需要重新扫描遍历GC Roots（当然标记过的无需再遍历了），这是由于CMS对于astore_x等指令不添加写屏障的原因，具体可参考这里。
为什么G1用SATB？CMS用增量更新？
增量更新：黑色对象新增一条指向白色对象的引用，那么要进行深入扫描白色对象及它的引用对象。
原始快照：灰色对象删除了一条指向白色对象的引用，实际上就产生了浮动垃圾，好处是不需要像 CMS 那样 remark，再走一遍 root
trace 这种相当耗时的流程。
我的理解：SATB相对增量更新效率会高(当然SATB可能造成更多的浮动垃圾)
，因为不需要在重新标记阶段再次深度扫描被删除引用对象，而CMS
对增量引用的根对象会做深度扫描，G1因为很多对象都位于不同的region，CMS就一块老年代区域，重新深度扫描对象的话G1
的代价会比CMS高，所以G1选择SATB不深度扫描对象，只是简单标记，等到下一轮GC再深度扫描。
记忆集与卡表
在新生代做GCRoots
可达性扫描过程中可能会碰到跨代引用的对象，这种如果又去对老年代再去扫描效率太低了。为此，在新生代可以引入记录集（Remember Set
）的数据结构（记录从非收集区到收集区的指针集合），避免把整个老年代加入GCRoots扫描范围。事实上并不只是新生代、
老年代之间才有跨代引用的问题， 所有涉及部分区域收集（Partial GC） 行为的垃圾收集器， 典型的如G1、 ZGC和Shenandoah收集器，
都会面临相同的问题。
垃圾收集场景中，收集器只需通过记忆集判断出某一块非收集区域是否存在指向收集区域的指针即可，无需了解跨代引用指针的全部细节。
跨代引用
所谓跨代引用就是老年代的对象引用了新生代的对象，或者新生代的对象引用了老年代的对象。那对于这种情况我们的GC
在进行扫描的时候不可能直接把我们的整个堆都扫描完，那这样效率也太低了。所以这时候就需要开辟了一小块空间，维护这种引用，而不必让GC
扫描整个堆区域。
记忆集
记忆集也叫rememberSet，垃圾收集器在新生代中建立了记忆集这样的数据结构，用来避免把整个老年代加入到GC ROOTS
的扫描范围中。对于记忆集来说，我们可以理解为他是一个抽象类，那么具体实现它的方法将由子类去完成。这里我们简单列举一下实现记忆集的三种方式：
1.字长精度
2.对象精度
3.卡精度（卡表）
卡表
卡表(Card Table)
是一种对记忆集的具体实现。主要定义了记忆集的记录精度、与堆内存的映射关系等。卡表中的每一个元素都对应着一块特定大小的内存块，这个内存块我们称之为卡页（card page
），当存在跨代引用的时候，它会将卡页标记为dirty。那么JVM对于卡页的维护也是通过写屏障
的方式，这也就是为什么刚刚我们跟进写屏障操作到最后会发现它会对卡表进行一系列的操作。