jvm深度学习（11）：GC并发标记之三色标记及漏标问题

港控/mmm° 2023-03-02 05:08 186阅读 0赞

## 三色标记 ##

### 概念叙述 ###

在三色标记法之前有一个算法叫Mark-And-Sweep（标记清除）。这个算法会设置一个标志位来记录对象是否被使用。最开始所有的标记位都是 0，如果 发现对象是可达的就会置为 1，一步步下去就会呈现一个类似树状的结果。等标记的步骤完成后，会将未被标记的对象统一清理，再次把所有的标记位设置成 0方便下次清理。

这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停，不能异步进行 GC 操作。因为在不同阶段标记清扫法的标志位 0 和 1 有不同的含义， 那么新增的对象无论标记为什么都有可能意外删除这个对象。对实时性要求高的系统来说，这种需要长时间挂起的标记清扫法是不可接受的。所以就需 要一个算法来解决 GC 运行时程序长时间挂起的问题，那就三色标记法。  
三色标记最大的好处是可以异步执行，从而可以以中断时间极少的代价或者完全没有中断来进行整个 GC。

三色标记法很简单。首先将对象用三种颜色表示，分别是白色、灰色和黑色。

![20200727203810581.png][]

**黑色**：根对象，或者该对象与它的子对象都被扫描过。  
        **灰色**：对本身被扫描，但是还没扫描完该对象的子对象。  
        **白色**：未被扫描对象，如果扫描完所有对象之后，最终为白色的为不可达对象，既垃圾对象。

### 三色标记的问题 ###

1.   线程1和2开始三色标记，

![20200727204724578.png][]

2.   此时B与C之间引用关系断开，添加A与C的引用关系

![20200727205506478.png][]

3.  完成标记

![20200727205927593.png][]

问题：我们发现C虽然有引用关系但是并没有标记，这就是**漏标**问题

## GC 并发情况下的漏标问题解决方案 ##

### CMS 中的解决方案 ###

使用**Incremental Update 算法**

当一个白色对象被一个黑色对象引用，将黑色对象重新标记为灰色，让垃圾回收器重新扫描。

![2020072722373290.png][]

注意：圈红的位置，触发1线程重新扫描的是A增加一个引用。

小结：**Incremental Update关注的是引用关系的增加，当发现有可达的引用增加，便开始重新标记。**

### G1 中的解决方案 ###

使用**SATB算法**(snapshot-at-the-beginning  快照)

刚开始做一个**快照**，当 B 和 C 引用消失的时候要把这个引用推到 GC 的堆栈，保证 C 还能被 GC 扫描到，最重要的是要把这个引用推到 GC 的堆栈，是灰色对象指向白色的引用，如果一旦某一个引用**消失**掉了，我会把它放到栈（GC 方法运行时数据也是来自栈中），我其实还是能找到它的，我下回直接扫描他 就行了，那样白色就不会漏标。  
对应 G1 的垃圾回收过程中的：

**最终标记**( Final Marking)：对**用户线程做另一个短暂的暂停**，用于处理并发阶段结后仍遗留下来的最后那少量的 SATB 记录(漏标对象)。

![20200727224552591.png][]

注意：圈红的位置，触发1线程重新扫描的是B少了一个引用。即使用**SATB关注的是引用关系的删除。**

**小结：SATB通过快照记录引用关系，一旦发现有引用删除，通过查看快照记录的引用关系，重新标记**

### **Incremental Update算法和SATB算法**对比 ###

SATB 算法是关注引用的删除。（B->C 的引用），而Incremental Update 算法关注引用的增加。（A->C 的引用）。  
        G1 如果使用 Incremental Update 算法，因为变成灰色的成员还要重新扫，重新再来一遍，效率太低了。 所以 G1 在处理并发标记的过程比 CMS 效率要高，这个主要是解决漏标的算法决定的。

**声明：本文为学习享学课堂三期JVM章节课后所做的学习总结，文中借鉴King老师上课笔记和课堂PPT。**

[20200727203810581.png]: /images/20230208/9f8b41c7a49640ed8a97228840dc4d92.png
[20200727204724578.png]: /images/20230208/9486e87c96124f11a88f2791e6468c6d.png
[20200727205506478.png]: /images/20230208/190c52f9dba0483f843d888c29d9469c.png
[20200727205927593.png]: /images/20230208/6bc702cf01cc4e21bdfbd2c013c9a9a4.png
[2020072722373290.png]: /images/20230208/bc5c0b510cf1408dacbf6ee24c1a7c24.png
[20200727224552591.png]: /images/20230208/a4f7778edafe45b0be63a60209eeb180.png