从原理聊JVM（一）：染色标记和垃圾回收算法

作者：京东科技 康志兴

1 JVM运行时内存划分

1.1 运行时数据区域

? 方法区

属于共享内存区域，存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。运行时常量池，属于方法区的一部分，用于存放编译期生成的各种字面量和符号引用。

JDK1.8之前，Hotspot虚拟机对方法区的实现叫做永久代，1.8之后改为元空间。二者区别主要在于永久代是在JVM虚拟机中分配内存，而元空间则是在本地内存中分配的。很多类是在运行期间加载的，它们所占用的空间完全不可控，所以改为使用本地内存，避免对JVM内存的影响。根据《Java虚拟机规范》的规定，如果方法区无法满足新的内存分配需求时，将抛出OutOfMemoryError异常。

? 堆

线程共享，主要是存放对象实例和数组。如果在Java堆中没有内存完成实例分配，并且堆也无法再扩展时，Java虚拟机将会抛出OutOfMemoryError异常。PS：实际上写入时并不完全共享，JVM会为线程在堆上划分一块专属的分配缓冲区来提高对象分配效率。详见：TLAB

? 虚拟机栈

线程私有，方法执行的过程就是一个个栈帧从入栈到出栈的过程。每个方法在执行时都会创建一个栈帧(Stack Frame)用于存储局部变量表、操作数栈、动态链接、方法出口等信息。如果线程入栈的栈帧超过限制就会抛出StackOverFlowError，如果支持动态扩展，那么扩展时申请内存失败则抛出OutOfMemoryError。

? 本地方法栈

和虚拟机栈的功能类似，区别是作用于Native方法。

? 程序计数器

线程私有，记录着当前线程所执行的字节码的行号。其作用主要是多线程场景下，记录线程中指令的执行位置。以便被挂起的线程再次被激活时，CPU能从其挂起前执行的位置继续执行。唯一一个在 Java 虚拟机规范中没有规定任何 OutOfMemoryError 情况的区域。注意：如果线程执行的是个java方法，那么计数器记录虚拟机字节码指令的地址。如果为native（底层方法），那么计数器为空。

1.2 对象的内存布局

在 HotSpot 虚拟机中，对象分为如下3块区域：

? 对象头(Header)运行时数据：哈希码、GC分代年龄、锁状态标志、偏向线程ID、偏向时间戳等。类型指针：对象的类型元数据的指针，如果对象是数据，还会记录数组长度。

? 对象实例数据(Instance Data)包含对象真正的内容，即其包括父类所有字段的值。

? 对齐填充(Padding)对象大小必须是是8字节的整数倍，所以对象大小不满足这个条件时，需要用对齐填充来补齐。

2 标记的方法和流程

2.1 判断对象是否需要被回收

要分辨一个对象是否可以被回收，有两种方式：引用计数法和可达性算法。

? 引用计数法就是在对象被引用时，计数加1，引用断开时，计数减1。那么一个对象的引用计数为0时，说明这个对象可以被清除。这个算法的问题在于，如果A对象引用B的同时，B对象也引用A，即循环引用，那么虽然双方的引用计数都不为0，但如果仅仅被对方引用实际上没有存在的价值，应该被GC掉。

? 可达性算法通过引用计数法的缺陷可以看出，从被引用一方去判定其是否应该被清理过于片面，所以我们可以通过相反的方向去定位对象的存活价值：一个存活对象引用的所有对象都是不应该被清除的（Java中软引用或弱引用在GC时有不同判定表现，不在此深究）。这些查找起点被称为GC Root。

2.2 哪些对象可以作为GC Root呢？

1. JAVA虚拟机栈中的本地变量引用对象

2. 方法区中静态变量引用的对象

3. 方法区中常量引用的对象

4. 本地方法栈中JNI引用的对象

2.3 快速找到GC Root - OopMap

栈与寄存器都是无状态的，保守式垃圾收集会直接线性扫描栈，再判断每一串数字是不是引用，而HotSpot采用准确式垃圾收集方式，所有对象都存放在OopMap（Ordinary Object Pointer）中，当GC发生时，直接从这个map中寻找GC Root。

将GC Root存放到OopMap有两个触发时间点：

1. 类加载完成后，HotSpot就会把对象内什么偏移量上是什么类型的数据计算出来。

2. 即时编译过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用。

2.4 更新OopMap的时机 - 安全点

导致OopMap更新的指令非常多，所以HotSpot只在特定位置进行记录更新，这些位置叫做安全点。安全点位置的选取的标准是：“是否具有让程序长时间执行”。比如方法调用、循环跳转、异常跳出等等。

2.5 可达性分析过程

三色标记法

? 白色：表示垃圾回收过程中，尚未被垃圾收集器访问过的对象，在可达性分析开始阶段，所有对象都是白色的，即不可达。

? 黑色：被垃圾收集器访问过的对象，且这个对象所有的引用均扫描过。黑色的对象是安全存活的，如果其他对象被访问时发现其引用了黑色对象，该黑色对象也不会再被扫描。

? 灰色：被垃圾收集器访问过的对象，但这个对象至少有一个引用的对象没有被扫描过。那么标记阶段就是从GC Root的开始，沿着其引用链将每一个对象从白色标记为灰色最后标记为黑色的过程。

标记过程中不一致问题

由于这个阶段是层层递进的标记，所以过程中难免出现不一致的情况导致原本是黑色的对象被标记为白色，比如，当前扫描到B对象了，C对象尚未被访问时，标记情况如下：

那么如果这时A对象取消了对B对象的引用，而GC Root增加了对C对象的引用，GC Root作为黑色标记不会再次被扫描，那么C对象在标记阶段结束后仍然会保持白色，就会被清除掉。

