一、判断对象是否存活的算法：

1.1遍历算法

可达性分析算法(根搜索算法)：

概念：

• 从根节点开始向下搜索，搜索所走过的路径称为引用链，当一个对象与根节点之间不存在任何引用链时，则证明此对象是不可用的。

根对象的判定：

• 虚拟机栈(栈帧中的本地变量表)中引用的对象、本地方法栈中JNI(即native方法)引用的对象。

• 方法区中：类静态属性引用的对象、常量引用的对象。

• 引用java中对象的可达性 && 弱引用简介_A__17的博客-CSDN博客

引用计数算法：

• 概念：给对象添加一个引用计数器，每当有一个地方引用它时，计数器就加1；当引用失效时，计数器就减1；当计数器为0时，对象就不能再使用了。

• 说明：Java虚拟机里面没有采用 引用计数算法 来管理内存。原因：不能解决对象之间相互循环引用的问题

1.2 标记算法

三色标记法(Tri-color Marking)：

说明：相对复杂，了解概念即可，不要纠结细节！

概念：

遍历对象图时按照“对象是否被访问过”这个条件，将对象标记为三种颜色：

• 白色：表示对象尚未被垃圾收集器访问过。

  • 显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。

• 灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

• 黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。

  • 黑色的对象代表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。

  • 黑色对象不可能（不经过灰色对象）直接指向某个白色对象。

过程：

1. 在 GC 并发开始的时候，所有的对象均为白色；

2. 在将所有的 GC Roots 直接引用的对象标记为灰色集合；

3. 如果判断灰色集合中的对象不存在子引用，则将其放入黑色集合，若存在子引用对象，则将其所有的子引用对象存放到灰色集合，当前对象放入灰色集合

4. 按照此步骤 3 ，依此类推，直至灰色集合中所有的对象变黑后，本轮标记完成，并且在白色集合内的对象称为不可达对象，即垃圾对象。

5. 标记结束后，为白色的对象为 GC Roots 不可达，可以进行垃圾回收。

对象的误标和漏标：

• 三色标记的过程中，标记线程和用户线程是并发执行的，那么就有可能在我们标记过程中，用户线程修改了引用关系，导致某个对象被误标或漏标。

误标

• 概念：把原本应该回收的对象错误标记成了存活。

• 场景：已经被GC线程标黑的对象被用户线程将其从引用链上删掉，这样导致本应该被回收的对象却被标记为黑色(存活的对象)，这个对象我们称之为浮动垃圾(float garbage)。

• 浮动垃圾的处理：

  • 本次GC中不会回收浮动垃圾，这些浮动垃圾只能等到下次GC时再去回收。

漏标

• 概念：把本来应该存活的垃圾，标记为了死亡。这就会导致非常严重的错误。

• 场景：

• 当对象A被标记为了黑色，对象A所引用的两个对象B,C都被标记为灰色。

• 若此时用户线程把B->D之间的的引用关系删除，并且在A->D之间建立引用。

• 此时B对象还未扫描结束，而A对象又已经被扫描过了，不会继续接着往下扫描了，导致D对象永远不会被标记(为灰色或黑色)，最终D对象会被当做垃圾回收掉。

• 漏标的2个必要条件：

  • 赋值器插入了一条或者多条黑色对象到白色对象的引用。

  • 赋值器删除了全部从灰色对象到白色对象的直接引用或者间接引用。

1.3对象漏标的解决：

• 要解决误标的问题，只需要破坏这两个条件中的任意一种即可，分别有两种解决方案：

增量更新(Incremental Update)

原理：

• 抽象解释：增量更新要破坏的是第一个条件，可以简化理解为：增量更新方案关注引用的增加，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了，后续还可以再进行扫描。

• 具体实现：当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。

应用

• CMS收集器采用增量更新的方式来解决对象漏标的问题：

  • 在并发标记阶段：将这些引用发生变化的对象（包括新进入老年代的对象）所在的Card标记为Dirty Card。

  • 在并发预清理阶段和可中断的并发预清理阶段：从Dirty Card中包含的对象开始，沿着引用链往下检索(RootsTracing)，标记出引用链上所有老年代中存活的对象。

初始快照-SATB(snapshot-at-the-beginning)

原理：

• 抽象解释：原始快照要破坏的是第二个条件，可以简化理解为：无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行扫描。

• 具体实现：

  • 在标记周期开始时，将堆中存活对象的集合做一个快照。之后在整个GC的过程中只要某个对象在快照内，则该对象就被认定的是存活的，即使该对象的引用稍后被修改或者删除。同时新分配的对象也会被认为是活的。

  • 除此之外其它不可达的对象就被认为是死掉了。

  • 当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。

