三色标记算法原理
- JVM学习系列
- 时间：2021-08-20 10:07
- 5522人已阅读
🔔🔔🔔好消息!好消息!🔔🔔🔔
有需要的朋友👉:联系凯哥
什么是三色标记算法
jvm垃圾回收期使用的，在并行标记的时候的一种算法，CMS/G1中的核心算法。
把对象从逻辑上分为三种颜色，分别是黑色，灰色，白色
黑色：自身和成员变量均已标记
灰色：自身被标记，成员变量未被标记
白色：未被标记的对象
它主要用于收集器内存管理，适用于任何的垃圾收集器，也就是通用的算法。
我们通过G1回收器来了解这个算法，我们都知道G1收集器分为三个步骤
新生代回收过程
当新生代eden区内存满的时候，G1年轻代收集器会采用并行多线程的方式清理堆内存垃圾，这时候会暂停所有用户的线程，让后新生代存活的对象会拷贝到S区或者老年代中。但是在G1中，它使用的是标记复制算法
新生代GC+并发标记过程
在新生代进行回收时，进行GCRoot初始化标记与CMS实现原理基本相同，老年代达到堆内存空间阈值时，会实现并发标记（不会stw），jvm配置参数-XX：InitiatingHeapOccupancyPercen=45%，在使用再次标记（修正的时候）的时候，G1中采用了比CMS更快的初始快照算法：snapshot一at一the一beginning （SATB）。三色标记算法，前面提到过三色一共有三个颜色，黑、灰、白。
并发标记不会触发stw
这里要注意的是：CMS中使用，漏标采用增量更新，G1中使用，漏标采用SATB
混合收集
当越来越多的对象晋升到老年代的时候，为了避免堆内存耗尽，会触发混合收集器，即Mixed GC。在此收集中，最终标记和拷贝存活，均会触发stw。
回收整个Young Region（新生代区域），部分的老年代区域，如果G1无法有足够的空间复制对象的时候，有可能会引发FullGc
所以也就是说，G1收集器一共有四个回收步骤。最后一个是FullGC。
三色标记算法原理
初始的时候，会将所有对象都在白色容器中；
当收集器在做初始标记的时候，会暂停所有的用户线程，标记与GCRoot直接关联的对象；并且放入到灰色盒子中。
在并发标记中（用户线程与GC线程同时运行），将与GCRoot直接关联的对象和直接关联的对象的引用对象移动灰色容器中，如果该对象没有引用到其他对象或者其他对象已经标记过，则该对象放到黑色容器中。
重复以上这些操作，到灰色容器为空时，则停止。
在重新标记时，将与GCRoot直接关联的对象的引用对象移动灰色容器中，重复此操作，到灰色容器为空时，则停止。结束后，如果在白色容器中任然存在的对象，则认为就是与GCRoot没有直接关联，则认为就是为不可达对象，可以被垃圾回收线程清理。
在这里面，如果我们在多线程的环境下，那么会产生两个问题，漏标和多标。
我们先来说说多标的问题。
多标的产生
在多线程的情况下，因为我们的并发标记是用户线程和GC线程可以同时运行的，
所以当GC线程先执行遍历到A对象，那么A对象已经存放到灰色容器中，突然用户线程修改了A对象中的属性B对象，并设置为Null，这时候B对象已经是为垃圾对象了（因为没有被引用），但是B对象已经存放到灰色容器中，然后GC线程运行，遍历到B对象的时候，因为它被标记的不是白色，所以GC线程不认为B对象是垃圾对象，这个过程我们可以称作为多标-浮动垃圾，但是又有人疑问了，后面不是有一个重新标记吗？为什么不能把浮动垃圾变为白色的呢？前面的三色标记法，已经提到过，在重新标记的过程中，遍历方式是–>"将与GCRoot直接关联的对象的引用对象移动灰色容器中，重复此操作，到灰色容器为空时，则停止"，但是我们的B对象在之前初始标记的时候是灰色对象，所以我们直接从B对象开始遍历引用链了，所以无法标记为白色。其实这种问题并不大，多标最多就是产生一次垃圾，下次回收的时候就可直接回收了，问题不大，漏标才是最大的问题。我们来看看漏标
漏标的产生
漏标的问题满足两个条件：
至少有一个黑色对象指向了白色对象
所有灰色对象扫描完整个链时，删除之前所有白色对象。
当遍历的B对象（与GCRoot间接相连的对象，与A对象直接相连）的时候，B对象已经存放到灰色容器中，突然用户线程修改B对象属性C对象设置为Null; 那么B对象与C对象断开链接，则C对象则会变为垃圾对象，但是用户线程修改A对象（与GCRoot直接相连的对象，与B对象直接相连）的属性C = C对象，但是A对象已经为黑色不会继续遍历，就会导致C对象会被GC线程线程定义为垃圾对象清理，这个过程称作为漏标问题。
这个问题相比于多标是很严重的问题，因为漏标会将需要使用的对象清空。
那么在CMS收集器和G1收集器是怎么处理这两个问题的呢？
CMS收集器中处理漏标问题：
使用增量更新，满足了第一个条件（灰色对象不在关联白色对象的时候），当黑色对象关联该白色对象的时候，会通过“写屏障”记录该黑色对象， 在重新标记的时候，以该黑色对象变为灰色，从新开始修正标记，但是这种方案能够确保垃圾都被清理，缺点就是效率非常低，因为会扫描到整个黑色对象所有引用。
G1收集器中处理漏标问题：
使用原始快照SATB（Snapshot At The Beginning）
原始快照：简单理解就是备份
如果用户线程在灰色对象断开一个白色对象的时候，会记录原始快照，在重新标记的时候，以白色对象变为灰色对象扫描整个链。如果该白对象没有被其他对象关联，那么此次并不会被清理，而是在下次再进行回收，此次就幸存了。G1收集器宁愿产生浮动垃圾，但是可以提高效率
原文链接：https://blog.csdn.net/weixin_43911969/article/details/115914329