cms垃圾回收算法

㈠ JVM垃圾回收的“三色标记算法”实现，内容太干

三色标记法是一种垃圾回收法，它可以让JVM不发生或仅短时间发生STW(Stop The World)，从而达到清除JVM内存垃圾的目的。JVM中的 CMS、G1垃圾回收器 所使用垃圾回收算法即为三色标记法。

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

白色 ：该对象没有被标记过。（对象垃圾）

灰色 ：该对象已经被标记过了，但该对象下的属性没有全被标记完。（GC需要从此对象中去寻找垃圾）

黑色 ：该对象已经被标记过了，且该对象下的属性也全部都被标记过了。（程序所需要的对象）

从我们main方法的根对象（JVM中称为GC Root）开始沿着他们的对象向下查找，用黑灰白的规则，标记出所有跟GC Root相连接的对象,扫描一遍结束后，一般需要进行一次短暂的STW(Stop The World)，再次进行扫描，此时因为黑色对象的属性都也已经被标记过了，所以只需找出灰色对象并顺着继续往下标记（且因为大部分的标记工作已经在第一次并发的时候发生了，所以灰色对象数量会很少，标记时间也会短很多）, 此时程序继续执行，GC线程扫描所有的内存，找出扫描之后依旧被标记为白色的对象（垃圾）,清除。

具体流程:

在JVM虚拟机中有两种常见垃圾回收器使用了该算法：CMS(Concurrent Mark Sweep)、G1(Garbage First) ，为了解决三色标记法对对象漏标问题各自有各自的法:

CMS(Concurrent Mark Sweep)收集器是一种以获取最短回收停顿时间为目标的收集器。目前很大一部分的Java应用集中在互联网网站或者基于浏览器的B/S系统的服务端上，这类应用通常都会较为关注服务的响应速度，希望系统停顿时间尽可能短，以给用户带来良好的交互体验。CMS收集器就非常符合这类应用的需求(但是实际由于某些问题,很少有使用CMS作为主要垃圾回收器的)。

从名字（包含“Mark Sweep”）上就可以看出CMS收集器是基于标记-清除算法实现的，它的运作过程相对于前面几种收集器来说要更复杂一些，整个过程分为四个步骤，包括：1）初始标记（CMS initial mark） 2）并发标记（CMS concurrent mark） 3）重新标记（CMS remark） 4）并发清除（CMS concurrent sweep）

其中初始标记、重新标记这两个步骤仍然需要“Stop The World”。初始标记仅仅只是标记一下GCRoots能直接关联到的对象，速度很快；

并发标记阶段就是从GC Roots的直接关联对象开始遍历整个对象图的过程，这个过程耗时较长但是不需要停顿用户线程，可以与垃圾收集线程一起并发运行；

重新标记阶段则是为了修正并发标记期间，因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录，这个阶段的停顿时间通常会比初始标记阶段稍长一些，但也远比并发标记阶段的时间短；

最后是并发清除阶段，清理删除掉标记阶段判断的已经死亡的对象，由于不需要移动存活对象，所以这个阶段也是可以与用户线程同时并发的。由于在整个过程中耗时最长的并发标记和并发清除阶段中，垃圾收集器线程都可以与用户线程一起工作，所以从总体上来说，CMS收集器的内存回收过程是与用户线程一起并发执行的。

在应对漏标问题时，CMS使用了增量更新(Increment Update)方法来做：

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

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

G1(Garbage First)物理内存不再分代，而是由一块一块的Region组成,但是逻辑分代仍然存在。G1不再坚持固定大小以及固定数量的分代区域划分，而是把连续的Java堆划分为多个大小相等的独立区域（Region），每一个Region都可以根据需要，扮演新生代的Eden空间、Survivor空间，或者老年代空间。收集器能够对扮演不同角色的Region采用不同的策略去处理，这样无论是新创建的对象还是已经存活了一段时间、熬过多次收集的旧对象都能获取很好的收集效果。

Region中还有一类特殊的Humongous区域，专门用来存储大对象。G1认为只要大小超过了一个Region容量一半的对象即可判定为大对象。每个Region的大小可以通过参数-XX：G1HeapRegionSize设定，取值范围为1MB～32MB，且应为2的N次幂。而对于那些超过了整个Region容量的超级大对象，将会被存放在N个连续的Humongous Region之中，G1的大多数行为都把Humongous Region作为老年代的一部分来进行看待，如图所示

Card Table（多种垃圾回收器均具备）

RSet(Remembered Set)

是辅助GC过程的一种结构，典型的空间换时间工具，和Card Table有些类似。

后面说到的CSet(Collection Set)也是辅助GC的，它记录了GC要收集的Region集合，集合里的Region可以是任意年代的。

在GC的时候，对于old->young和old->old的跨代对象引用，只要扫描对应的CSet中的RSet即可。逻辑上说每个Region都有一个RSet，RSet记录了其他Region中的对象引用本Region中对象的关系，属于points-into结构（谁引用了我的对象）。

