G1垃圾收集器

特点

==从整体看基于标记-整理算法，从局部看基于复制算法。==
==停顿可预测==。降低停顿时间是G1和CMS共同的关注点，但G1除了降低停顿外，还能建立可预测的停顿时间模型，能让使用者明确指定在一个长度为M毫秒的时间片段内，消耗在GC上的时间不得超过N毫秒。
收集范围是整个堆内存。
适合大堆，因为不像CMS和Parallel GC在对老代进行收集的时候需要将整个老代全部收集，G1收集老代==一次只收集老代的一部分Region==。
G1的Heap划分为多个Region，新生代和老年代都只是逻辑概念，不再是物理上隔离又连续的空间。
G1的新老代划分不是固定的，一个新生代的Region在被回收之后可以作为老年代的Region使用，新生代和老年代的大小也会随着系统运行而调整。
==G1的新生代收集和Parallel、CMS GC一样是并发的Stop The World收集，且每次Young GC会将整个新生代收集。==
==G1的老年代收集每次只收集一部分性价比最高的Old Region，且这部分Old Region是和Young GC一起进行的，所以称为Mixed GC。==
和CMS一样，G1也有 fail-safe 的 FullGC，单线程且会做内存压缩。
G1 的 Old Generation GC (Mixed GC) 也是自带内存压缩的。
G1 没有永久代的概念。

内存分布

传统的GC收集器将连续的内存空间划分为新生代、老年代和永久代(jdk 8去除永久代加入元空间)。各代的存储地址是连续的。

而G1的各代存储地址是不连续的，每一代都使用N个不连续的大小相同的Region，每个Region占有一块连续的虚拟内存地址。
图中，H为Humongous，表示这些Region存储的是巨大对象(H-obj)，大小大于等于Region一半的对象。为了防止反复拷贝移动，H-obj直接分配到老年代。

Remembered Set和Card Table

Remembered Set

G1 中每个 Region 都会维护一个 Remembered Sets，也叫 RSet，用于记录当前 Region 之外，有哪些 Region 有指向当前 Region 的引用。
在传统分代垃圾回收算法中，Remembered Set被用来记录分代之间的指针，可以认为传统分代回收器只有新生代和老年代两个Region，仍然是每个Region一个Remembered Set。

Card Table

每一个Region都被划分成若干张固定大小的Card，每一张Card都用Card Table中的一个byte记录是否修改过。

Remembered Set,Card Table和Region的关系

每个Region会在自身的Remembered Set中纪录下来自其他Region的指向自身的Card位置。这个Remembered Set是一个Hash Table，Key是别的Region的起始地址，Value是一个集合，里面的元素是Card Table的Index。

一个Region可能有多个线程在并发修改，因此它们也会并发修改Remembered Set。为了避免这样一种冲突，G1垃圾回收器进一步把Remembered Set划分成了多个哈希表。每一个线程都在各自的哈希表里面修改。最终，从逻辑上来说，RS就是这些哈希表的集合。Remembered Set的虚线表名的是，Remembered Set并不是一个和Card Table独立的，不同的数据结构，而是指RS是一个概念模型。实际上，Card Table是Remembered Set的一种实现方式。

G1垃圾回收

young GC

选定所有年轻代里的Region。==通过控制年轻代的region个数，即年轻代内存大小，来控制young GC的时间开销。==

当Eden Region满了后会触发Young GC, Stop The World。
Eden区的数据移动到Survivor区，如果Survivor空间不够，部分数据直接晋升到老年代。 Survivor区的数据移动到新的Survivor区中，也有部分数据晋升到老年代中。最终Eden区的数据为空。

youngGC步骤：

扫描GC Root。
扫描新生代的Rememebered Set中的==老年代对象加入GC Root==。
根据GC Root标记存活的新生代对象。

MIXED GC

MIXED GC收集整个年轻代的Region和部分Global Concurrent Mark统计得出的用户指定开销范围内收益较高的老年代Region。

Old GC在Young GC后开始，并且Old GC的过程中可能伴随有Young GC，所以称作Mixed GC，只有G1垃圾收集器有Mixed GC模式。

