【重要】三色标记法与垃圾回收器（CMS、G1）

旧城等待， 2021-06-22 15:38 576阅读 0赞

## 三色标记法-算法思想 ##

三色标记法将对象的颜色分为了黑、灰、白，三种颜色。

*  黑色：该对象已经被标记过了，且该对象下的属性也全部都被标记过了。（程序所需要的对象）
 *  灰色：该对象已经被标记过了，但该对象下的属性没有全被标记完。（GC需要从此对象中去寻找垃圾）
 *  白色：该对象没有被标记过。（对象垃圾）

算法流程：

*  从我们`main`方法的根对象（JVM中称为`GC Root`）开始沿着他们的对象向下查找，用黑灰白的规则，标记出所有跟`GC Root`相连接的对象
 *  扫描一遍结束后，一般需要进行一次短暂的STW(Stop The World)，再次进行扫描，此时因为黑色对象的属性都也已经被标记过了，所以只需找出灰色对象并顺着继续往下标记（且因为大部分的标记工作已经在第一次并发的时候发生了，所以灰色对象数量会很少，标记时间也会短很多）
 *  此时程序继续执行，`GC`线程扫描所有的内存，找出被标记为白色的对象（垃圾）清除

### 存在问题： ###

1、 浮动垃圾：并发标记的过程中，若一个已经被标记成黑色或者灰色的对象，突然变成了垃圾，此时，此对象不是白色的不会被清除，重新标记也不能从`GC Root`中去找到，所以成为了浮动垃圾，这种情况对系统的影响不大，留给下一次GC进行处理即可。  
2、 对象漏标问题（需要的对象被回收）：并发标记的过程中，一个业务线程将一个未被扫描过的白色对象断开引用成为垃圾（删除引用），同时黑色对象引用了该对象（增加引用）（这两部可以不分先后顺序）；因为黑色对象的含义为其属性都已经被标记过了，重新标记也不会从黑色对象中去找，导致该对象被程序所需要，却又要被GC回收，此问题会导致系统出现问题，而`CMS`与`G1`，两种回收器在使用三色标记法时，都采取了一些措施来应对这些问题，==CMS对增加引用环节进行处理（Increment Update），G1则对删除引用环节进行处理(SATB)。==

## 三色标记法的实践与应对对象漏标问题的具体做法 ##

> 在JVM虚拟机中有两种常见垃圾回收器使用了该算法：
> 
> 1、 CMS(Concurrent Mark Sweep)  
> 2、 G1(Garbage First)

### CMS(Concurrent Mark Sweep) ###

> CMS，是非常有名的JVM垃圾回收器，它起到了承上启下的作用，开启了并发回收的篇章。
> 
> 但是CMS由于许多小问题，现在基本已经被淘汰。

增量更新(Increment Update)

在应对漏标问题时，CMS使用了`Increment Update`方法来做：

在一个未被标记的对象（白色对象）被重新引用后，==引用它的对象==，若为黑色则要变成灰色，在下次二次标记时让GC线程继续标记它的属性对象。

但是就算时这样，其仍然是存在漏标的问题：

*  在一个灰色对象正在被一个GC线程回收时，当它已经被标记过的属性指向了一个白色对象（垃圾）
 *  而这个对象的属性对象本身还未全部标记结束，则为灰色不变
 *  **而这个GC线程在标记完最后一个属性后，认为已经将所有的属性标记结束了，将这个灰色对象标记为黑色，被重新引用的白色对象，无法被标记**

补充，CMS除了这个缺陷外，仍然存在两个个较为致命的缺陷：

1、 CMS采用了`Mark-Sweep`算法，最后会产生许多内存碎片，当到一定数量时，CMS无法清理这些碎片了，CMS会让`Serial Old`来清理这些垃圾碎片，而`Serial Old`是单线程操作进行清理垃圾的，效率偏低。

所以使用CMS就会出现一种情况，硬件升级了，却越来越卡顿，其原因就是因为进行`Serial Old GC`时，效率过低。
    
     *  解决方案：使用`Mark-Sweep-Compact`算法，减少垃圾碎片
     *  调优参数（配套使用）：

-XX:+UseCMSCompactAtFullCollection  开启CMS的压缩
            -XX:CMSFullGCsBeforeCompaction 默认为0，指经过多少次CMS FullGC才进行压缩

2、 当JVM认为内存不够了，再使用CMS进行并发清理内存可能会发生OOM的问题，而不得不进行`Serial Old GC`，`Serial Old`是单线程垃圾回收，效率低

*  解决方案：降低触发`CMS GC`的阈值，让浮动垃圾不那么容易占满老年代
     *  调优参数：

-XX:CMSInitiatingOccupancyFraction 92% 可以降低这个值，让老年代占用率达到该值就进行CMS GC

### G1(Garbage First) ###

> 从G1垃圾回收器开始，G1的物理内存不再分代，而是由一块一块的`Region`组成；逻辑分代仍然存在。

前置知识 — Card Table（多种垃圾回收器均具备）

*  由于在进行`YoungGC`时，我们在进行对一个对象是否被引用的过程，需要扫描整个Old区，所以JVM设计了`CardTable`，将Old区分为一个一个Card，一个Card有多个对象；如果一个Card中的对象有引用指向Young区，则将其标记为`Dirty Card`，下次需要进行`YoungGC`时，只需要去扫描`Dirty Card`即可。
 *  Card Table 在底层数据结构以 `Bit Map`实现。

--------------------

CSet(Collection Set)

一组可被回收的分区Region的集合；Region，是多个对象的集合内存区域。

RSet(Remembered Set)

每个`Region`中都有一个`RSet`，记录其他`Region`到本`Region`的引用信息；使得垃圾回收器不需要扫描整个堆找到谁引用当前分区中的对象，只需要扫描RSet即可。

新生代与老年代的比例

`5% - 60%`，一般不使用手工指定，因为这是G1预测停顿时间的基准。

SATB(Snapshot At The Beginning)

在应对漏标问题时，CMS使用了`SATB`方法来做：

1、 在开始标记的时候生成一个快照图标记存活对象  
2、 在一个引用断开后，要将此引用推到GC的堆栈里，保证白色对象（垃圾）还能被GC线程扫描到  
3、 配合`Rset`，去扫描哪些Region引用到当前的白色对象，若没有引用到当前对象，则回收

SATB效率高于Increment update原因？

*  因为SATB在重新标记环节只需要去重新扫描那些被推到堆栈中的引用，并配合`Rset`来判断当前对象是否被引用来进行回收；
 *  并且在最后`G1`并不会选择回收所有垃圾对象，而是根据`Region`的垃圾多少来判断与预估回收价值（指回收的垃圾与回收的`STW`时间的一个预估值），将一个或者多个`Region`放到`CSet`中，最后将这些`Region`中的存活对象压缩并复制到新的`Region`中，清空原来的`Region`。

问题：G1会不会进行Full GC?

会，当内存满了的时候就会进行`Full GC`；且`JDK10`之前的`Full GC`，为单线程的，所以使用G1需要避免`Full GC`的产生。

解决方案：

*  加大内存；
 *  提高CPU性能，加快GC回收速度，而对象增加速度赶不上回收速度，则Full GC可以避免；
 *  降低进行Mixed GC触发的阈值，让Mixed GC提早发生（默认45%）

文章永久链接：[https://tech.souyunku.com/?p=45733][https_tech.souyunku.com_p_45733]

[https_tech.souyunku.com_p_45733]: https://tech.souyunku.com/?p=45733