• 初始快照和增量更新的对比：

  • 增量更新关注的是黑色对象指向白色对象引用的增加，将这些增加的引用记录下来后续再进行扫描。

  • 初始快照关注的是灰色对象指向白色对象引用的删除，将这些删除的引用记录下来后续再进行扫描。

• 说明：

  • STAB保证了真正存活的对象不会被GC误回收，但同时也造成了某些可以被回收的对象逃过了GC，导致了内存里面存在浮动的垃圾。

应用：

G1收集器就是采用初始快照的方式来解决对象漏标的问题。

• 在标记周期开始时，将堆中存活对象的集合做一个快照，存活对象的包括：

  • 根据root tracing中扫描到的对象。

  • 新分配的对象。

  • 并发阶段变化的对象（由于并发阶段应用线程和gc线程同时进行，故引用关系可能会发生变化）。

• 之后每当对象的引用关系发生变化时，G1通过写屏障(pre-write barrier)把变化的引用关系记录在一个队列中，然后在最终标记阶段扫描这个队列，通过这种方式，旧的引用所指向的对象就会被标记上，其子孙也会被递归标记上，这样就不会漏标记任何存活的对象，存活对象快照的正确性也就得到了保证。

• G1 GC uses the snapshot-at-the-beginning (SATB) algorithm, which logically takes a snapshot of the set of live objects in the heap at the start of a marking cycle. The set of live objects also includes objects allocated since the start of the marking cycle. The G1 GC marking algorithm uses a pre-write barrier to record and mark objects that are part of the logical snapshot.

• 官方文档：https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/g1_gc_tuning.html

G1和CMS处理对象漏标方案的对比：

• CMS采用增量更新的方案，G1采用初始快照的方案。

• 在重新标记(remark)阶段扫描的范围不同：

  • CMS在重新标记(remark)阶段需要重新扫描所有的线程栈和年轻代作为GC roots。

  • G1在重新标记(remark)阶段只需要扫描 引用关系发生过变化的对象集合。

1.4一个对象被回收要经过两次标记：

第一次标记：

如果一个对象在进行可达性分析后没有发现与根对象间存在引用链，那么这个对象将被第一次标记，并进行判断：判断此对象是否有必要去执行finalize()方法。

• 若对象没有覆盖finalize()方法，或者finalize()方法已经被调用过了，虚拟机就不会执行该对象的finalize()方法，直接回收该对象。

• 若对象覆盖了finalize()方法，并且finalize()方法没有被调用过，那么：

  • 这个对象将会放置在一个叫做F-Queue 的队列中，稍后(在第二次标记之前)，会有一个由虚拟机自动建立的、低优先级的Finalizer线程去执行该对象的finalize()方法。

  • 注意：这里的“执行”是指虚拟机会触发这个方法，但是并不保证会等待这个方法运行结束。原因：如果某个对象执行finalize()方法花费的时间比较长，或者发生了死循环，这样的话就很可能会导致F-Queue队列中其它的对象永久等待，如果JVM要等待它运行结束，则有可能会导致整个内存回收系统崩溃。

第二次标记：

在第一次标记后，GC将对 F-Queue 中的对象进行第二次标记，如果对象在finalize()方法中成功拯救自己,那么这个对象将被移出”即将回收“的那个集合。

• 如果没有在finalize()方法中救出自己，那么它将被GC回收。

• 注：在finalize()方法中拯救自己的方法：只要重新与引用链上的任何一个对象建立关联即可。例如：将自己(this)赋值给某个对象的成员变量。

二、跨代引用对象的标记

跨代引用

场景：

• 年轻代的对象持有着老年代对象的引用、老年代的对象持有着年轻代对象的引用

特点：

• 互相引用的两个对象几乎总是同生共死：

  • 如果某个新生代对象存在跨代引用，由于老年代对象难以消亡，该引用会使得新生对象在minor gc时得以存活，该对象经历多次minor gc后晋升到老年代，此时跨代引用自然也随着该对象的晋升而消失了。

• 因此，存在跨代引用的对象较少。

跨代引用带来的问题：

• 年轻代对象引用老年代对象：minor gc时需要扫描老年代。

• 老年代对象引用年轻代对象：major gc时需要扫描年轻代。

解决方案：

