G1 GC分享-并发标记原理

背景 我们服务的GC情况

4G内存，Evacuation频繁且耗时久 如何优化，从GC日志分析原因？ 代码层面该如何改动？ 何处着手

G1 回顾

之前分享过GC的基本原理

 

一个假想的混合的STW时间线：

启动程序 -> young GC -> young GC -> young GC -> young GC + initial marking (... concurrent marking ...) -> young GC (... concurrent marking ...) (... concurrent marking ...) -> young GC (... concurrent marking ...) -> final marking -> cleanup -> mixed GC -> mixed GC -> mixed GC ... -> mixed GC -> young GC + initial marking (... concurrent marking ...) ...

其中可以看到young GC可以单独运行，也可以搭上initial marking在同一个STW中运行。 “young GC (... concurrent marking ...)”的行里面young GC还是单独运行的，跟后台正在进行的concurrent marking不冲突。

也就是说做YGC的时候，只需要选定young gen region的RSet（记录了old->young的跨代引用）作为根集，这样就避免了扫描old gen

回收过程 global concurrent marking 和 Evacuation Pause

Global concurrent marking基于SATB形式的并发标记。它具体分为下面几个阶段： 1、初始标记（initial marking）：暂停阶段。扫描根集合，标记所有从根集合可直接到达的对象并将它们的字段压入扫描栈（marking stack）中等到后续扫描。G1使用外部的bitmap来记录mark信息，而不使用对象头的mark word里的mark bit。在分代式G1模式中，初始标记阶段借用young GC的暂停，因而没有额外的、单独的暂停阶段。 2、并发标记（concurrent marking）：并发阶段。不断从扫描栈取出引用递归扫描整个堆里的对象图。每扫描到一个对象就会对其标记，并将其字段压入扫描栈。重复扫描过程直到扫描栈清空。过程中还会扫描SATB write barrier所记录下的引用。 3、最终标记（final marking，在实现中也叫remarking）：暂停阶段。在完成并发标记后，每个Java线程还会有一些剩下的SATB write barrier记录的引用尚未处理。这个阶段就负责把剩下的引用处理完。同时这个阶段也进行弱引用处理（reference processing）。 注意这个暂停与CMS的remark有一个本质上的区别，那就是这个暂停只需要扫描SATB buffer，而CMS的remark需要重新扫描mod-union table里的dirty card外加整个根集合，而此时整个young gen（不管对象死活）都会被当作根集合的一部分，因而CMS remark有可能会非常慢。 4、清理（cleanup）：暂停阶段。清点和重置标记状态。这个阶段有点像mark-sweep中的sweep阶段，不过不是在堆上sweep实际对象，而是在marking bitmap里统计每个region被标记为活的对象有多少。这个阶段如果发现完全没有活对象的region就会将其整体回收到可分配region列表中。

global concurrent marking对mixed gc中的old gen gc有帮助，与young gc没多大关系，young gc和mixed gc都是STW的，他们都是用了拷贝算法。

名词理解 Cset

collection set，简称CSet 在Evacuation阶段，由G1垃圾回收器选择的待回收的Region集合。G1垃圾回收器的软实时的特性就是通过CSet的选择来实现的。对应于算法的两种模式fully-young generational mode和partially-young mode，CSet的选择可以分成两种：

1. 在fully-young generational mode下：顾名思义，该模式下CSet将只包含young的Region。G1将调整young的Region的数量来匹配软实时的目标；
2. 在partially-young mode下：该模式会选择所有的young region，并且选择一部分的old region。old region的选择将依据在Marking cycle phase中对存活对象的计数。G1选择存活对象最少的Region进行回收。

Rset

remembered set（下面简称RSet）是每个region有一份。这个RSet记录的是从别的region指向该region的card 由于PointIn模式的缺点，一个对象可能被引用的次数不固定，为了节约空间，G1采用了三级数据结构来存储：

• 稀疏表：通过哈希表来存储，key是region index，value是card数组
• 细粒度PerRegionTable：当稀疏表指定region的card数量超过阈值时，则在细粒度PRT中创建一个对应的PerRegionTable对象，其包含一个C heap位图，每一位对应一个card
• 粗粒度位图：当细粒度PRT size超过阈值时，则退化为分区位图，每一位表示对应分区有引用到当前分区

