CMS垃圾回收器与三色标记算法

[dccmmtop]

垃圾收集算法

整体可以分为以下几种算法：

• 标记复制算法
• 标记整理算法
• 标记清除算法

分代收集理论

目前的虚拟机的垃圾回收器都是采用分代收集算法，一般根据对象存活周期的不同，将内存分为几块，一般将java堆分为新生代和老年代，然后根据各代的特点选择不同的垃圾回收器算法

比如在新生代，每次收集都会有大量的对象死去（近 99% ），所以选择复制算法，只需复制少量对象就可以完成垃圾回收，成本较低。 而老年代对象存活几率是比较高的，也没有额外的空间给担保，所以要选择标记清除或标记整理算法，这两种算法比复制算法慢10倍以上

标记复制算法

将内存分为大小相同的两个块，只把对象分配到其中一个块上，当这个块的空间不足时，就将还存活的对象复制到另外一块上去，然后把使用过那块空间清理掉。每次都是对内存空间的一半进行回收

标记清除算法

分为两步

1. 标记存活的对象
2. 清理没有被标记的对象

一般选择这种，也可以反过来，标记需要回收的对象，然后清理所有被标记的对象

缺点:

• 效率低，（要标记的对象可能很多）
• 内存碎片多（会产生大量的不连续下空间，无法利用） 如图:

标记整理算法

根据老年代的特点专门制定的清除方案，与标记清除一样，需要先标记存活对象，不同的是，后续没有直接回收垃圾，而是将存活的对象统一向一端移动，然后清理掉边界以外的内存

垃圾回收器

上述几个算法是理论，实现垃圾回收算法的叫做垃圾收集器

垃圾回收器没有最好的，只有最合适的

概览

Serial 收集器

-XX:+UseSerialGC 开启年轻代使用

-XX:+UseSerialOldGC 开启老年代使用

Serial（串行）收集器是最基本、历史最悠久的垃圾收集器了。看名字就知道这个收集器是一个单线程收集器了。它的 “单线程” 的意义不仅仅意味着它只会使用一条垃圾收集线程去完成垃圾收集工作，更重要的是它在进行垃圾收集工作的时候必须暂停其他所有的工作线程（ "Stop The World" ），直到它收集结束。

新生代采用复制算法，老年代采用标记-整理算法。

示意图：

Serial Old 收集器是Serial收集器的老年代版本，它同样是一个单线程收集器。

它主要有两大用途：

1. 在JDK1.5以及以前的版本中与Parallel Scavenge收集器搭配使用
2. 作为CMS收集器的后备方案。

实现简单，单线程的收集效率高

Parallel Scavenge 收集器

JK8 默认的垃圾回收器

-XX:+UseParallelGC(年轻代)， 采用复制算法

-XX:+UseParallelOldGC(老年代) 标记整理算法

Parallel 其实就是 Serial 的多线程版本，默认的收集线程数与CPU核心数相同，也可以使用参数 -XX:ParallelGCThreads 指定收集线程数，但是一般不推荐修改。

Parallel Scavenge 注重的是收集效率，后面要介绍的 CMS，G1 收集器 更注重用户体验，缩短 STW 的时长。但是他不能与 CMS 收集器配合使用

示意图:

ParNew 收集器

ParNew 收集器和 Parallel 很类似，主要区别在于，他可以与 CMS 配合使用，新生代采用复制算法，老年代采用标记-整理算法。

只有 Serial ,ParNew 可以与 CMS 配合使用 ， ParNew 是很多虚拟机的首要选择。

CMS 收集器

-XX:+UseConcMarkSweepGC(old)

CMS(ConcurrentMarkSweep) 是一种追求短 STW 为目标的收集器，注重用户体验，他是 HotSpot 虚拟机第一款真正意义上的收集器，第一次实现了让用户线程和收集线程同时工作

从名字就可以看出来，Mark: 标记，Sweep: 清除， 它采用标记清理算法， 他的工作流程更复杂，主要分下面5个步骤:

1. 初始标记: 暂停用户线程，标记GC Root 直接引用 的对象，速度很快
2. 并发标记： 从第一步标记的对象开始遍历所有引用对象，过程耗时很长，但是不需要暂停用户线程，因为有用户线程的干扰，可能会修改已经标记的对象，产生问题
3. 重新标记：为了修正并发标记时产生的问题，产生问题的对象比例小，所以速度很快。此过程会STW
4. 并发清理： 清理线程与用户线程同时运行，清理掉没有标记的对象，如果此时有新增的对象虽然没有被标记，统一会当作存活对象，不会误清理
5. 并发重置： 重置本次GC被标记的数据

优点:

• 并发收集
• 短停顿

缺点:

• 和用户线程抢占CPU资源
• 无法处理浮动垃圾
• 由于时标记清除算法，会产生内存碎片，可以通过参数: -XX:+UseCMSCompactAtFullCollection 控制是否做空间整理
• 由于允许用户线程同时运行，会造成在GC过程中不断的有对象进入内存，当前GC没有完成，空间没有释放，可能导致没有足够的空间放新进来的对象，此时会导致 STW,然后退化成 serial 收集器进行垃圾回收

CMS的相关核心参数

