从回收算法理解JVM（一）

提到 JVM 的话大家会想到什么呢？是它的内存区域划分，各种 GC 收集器？又或者是垃圾回收算法？常见的 JVM 参数？

这些问题可能大家已经耳熟能详了。但大家是否有思考过为什么会有多种回收算法，他们分别适应什么样的场景，有什么优劣性质。他们是如何解决跨代引用，如何处理业务线程与 GC 线程的并发等等。本篇文章会从回收算法入手，逐个分析这些问题。

评价/设计一个垃圾回收算法时应该考虑哪些因素？

在谈论垃圾回收算法时，我们通常会从以下几个方面来进行判断（时间复杂度会正影响停顿时长）：

分配的效率
回收的效率
是否产生内存碎片
空间利用率
是否停顿（停顿时长）
时间复杂度
实现的复杂度

如何判断对象是否可回收？

引用计数法
- 统计每一个对象被引用的次数，每引用一次计数加一，取消引用时计数减一（写屏障）。如果为 0，就释放该对象
- 并发场景下，对引用计数的修改需要与对象指针同步，通常需要加锁、或者非常复杂的无锁算法（对象指针和 count 计数都需要原子操作，单变量还好，双变量就会更复杂）
- 连锁式回收问题：原本以为只需要回收 1 个对象，结果关联的引用计数也是 1，减 1 后都变成了 0，导致一次回收很多对象，停顿时间不可控
- 循环引用问题（主要问题）
- 优点：实现简单，能立即回收。一个对象的引用计数归零的那一刻即是它成为垃圾的那一刻，同时也是它被回收的那一刻。
根节点枚举（又称GCRoots）：通过一系列名为 GCRoots 的对象作为起始点，从这个被称为 GCRoots 的对象开始，根据引用关系的图向下搜索，如果一个对象到 GCRoots 没有任何引用链相连时，则说明此对象可回收

JVM 选用的方法是根节点枚举的方式，单说概念的话，会让我们觉得难以理解，哪些对象属于 GCRoots 呢？书中（《深入理解 java 虚拟机》）给我们的定义是：当前正在运行的方法中参数以及局部变量、静态变量、常量，syncronized 的持有者等。（还有跨代引用，后面详细解释）

在下面的图中 for 循环创建了四个对象 MyInst(0)--->MyInst(4)，每一次循环结束，变量 mi 都会指向一个堆中的一个新对象，此时的 mi 就是根对象

jvm 中常见的垃圾回收算法

标记-清除算法 Mark-Sweep

最早，也是最基础的垃圾回收算法，分为标记和清除两个阶段：第一阶段先标记出需要回收的对象，第二阶段将被标记的对象进行统一回收。

使用链表管理空闲内存，分配时从链表中取满足大小的内存，回收时将垃圾对象占用的空间交还给链表（所以这种分配方式也叫做空闲列表）
有内存碎片
总体的空间利用率较高
不需要更改对象的地址，可以实现并发标记和清除—–> 这也是 ConcurrentMarkSweep 的来源
如果垃圾对象很多，那么整体的执行效率会比较低—–> 适用于垃圾对象较少的场景

回收前

回收后

复制算法 Copy

标记-复制算法，简称复制算法。为了解决标记清除在面对大量垃圾对象时的困境，一种名为 “半区复制” 的思想被提了出来，它将整个内存区域分为大小相同的两块,一个称为 From，一个称为 To，每次只使用 From 区域进行分配，当内存用完了，就将存活的对象拷贝到 To 上，然后交换 From 和 To

分配时在空闲区域中有一个 top 指针，每次分配内存时，都将 top 指针向右移动对象所申请大小相等的距离（这种分配方式又称为碰撞指针）碰撞指针示意图
没有内存碎片
浪费一半的内存空间
移动对象时，需要修改对象地址，会产生停顿

那这时候就产生了一个问题：移动对象，必然会导致对象的内存地址发生变动，那么移动后，对象是怎么找到在堆中对象的新内存地址的呢？

方案一：引入中间层