每个HeapRegion都包含了一个HeapRegionRemSet，每个HeapRegionRemSet都包含了一个OtherRegionsTable，引用数据就保存在这个OtherRegionsTable中。

Card Table

 

G1里不易理解的部分 SATB 和Incremental Update 着色标记

我们都知道cms gc 和g1 gc 的算法都是通过对gc root 进行遍历，并进行三颜色标记，具体标记算法如下：

• 黑色(black):节点被遍历完成，而且子节点都遍历完成。
• 灰色(gray): 当前正在遍历的节点，而且子节点还没有遍历。
• 白色(white):还没有遍历到的节点，即灰色节点的子节点。

并行gc 面对的共同问题 我们都知道cmg gc 和g1 gc 都是和程序有并行执行的阶段。既然有并行，那就有可能在并行运行期间之前的标记过的对象的引用关系可能被改变，比如一个白色对象从被灰色的引用变为被黑色的对象引用。如果不做处理，那这个白色的对象会被漏掉，会被错误的回收。会导致程序错误。 这也是cms gc 和g1 gc 都有remark阶段的原因。都需要重新对被修改的card 进行扫描。 那cms gc 和g1 gc 是怎么解决这个问题的呢。而且有什么区别呢。这就需要了解cms gc 和g1 gc 所用的算法的不一样而导致不一样的解决方案了。 cms gc 是Incremental Update算法，g1 gc 是采用的 stab 算法，下面我们先讲下Incremental Update。 要知道怎么解决问题，我们先描述下问题的场景，并行gc 在什么情况下会出现漏掉活的对象，根据三色扫描算法，如果有下面两种情况发生，则会出现漏扫描的场景：

1. 把一个白对象的引用存到黑对象的字段里,如果这个情况发生，因为标记为黑色的对象认为是扫描完成的，不会再对他进行扫描。只能通过灰色的对象
2. 某个白对象失去了所有能从灰对象到达它的引用路径(直接或间接)

文字描述可能太抽象，通过下面的图更形象

如上图所示，的对象D 同时满足上面两个条件，引用存到了黑对象A上面，同时切断了灰对象B对它的引用，那D对象将被漏扫描了。 那CMS GC和G1 GC 是怎么解决这个问题的呢？ 解决这个问题可以从两个角度入手，从上面的图可以看出，指向D的这个引用从源B到目的地址A,所以就有两种算法分别是从源和目标的角度来解决，分别产生了下面两种算法：

SATB 即 Snapshot-at-beginning

satb 算法认为开始标记的都认为是活的对象，如上图所示,引用B到D 的引用改为B到C时，通过write barrier写屏障技术，会把B到D 的引用推到gc 遍历执行的堆栈上，保证还可以遍历到D对象，相对于d来说，引用从B-->A,SATB 是从源入手解决的，即上面说的第2种情况， 这也能理解为啥叫satb 了，即认为开始时所有能遍历到的对象都是需要标记的，即都认为是活的。如果我吧b = null,那么d 久是垃圾了， satb算法也还是会把D最终标记为黑色，导致D 在本轮gc 不能回收，成了浮动垃圾。

Incremental Update write barrier

Incremental Update 算法判断如果一个白色的对象由一个黑色的对象引用，即目的，如上图，D的引用由B-->A,A是目的地址，所以cms 的Incremental Update算法是从目标入手解决的，这是和SATB的第一个区别，发现这种情况时，也是通过write barrier写屏障技术，把黑色的对象重新标记为灰色，让collector 重新来扫描，活着通过mod-union table 来标记，cms 就是这样实现的，这是第二个区别，做法不一样，也是上面讲的防止第一种情况发生。

为什么我们YoungGC慢

实战分析，流量回放 dump分析  

参考

G1垃圾回收器详解 - 简书   SATP:G1 SATB和Incremental Update算法的理解 - 简书

可能是最全面的G1学习笔记 - 知乎

并行标记的算法：G1 SATB和Incremental Update算法的理解 - 简书

Young GC源码：通过源码学习G1GC —— Pause Young (G1 Evacuation Pause) - 简书