JVM_垃圾收集之三色标记算法详解

Love The Way You Lie 2024-03-25 21:15 16阅读 0赞

## 前言 ##

> 在可达性分析中，CMS、G1、ZGC都采用三色标记算法，该算法会出现错标和漏标的问题，该怎么解决呢？还有写屏障、读屏障、以及原始快照和增量更新，这些都是面试中常问的问题，本文将详细概述。

## 1、 三色标记算法 ##

在CMS垃圾收集器中提到了，在CMS的并发清理阶段才产生的垃圾对象，会被当做浮动垃圾，留到下一次GC再清理。其实在并发标记阶段，由于用户线程在并发运行，也可能会导致引用关系发生改变，导致标记结果不准确，从而引发更加严重的问题，这些发生变更的数据会在重新标记阶段被处理，那么会出现什么问题？又是如何处理的呢？

> CMS算法的基础是通过可达性分析找到存活的对象，然后给存活的对象打个标记，最终在清理的时候，如果一个对象没有任何标记，就表示这个对象不可达，需要被清理，标记算法就是使用的三色标记。并发标记阶段是从GC Root直接关联的对象开始枚举的过程。  
> 对于三色标记算法而言， 对象会根据是否被访问过（也就是是否在可达性分析过程中被检查过）被分为三个颜色：白色、灰色和黑色：

> 白色：这个对象还没有被访问过，在初始阶段，所有对象都是白色，所有都枚举完仍是白色的对象将会被当做垃圾对象被清理。  
> 灰色：这个对象已经被访问过，但是这个对象所直接引用的对象中，至少还有一个没有被访问到，表示这个对象正在枚举中。  
> 黑色：对象和它所直接引用的所有对象都被访问过。这里只要访问过就行，比如A只引用了B，B引用了C、D，那么只要A和B都被访问过，A就是黑色，即使B所引用的C或D还没有被访问到，此时B就是灰色。  
>     
> 根据这些定义，我们可以得出：  
> 在可达性分析的初始阶段，所有对象都是白色，一旦访问了这个对象，那么就变成灰色，一旦这个对象所有直接引用的对象都访问过（或者没有引用其它对象），那么就变成黑色 初始标记之后，GC Root节点变为黑色（GC Root不会是垃圾），GC Root直接引用的对象变为灰色 正常情况下，一个对象如果是黑色，那么其直接引用的对象要么是黑色，要么是灰色，不可能是白色（如果出现了黑色对象直接引用白色对象的情况，就说明漏标了，就会导致对象误删，后面会介绍如何解决），这个特性也可以说是三色标记算法正确性保障的前提条件。  
> 算法大致的流程是（初始状态所有对象都是白色）：

> 首先我们从GC Roots开始枚举，它们所有的直接引用变为灰色，自己变为黑色。可以想象有一个队列用于存储灰色对象，会把这些灰色对象放到这个队列中 然后从队列中取出一个灰色对象进行分析：将这个对象所有的直接引用变为灰色，放入队列中，然后这个对象变为黑色；如果取出的这个灰色对象没有直接引用，那么直接变成黑色 继续从队列中取出一个灰色对象进行分析，分析步骤和第二步相同，一直重复直到灰色队列为空 分析完成后仍然是白色的对象就是不可达的对象，可以作为垃圾被清理 最后重置标记状态

> 前面的描述都比较抽象，这里以一个例子进行说明，假设现在有以下引用关系：  
> 首先，所有GC Root的直接引用（A、B、E）变为灰色，放入队列中，GC Root变为黑色：  
> ![在这里插入图片描述][a8794a687f484ce7a7f43e00832e41ec.png]  
> 然后从队列中取出一个灰色对象进行分析，比如取出A对象，将它的直接引用C、D变为灰色，放入队列，A对象变为黑色：  
> ![在这里插入图片描述][4f3f4b28811a423d9ad431b342d32f12.png]  
> 继续从队列中取出一个灰色对象，比如取出B对象，将它的直接引用F变为灰色，放入队列，B对象变为黑色：  
> ![在这里插入图片描述][738bd72fbe254863a1cd4ad3b6214859.png]  
> 继续从队列中取出一个灰色对象E，但是E对象没有直接引用，变为黑色：  
> ![在这里插入图片描述][28dff2f7626f430786fb673652399c0a.png]  
> 同理依次取出C、D、F对象，他们都没有直接引用，那么变成黑色（这里就不一个一个的画了）：  
> ![在这里插入图片描述][dbe7e55998b44b89853e4c880b8f539e.png]  
> 到这里分析已经结束了，还剩一个G对象是白色，证明它是一个垃圾对象，不可访问，可以被清理掉。