当我们引用对象时，实际上使用的是中间指针，由中间指针帮我们去定位具体的对象地址（这种方式其实就是句柄的方式。每次移动对象时，都维护一次中间指针），缺点在于每次访问对象属性都变成了两次访存，有一定程度的性能退化（ps：万能的中间层）

我们知道，在 jvm 虚拟机中，栈上存放的是 reference 引用，实际的对象是存储在堆中的。而《java虚拟机规范》里只规定了它是指向对象的一个引用，并没有定义这个引用应该使用何种方式去定位堆中的对象，所以对象的访问方式由虚拟机的具体实现而定，常规的有句柄、直接指针两种方式。 Hotspot 选择的是直接指针的方式。句柄示意图

方案二：forwarding指针

由于 HotSpot 使用的是直接指针的方式，为了解决对象地址的移动问题，它在对象的对象头中引入了 forwarding 指针（除此之外对象头中我们常见的内容还包括 hashcode、对象分代年龄、锁标记位这几个）

它的原理是，在 GC 线程移动对象的地址时，将对象头里的 forwarding 指针指向拷贝后的内存地址，栈上的 Referrence 根据引用找到原对象时，发现门上贴了一个新的地址，于是就将引用更新到新的地址去

针对复制算法的优化

由于 “半区复制” 过于浪费空间，空出一半的空间未免太过可惜，再加上复制算法本身的特性——-> 只适合存活对象较少的场景。

于是就有了对于复制算法的优化（也就是现在的年轻代回收）：

HotSpot 将整个年轻代划分为了 Eden， Survivor0 和 Survivor1 三个区域，使用时将 Eden + S0 一起作为 From ，剩下的 S1 作为 To 区域（空闲），每完成一次年轻代的 GC 之后， S0 和 S1 就进行交换，轮流作为 To 区域（同时将对象的年龄 +1 ）。这样一来 Survivor 空间的浪费就可以减少了。配置 Survivor 空间的大小是由 JVM 参数控制的，例如：-XX:SurvivorRatio=8 代表 Eden:S0:S1=8:1:1（默认），空间率用率直接提升到了 90%

大家可以思考一个小问题：如果回收时发现 To 空间不够了会怎么办？

标记-整理算法 Mark-Compact

在标记阶段完成后（标记阶段，是所有追踪式垃圾回收算法（引用计数不属于）的共同特征），先将存活对象向内存的某一方进行靠拢整理（这个步骤会改变对象的地址），然后清理掉边界以外的区域。这种方式带来的优劣，将前两者结合到了一起

如果移动对象？那么存活对象过多时，更新对象的引用就已经是个极为负重的操作了
如果像标记-清除那样，完全不整理内存碎片，又会导致严重的内存碎片问题。内存的分配回收是最频繁的操作，甚至没有之一，进而导致应用的吞吐量下降
如果不移动对象，那么停顿时间会更短
如果移动对象，那么应用的整体吞吐量会更高

在常见的垃圾回收器中，java8 中默认的关注吞吐量的 ParallelOld 是基于标记整理的，而关注停顿时间的 CMS 是基于标记清除的。
（当然，CMS 虽然 95% 的时间是使用标记-清除。但在内存碎片过多的时候，还是会再使用标记-整理收集一次）

标记整理算法的处境在 ZGC 和 Shenandoah 出现之前其实挺尴尬的，因为每次都去整理内存对于停顿时间来说是个硬伤，而在它们出现之后，对象复制阶段也可以并发了—>所以才有了所谓的停顿时间在 10ms 以内

分代回收思想

分代思想来源于两个假说：

①大对数对象都是朝生夕灭的；
②熬过越多次垃圾收集过程的对象就越难以消亡。

在这两个假说之下，JVM 一般将堆分为年轻代和老年代两个部分，对象创建时都在新生代中进行分配（例外：大对象直接进入老年代），每次垃圾回收时都有大量对象被回收，少数存活的对象被放入 Survivor 区域。当经过数次 GC 后仍然存活的对象，就晋升到老年代中（即分代年龄，默认是大于 15 时晋升）

