JVM垃圾回收之三⾊标记
三⾊标记法是⼀种垃圾回收法，它可以让JVM不发⽣或仅短时间发⽣STW(Stop The World)，从⽽达到清除JVM内存垃圾的⽬的。JVM中的CMS、G1垃圾回收器所使⽤垃圾回收
算法即为三⾊标记法。
三⾊标记算法思想
三⾊标记法将对象的颜⾊分为了⿊、灰、⽩，三种颜⾊。
⽩⾊：该对象没有被标记过。（对象垃圾）
灰⾊：该对象已经被标记过了，但该对象下的属性没有全被标记完。（GC需要从此对象中去寻垃圾）
⿊⾊：该对象已经被标记过了，且该对象下的属性也全部都被标记过了。（程序所需要的对象）
算法流程
从我们main⽅法的根对象（JVM中称为GC Root）开始沿着他们的对象向下查，⽤⿊灰⽩的规则，标记出所有跟GC Root相连接的对象，扫描⼀遍结束后，⼀般需要进⾏⼀次短暂的STW(Stop The World)，再次进⾏扫描，此时因为⿊⾊对象的属性都也已经被标记过了，所以只需出灰⾊对象并顺着继续往下标记（且因为⼤部分的标记⼯作已经在第⼀次并发的时候发⽣了，所以灰⾊对象数量会很少，标记时间也会短很多）, 此时程序继续执⾏，GC线程扫描所有的内存，出扫描之后依旧被标记为⽩⾊的对象（垃圾），清除。
具体流程:
⾸先创建三个集合：⽩、灰、⿊。
将所有对象放⼊⽩⾊集合中。
然后从根节点开始遍历所有对象（注意这⾥并不递归遍历），把遍历到的对象从⽩⾊集合放⼊灰⾊集合。
之后遍历灰⾊集合，将灰⾊对象引⽤的对象从⽩⾊集合放⼊灰⾊集合，之后将此灰⾊对象放⼊⿊⾊集合
重复 4 直到灰⾊中⽆任何对象
通过write-barrier检测对象有变化，重复以上操作
收集所有⽩⾊对象（垃圾）
三⾊标记存在问题
浮动垃圾：并发标记的过程中，若⼀个已经被标记成⿊⾊或者灰⾊的对象，突然变成了垃圾，由于不会再对⿊⾊标记过的对象重新扫描，所以不会被发现，那么这个对象不是⽩⾊的但是不会被清除，重新标记也不能从GC Root中去到，所以成为了浮动垃圾，浮动垃圾对系统的影响不⼤，留给下⼀次GC进⾏处理即可。
对象漏标问题（需要的对象被回收）：并发标记的过程中，⼀个业务线程将⼀个未被扫描过的⽩⾊对象断开引⽤成为垃圾（删除引⽤），同时⿊⾊对象引⽤了该对象（增加引⽤）（这两部可以不分先后顺序）；因为⿊⾊对象的含义为其属性都已经被标记过了，重新标记也不会从⿊⾊对象中去，导致该对象被程序所需要，却⼜要被GC回收，此问题会导致系统出现问题，⽽CMS与G1，两种回收器在使⽤三⾊标记法时，都采取了⼀些措施来应对这些问题，CMS对增加引⽤环节进⾏处理（Increment Update），G1则对删除引⽤环节进⾏处理(SATB)。解决办法
在JVM虚拟机中有两种常见垃圾回收器使⽤了该算法：CMS(Concurrent Mark Sweep)、G1(Garbage First) ，为了解决三⾊标记法对对象漏标问题各⾃有各⾃的法:
CMS回顾
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解决办法：增量更新
在应对漏标问题时，CMS使⽤了增量更新(Increment Update)⽅法来做：
在⼀个未被标记的对象（⽩⾊对象）被重新引⽤后，引⽤它的对象若为⿊⾊则要变成灰⾊，在下次⼆次标记时让GC线程继续标记它的属性对象。
但是就算时这样，其仍然是存在漏标的问题：
在⼀个灰⾊对象正在被⼀个GC线程回收时，当它已经被标记过的属性指向了⼀个⽩⾊对象（垃圾）
⽽这个对象的属性对象本⾝还未全部标记结束，则为灰⾊不变
⽽这个GC线程在标记完最后⼀个属性后，认为已经将所有的属性标记结束了，将这个灰⾊对象标记为⿊⾊，被重新引⽤的⽩⾊对象，⽆法被标记
CMS另两个致命缺陷
CMS采⽤了Mark-Sweep算法，最后会产⽣许多内存碎⽚，当到⼀定数量时，CMS⽆法清理这些碎⽚了，CMS会让Serial Old垃圾处理器来清理这些垃圾碎⽚，⽽Serial Old垃圾处理器是单线程操作进⾏清理垃圾的，效率很低。
所以使⽤CMS就会出现⼀种情况，硬件升级了，却越来越卡顿，其原因就是因为进⾏Serial Old GC时，效率过低。
解决⽅案：使⽤Mark-Sweep-Compact算法，减少垃圾碎⽚
调优参数（配套使⽤）：
-XX:+UseCMSCompactAtFullCollection  开启CMS的压缩
-XX:CMSFullGCsBeforeCompaction 默认为0，指经过多少次CMS FullGC才进⾏压缩jvm调优参数
当JVM认为内存不够，再使⽤CMS进⾏并发清理内存可能会发⽣OOM的问题，⽽不得不进⾏Serial Old GC，Serial Old是单线程垃圾回收，效率低
解决⽅案：降低触发CMS GC的阈值，让浮动垃圾不那么容易占满⽼年代
调优参数：
-XX:CMSInitiatingOccupancyFraction 92% 可以降低这个值，让⽼年代占⽤率达到该值就进⾏CMS GC
G1回顾
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作为⽼年代的⼀部分来进⾏看待，如图所⽰
G1前置知识
Card Table（多种垃圾回收器均具备）
由于在进⾏YoungGC时，我们在进⾏对⼀个对象是否被引⽤的过程，需要扫描整个Old区，所以JVM设计了CardTable，将Old区分为⼀个⼀个Card，⼀个Card有多个对象；如果⼀个Card中的对象有引⽤指向Young区，则将其标记为Dirty Card，下次需要进⾏YoungGC时，只需要去扫描Dirty Card即可。
Card Table 在底层数据结构以 Bit Map实现。
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尽早⾏。
G1解决办法:SATB
SATB(Snapshot At The Beginning), 在应对漏标问题时，G1使⽤了SATB⽅法来做，具体流程：
在开始标记的时候⽣成⼀个快照图标记存活对象
在⼀个引⽤断开后，要将此引⽤推到GC的堆栈⾥，保证⽩⾊对象（垃圾）还能被GC线程扫描到(在write barrier(写屏障)⾥把所有旧的引⽤所指向的对象都变成⾮⽩的)。
配合Rset，去扫描哪些Region引⽤到当前的⽩⾊对象，若没有引⽤到当前对象，则回收
SATB详细流程
SATB是维持并发GC的⼀种⼿段。G1并发的基础就是SATB。SATB可以理解成在GC开始之前对堆内存⾥的对象做⼀次快照，此时活的对像就认为是活的，从⽽开成⼀个对象图。
在GC收集的时候，新⽣代的对象也认为是活的对象，除此之外其他不可达的对象都认为是垃圾对象。
如何到在GC过程中分配的对象呢？每个region记录着两个top-at-mark-start(TAMS)指针，分别为prevTAMS和nextTAMS。在TAMS以上的对象就是新分配的，因⽽被视为隐式marked。
通过这种⽅式我们就到了在GC过程中新分配的对象，并把这些对象认为是活的对象。
解决了对象在GC过程中分配的问题，那么在GC过程中引⽤发⽣变化的问题怎么解决呢？
G1给出的解决办法是通过Write Barrier。Write Barrier就是对引⽤字段进⾏赋值做了额外处理。通过Write Barrier就可以了解到哪些引⽤对象发⽣了什么样的变化。
mark的过程就是遍历heap标记live object的过程，采⽤的是三⾊标记算法，这三种颜⾊为white（表⽰还未访问到）、gray（访问到但是它⽤到的引⽤还没有完全扫描）、back（访问到⽽且其⽤到的引⽤已经完全扫描完）。
整个三⾊标记算法就是从GC roots出发遍历heap，针对可达对象先标记white为gray，然后再标记gray为black；遍历完成之后所有可达对象都是balck 的，所有white都是可以回收的。
SATB仅仅对于在marking开始阶段进⾏“snapshot”(marked all reachable at mark start)，但是concurrent的时候并发修改可能造成对象漏标记。
对black新引⽤了⼀个white对象，然后⼜从gray对象中删除了对该white对象的引⽤，这样会造成了该white对象漏标记。
对black新引⽤了⼀个white对象，然后从gray对象删了⼀个引⽤该white对象的white对象，这样也会造成了该white对象漏标记。
对black新引⽤了⼀个刚new出来的white对象，没有其他gray对象引⽤该white对象，这样也会造成了该white对象漏标记。
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%）
站在巨⼈的肩膀上