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

JVM中的CMS、G1垃圾回收器所使用垃圾回收算法即为三色标记法。

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

存在问题：

浮动垃圾：并发标记的过程中，若一个已经被标记成黑色或者灰色的对象，突然变成了垃圾，此时，此对象不是白色的不会被清除，重新标记也不能从GC Root中去找到，所以成为了浮动垃圾，这种情况对系统的影响不大，留给下一次GC进行处理即可。

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

在JVM虚拟机中有两种常见垃圾回收器使用了该算法：

CMS(Concurrent Mark Sweep)

CMS，是非常有名的JVM垃圾回收器，它起到了承上启下的作用，开启了并发回收的篇章。

但是CMS由于许多小问题，现在基本已经被淘汰。

增量更新(Increment Update)

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

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

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

在一个灰色对象正在被一个GC线程回收时，当它已经被标记过的属性指向了一个白色对象（垃圾）

而这个对象的属性对象本身还未全部标记结束，则为灰色不变

而这个GC线程在标记完最后一个属性后，认为已经将所有的属性标记结束了，将这个灰色对象标记为黑色，被重新引用的白色对象，无法被标记

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

解决方案：使用Mark-Sweep-Compact算法，减少垃圾碎片

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

解决方案：降低触发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)

SATB(Snapshot At The Beginning)

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

因为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%）

G1的第一篇paper（附录1）发表于2004年，在2012年才在jdk1.7u4中可用。oracle官方计划在jdk9中将G1变成默认的垃圾收集器，以替代CMS。为何oracle要极力推荐G1呢，G1有哪些优点？

首先，G1的设计原则就是简单可行的性能调优

开发人员仅仅需要声明以下参数即可：

其中-XX:+UseG1GC为开启G1垃圾收集器，-Xmx32g 设计堆内存的最大内存为32G，-XX:MaxGCPauseMillis=200设置GC的最大暂停时间为200ms。如果我们需要调优，在内存大小一定的情况下，我们只需要修改最大暂停时间即可。

其次，G1将新生代，老年代的物理空间划分取消了。

这样我们再也不用单独的空间对每个代进行设置了，不用担心每个代内存是否足够。

取而代之的是，G1算法将堆划分为若干个区域（Region），它仍然属于分代收集器。不过，这些区域的一部分包含新生代，新生代的垃圾收集依然采用暂停所有应用线程的方式，将存活对象拷贝到老年代或者Survivor空间。老年代也分成很多区域，G1收集器通过将对象从一个区域复制到另外一个区域，完成了清理工作。这就意味着，在正常的处理过程中，G1完成了堆的压缩（至少是部分堆的压缩），这样也就不会有cms内存碎片问题的存在了。

在G1中，还有一种特殊的区域，叫Humongous区域。 如果一个对象占用的空间超过了分区容量50%以上，G1收集器就认为这是一个巨型对象。这些巨型对象，默认直接会被分配在年老代，但是如果它是一个短期存在的巨型对象，就会对垃圾收集器造成负面影响。为了解决这个问题，G1划分了一个Humongous区，它用来专门存放巨型对象。如果一个H区装不下一个巨型对象，那么G1会寻找连续的H分区来存储。为了能找到连续的H区，有时候不得不启动Full GC。

PS：在java 8中，持久代也移动到了普通的堆内存空间中，改为元空间。

对象分配策略

说起大对象的分配，我们不得不谈谈对象的分配策略。它分为3个阶段：

对TLAB空间中无法分配的对象，JVM会尝试在Eden空间中进行分配。如果Eden空间无法容纳该对象，就只能在老年代中进行分配空间。

最后，G1提供了两种GC模式，Young GC和Mixed GC，两种都是Stop The World(STW)的。下面我们将分别介绍一下这2种模式。