而Card Table则是一种points-out（我引用了谁的对象）的结构，每个Card 覆盖一定范围的Heap（一般为512Bytes）。G1的RSet是在Card Table的基础上实现的：每个Region会记录下别的Region有指向自己的指针，并标记这些指针分别在哪些Card的范围内。这个RSet其实是一个Hash Table，Key是别的Region的起始地址，Value是一个集合，里面的元素是Card Table的Index。每个Region中都有一个RSet，记录其他Region到本Region的引用信息；使得垃圾回收器不需要扫描整个堆找到谁引用当前分区中的对象，只需要扫描RSet即可。

CSet(Collection Set)

一组可被回收的分区Region的集合, 是多个对象的集合内存区域。

新生代与老年代的比例

5% - 60%，一般不使用手工指定，因为这是G1预测停顿时间的基准,这地方简要说明一下,G1可以指定一个预期的停顿时间,然后G1会根据你设定的时间来动态调整年轻代的比例,例如时间长,就将年轻代比例调小,让YGC尽早行。

SATB(Snapshot At The Beginning), 在应对漏标问题时，G1使用了SATB方法来做,具体流程：

因为SATB在重新标记环节只需要去重新扫描那些被推到堆栈中的引用，并配合Rset来判断当前对象是否被引用来进行回收；

并且在最后G1并不会选择回收所有垃圾对象，而是根据Region的垃圾多少来判断与预估回收价值（指回收的垃圾与回收的STW时间的一个预估值），将一个或者多个Region放到CSet中，最后将这些Region中的存活对象压缩并复制到新的Region中，清空原来的Region。

会，当内存满了的时候就会进行Full GC；且JDK10之前的Full GC，为单线程的，所以使用G1需要避免Full GC的产生。

解决方案：

㈡ CMS 和G1 的区别

CMS收集器是老年代的收集器，可以配合新生代的Serial和ParNew收集器一起使用
G1收集器收集范围是老年代和新生代。不需要结合其他收集器使用

CMS收集器以最小的停顿时间为目标的收集器。

G1收集器可预测垃圾回收的停顿时间（建立可预测的停顿时间模型）

CMS收集器是使用“标记-清除”算法进行的垃圾回收，容易产生内存碎片

G1收集器使用的是“标记-整理”算法，进行了空间整合，降低了内存空间碎片。

初始标记
并发标记
重新标记
并发清理

初始标记阶段：会让线程全部停止，也就是 Stop the World 状态
并发标记阶段：对所有的对象进行追踪，这个阶段最耗费时。但这个阶段是和系统并发运行的，所以不会对系统运行造成影响
重新标记阶段：由于第二阶段是并发执行的，一边标记垃圾对象，一边创建新对象，老对象会变成垃圾对象。 所以第三阶段也会进入 Stop the World 状态，并且重新标记，标记的是第二阶段中变动过的少数对象，所以运行速度很快
并发清理阶段： 这个阶段也是会耗费很多时间，但由于是并发运行的，所以对系统不会造成很大的影响

CMS采用 标记-清理 的算法，标记出垃圾对象，清除垃圾对象。算法是基于老年代执行的，因为新生代产生无法接受该算法产生的碎片垃圾。

优点 ：并发收集，低停顿

不足 ：

G1的出现就是为了替换jdk1.5种出现的CMS,这一点已经在jdk9的时候实现了，jdk9默认使用了G1回收器，移除了所有CMS相关的内容。G1和CMS相比，有几个特点：

G1把Java内存拆分成多等份，多个域（Region），逻辑上存在新生代和老年代的概念，但是没有严格区分

贴图感受一下：

依旧存在新生代老年代的概念，但是没有严格区分。Region最多分为2048个

除了上面优点之外，还有一个优点，那就是对大对象的处理。在CMS内存中，如果一个对象过大，进入S1、S2区域的时候大于改分配的区域，对象会直接进入老年代。G1处理大对象时会判断对象是否大于一个Region大小的50%，如果大于50%就会横跨多个Region进行存放

初始标记： 标记GC Roots 可以直接关联的对象，该阶段需要线程停顿但是耗时短

并发标记： 寻找存活的对象，可以与其他程序并发执行，耗时较长

最终标记： 并发标记期间用户程序会导致标记记录产生变动（好比一个阿姨一边清理垃圾，另一个人一边扔垃圾）虚拟机会将这段时间的变化记录在Remembered Set Logs 中。最终标记阶段会向Remembered Set合并并发标记阶段的变化。这个阶段需要线程停顿，也可以并发执行

筛选回收： 对每个Region的回收成本进行排序，按照用户自定义的回收时间来制定回收计划

参考官方文档：

控制G1回收垃圾的时间

-XX:MaxGCPauseMillis=200 （默认200ms）