## 2、并发标记带来的问题 ##

如果整个标记过程是STW的，那么没有任何问题，但是并发标记的过程中，用户线程也在运行，那么对象引用关系就可能发生改变，进而导致两个问题出现。

### 2.1 非垃圾变为了垃圾 ###

> 比如我们回到上述流程中的这个状态：  
> ![在这里插入图片描述][cf47de7cbb8c42e58a294c57313b2669.png]  
> 后面的图就不用画了，很显然，E对象变为了垃圾对象，但是由于已经被标记为黑色，就不会被当做垃圾删除，姑且也可以称之为浮动垃圾。

### 2.2 垃圾变为了非垃圾 ###

> 如果上面提到的浮动垃圾你觉得没啥所谓，即使本次不清理，下一次GC也会被清理，而且并发清理阶段也会产生所谓的浮动垃圾，影响不大。但是如果一个垃圾变为了非垃圾，那么后果就会比较严重。比如我们回到上述流程中的这个状态：  
> ![在这里插入图片描述][e13c1e57c5004eb79ed6b367995ddd1c.png]  
> 标记的下一步操作是从队列中取出B对象进行分析，但是这个时候GC线程的时间片用完了，操作系统调度用户线程来运行，而用户线程先执行了这个操作：A.f = F；那么引用关系变成了：

![在这里插入图片描述][e4a72222dd5c46f3a418d4a8f78a173e.png]

> 接着执行：B.f=null；那么引用关系变成了：  
> ![在这里插入图片描述][1b632edd50334d3399bf96ec42272c12.png]  
> 好了，用户线程的事儿干完了，GC线程重新开始运行，按照之前的标记流程继续走：从队列中取出B对象，发现B对象没有直接引用，那么将B对象变为黑色：

![在这里插入图片描述][e76caad93b9740b6a68ff8f9e03bd705.png]  
接着继续分别从队列中取出E、C、D三个灰色对象，它们都没有直接引用，那么变为黑色对象：

![在这里插入图片描述][2642cdf37ef34fdcbab2262d5db78605.png]

> 到现在所有灰色对象分析完毕，你肯定已经发现问题了，出现了黑色对象直接引用白色对象的情况，而且虽然F是白色对象，但是它是垃圾吗？显然不是垃圾，如果F被当做垃圾清理掉了，那就GG~

## 3、增量更新和原始快照(SATB) ##

> 上面一共出现了两个问题，从结果上来看，可以这样描述：  
> 一个本应该是垃圾的对象被视为了非垃圾 一个本应该不是垃圾的对象被视为了垃圾  
> 对于第一个问题，我们前文也提到了，即使不去处理它也无所谓，大不了等到下次GC再清理。最重要的是第二个问题，如果误清理了正在被使用的对象，那就是实打实的BUG了。那么如何解决这个问题呢？  
> 出现这个问题的主要原因是，一个对象从被B引用，变更为了被A引用。那么对于A来说就是多了一个直接引用，对于B来说就是少了一个直接引用。我们可以从这两个方面入手来解决这个问题，对应了也有两个方案，分别是增量更新（Incremental Update） 和原始快照（SATB，Snapshot At The Beginning）。

### 3.1 读写屏障 ###

> 在这讲述解决方案之前，要描述两个名词：读屏障和写屏障。注意，这里的屏障和并发编程中的屏障是两码事儿。这里的屏障很简单，可以理解成就是在读写操作前后插入一段代码，用于记录一些信息、保存某些数据等，概念类似于AOP。

### 3.2 增量更新 ###