Young GC主要是对Eden区进行GC，它在Eden空间耗尽时会被触发。在这种情况下，Eden空间的数据移动到Survivor空间中，如果Survivor空间不够，Eden空间的部分数据会直接晋升到年老代空间。Survivor区的数据移动到新的Survivor区中，也有部分数据晋升到老年代空间中。最终Eden空间的数据为空，GC停止工作，应用线程继续执行。

这时，我们需要考虑一个问题，如果仅仅GC 新生代对象，我们如何找到所有的根对象呢？ 老年代的所有对象都是根么？那这样扫描下来会耗费大量的时间。于是，G1引进了RSet的概念。它的全称是Remembered Set，作用是跟踪指向某个heap区内的对象引用。

在CMS中，也有RSet的概念，在老年代中有一块区域用来记录指向新生代的引用。这是一种point-out，在进行Young GC时，扫描根时，仅仅需要扫描这一块区域，而不需要扫描整个老年代。

但在G1中，并没有使用point-out，这是由于一个分区太小，分区数量太多，如果是用point-out的话，会造成大量的扫描浪费，有些根本不需要GC的分区引用也扫描了。于是G1中使用point-in来解决。point-in的意思是哪些分区引用了当前分区中的对象。这样，仅仅将这些对象当做根来扫描就避免了无效的扫描。由于新生代有多个，那么我们需要在新生代之间记录引用吗？这是不必要的，原因在于每次GC时，所有新生代都会被扫描，所以只需要记录老年代到新生代之间的引用即可。

需要注意的是，如果引用的对象很多，赋值器需要对每个引用做处理，赋值器开销会很大，为了解决赋值器开销这个问题，在G1 中又引入了另外一个概念，卡表（Card Table）。一个Card Table将一个分区在逻辑上划分为固定大小的连续区域，每个区域称之为卡。卡通常较小，介于128到512字节之间。Card Table通常为字节数组，由Card的索引（即数组下标）来标识每个分区的空间地址。默认情况下，每个卡都未被引用。当一个地址空间被引用时，这个地址空间对应的数组索引的值被标记为”0″，即标记为脏被引用，此外RSet也将这个数组下标记录下来。一般情况下，这个RSet其实是一个Hash Table，Key是别的Region的起始地址，Value是一个集合，里面的元素是Card Table的Index。

Young GC 阶段：

Mix GC不仅进行正常的新生代垃圾收集，同时也回收部分后台扫描线程标记的老年代分区。

它的GC步骤分2步：

全局并发标记（global concurrent marking）

拷贝存活对象（evacuation）

在进行Mix GC之前，会先进行global concurrent marking（全局并发标记）。 global concurrent marking的执行过程是怎样的呢？

在G1 GC中，它主要是为Mixed GC提供标记服务的，并不是一次GC过程的一个必须环节。global concurrent marking的执行过程分为五个步骤：

初始标记（initial mark，STW）

在此阶段，G1 GC 对根进行标记。该阶段与常规的 (STW) 年轻代垃圾回收密切相关。

根区域扫描（root region scan）

G1 GC 在初始标记的存活区扫描对老年代的引用，并标记被引用的对象。该阶段与应用程序（非 STW）同时运行，并且只有完成该阶段后，才能开始下一次 STW 年轻代垃圾回收。

并发标记（Concurrent Marking）

G1 GC 在整个堆中查找可访问的（存活的）对象。该阶段与应用程序同时运行，可以被 STW 年轻代垃圾回收中断

最终标记（Remark，STW）

该阶段是 STW 回收，帮助完成标记周期。G1 GC 清空 SATB 缓冲区，跟踪未被访问的存活对象，并执行引用处理。

清除垃圾（Cleanup，STW）

在这个最后阶段，G1 GC 执行统计和 RSet 净化的 STW *** 作。在统计期间，G1 GC 会识别完全空闲的区域和可供进行混合垃圾回收的区域。清理阶段在将空白区域重置并返回到空闲列表时为部分并发。

