JVM——三色标记（Tri-color Marking）和写屏障

﹏ヽ暗。殇╰゛Y 2022-12-19 09:26 133阅读 0赞

并发标记的主要问题是垃圾回收器在标记对象的过程中，用户线程可能正在改变对象引用关系图，从而造成漏标和错标。错标不会影响程序的正确性，只是造成所谓的浮动垃圾。但漏标则会导致可达对象被当做垃圾收集掉，从而影响程序的正确性。为了区别对象的不同状态，引入了三色标记法。

# 一、三色标记（Tri-color Marking） #

垃圾收集器依据可达性分析算法判断对象是否存活时，将遍历GC Roots过程中遇到的对象，按照“是否访问过”这个条件，把对象标记成白色（white）、灰色（gray）、黑色（black）三种颜色，这个标记过程称为三色标记法。

*  白色：表示对象没有被垃圾收集器访问过。在可达性分析开始阶段，所有的对象都是白色的，在分析结束阶段，白色对象即代表不可达。
 *  黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过，安全存活的。
 *  灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

# 二、并发标记存在的问题 #

在可达性分析的扫描过程，如果用户线程此时是冻结的，只有收集器线程在工作，那不会有任何问题。但如果用户线程与收集器是并发工作呢？

收集器在对象图上标记颜色，同时用户线程在修改引用关系——即修改对象图的结构，这样可能出现两种后果。一种是把原本消亡的对象错误标记为存活，这样会产生了一点浮动垃圾。另一种是把原本存活的对象错误标记为已消亡，这就是非常致命的后果了，程序肯定会因此发生错误，

当且仅当以下两个条件同时满足时，会产生“对象消失”的问题，即原本应该是黑色的对象被误标为白色：

赋值器插入了一个从黑色对象到该白色对象的新引用，因为黑色对象已经被标记，如果不对黑色对象重新处理，那么白色对象将被漏标，造成错误。

赋值器删除了所有从灰色对象到该白色对象的直接或者间接引用，因为灰色对象正在标记，字段引用的对象还没有被标记，如果这个引用的白色对象被删除了（引用发生了变化），那么这个引用对象也有可能被漏标。

# 三、标记过程 #

初始状态，只有GC Roots是黑色的，对象只有被黑色对象引用才能存活，如果没有黑色对象引用它，它再如何引用其他对象都是会被回收的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70][]

在扫描过程中，如果对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过，就标记成灰色。如果对象的所有引用都已经扫描过并且存活，就标记成黑色，即黑色对象不可能直接指向某个白色对象，黑色必须通过灰色连接白色。

图中的对象1和对象2都可以通过GC Roots引用链到达。GC Roots和对象1被标记为黑色。对象1引用指向的对象地址放入到待标记栈。当对象2已经标记完成，需要把对象2引用指向的对象入栈，即对象3入栈待处理。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70 1][]

如果此时并发标记线程让出CPU，赋值器执行并修改了引用关系。对象2指向NULL，对象1指向对象3

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70 2][]

这时候并发线程重新获得执行，将会发生什么？对象1已经变成黑色，说明对象1的引用对象都标记完了。对象2灰色待处理，但是对象2的引用已经为NULL，所以不需要处理。那么对象3怎么办？对象3是白色，很有可能被回收，但是对象3被对象1引用，这就有问题了。如果不进行额外的处理就会导致漏标。这里有两种解决漏标的方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。

# 四、并发标记解决方案： #

## 4.1、增量更新（Incremental Update） ##

增量更新算法关注对象引用的插入，把被更新的黑色或者白色对象标记成灰色。

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

增量更新就是当发生了对象1的引用指向对象3，就把对象1重新标记为灰色，也就是对象1的引用需要被再次处理一遍。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70 3][]

CMS是基于增量更新来做并发标记的

## 4.2、原始快照（Snapshot At The Beginning，SATB） ##

SATB算法关注对象引用的删除，即在对象被赋值前，把老的被引用对象记录下来，然后根据这些对象为根重新标记一遍。

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

如下图，发生对象2的引用为NULL之前把老的对象2的引用指向的对象3放入待标记栈中，相当于把对象3设置成灰色

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70 4][]

G1、Shenandoah则是用原始快照来实现。

# 五、写屏障 #

以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70]: /images/20221120/2824bf34e4ce49ec8103c96b060f7552.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201109221738613.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201109222007273.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201109222113692.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201109222140756.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY2hhb3lhbmc=,size_16,color_FFFFFF,t_70