当前位置：首页 > news >正文

JVM-三色标记

news 来源：原创 2024/11/15 9:55:47

一、什么叫三色标记

三色也叫三色抽象，它是所有mutator和collector都必须遵守的定律。它把对象标记为三种颜色：

白色：对象还未被垃圾收集器访问，在回收的开始阶段所有的对象均为白色（当然了这只是指概念上的，一般在初始标记时都会顺便对根的直达对象染色）。而当这次回收结束之后，所有白色对象均为不可达对象（消亡的对象）

灰色：已经被垃圾收集器访问过了，但他还有其他的field需要垃圾收集器去访问。

黑色：已经被垃圾收集器访问过了，并且他的所有filed也被访问过了。黑色对象的任何一个filed都不可能是白色对象。并且黑色对象永远都不会被垃圾收集器再次访问，除非它的颜色发生变化。

二、三色标记的过程和缺点

2.1 标记过程

每次垃圾收集都从GC-Roots出发，然后遍历整个堆。如果把他们画成图如上图。

第一次A被垃圾收集器扫描到了，但是field是B还没被扫描到，为灰色

第二次扫描了B，这时候A的field全部被扫描了，就标记黑色，由于B的C、D还没被扫描到，标记灰色

第三次C、D都被扫描了，所以B标为黑色，但是C的field是E，D的field是G，所以C、D为灰色

第四次E、G都被扫描了，并没有其他field，所以直接标记为黑色

由于F没有引用，属于不可达对象，随时会在垃圾收集被回收掉

2.2 缺点

假如正在运行的java程序和垃圾收集器没有互相干扰的话，那么垃圾收集器在标记过程中不会有任何问题。但是一但垃圾收集器在执行标记工作的时候，java程序也在同时运行，那么问题就来了，如下图：

当B被垃圾收集器染成灰色是，java程序删除了B-->C的引用，并在随后新增了A-->E的引用。因此B-->C的引用链断开了，根据三色标记算法的定义，垃圾收集器不能重新从黑色对象出发去扫描E，所以E对象被视为不可达对象，会被误标为已消亡，这就是“对象消失”问题，它造成的后果也是致命的。

经过研究发现：

用户线程插入一条或多条从黑色到白色对象的新引用。

用户线程删除全部从灰色对象到白色对象的直接或间接引用。

当以上两条同时出现时，就会出现“对象消失”问题。也就是说我们只要保证这两条不会同时出现，就可以解决这个问题。因而产生了两种解决的方案--增量更新（Incremental Update）和原始快照（Snapshot At The Beginning, SATB）

三、增量更新和原始快照

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

原始快照就是当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次，这样就能扫描到白色的对象，将白色对象直接标记为黑色(目的就是让这种对象在本轮gc清理中能存活下来，待下一轮gc的时候重新扫描，这个对象也有可能是浮动垃圾)

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

1.1 写屏障

给某个对象的成员变量赋值时，其底层代码大概长这样：

/**
* @param field 某对象的成员变量，如 a.b.d 
* @param new_value 新值，如 null
*/
void oop_field_store(oop* field, oop new_value) { 
    *field = new_value; // 赋值操作
}

所谓写屏障，其实就是指在赋值操作的前后加上一些操作，有点类似AOP的概念

void oop_field_store(oop* field, oop new_value) {  
    pre_write_barrier(field);          // 写屏障-写前操作
    *field = new_value; 
    post_write_barrier(field, value);  // 写屏障-写后操作
}

写屏障实现SATB--（写屏障-写前操作）

当对象B的成员变量的引用发生变化时，比如引用消失（a.b.d = null），我们可以利用写屏障，将B原来成员变量的引用对象D记录下来：

void pre_write_barrier(oop* field) {
    oop old_value = *field;    // 获取旧值
    remark_set.add(old_value); // 记录原来的引用对象
}

写屏障实现增量更新--（写屏障-写后操作）

当对象A的成员变量的引用发生变化时，比如新增引用（a.d = d），我们可以利用写屏障，将A新的成员变量引用对象D记录下来：

void post_write_barrier(oop* field, oop new_value) {  
    remark_set.add(new_value);  // 记录新引用的对象
}

1.2 读屏障

oop oop_field_load(oop* field) {
    pre_load_barrier(field); // 读屏障-读取前操作
    return *field;
}

读屏障是直接针对第一步：D d = a.b.d，当读取成员变量时，一律记录下来：

void pre_load_barrier(oop* field) {  
    oop old_value = *field;
    remark_set.add(old_value); // 记录读取到的对象
}

四、三色标记的应用

现代追踪式（可达性分析）的垃圾回收器几乎都借鉴了三色标记的算法思想，尽管实现的方式不尽相同：比如白色/黑色集合一般都不会出现（但是有其他体现颜色的地方）、灰色集合可以通过栈/队列/缓存日志等方式进行实现、遍历方式可以是广度/深度遍历等等。

对于读写屏障，以Java HotSpot VM为例，其并发标记时对漏标的处理方案如下：

CMS：写屏障 + 增量更新

G1，Shenandoah：写屏障 + SATB

ZGC：读屏障

工程实现中，读写屏障还有其他功能，比如写屏障可以用于记录跨代/区引用的变化，读屏障可以用于支持移动对象的并发执行等。功能之外，还有性能的考虑，所以对于选择哪种，每款垃圾回收器都有自己的想法。

为什么G1用SATB？CMS用增量更新？

SATB相对增量更新效率会高(当然SATB可能造成更多的浮动垃圾)，因为不需要在重新标记阶段再次深度扫描被删除引用对象，而CMS对增量引用的根对象会做深度扫描，G1因为很多对象都位于不同的region，CMS就一块老年代区域，重新深度扫描对象的话G1的代价会比CMS高，所以G1选择SATB不深度扫描对象，只是简单标记，等到下一轮GC再深度扫描。