提到并发标记，我们不得不了解并发标记的三色标记算法。它是描述追踪式回收器的一种有用的方法，利用它可以推演回收器的正确性。 首先，我们将对象分成三种类型的。

根对象被置为黑色，子对象被置为灰色。

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

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

这看起来很美好，但是如果在标记过程中，应用程序也在运行，那么对象的指针就有可能改变。这样的话，我们就会遇到一个问题：对象丢失问题

我们看下面一种情况，当垃圾收集器扫描到下面情况时：

这时候应用程序执行了以下 *** 作：

这样，对象的状态图变成如下情形：

这时候垃圾收集器再标记扫描的时候就会下图成这样：

很显然，此时C是白色，被认为是垃圾需要清理掉，显然这是不合理的。那么我们如何保证应用程序在运行的时候，GC标记的对象不丢失呢？有如下2中可行的方式：

在插入的时候记录对象

在删除的时候记录对象

刚好这对应CMS和G1的2种不同实现方式：

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

在G1中，使用的是STAB（snapshot-at-the-beginning）的方式，删除的时候记录所有的对象，它有3个步骤：

这样，G1到现在可以知道哪些老的分区可回收垃圾最多。 当全局并发标记完成后，在某个时刻，就开始了Mix GC。这些垃圾回收被称作“混合式”是因为他们不仅仅进行正常的新生代垃圾收集，同时也回收部分后台扫描线程标记的分区。混合式垃圾收集如下图：

混合式GC也是采用的复制的清理策略，当GC完成后，会重新释放空间。

至此，混合式GC告一段落了。下一小节我们讲进入调优实践。

MaxGCPauseMillis调优

前面介绍过使用GC的最基本的参数：

前面2个参数都好理解，后面这个MaxGCPauseMillis参数该怎么配置呢？这个参数从字面的意思上看，就是允许的GC最大的暂停时间。G1尽量确保每次GC暂停的时间都在设置的MaxGCPauseMillis范围内。 那G1是如何做到最大暂停时间的呢？这涉及到另一个概念，CSet(collection set)。它的意思是在一次垃圾收集器中被收集的区域集合。

Young GC：选定所有新生代里的region。通过控制新生代的region个数来控制young GC的开销。

Mixed GC：选定所有新生代里的region，外加根据global concurrent marking统计得出收集收益高的若干老年代region。在用户指定的开销目标范围内尽可能选择收益高的老年代region。

在理解了这些后，我们再设置最大暂停时间就好办了。 首先，我们能容忍的最大暂停时间是有一个限度的，我们需要在这个限度范围内设置。但是应该设置的值是多少呢？我们需要在吞吐量跟MaxGCPauseMillis之间做一个平衡。如果MaxGCPauseMillis设置的过小，那么GC就会频繁，吞吐量就会下降。如果MaxGCPauseMillis设置的过大，应用程序暂停时间就会变长。G1的默认暂停时间是200毫秒，我们可以从这里入手，调整合适的时间。

其他调优参数

避免使用以下参数：

避免使用 -Xmn 选项或 -XX:NewRatio 等其他相关选项显式设置年轻代大小。固定年轻代的大小会覆盖暂停时间目标。

触发Full GC

在某些情况下，G1触发了Full GC，这时G1会退化使用Serial收集器来完成垃圾的清理工作，它仅仅使用单线程来完成GC工作，GC暂停时间将达到秒级别的。整个应用处于假死状态，不能处理任何请求，我们的程序当然不希望看到这些。那么发生Full GC的情况有哪些呢？

并发模式失败

G1启动标记周期，但在Mix GC之前，老年代就被填满，这时候G1会放弃标记周期。这种情形下，需要增加堆大小，或者调整周期（例如增加线程数-XX:ConcGCThreads等）。

晋升失败或者疏散失败

G1在进行GC的时候没有足够的内存供存活对象或晋升对象使用，由此触发了Full GC。可以在日志中看到(to-space exhausted)或者（to-space overflow）。解决这种问题的方式是：

