JVM实战：三色标记法

垃圾回收流程的一些流程

哪些对象是垃圾？

当我们进行垃圾回收的时候，首先需要判断哪些对象是存活的？

常用的方法有如下两种

1. 引用计数法
2. 可达性分析法

Python判断对象存活的算法用的是引用计数法，而Java则使用的是可达性分析法。

通过GC ROOT可达的对象，不能被回收，不可达的对象则可以被回收，搜索走过的路径叫做引用链

不可达对象会进行2次标记的过程，通过GC ROOT不可达，会被第一次标记。如果需要执行finalize()方法，则这个对象会被放入一个队列中执行finalize()，如果在finalize()方法中成功和引用链上的其他对象关联，则会被移除可回收对象集合（一般你不建议你使用finalize方法），否则被回收

常见的GC ROOT有如下几种

1. 虚拟机栈（栈帧中的本地变量表）中引用的对象
2. 方法区中类静态属性引用的对象
3. 方法区中常量引用的对象
4. 本地方法栈中JNI（Native方法）引用的对象

照这样看，程序中的GC ROOT有很多，每次垃圾回收都要对GC ROOT的引用链分析一遍，感觉耗费的时间很长啊，有没有可能减少每次扫描的GC ROOT？

分代和跨代引用

其实当前虚拟机大多数都遵循了“分代收集”理论进行设计，它的实现基于2个分代假说之上

1. 绝大多数对象都是朝生夕灭的
2. 熬过多次垃圾收集过程的对象就越难以消亡

因此堆一般被分为新生代和老年代，针对新生代的GC叫MinorGC，针对老年代的GC叫OldGC。但是分代后有一个问题，为了找到新生代的存活对象，不得不遍历老年代，反过来也一样

当进行MinorGC的时候，如果我们只遍历新生代，那么可以判定ABCD为存活对象。但是E不会被判断为存活对象，所以就会有问题。

为了解决这种跨代引用的对象，最笨的办法就是遍历老年代的对象，找出这些跨代引用的对象。但这种方式对性能影响较大

这时就不得不提到第三个假说

跨代引用相对于同代引用来说仅占极少数。

根据这条假说，我们就不需要为了少量的跨代引用去扫描整个老年代。为了避免遍历老年代的性能开销，垃圾回收器会引入一种记忆集的技术，记忆集就是用来记录跨代引用的表

如新生代的记忆集就保存了老年代持有新生代的引用关系

所以在进行MinorGC的时候，只需要将包含跨代引用的内存区域加入GC ROOT一起扫描就行了

卡表

前面我们说到垃圾收集器用记忆集来记录跨代引用。其实你可以把记忆集理解为接口，卡表理解为实现，类比Map和HashMap。

卡表最简单的形式可以只是一个字节数组， 而HotSpot虚拟机确实也是这样做的。 以下这行代码是HotSpot默认的卡表标记逻辑：

CARD_TABLE [this address >> 9] = 0;

HotSpot用一个数组元素来保存对应的内存地址是有有跨代引用对象（从this address右移9位可以看出每个元素映射了512字节的内存）

当数组元素值为0时表明对应的内存地址不存在跨代引用对象，否则存在（称为卡表中这个元素变脏）

如何更新卡表？

将卡表元素变脏的过程，HotSpot是通过写屏障来实现的，即当其他代对象引用当前分代对象的时候，在引用赋值阶段更新卡表，具体实现方式类似于AOP

void oop_field_store(oop* field, oop new_value) { 
// 引用字段赋值操作
*field = new_value;
// 写后屏障，在这里完成卡表状态更新 
post_write_barrier(field, new_value);
}

三色标记法

执行思路

如何判断一个对象可达呢？这就不得不提到三色标记法

白色：刚开始遍历的时候所有对象都是白色的
灰色：被垃圾回收器访问过，但至少还有一个引用未被访问
黑色：被垃圾回收器访问过，并且这个对象的所有引用都被访问过，是安全存活的对象（GC ROOT会被标记为黑色）

以上图为例，三色标记法的执行流程如下

1. 先将GC ROOT引用的对象B和E标记为灰色
2. 接着将B和E引用的对象A，C和F标记为灰色，此时B和E标记为黑色
3. 依次类推，最终被标记为白色的对象需要被回收

三色标记法问题

可达性分析算法根节点枚举这一步必须要在一个能保障一致性的快照中分析，所以要暂停用户线程（Stop The World ，STW），在各种优化技巧的加持下，停顿时间已经非常短了。

在从根节点扫描的过程则不需要STW，但是也会发生一些问题。由于此时垃圾回收线程和用户线程一直运行，所以引用关系会发生变化

1. 应该被回收的对象被标记为不被回收
2. 不应该被回收的对象标记为应该回收

第一种情况影响不大，大不了后续回收即可。但是第二种情况则会造成致命错误

所以经过研究表明，只有同时满足两个条件才会发生第二种情况

1. 插入了一条或者多条黑色到白色对象的引用
2. 删除了全部从灰色到白色对象的引用

如下图所示

为了解决这个问题，我们破坏2个条件中任意一个不就行了，由此产生了2中解决方案，增量更新和原始快照。CMS使用的是增量更新，G1使用的是原始快照

增量更新要破坏的是第一个条件， 当黑色对象插入新的指向白色对象的引用关系时， 就将这个新插入的引用记录下来， 等并发扫描结束之后， 再将这些记录过的引用关系中的黑色对象为根， 重新扫描一次。 这可以简化理解为， 黑色对象一旦新插入了指向白色对象的引用之后， 它就变回灰色对象了

原始快照要破坏的是第二个条件， 当灰色对象要删除指向白色对象的引用关系时， 就将这个要删除的引用记录下来， 在并发扫描结束之后， 再将这些记录过的引用关系中的灰色对象为根， 重新扫描一次。 这也可以简化理解为， 无论引用关系删除与否， 都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。