1. -XX:+UseConcMarkSweepGC：启用cms 
2. -XX:ConcGCThreads：并发的GC线程数
3. -XX:+UseCMSCompactAtFullCollection：FullGC之后做压缩整理（减少碎片）
4. -XX:CMSFullGCsBeforeCompaction：多少次FullGC之后压缩一次，默认是0，代表每次FullGC后都会压缩一次
5. -XX:CMSInitiatingOccupancyFraction: 当老年代使用达到该比例时会触发FullGC（默认是92，这是百分比）
6. -XX:+UseCMSInitiatingOccupancyOnly：只使用设定的回收阈值(-XX:CMSInitiatingOccupancyFraction设定的值)，如果不指定，JVM仅在第一次使用设定值，后续则会自动调整
7. -XX:+CMSScavengeBeforeRemark：在CMS GC前启动一次minor gc，降低CMS GC标记阶段(也会对年轻代一起做标记，如果在minor gc就干掉了很多对垃圾对象，标记阶段就会减少一些标记时间)时的开销，一般CMS的GC耗时 80%都在标记阶段
8. -XX:+CMSParallellnitialMarkEnabled：表示在初始标记的时候多线程执行，缩短STW
9. -XX:+CMSParallelRemarkEnabled：在重新标记的时候多线程执行，缩短STW;

三色标记

初始标记

并发标记

并发标记产生的问题的原因

出现问题的后果

问题的解决办法

出现漏标的两个必要条件:

1. 有对象的引用关系被删除
2. 删除的对象又被重新引用

见上图 破环任意步骤，即可避免漏标的现象。有以下两种解决方案:

• 增量更新 因为重新标记时，要再次从黑色对象出发，深度扫描所有引用，效率没有原始快照高
  • 优点: 不会产生浮动垃圾
  • 缺点: 效率低
• 原始快照 再引用被删除时，记录关系，重新扫描时，将被引用的对象标记为非垃圾，如果后续没有再次引该对象，那么该对象就会变成浮动垃圾
  • 缺点: 可能会产生浮动垃圾
  • 优点: 不要重新扫描，效率高

那除此之外，还没有没有其他可能重新引用对象呢？答案只有一个， new 一个新对象。在GC期间，有新的对象进来时，统一被当成黑色处理，不会被回收

那么上图中的 brand 会不会被重新引用呢？答案是不会！因为已经找不到引用 brand 对象的变量了，在引用程序中无法再次引用这个垃圾对象

上图中说到，在对象被引用上，删除对象引用是，记录这个引用关系，从而方便后续的重新编辑，那么这个记录的动作是如何发生的？ 这时就要引入写屏障的技术了。

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

写屏障

类似于切面，在赋值动作的前后做一些事情。

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); // 记录新引用的对象 
}

读屏障

与写屏障类似

重新标记

并发清理

并发重置

以上就是三色标记的大体流程了

不同垃圾回收器对三色标记的选择

• CMS 写屏障 + 增量更新
• G1 ,Shenandoah： 写屏障 + STAB
• ZGC: 读屏障

为什么 G1 采用 STAB， CMS 采用 增量更新

个人理解： G1 一般用于大内存的机器，内存 8G 至百G级别, 存放的对象更多，自然要扫描的对象更多，如果采用效率低的增量更新方式，效率下降的更严重，所以采用效率较高的 STAB,虽然会产生一些浮动垃圾，但是对于大内存机器来说，影响不大。

CMS 适用于内存较小的机器,多用于 4G 到 8G 的机器上，无论采用 STAB 还是 CMS, 效率上无法拉开明显差距，而增量更新不会产生浮动垃圾，对内存更小的机器来说，内存的使用更敏感，自然采用增量更新的方式

记忆集与卡表

这两个结构是为了垃圾器在跨代访问时提高速度的。

在新生代做GCRoots可达性扫描过程中可能会碰到跨代引用的对象，这种如果又去对老年代再去扫描，甚至老年代内存在很多对象的间接引用，这种效率就太低了，大大的延长了 Minor GC 的时间。

为此，在新生代可以引入记录集（Remember Set）的数据结构（记录从非收集区到收集区的指针集合），避免把整个老年代加入GCRoots扫描范围。事实上并不只是新生代、 老年代之间也有跨代引用的问题， 所有涉及部分区域收集（Partial GC） 行为的垃圾收集器， 典型的如G1、 ZGC和Shenandoah收集器， 都会面临相同的问题。

垃圾收集场景中，收集器只需通过记忆集判断出某一块非收集区域是否存在指向收集区域的指针即可，无需了解跨代引用指针的全部细节。

hotspot使用一种叫做“卡表”(Cardtable)的方式实现记忆集，也是目前最常用的一种方式。关于卡表与记忆集的关系， 可以类比为Java语言中HashMap与Map的关系。

卡表是使用一个字节数组实现：CARD_TABLE[ ]，每个元素对应着其标识的内存区域一块特定大小的内存块，称为“卡页”。

hotSpot使用的卡页是2^9大小，即512字节

一个卡页中可包含多个对象，只要有一个对象的字段存在跨代指针，其对应的卡表的元素标识就变成1，表示该元素变脏，否则为0.

GC时，只要筛选本收集区的卡表中变脏的元素加入GCRoots里。

卡表的维护

卡表变脏上面已经说了，但是需要知道如何让卡表变脏，即发生引用字段赋值时，如何更新卡表对应的标识为1。

Hotspot使用写屏障维护卡表状态。