• 通过降低扫描对象的范围或数量来降低gc的耗时：

  • 年轻代对象引用老年代对象：借助 卡表/记忆集合 来减小minor gc时扫描老年代的范围，进而降低minor gc的时间。

  • 老年代对象引用年轻代对象：

    • CMS收集器：借助 提前触发minor gc 来减少年轻代中对象的数量，进而降低major gc的时间。

    • G1收集器：借助 记忆集合 来减少老年代gc时扫描年轻代的范围，进而降低minor gc的时间。

卡表

数据结构：

• 卡表：jvm将老年代划分为若干个大小为512字节的区域(card)，并使用一个 字节(byte)数组 来标记老年代中这些区域(card)中的对象是否持有新生代对象的引用。jvm将这个 字节数组 称为卡表(card table)。

• 卡表中的元素：表示老年代中某块区域(card)中的对象是否持有新生代对象的引用。

• 卡表属于points-out(我引用了谁的对象)的结构。

说明：之所以使用byte数组而不是bit数组主要是速度上的考量，现代计算机硬件都是最小按字节寻址的，没有直接存储一个bit指令，所以要用bit的话就不得不多消耗几条shift+mask指令。

原理：

• 当老年代中的某个对象持有了新生代对象的引用时，jvm将卡表中表示该对象所在区域(card)的元素设为1，表示该对象所在区域(card)是一个 dirty card。（注意：新生代对象引用老年代对象时，老年代对象所在的区域(card)不会被标记为dirty card）。

• 年轻代gc时只扫描dirty card中的对象，而无需扫描整个老年代中的对象，从而减少年轻代gc的停顿时间。

• 当完成所有脏卡的扫描之后，jvm便会将所有脏卡的标识位清零。

card标记为dirty card的原理

写屏障：

• 写屏障是一小段将card标记为dirty card的代码：检查对象的引用变更时是否出现了跨代引用(g1是跨region引用)，如果出现，这将对应的card标记为dirty card。

Hotspot VM的字节码解释器和JIT编译器使用写屏障维护卡表：

• 解释器每次执行更新引用的字节码时，都会执行一段写屏障。

• JIT编译器在生成更新引用的代码后，也会生成一段写屏障。

• 虽然写屏障使得应用线程增加了一些性能开销，但是minor gc的效率提高了很多，进而提高了系统的吞吐量。

思考：

minor gc时只扫描dirty card中的对象，并行收集模式下gc线程有多个，那么针对多个dirty card，这些gc线程是如何分工的呢？

步块

数据结构：

• jvm将一定数量(默认是256)的card组成一个更大区域，这个区域称为步块(stride chunk)。

作用：

• 多个gc线程并行收集时，每个线程每次负责扫描一个步块，其中包括：扫描该步块对应的 部分卡表 以及 该步块内dirty card中的对象。

参数：

-XX:+UnlockDiagnosticVMOptions

• 解锁诊断虚拟机参数，否则 XX:ParGCCardsPerStrideChunk 不生效

-XX:ParGCCardsPerStrideChunk

• 设置一个gc线程每次扫描的card数量，默认是256。

• 不能设置的太小：太小会造成老年代stride chunk数量太多，导致gc线程在stride chunk之间切换的开销增加，进而导致gc暂停时间增加。

• 经验值：堆大小为4G时，该值设为2k，具体取值以最终调优结果为准。参考：

  • 蚂蚁消息中间件 (MsgBroker) 在 YGC 优化上的探索 - 知乎

  • 2019-11-15 JVM参数调优推荐 - 云+社区 - 腾讯云

记忆集合

数据结构

• 每个region都维护着一个记忆集合(Remembered Set / Rset)，收集器在标记跨代引用的对象时只需扫描(CSet中region维护的)RSet即可。

• RSet的整体结构是一个哈希表，底层是在卡表的基础上实现的。

  • key：key记录了引用本region中对象的对象所在region的位置。

  • value：是一个集合，其元素是：其它region(由key确定是哪个region)中的对象引用本region中对象的引用及引用所在的卡表位置。

• Rset属于points-into结构(谁引用了我的对象)

RSet、Card和Region的关系

• 每个region被分成了多个card。

• 不同region中的card会相互引用。

• 图示： 

• Region1中的Card中的对象引用了Region2中的Card中的对象，蓝色实线表示的就是points-out的关系，而在Region2的RSet中，记录了Region1的Card，即红色虚线表示的关系，这就是points-into。

• 维系RSet中的引用关系靠post-write barrier和Concurrent refinement threads来维护 。

参考：

从实际案例聊聊Java应用的GC优化 - 美团技术团队

Java Hotspot G1 GC的一些关键技术 - 美团技术团队

JVM 三色标记法与读写屏障 - 掘金