MIX GC的Old GC包括两个步骤：全局并发标记(Global Concurrent Mark)和拷贝存活对象(Evacuation)。

全局并发标记(Global Concurrent Mark)

初始标记(Initial Marking) Stop The World，
1. 标记GC Root直接关联的老年代对象。
2. 扫描Young GC后的Survivor区，标记可能拥有老年代对象引用的新生代对象。

由于Young GC也需要Stop The World，==该步骤通常在Young GC末尾时同时执行。==

并发标记(Concurrent Marking) 与应用程序同时进行，从上一阶段标记的存活对象开始，并发地跟踪所有可达的老年代对象，期间可以被Young GC打断。详见三色标记算法
最终标记(Remark) Stop The World，并行的跟踪上面阶段所有标记的对象，标记所有未被访问的存活对象。
复制/清除(Copy/Clean) 统计存活对象，重置并回收完全空闲的Region。
重置Remembered Set。
将存活对象复制到未被占用的区域(整理)，如只对新生代操作，则G1记录为[GC pause(young)]，如同时执行一部分老年代则为[GC Pause(mixed)]，老年代根据其“存活度”选择。

三色标记算法

首先，我们将对象分成三种类型的。
黑色:根对象，或者该对象与它的子对象都被扫描。
灰色:对象本身被扫描,但还没扫描完该对象中的子对象。
白色:未被扫描对象，扫描完成所有对象之后，最终为白色的为不可达对象，即垃圾对象。

当GC开始扫描对象时，按照如下图步骤进行对象的扫描：
根对象被置为黑色，子对象被置为灰色。

继续由灰色遍历,将已扫描了子对象的对象置为黑色。

遍历了所有可达的对象后，所有可达的对象都变成了黑色。不可达的对象即为白色，需要被清理。

然而，当垃圾回收的同时用户程序也在运行时，对象指针可能被同时改变：
如下图，垃圾收集器扫描到如下结构。

此时，用户线程执行A.c = C, B.c = null，对象状态改变为：

垃圾收集器再标记：

标记结束后，对象C被A引用，但是仍然为白色，会错误的被当做垃圾收集。

解决办法

错误回收的情况发生，有两个必要的条件：

用户线程删除了所有从灰对象到该白对象的直接或者间接引用。，B.c = null。
用户线程赋予一个黑对象该白对象的引用，A.c = C。

在G1中，采用STAB法(Snapshot-at-the-beginning)，破坏条件1：

1. 在开始标记时生成快照(Snapshot)标记所有存活的对象。
2. 在并发标记时，和快照相比所有被改变的对象都不回收，确保在本轮GC中存活。

该方法能够保证不会有错误回收的情况，但是可能漏标垃圾对象，产生浮动垃圾。

在CMS中，采用的是增量更新（Incremental update），破坏条件2：

只要在写屏障（write barrier）里发现要有一个白对象的引用被赋值到一个黑对象的字段里，那就把这个白对象变成灰色的。即插入的时候记录下来。  

同样能够保证不会有错误回收的情况，可能有漏标。

触发Full GC

==由于Mixed GC不是Full GC，只是回收部分老年代==，因此可能导致垃圾回收的速度无法跟上用户分配的速度。

在以下几种情况下，G1会触发Full GC，退化成使用Serial收集器(Serial New + Serial Old)完成垃圾收集。

移动对象时没有足够的to-space存放晋升的对象(Promition Fail)。
并发处理过程完成之前空间耗尽(Concurrent Mode Failure)。
Full GC会会对所有region做Evacuation-Compact，而且是单线程的STW

refs:

https://tech.meituan.com/g1.html
https://www.jianshu.com/p/bdd6f03923d1
http://ifeve.com/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3g1%E5%9E%83%E5%9C%BE%E6%94%B6%E9%9B%86%E5%99%A8/
https://www.jianshu.com/p/35cd012eeb8c
https://www.jianshu.com/p/9e70097807ba

本文地址：https://cheng-dp.github.io/2018/11/30/gc-g1/

东平的笔记仓库