解决方式

? 增量更新

当黑色对象增加了对白色对象的引用时，将其从黑色改为灰色，等并发标记阶段结束后，从GC Root开始顺着对象图再将灰色对象重新扫描一次，这个扫描过程会STW，不会再次产生不一致问题。CMS就采用了这种方式。

? 原始快照（SATB）

当灰色对象删除了白色对象的引用时，将其记录在线程独占的SATB Queue中，让其在标记阶段结束后被再次扫描。 G1、Shenandoah采用了这种方式。

示例

我们通过一个例子来展示两种处理方式的不同，比如正常标记到对象A时，将其标记为灰色：

此时，用户线程发生如下行为：

1. GC Root直接引用了C

2. A取消了引用B

理论上，C仍然是可达对象，不应被清除，而B不可达，应当被清除。

增量更新会记录行为1，将GC Root标记为灰色，B不能访问到被标记为可以回收：

等到重新标记阶段再次访问灰色的GC Root，顺序将GC Root和C标记为黑色：

而原始快照会记录行为2，将发生引用变化的对象全部记录下来，等到重新标记阶段再次访问这些灰色，将其标记为黑色并顺着对象图扫描。

那么最终B作为浮动垃圾就被保存下来了，只能等到下一次GC时才能被回收。

3 分代模型

3.1 分代假说

弱分代假说（WeakGenerationalHypothesis）：绝大多数对象都是朝生夕灭的。 强分代假说（StrongGenerationalHypothesis）：熬过越多次垃圾收集过程的对象就越难以消亡。 跨代引用假说（IntergenerationalReferenceHypothesis）：跨代引用相对于同代引用来说仅占极少数。

上述假说是根据实际经验得来的，由此垃圾收集器通常分为“年轻代”和“年老代”：

? 年轻代用来存放不断生成且生命周期短暂的对象，收集动作相对高频

? 年老代用来存放经历多次GC仍然存活的对象，收集动作相对低频

3.2 空间分配担保

如果在GC后新生代存货对象过多，Survivor无法容纳，那么将会把这些对象直接送入年老代，这就叫年老代进行了“分配担保”。 为了保证年老代能够足够空间容纳这些直接晋升的对象，在发生Minor GC之前，虚拟机必须先检查年老代最大可用的连续空间，如果大于新生代所有对象总空间或者历次晋升的平均大小，就会进行MinorGC，否则将进行FullGC以同时清理年老代。

3.3 记忆集和卡表

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。

记忆集的作用

新生代发生垃圾收集时（Minor GC），如果想确定这个新生代对象是否被年老代的对象引用，则需要扫描整个年老代，成本非常高。

如果我们能知道哪一部分年老代可能存在对新生代的引用，就可以降低扫描范围。

所以我们可以在新生代建立一个全局数据结构叫“记忆集（Remembered Set）”，这个结构把年老代分为若干个小块，标记了哪些小块内存中存在引用了新生代对象的情况，等到Minor GC时，只扫描这部分存在跨代引用的内存块即可。虽然在对象变化时增加了维护记忆集的成本，但相比垃圾收集时扫描整个年老代来说是值得的。

JVM通常在对象增加引用前设置写屏障判断是否发生跨代引用，如果有跨代情况，则更新记忆集。

卡表

实现记忆集时，可以有不同精度的粒度：可以指向内存地址，也可以指向某个对象，或者指向某一块内存区域。精度越低，维护成本越低。指向某一块内存区域的实现方式就是“卡表”。卡表通常就是一个byte数组，数组中每一个元素代表某一块内存，其值是1或者0：当发生跨代引用时，就表示该元素“dirty”了，那么将将其设置为1，否则就是0。

4 垃圾回收算法

4.1 标记-清除（Mark-Sweep）

GC分为两个阶段，标记和清除。首先标记所有可回收的对象，在标记完成后统一回收所有被标记的对象。

缺点是清除后会产生不连续的内存碎片。碎片过多会导致以后程序运行时需要分配较大对象时，无法找到足够的连续内存，而不得已再次触发GC。

4.2 标记-复制（Mark-Copy）

将内存按容量划分为两块，每次只使用其中一块。当这一块内存用完了，就将存活的对象复制到另一块上，然后再把已使用的内存空间一次清理掉。

这样使得每次都是对半个内存区回收，也不用考虑内存碎片问题，简单高效。

缺点需要两倍的内存空间。

一种优化方式是使用eden和survivior区，具体步骤如下：

eden和survivior区默认内存空间占比为8:1:1，同一时间只使用eden区和其中一个survivior区。标记完成后，将存活对象复制到另一个未使用的survivior区（部分年龄过大的对象将升级到年老代）。

这种做法，相比普通的两块空间的标记复制算法来说，只有10%的内存空间浪费，而这样做的原因是：大部分情况下，一次young gc后剩余的存活对象非常少。

4.3 标记-整理（Mark-Compact）

标记-整理也分为两个阶段，首先标记可回收的对象，再将存活的对象都向一端移动，然后清理掉边界以外的内存。

此方法避免标记-清除算法的碎片问题，同时也避免了复制算法的空间问题。 一般年轻代中执行GC后，会有少量的对象存活，就会选用复制算法，只要付出少量的存活对象复制成本就可以完成收集。

而年老代中因为对象存活率高，用标记复制算法时数据复制效率较低，且空间浪费较大。所以需要使用标记-清除或者标记-整理算法来进行回收。

所以通常可以先使用标记清除算法，当碎片率高时，再使用标记整理算法。

5 最后

本篇介绍了JVM中垃圾回收器相关的基础知识，后续会深入介绍CMS、G1、ZGC等不同垃圾收集器的运作流程和原理，欢迎关注。