G1垃圾回收器详解 SATB算法

G1垃圾回收器

主要针对配备多颗处理器及大容量内存的机器. 以极高概率满足GC停顿时间要求的同时,还具备高吞吐量性能特征, 整体采用“标记—整理”算法，局部（region之间）采用“复制”算法

G1 给整一块Heap内存区域均匀等分了N个 Region，N 默认情况下是 2048， Region为2-32MB

• 可以像CMS收集器一样,GC操作与应用的线程一起并发执行
• 紧凑的空闲内存区间且没有很长的GC停顿时间.
• 需要可预测的GC暂停耗时.
• 不想牺牲太多吞吐量性能.
• 启动后不需要请求更大的Java堆.
  

Remembered Sets 简称 RSets. RSet记录了其他Region中的对象引用本Region中对象的关系. RSet的价值在于使得垃圾收集器不需要扫描整个堆找到谁引用了当前分区中的对象，只需要扫描RSet即可. 堆内存中的每个region都有一个RSet. RSet 使heap区能并行独立地进行垃圾集合. RSets的总体影响小于5%.

Collection Sets 简称 CSets. 收集集合,一组可被回收的分区的集合。在CSet中存活的数据会在GC过程中被移动到另一个可用分区，CSet中的分区可以来自Eden空间、survivor空间、或者老年代。CSet会占用不到整个堆空间的1%大小。

巨型对象: 在G1中，如果一个对象的大小超过分区大小的一半，该对象就被定义为巨型对象。巨型对象时直接分配到老年代分区，如果一个对象的大小超过一个分区的大小，那么会直接在老年代分配两个连续的分区来存放该巨型对象。巨型分区一定是连续的，分配之后也不会被移动。

Region分配: 每一次都只有一个Region处于被分配的状态中，被称为current region。在多线程的情况下，这会带来并发的问题。G1回收器采用和CMS一样的TLABs的手段。即为每一个线程分配一个Buffer，线程分配内存就在这个Buffer内分配。但是当线程耗尽了自己的Buffer之后，需要申请新的Buffer。这个时候依然会带来并发的问题。G1回收器采用的是CAS（Compate And Swap）操作。

G1的年轻代收集 (young GC)

1. Eden Regions耗尽的时候就会触发新生代收集，新生代垃圾收集会对整个新生代进行回收
2. 年轻代内存由一组不连续的region组成.
3. 新生代垃圾收集期间，整个应用STW.
4. 年轻代 GC 通过多线程并行进行.
5. 存活的对象被拷贝到新的 survivor 区或者老年代.

G1的老年代收集 (mixed GC)

1. 初始标记: 需要停顿，但是耗时很短. 通常初始标记阶段会跟一次新生代收集一起进行
2. 根分区扫描: 不需要停顿，这个阶段G1开始扫描survivor分区，所有被survivor分区所引用的对象都会被扫描到并将被标记. 该阶段不能发生新生代收集
3. 并发标记： 不需要停顿，并发标记利用trace算法找出存活对象,并记录在一个bitmap中. 使用了SATB算法解决该过程中引用发生变化产生对象漏标问题
4. 再次标记： 需要停顿，可并发执行. G1垃圾收集器会处理掉剩下的SATB日志缓冲区和所有更新的引用. 空的区域会直接被移除并回收。
5. 清除回收： 需要停顿，可并发执行。 对各个Region的回收价值和成本记性排序，根据用户的期望进行回收。转移或拷贝存活的对象到新的未使用的heap区

SATB算法

是为增量式标记清除垃圾收集器设计的快照标记算法，G1并发的基础就是SATB. 主要应用于垃圾收集的并发标记阶段. SATB可以理解成在GC开始之前对堆内存里的对象做一次快照，此时活的对象就认为是活的，从而形成一个对象图
步骤：

1. 在初始标记的时候生成一个快照图，标记存活对象
2. 在并发标记的时候出现了引用修改会把这些引用的原始值捕获下来，记录在log buffer中
3. 在再次标记阶段扫描SATB，修正SATB的误差

可能存在浮动垃圾，将在下次被收集。

对象漏标
垃圾回收的并发标记阶段，GC线程和应用线程是并发执行的，所以一个对象被标记之后，应用线程可能篡改对象的引用关系，从而造成对象的漏标、误标，其实误标没什么关系，顶多造成浮动垃圾，在下次gc还是可以回收的，但是漏标的后果是致命的，把本应该存活的对象给回收了，从而影响的程序的正确性。

首先需要了解两个概念 三色算法 与 Region结构

三色算法
给每一个对象用颜色进行区分
黑色：自身以及可达对象都已经被标记
灰色：自身被标记，可达对象还未标记
白色：还未被标记
漏标的情况只会发生在白色对象中，且满足以下任意一个条件：

1. 并发标记时，应用线程给一个黑色对象的引用类型字段赋值了白色对象
   解决方案: 利用post-write barrier，记录所有新增的引用关系，然后根据这些引用关系为根重新扫描一遍。
2. 并发标记时，应用线程删除所有灰色对象到白色对象的引用
   解决方案: 利用pre-write barrier，将所有既将被删除的引用关系的旧引用记录下来，最后以这些旧引用为根重新扫描一遍。

Region结构: 每一个Region 包含了5个指针，分别是bottom、previous TAMS、next TAMS、top和end, 其中previous TAMS、next TAMS是前后两次发生并发标记时的位置. 在prevTAMS和nextTAMS以上的对象就是新分配的

1. A是初始标记阶段。next TAMS尚未标记任何存活对象，而此时的previous TAMS被初始化为region内存地址起始值，next TAMS被初始化为top。top实际上就是一个region未分配区域和已分配区域的分界点；
2. B是并发标记之后，进入了再次标记阶段。此时存活对象的扫描已经完成了，因此next bitmap构造好了，代表的是当下状态中region中的内存使用情况。注意的是，此时top已经不再与next TAMS重合了，top和next TAMS之间的就是在前面标记阶段之时，新分配的对象
3. C代表的是clean up阶段。C和B比起来，next bitmap变成了previous bitmap，而在bitmap中标记为垃圾（也就是白色区域的）的对应的region的区域也被染成了浅灰色。这并不是指垃圾对象已经被清扫了，仅仅是标记出来了。
4. D代表的是下一个初始标记阶段，该阶段和A类似，next TAMS重新被初始化为top的值；
5. EF就是BC的重复；

但如果在TAMS之前有一个白色对象W，被一个灰色对象G引用，在并发标记扫描到这个字段之前被赋值为null，切断了对象W和对象G之间的引用关系，对象W就有可能漏标，这就是白色对象被漏标的第二种情况

SATB保证了在并发标记过程中对象引用发生改变时不会漏标，保证GC准确性