> 增量更新是站在新增引用的对象（也就是例子中的A对象）的角度来解决问题。所谓增量更新，就是在赋值操作之前添加一个写屏障，在写屏障中记录新增的引用。比如，用户线程要执行：A.f = F；那么在写屏障中将新增的这个引用关系记录下来。标准的描述就是，当黑色对象新增一个白色对象的引用时，就通过写屏障将这个引用关系记录下来。然后在重新标记阶段，再以这些引用关系中的黑色对象为根，再扫描一次，以此保证不会漏标。  
> 在我们这个例子中，在并发标记阶段，A是一个黑色对象，F是一个白色对象，A引用了F，这个引用关系会被记录下来，然后通过这个记录在重新标记阶段再从A对象开始枚举一次，保证如果A还是保持着F的引用，那么F会被正确标记；如果A到F的引用在并发标记阶段又断开了，此次枚举也无法访问到它，活该被清除。  
> 要实现也很简单，在重新标记阶段直接把A对象（和其它有相同情况发生的对象）变为灰色，放入队列中，再来一次枚举过程。要注意，在重新标记阶段如果用户线程还是继续执行，那么这个GC永远可能也做不完了，所以重新标记需要STW，但是这个时间消耗不会太夸张。如果实在重新标记阶段耗时过长，那么可以尝试在重新标记之前做一次Minor GC，这个在CMS垃圾收集器中有介绍，这里就不赘述了。

### 3.3 原始快照(SATB) ###

> 原始快照是站在减少引用的对象（也就是例子中的B对象）的角度来解决问题。所谓原始快照，简单的讲，就是在赋值操作（这里是置空）执行之前添加一个写屏障，在写屏障中记录被置空的对象引用。比如，用户线程要执行：B.f=null；那么在写屏障中，首先会把B.f记录下来，然后再进行置空操作。记录下来的这个对象就可以称为原始快照。  
> 那么记录下来之后呢？很简单，之后直接把它变为黑色。意思就是默认认为它不是垃圾，不需要将其清理。当然，这样处理有两种情况，一种情况是，F的确不是垃圾，直到清理的那一刻，都仍然有至少一个引用链能访问到它，这没有什么问题；另一种情况就是F又变成了垃圾。在上述的例子中，就是A到F的引用链也断了，或者直接A都成垃圾了，那F对象就成了浮动垃圾。对于浮动垃圾，前面不止一次就提到了，直接不用理会，如果到下一次GC时它仍然是垃圾，自然会被清理掉。

### 3.4 方案抉择 ###

> 从增量更新和原始快照的实现（理论上）就可以发现，原始快照相比于增量更新来说效率会更高，因为不用在重新标记阶段再去做枚举遍历，但是也就可能会导致有更多的浮动垃圾。G1使用的就是原始快照，CMS使用的是增量更新。

> 既然原始快照可能会有更严重的浮动垃圾问题，那么为什么不使用增量更新呢？原因可能很简单，就是因为简单。想象一下，G1虽然也是基于年轻代和老年代的分代收集算法，但是年轻代和老年代被弱化为了逻辑上，其所管理的内存被划分为了很多region，对象跨代引用带来的问题在G1中要比传统的分代收集器更加突出，虽然有Remember Set方案缓解，但是相对来说在重新标记阶段进行再次遍历枚举的代价会大很多。最重要的是，重新标记（最终标记）阶段是会STW的，如果这个阶段花费太多的时间去做可达性分析，那么就违背了G1低延时的理念。当然这个是博主的猜测，如果读者朋友有更好的想法，欢迎提出。

[a8794a687f484ce7a7f43e00832e41ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/abb31e2356ce4cf4b29b7925d26ad34c.png
[4f3f4b28811a423d9ad431b342d32f12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/62a72b1794964fb0ac3728671dc6bb69.png
[738bd72fbe254863a1cd4ad3b6214859.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8856c4c1c46143c1adb4c776e8379950.png
[28dff2f7626f430786fb673652399c0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/dfcb5e313ca9499ea832cd8971990db1.png
[dbe7e55998b44b89853e4c880b8f539e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3aa825f732024773a9cf2555b6421446.png
[cf47de7cbb8c42e58a294c57313b2669.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/773e93f1f37742c09fc41c4cd2a1d4df.png
[e13c1e57c5004eb79ed6b367995ddd1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6dd87ef6105742529012c44c1672f48e.png
[e4a72222dd5c46f3a418d4a8f78a173e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/398a9159b0b9445aa86c68d2da64f5b6.png
[1b632edd50334d3399bf96ec42272c12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/961d57a700754308858c73d7830b620b.png
[e76caad93b9740b6a68ff8f9e03bd705.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3a442533c36f4bd18efe08f6b70e8780.png
[2642cdf37ef34fdcbab2262d5db78605.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2ca47214f1c047328a8471b1a876e5c2.png