巨型对象分配失败

当巨型对象找不到合适的空间进行分配时，就会启动Full GC，来释放空间。这种情况下，应该避免分配大量的巨型对象，增加内存或者增大-XX:G1HeapRegionSize，使巨型对象不再是巨型对象。

由于篇幅有限，G1还有很多调优实践，在此就不一一列出了，大家在平常的实践中可以慢慢探索。最后，期待java 9能正式发布，默认使用G1为垃圾收集器的java性能会不会又提高呢？

G1处理和传统的垃圾收集策略是不同的，关键的因素是它将所有的内存进行了子区域的划分。

总结

G1是一款非常优秀的垃圾收集器，不仅适合堆内存大的应用，同时也简化了调优的工作。通过主要的参数初始和最大堆空间、以及最大容忍的GC暂停目标，就能得到不错的性能；同时，我们也看到G1对内存空间的浪费较高，但通过**首先收集尽可能多的垃圾(Garbage First)的设计原则，可以及时发现过期对象，从而让内存占用处于合理的水平。

参考链接：

https://juejin.cn/post/6859931488352370702

https://blog.csdn.net/qq_39276448/article/details/104470796

Garbage First(简称G1)收集器是垃圾收集器技术发展史上里程碑式的成果，它开创了收集器面向局部收集的设计思路和基于Region的内存布局形式。

作为CMS收集器的替代者和继承人，设计者们希望做出一款能够建立起“停顿时间模型”的收集器，停顿时间模型的意思是能够支持指定在一个长度为M毫秒的时间片段内，消耗在垃圾收集上的时间大概率不超过N秒这样的目标。

G1的里程碑意义来源于其面向局部收集的设计思路和基于Region的内存布局形式，这也是G1实现其停顿时间模型的底气。在G1收集器出现之前的所有其他收集器，包括被它所替代的CMS，垃圾收集的目标范围都是整个新生代（Minor GC）或整个老年代（Major GC），亦或者是整个Java堆（Full GC）。而G1实现了可以面向堆内存的任何部分来组成回收集。衡量标准不再是分代，而是回收的实际收益，这就是Mixed GC模式。

G1基于Region的堆内存布局是它实现Mixed GC的关键。我们不能说G1摈弃了分代理论，相反，G1依然是依据分代理论设计的，但其堆内存布局与其他收集器有非常明显的差异，它不再坚持固定大小以及固定数量的分代区域划分，而是把堆分成多个大小相等的独立区域，称为Region，而每个Region都可能是新生代或老年代。这样无论是针对哪种对象，都可以有比较好的收集效果。

从上图中我们可以看见，Region中还有一种Humongous区域，它专门用来存储大对象。G1认为一个对象的大小超过了一个Region的一半，那就可以称为大对象。如果对象大小超过一个Region，就存储在连续的多个Region当中。另外值得注意的是，G1的大部分行为都把Humongous Region作为老年代的一部分来看待。

G1之所以能够建立起可预测的停顿时间模型，是因为它将Region作为单次回收的最小单元。G1收集器会跟踪每个Region中垃圾总的“价值”大小，即回收所获得的空间大小和回收所需时间的经验值，然后在后台维护一个优先级列表。并可以根据用户的设定回收价值收益最大的Region。这也是“Garbage First”其名的由来。

G1收集器作为一款跨时代的收集器，它从发表论文到商用经历了超过十年的研发，其中解决了无数的问题，以下是三个典型且重要的问题向读者说明。

和其他收集器解决跨代问题的方法一样，G1使用记忆集从而避免全堆作为GC Roots扫描。但不同的是G1的每个Region都维护属于自己的记忆集，它们会记录下别的Region指向自己的指针，并标记这些指针分别在哪些卡页的范围内。G1的记忆集在存储结构的本质上是哈希表（key是别的Region的起始地址，Value是卡表索引号的集合）。