那基于前面的分析我们可以知道，Copy 算法适用于存活对象少的情况,而 Mark-Sweep 更适用于存活对象多的情况，所以对于存活时间短的对象，我们倾向于使用复制算法，而对于存活时间长的对象，我们更倾向使用标记-清除类型的算法。所以在业界中年轻代通常使用复制算法，老年代使用标记清除。

分代思想使得不同的回收算法能在自己擅长的场景下进行工作，将各自的优势都结合起来，看似是非常好的一种方式，但同时呢它也带来了新的问题——> 跨代引用

假设现在要进行一次只局限于年轻代的回收，但新生代中新创建的对象完全有可能被老年代引用，为了找出年轻代中的存活对象，不得不将老年代也扫描一次来保证可达性分析的正确性。。毕竟任何一个存活对象被错误回收都是重大事故

到这里大家会发现一个问题，如果我真这么做了，那还分代干什么呢？于是乎，第三个假说诞生了：③ 跨代引用假说：跨代引用相对同代引用来说，仅占极少数。

虽然写的是假说，但它其实是真的- -。（雾）

记忆集和卡表

为了避免因为极少数的跨代引用而去扫描整个老年代，JVM 虚拟机在年轻代引入了 Remember Set（记忆集，可以理解为一种数据结构）的概念。垃圾回收器通过记忆集来判断，非收集区域是否存在指向收集区域的指针（说人话，当 GC 进行年轻代收集时，老年代属于非收集区域，通过记忆集可以判断是否存在指向了年轻代的跨代引用），根据记忆集的记录精度，分为了字长精度、对象精度、卡精度（又称为 Card Table）三种

堆中的对象数量非常庞大，所以为每个字长，或者对象都去记录跨代引用是不符合实际的，HotSpot 选择的方式是卡精度进行记录，以 512 字节的内存块为一个区域进行记录，可以理解为下面这个样子

老年代的 A 对象存在跨代引用，那么将老年代所在的内存块进行标记，CardTable 本质上是一个位图，当需要进行回收时，就会把这块区域的对象也加入到 GCRoots 中

记忆集的维护是通过写屏障来完成的（这里使用的是写后屏障来更新卡表），后续会详细介绍什么是写屏障

GC停顿与并发

在复制算法和标记-整理中，对象的地址都会发生变化，最简单的办法是让业务线程全部停下来，等回收器把对象地址全部调整好了以后再工作，这就是 GC 停顿产生的原因。（新版的 ZGC 和 Shenandoah 已经利用读屏障实现了整理过程与用户线程的并发执行）

为了减少 GC 停顿，我们可以在标记阶段，让业务线程不要停下来。这意味着 GC Mark 和业务线程在同时工作，也就是并发（Concurrent）的 GC 算法。

注意区别并发和并行的区别，Concurrent 指的是 GC 和业务线程同时工作，而 Parallel 指的是多个 GC 线程同时工作。

以下是 CMS 收集器的工作示意图

小问题：为什么要做并发，不使用并发会有什么问题（从堆大小来考虑）？

使用并发虽然解决了停顿问题，但是新问题又双叒来了！！！，如果业务线程和 GC 线程并发工作的话，就会存在 GC 正在进行 GCRoots 枚举，但是呢，业务线程把对象的引用关系给修改了。那这样就会导致标记出来的结果不正确，明明是垃圾没回收到，我还需要用的对象，你给我回收了?

初始标记、以及 Remark 阶段需要停顿，且 Remark 并不是指重新扫描，仅扫描在并发标记阶段修改了引用的对象

三色标记法 + 写屏障

为了保证对象不被错误回收， GCRoots 的遍历必须要在一个能保障一致性的快照上进行。在理解这个原理时，通常会引入“三色标记”作为工具来辅助推导

需要注意的是，三色并不是指真的要给对象一个颜色属性，而是一种为了把问题说清楚而引出来的抽象概念，它在不同的 GC 算法中代表着不同的状态

黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过；
灰色：表示对象已经被垃圾收集器访问过，但该对象至少还有一个引用没有被扫描过；
白色：表示对象尚未被垃圾收集器访问过，在可达性分析的初始阶段，所有对象都是白色的，在分析结束后仍处于白色的对象则表示不可达；

由于 GC 线程在遍历过程中会给对象标记颜色，但同时业务线程也有可能更改引用关系，这样一来就可能会导致两种结果：

本来已经是垃圾的对象被误标为了存活，虽然不好，但其实只是产生了部分浮动垃圾，还算可以接受，下次 GC 收集掉就好了
本来是存活的对象被误标为了垃圾，这就是重大问题了，势必会导致程序错误（主要解决这个问题）

三色标记的漏标问题：发生在当黑色对象修改引用指向白色对象时

如下图所示，此时黑色对象修改了引用，直接指向 C, 同时 B 指向 C 的引用也断开（两个条件），由于黑色对象 A 所有的引用都已经遍历结束了，这就会导致可达性分析结束之后 C 仍然处于白色状态，最后被当作垃圾错误回收。

所谓的两个条件是指：①黑色对象直接指向白色对象；②灰色对象到该白色对象的引用被删除

写屏障

出现对象消失的情况，仅在上述所说的两个条件均满足时才会产生存活对象消失的情况，所以要解决并发标记只需要破坏这两个条件的其中一个即可。

在这里需要先引出两种三色不变性的定义：

强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象；
弱三色不变性：黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径

解决方式一：往前进（满足强三色不变性）

Dijkstra 提出的写屏障：把白色对象直接标灰，在实现时其实不用管引用的出发点A是什么颜色，可以直接将未标记的对象置灰（简单地说，就是当需要修改黑色对象的引用以指向白色对象之前，直接将白色对象置灰，破坏的是条件①）

缺点

通过这个图可以意识到，写屏障其实是虚拟机层面 “对引用类型赋值” 这个动作的 AOP ，他可以在修改某个对象的应用前，或者修改引用之后触发，前面提到的维护跨代引用卡表，使用的就是写后屏障（在赋值之后触发，将卡表的对应位置置为1或0）

解决方式二：往后退(满足弱三色不变性)

把黑色对象还原回灰色状态，重新进行遍历

CMS的做法—>增量更新

CMS 本质上使用的其实是往后退的方法，但是它的巧妙之处在于，它并不是直接开倒车（雾），而是将修改了黑色–>白色引用的卡表区域进行标记。下图中，黑色对象 A 在修改引用指向白色对象 B 的时候，会把 cardTable 对应的区域置为灰色（中间那个），这样一来 cardTable 就有了两个作用：①维护跨代引用；②标记灰色节点

现在回想一下，当发生年轻代 GC 时，会将卡表中有标记的位置也加入到 GCRoots ，如果某个 card 中没有找到跨代引用指针，就不需要在下一次回收中扫描该区域，此时该 card 对应的标记会被清空！！那这样一来就会影响到 cardTable 的第二个功能—>灰色节点标记被年轻代回收给清除了。

为了解决 cardTable 功能冲突问题，HotSpot 在 CMS 上打了一个补丁—-> 即 mod union table ,每次进行年轻代回收时，如果某个标记位置要被清空，那么将 cardTable 上标记的位置转移到 mod union table

虽然复用 cardTable 提高了写屏障的性能，但这样一来 cardTable 同时承担着两个职责，导致互相影响

CMS 的粗糙点：

内存碎片过多时，需要一次全局整理，停顿会比较长
和对象 A 在同一个区域的 D 对象即使已经没有对象引用它了，CMS 仍然会认为他是存活对象，导致浮动垃圾的产生。
需要和业务线程同时工作，所以不能等空间不够了才回收，需要留出足够的空间给业务线程做内存分配，CMS的启动百分比配置：-XX:CMSInitiatingOccupancyFraction

为什么Concurrent Mark Sweep被弃用了？

分区 GC (简单介绍)