由于Region的数量较多，而每个Region都有自己的记忆集，所以G1收集器要花费更大的内存来维持工作，这个数通常是Java堆的10%~20%。

首先，用户线程改变对象引用关系时，必须保证不打破原本的对象图结构，导致标记结果出现错误。CMS对这个问题采取了增量更新的算法进行解决，而G1选择了原始快照(SATB)的方法进行解决。

其次，回收过程中会有新对象需要进行内存分配。G1为每个Region设置了两个名为TAMS的指针，把Region的一部分空间用于并发回收过程中的新对象分配。新对象的地址必须在这两个指针之上。这部分空间被收集器视为默认存货， 不纳入回收范围。

G1收集器的停顿预测模型是以衰减均值作为理论基础来实现的。在垃圾收集过程中，G1收集器会记录每个Region的回收时间、记忆集中的脏卡数量等各个步骤的成本，并按照一定的统计信息和统计算法得出“衰减平均值”。衰减平均值更准确地代表了最近的平均状态，Region的统计状态越新就越能决定回收的价值。

根据这些信息，收集器可以决定应当找出哪些Region进入回收集，最终在不超过期望时间的前提下获得最高收益。

标记一下GC Roots能直接关联到的对象。并且修改TAMS的值，让并发标记阶段分配对象有据可依。这个阶段需要停顿线程，但耗时很短，并且在Minor GC时同步完成。

从GC Root中开始对堆中对象进行可达性分析，扫描对象图，找出要回收的对象，这阶段耗时长但是可以和用户程序并发执行。当对象图扫描完成后，还要重新处理SATB记录下的在并发时有引用变动的对象。

对用户线程做一个短暂的暂停，用于处理并发阶段结束后仍遗留下来的最后那些少量的SATB记录。

负责更新Region的统计数据，对各个Region的回收价值和成本进行排序，制定具体的回收计划。可以自由地选择多个Region作为回收集，把其中存活的对象复制到空的Region中，再清理掉整个回收集。由于涉及存活对象的移动，所以必须暂停用户线程。

总之，G1收集器的设计目标是在延迟可控的前提下获得尽可能高的吞吐量。

作为两款关注停顿时间的收集器，G1常被作为CMS收集器的比较对象。在今天，G1已经几乎完全取代了CMS的地位，但这并不意味着CMS在G1面前不值一提。

先说明一个事实：在小内存上CMS的表现可能会优于G1，而大内存上G1毫无疑问会占据优势。这个堆内存大小的平衡点通常在6~8GB左右。

指定最大停顿时间、分Region的内存布局、按收益确定最终回收集，这些都是G1的新设计给它带来的相对于CMS的优势。

CMS集于标记-清除算法进行收集，而G1从整体看集于标记-整理算法进行收集，局部看基于标记-复制算法进行收集。显然，G1的两种解读方法都意味着它不会产生任何内存碎片。这样的特性有利于程序长久地平稳运行。

我们前文中提到，G1收集器为每一个Region都提供了卡表作为记忆集，显然这意味着G1相比CMS需要消耗更大量的内存来完成其本职工作。相比之下CMS的卡表仅有一份且实现简单。

CMS使用写后屏障来更新和维护卡表。G1除了使用写后屏障，为了实现快照搜索算法，它还得使用写前屏障来跟踪并发时的指针变化情况。这也引出了原始快照和增量更新两种方法的比较：原始快照能够减少并发标记和重新标记阶段的损耗，避免在标记阶段停顿时间过长，但它同时也会产生由于跟踪引用变化带来的额外负担。

由于G1写屏障的复杂 *** 作要比CMS消耗更多的运算资源，CMS的写屏障实现是直接的同步 *** 作，而G1必须把它实现为类似消息队列的架构，即把写前屏障和写后屏障要做的事都放到队列里，然后异步处理。

---