对于分代 GC 来说，对象都集中在一起，不管是回收老年代还是年轻代，垃圾(存活)对象的多少会直接影响 GC 停顿的时间，停顿时间相对来说是不可控的。

为了使 GC 停顿时间可控，分区 GC 的思想被提了出来，它将整个堆内存划分为多个区域（Region），每个区域都可以根据需要，扮演新生代的 Eden 空间、Survivor 空间或者老年代空间（G1 GC）

分区GC 带来的新问题

分区 GC 带来了停顿时间可控的好处，例如 G1 GC 可以设置 JVM 参数 -XX:MaxGCPauseMillis=80 代表停顿时间控制在 80ms 左右，回收器在工作时，会尽力保证停顿时间接近该值。

分区 GC 的新问题：

1.如何维护跨区引用
2.如何合理地选择回收区域
- 根据停顿时间要求反向估算，
- 优先回收垃圾更多的区域—> Garbige First 的由来
3.仍需要考虑分代问题，Region 所扮演的角色是可以相互转换的
4.大对象分配问题

G1是如何解决跨区引用的

总体思想与维护跨代引用类似→使用写屏障维护卡表。我们现在知道，所谓的写屏障其实就是在更改对象之间的引用关系的时候，通过额外做一些事情来维护相关信息。前面提到的引用计数、维护 cardTable 都是写屏障的应用，但G1 的写屏障相对复杂，它需要解决以下两个问题：

问题①：并发标记阶段的删除写屏障（解决漏标问题）

G1在进行三色标记时，使用的是删除法—>当开始 GCRoots 遍历后,如果某个对象的引用关系被删除时，会将对象置灰。现在回想一下垃圾对象是如何产生的—->当一个对象的所有引用都被删除时，它才会被标记为垃圾，这样一来，删除写屏障的存在使得在并发标记之后才产生的垃圾都会被认为是存活对象，这就好比在并发标记开始时对堆内存拍了个快照，在这一瞬间存活的对象，都会被标记为存活，也就是 SATB(原始快照) 的由来

为了提高性能。G1 不会在每次删除都去维护写屏障（标记），而是将引用被删除的对象记录在 SATB队列中。每个业务线程都有自己的本地 SATB队列，最后再由 GC 线程来维护（标记）这些对象

问题②：维护跨区引用

维护跨区引用与维护跨代引用的原理是相同的，区别在于分代 GC只需要维护一个大卡表（整个区域对应一个），但到了分区 GC 中，回收部分的区域需要知道哪些 Region 存在跨区引用，那么记忆集也需要改变，

G1 为每个 Region (区域)都维护了自己的专属记忆集（这也导致 G1 需要占用更多内存，至少需要堆内存的 10%-20% 来维护收集器的正常工作）

因为 G1 的整个内存区域分为很多个 Region，对于下方左侧的图来说，与 Region1 存在跨区引用的只有 Region2、Region3 而已，如果使用通用记忆集，就会增加很多不必要的查找，所以 G1 实际使用的是右边的方式，每个 Region 都有自己的专属记忆集

根据每个 region 跨代引用的多少，专属记录集还分为稀疏表、细粒度表和粗粒度表三种。

如何选择回收区域

G1 内部维护了一个停顿预测模型，计算出每个 Region 所需要花费的回收时间，平均值，标准偏差等。

大对象的处理方式

G1 在进行分区时，会有一种 Humongous 的特殊区域存在，当一个对象的大小超过了一个 Region 容量的一半则认为是大对象，此时会将这些对象存放到多个连续的 Humongous Region 中（G1 的大多数行为都将此区域作为老年代来处理）

JVM中的垃圾回收算法

名称	算法
ParallelGC	copy-based
Parallel Old	Mark-Compaction
G1 GC	copy-based
CMS	Concurrent Mark Sweep
ParNew	copy-based

参考：

CMS 垃圾收集算法
golang里gc相关的write barrier(写屏障）是个什么样的过程或者概念？
为什么Concurrent Mark Sweep被弃用了？
《深入理解java虚拟机第三版》
编程高手必学的内存知识