[4] 垃圾收集策略与算法
[4] 垃圾收集策略与算法

程序计数器、虚拟机栈、本地方法栈随线程而生,也随线程而灭;栈帧随着方法的开始而入栈,随着方法的结束而出栈。这几个区域的内存分配和回收都具有确定性,在这几个区域内不需要过多考虑回收的问题,因为方法结束或者线程结束时,内存自然就跟随着回收了。
而对于 Java 堆和方法区,我们只有在程序运行期间才能知道会创建哪些对象,这部分内存的分配和回收都是动态的,垃圾收集器所关注的正是这部分内存。

1. 判定对象是否存活(标记阶段)

若一个对象不被任何对象或变量引用,那么它就是无效对象,需要被回收。

1.1 引用计数法

在对象头维护着一个整型的 counter 计数器,用于记录被对象引用的情况。对象被引用一次则计数器 + 1;若引用失效则计数器 - 1。当计数器为 0 时,就认为该对象无效了。
优点:
  • 实现简单
  • 判定效率高
  • 垃圾易于辨识
  • 回收没有延迟性
缺点:
  • 需要单独的字段存储计数器,增加了存储空间的开销
  • 每次赋值需要更新计数器,伴随加减法操作,增加了时间开销
  • 无法处理循环引用的情况,致命缺陷,导致JAVA的垃圾回收器中没有使用这类算法
在大部分情况下引用计数法都是一个不错的算法。但是主流的 JVM 里没有选用引用计数算法来管理内存,主要是因为它很难解决对象之间循环引用的问题。
举个栗子 👉 对象 objAobjB 都有字段 instance,令 objA.instance = objB 并且 objB.instance = objA,由于它们互相引用着对方,导致它们的引用计数都不为 0,于是引用计数算法无法通知 GC 回收它们。
📔
引用计数算法,还是很多语言的资源回收选择,例如Python,它更是同时支持引用计数和垃圾回收机制。Python 解决循环引用的办法:手动解除;使用弱引用,weakref,Python 提供的标准库,旨在解决循环引用。

1.2 可达性分析法

可达性分析法是 Java、C# 选择的回收标记算法,它的基本思路为:
  1. 根对象(GC Roots) 为起始点,按照从上到下的方式搜索被 GC Roots 集合所连接的目标对象是否可达。
  1. 使用可达性分析法后,内存中存活的对象都被被 GC Roots 集合直接或间接连接着,搜索时走过的路径称为引用链
  1. 如果目标对象没有任何引用链相连,则是不可达的,意味着该对象已经死亡,可以标记为垃圾对象。
  1. 在可达性分析算法中,只有能够被 GC Roots 集合直接或者间接连接的对象才是存活的对象。
GC Roots 包括:
  • Java 虚拟机栈(栈帧中的局部变量表)中引用的对象
    • 比如各个线程被调用的方法中使用到的参数、局部变量等
  • 本地方法栈中 JNI 引用的对象
  • 方法区中常量引用的对象
    • 比如字符串常量池里的引用
  • 方法区中类静态属性引用的对象
    • 比如 Java 类的引用类型静态变量
  • 所有被同步锁 synchronized 持有的对象
  • JVM 内部的引用
    • 比如基本数据类型对应的 Class 对象,一些常驻的异常对象,如 NullPointerExceptionOutOfMemoryError,系统类加载器等
  • 反映 JVM 内部情况的 JMXBean、JVMTI 中注册的回调,本地代码缓存等
GC Roots 并不包括堆中对象所引用的对象,这样就不会有循环引用的问题。
除了固定的 GC Roots 集合之外,根据用户选择的垃圾收集器以及当前回收的内存区域不同,还可以有其他临时性的对象加入,共同构成完整 GC Roots 集合,比如分代收集和局部回收。
如果只针对 Java 堆中某一块内存区域进行垃圾回收,必须要考虑这个区域的对象可能被其他区域对象所引用,这是需要一并将关联的区域对象加入GC Roots 集合中去考虑,才能保证可达性分析的准确性。
如果需要使用可达性分析法来判断内存是否可回收,那么分析工作必须在一个能保障一致性的快照中进行。这点不满足的话,分析结果的准确性就无法保证。

2. 回收堆中无效对象

对于可达性分析中不可达的对象,也并不是没有存活的可能。

2.1 判定 finalize() 是否有必要执行

JVM 会判断此对象是否有必要执行 finalize() 方法,如果对象没有覆盖 finalize() 方法,或者 finalize() 方法已经被 JVM 调用过,那么视为「没有必要执行」。那么对象基本上就真的被回收了。
如果对象被判定为有必要执行 finalize() 方法,那么对象会被放入一个 F-Queue 队列中,JVM 会以较低的优先级执行这些 finalize()方法,但不会确保所有的 finalize() 方法都会执行结束。如果 finalize() 方法出现耗时操作,JVM 就直接停止指向该方法,将对象清除。

2.2 对象重生或死亡

如果在执行 finalize() 方法时,将 this 赋给了某一个引用,那么这个对象就「重生」了。如果没有,则会被垃圾收集器清除。
任何一个对象的 finalize() 方法只会被系统自动调用一次,如果对象面临下一次回收,它的 finalize() 方法不会被再次执行,想继续在 finalize() 中自救就无效了。
所以 JVM 中的对象可能存在三种状态:
  • 可触及的:从 GC Roots 开始,可以到达这个对象。
  • 可复活的:对象的所有引用都被释放了,但是对象有可能在 finalize() 方法中「复活」。
  • 不可触及的:对象的 finalize() 方法被调用,且没有「复活」,那么就会进入不可触及状态。处于不可触及状态的对象不可能被「复活」,因为 finalize() 只会被调用一次。
只有对象不可触及时才可以被回收。
所以判断一个对象 objA 是否可以被回收,至少需要经历两次标记过程:
  1. 如果对象到 GC Roots 没有引用链,则进行第一次标记。
  1. 进行筛选,判断此对象是否有必要执行 finalize() 方法:
      • 如果对象 objA 没有重写 finalize() 方法,或者 finalize() 方法已经被 JVM 调用过,则 JVM 视为没有必要执行,对象 objA 被判定为不可触及的。
      • 如果对象 objA 重写 finalize() 方法,且还未被执行过,那么 objA 会被插入到 F-Queue 队列中,有一个 JVM 自动创建的、低优先级的 Finalizer 线程触发其 finalize() 方法执行。
      • finalize() 方法是对象逃脱死亡的最后机会,稍后垃圾收集器会对 F-Queue 队列中的对象进行第二次标记,如果 objAfinalize() 方法中与引用链上的任何一个对象建立了联系,那么在第二次标记时,objA 会被移出即将回收的集合。之后,对象会再次出现没有被引用的情况,finalize() 方法不会再被调用,对象直接变为不可触及状态。

3. 回收方法区内存

方法区中存放生命周期较长的类信息、常量、静态变量,每次垃圾收集只有少量的垃圾被清除。方法区中主要清除两种垃圾:
  • 废弃常量
  • 无用的类

3.1 判定废弃常量

只要常量池中的常量不被任何变量或对象引用,那么这些常量就会被清除掉。比如,一个字符串 "bingo" 进入了常量池,但是当前系统没有任何一个 String 对象引用常量池中的 "bingo" 常量,也没有其它地方引用这个字面量,必要的话,该 "bingo" 常量会被清理出常量池。

3.2 判定无用的类

判定一个类是否是「无用的类」,条件较为苛刻。
  • 该类的所有对象都已经被清除
  • 加载该类的 ClassLoader 已经被回收
  • 该类的 java.lang.Class 对象没有在任何地方被引用,无法在任何地方通过反射访问该类的方法
一个类被虚拟机加载进方法区,那么在堆中就会有一个代表该类的对象:java.lang.Class。这个对象在类被加载进方法区时创建,在方法区该类被删除时清除。

4. 垃圾回收概念

垃圾回收(Garbage Collection,GC),在计算机科学中是指一种自动的存储器管理机制,在 JVM 中是指通过某种策略算法来回收无用内存空间的行为。

4.1 Minor GC

Minor GC 指的是发生在新生代中的 GC(包括 Eden 和 Survivor 区域),也有人称其为 Young GC 或者 YGC。
当 JVM 无法为新对象分配空间时(如 Eden 区已满),总是会触发 Minor GC,因此分配频率越高,Minor GC 的执行频率就越高。
Eden 区满时触发第一次 Minor GC,将 Eden 和 From 区活着的对象复制到 To 区,清理 Eden 和 From 区的空间,同时将到 To 区的对象分代年龄 + 1,但如果已经到达到老年代的阈值(默认 15,可通过 -XX:MaxTenuringThreshold 参数调整),则直接转移到老年代中。
From 和 To 区不是固定的,每次 Minor GC 后,两个 Survivor 区空闲的一块作为 To 区,非空闲的一块作为 From 区。
因为 Java 对象大多都具备朝生夕灭的特性,所以 Minor GC 非常频繁,一般回收速度也比较快。

4.2 Major GC

Major GC 指的是发生在老年代中的 GC,也有人称为 Old GC、OGC等。
出现了 Major GC,经常会伴随至少一次的 Minor GC,但这并非绝对。Major GC 的速度一般会比 Minor GC 慢 10 倍 以上。
在《Java虚拟机规范》中,Major GC 和 Full GC 都没有一个正式的定义,所以有人也简单地认为 Major GC 清理老年代,而 Full GC 清理整个内存堆。

4.3 安全点与安全区域

安全点
程序执行并非在所有地方都能停顿下来开始 GC,只有在特定的位置才能停顿下来开始 GC,这些位置称为安全点(Safe Point),在这个时间点上没有字节码正在执行。
如果安全点太少,其中一个线程可能要花很长时间才能到达下一个安全点,其余线程都需要等着它,导致 GC 等待时间长;如果太多则导致运行时性能问题。大部分指令执行时间都比较短,通常会根据是否具有让程序长时间执行的特征为标准,选择一些执行时间较长的指令作为安全点,比如方法调用,循环跳转和异常跳转等。
  • 主动式中断:设置一个中断标志,各个线程运行到安全点的时候,主动轮询这个标志,如果标志为真,则将自己进行中断挂起。
  • 抢先式中断(没有虚拟机采用):中断所有线程,如果还有线程不在安全点,就恢复线程,让线程跑到安全点。

安全区域
如果线程处于 sleep 或者 blocked 状态,这时候线程无法响应 JVM 中断请求、走到安全点去中断挂起。对于这种情况,就需要安全区域(Safe Region)来解决。
安全区域是指在一段代码片段中,对象的引用关系不会发生变化,在这个区域中任何位置开始 GC 都是安全的。
当线程运行到安全区域代码时,首先标志已经进入了安全区域,如果发生 GC,JVM 会忽略标识为安全区域状态的线程。
当线程即将离开安全区域时,会检查 JVM 是否已经完成 GC,如果完成了,则继续运行。否则线程必须等待,直至收到可以安全离开安全区域的信号为止。

4.4 Stop-The-World

Stop-The-World(STW)指的是用户线程在运行至安全点或安全区域之后,就自行挂起,进入暂停状态。对外的表现看起来就像是全世界都停止运转了一样,而不论何种 GC 算法,不论是 Minor GC 还是 Major GC 都会 STW,区别只在于 STW 的时间长短。

4.5 Full GC

Full GC 也有人称为 FGC,这个术语没有正式的定义,《Java虚拟机规范》和垃圾收集研究论文均未提及。而且含义还特别混乱,在不同地方表达的含义是不同的,需要就不同的场景分别进行讨论。

从大众认知上
在通常意义上人们口中说的 Full GC 是一次特殊 GC 行为的描述,这次 GC 会回收整个 Java 堆的内存,包含老年代、新生代、元空间等,这是最常见的一种认知。

从 GC 日志上
在 GC 日志中会发现在部分 GC 日志头中也有 Full GC 这样的字眼,这里表示的含义是在这次 GC 的全过程中,都是 STW 的状态,也就是说在这次 GC 的全过程中所有用户线程都是处于暂停的状态。

从 JDK 自带的工具上
使用 jstat -gc 命令能够查看到制定 Java 线程的 GC 次数,使用 jstat 查出来的 Full GC 次数和时间,实际上指的是老年代的收集器发生 STW 的次数和持续时间。

4.6 可能触发 Full GC 的情况

System.gc() 方法的调用
System.gc()Runtime.getRuntime().gc() 方法的调用,会显示触发 Full GC,同时会对新生代和老年代进行回收,尝试释放对象占用的内存。
调用 System.gc() 方法无法保证一定会进行 GC,其作用只是告知垃圾收集器打算进行 GC 的意图,而垃圾收集器是否会进行 GC 是不确定的(尽管大多时候都会进行 GC)。一般不建议使用 System.gc() 去显示地要求进行 JVM 进行 GC。
一些特殊情况下,比如编写性能基准,我们就可以在运行期间调用 System.gc() 方法。

老年代空间不足
老年代空间不足会触发 Full GC 操作,若进行该操作后空间依然不足,则会抛出如下错误:java.lang.OutOfMemoryError: Java heap space

永久代空间不足
《Java虚拟机规范》中运行时数据区域中的方法区,在 HotSpot 虚拟机中也称为永久代(Permanet Generation),存放一些类信息、常量、静态变量等数据,当系统要加载的类、反射的类和调用的方法较多时,永久代可能会被占满,会触发 Full GC。如果经过 Full GC 仍然回收不了,那么 JVM 会抛出如下错误信息:java.lang.OutOfMemoryError: PermGen space

空间分配担保失败
  • 统计得到的 Minor GC 晋升到旧生代的平均大小大于老年代的剩余空间
  • CMS GC 时出现 promotion failedconcurrent mode failure
    • promotion failed,就是上文所说的担保失败,而 concurrent mode failure 是在执行 CMS GC 的过程中同时有对象要放入老年代,而此时老年代空间不足造成的。

4.7 记忆集与卡表

为了解决跨代引用问题,在新生代中建立了名为记忆集(Remembered Set)的数据结构(记录从非收集区到收集区的指针集合),用以避免把整个老年代加入 GC Roots 扫描范围。
在垃圾收集场景中,垃圾收集器只需通过记忆集判断出某一块非收集区域是否存在指向收集区域的指针即可,无需了解这些跨代指针的全部细节。所以 JVM 设计者在实现记忆集的时候就可以选择那些更为粗犷的记录粒度来节省记忆集的存储和维护成本,例如这些记忆集的实现方式:
  • 字长精度:每个记录精确到一个机器字长(处理器的寻址位数,如常见的 32 位或 64 位),该字包含跨代指针。
  • 对象精度:每个记录精确到一个对象,该对象中有字段包含跨代指针。
  • 卡精度:每个记录精确到一块内存区域,该区域中有对象包含跨代指针。
第三种卡精度是使用一种叫做卡表(Card Table)的方式实现记忆集,也是目前最常用的一种方式。记忆集是一种抽象概念,而卡表则是它的实现方式。它记录了记忆集的记录精度、与堆内存的映射关系等。
关于卡表与记忆集的关系,可以按照 Java 语言中 HashMap 与 Map 的关系来类比理解。
卡表是使用一个字节数组实现:CARD_TABLE [this addredd >> 9] = 0,每个元素对应着其标识的内存区域中一块特定大小的内存块,称为卡页(Card Page)
一般来说,卡页大小都是以 2 的 N 次幂的字节数,通过上面代码可 以看出HotSpot VM 中使用的卡页大小是 2 的 9 次幂,即 512 字节(地址右移 9 位,相当于用地址除以 512)。
那如果卡表标识内存区域的起始地址是 0x0000 的话,数组 CARD_TABLE 的第 0、1、2 号元素,分别对应了地址范围为 0x0000 ~ 0x01FF(长度 512)、0x0200 ~ 0x03FF0x0400 ~ 0x05FF 的卡页内存块:
notion image
一个卡页中可包含多个对象,只要有一个对象的字段存在跨代指针,其对应的卡表的元素标识就变成 1,表示该元素变脏(Dirty),否则为 0。
在发生 GC 时,只要筛选出卡表中变脏的元素,就能轻易得出哪些卡页内存块中包含跨代指针,把它们加入 GC Roots 中一并扫描,就可以保证不进行全局扫描,也不会有遗漏。

4.8 写屏障

HotSpot VM 通过写屏障(Write Barrier)来维护卡表状态。
写屏障可以看作在虚拟机层面对「引用类型字段赋值」这个动作的 AOP 切面,在引用对象赋值时会产生一个环形(Around)通知,供程序执行额外的动作。也就是说,赋值的前后都在写屏障的覆盖范畴内。在赋值前的部分的写屏障叫作写前屏障(Pre-Write Barrier),在赋值后的则叫作写后屏障(Post-Write Barrier)

性能问题
JVM 会为所有赋值操作生成相应的指令,一旦垃圾收集器在写屏障中增加了更新卡表操作,无论更新的是不是老年代对新生代的引用,每次只要对引用进行更新,就会产生额外的开销,不过这个开销与 Minor GC 时扫描整个老年代的代价相比还是低得多的。

伪共享问题
卡表在高并发场景下还面临着伪共享(False Sharing)问题。
伪共享是处理并发底层细节时一种经常需要考虑的问题,现代 CPU 的缓存系统中是以缓存行(Cache Line)为单位存储的,当多线程修改互相独立的变量时,如果这些变量恰好共享同一个缓存行,就会彼此影响(写回、无效化或者同步)而导致性能降低,这就是伪共享问题。
解决办法:
  • 不采用无条件的写屏障,而是先检查卡表标记,只有当该卡表元素未被标记过时才将其标记为变脏。
if (CARD_TABLE [this address >> 9] != 0)
    CARD_TABLE [this address >> 9] = 0;
  • 在 JDK 7 之后,HotSpot VM 增加了一个新的参数 -XX:+UseCondCardMark,用来决定是否开启卡表更新的条件判断。开启会增加一次额外判断的开销,但能够避免伪共享问题,两者各有性能损耗,是否打开要根据应用实际运行情况来进行测试权衡。

4.9 并发的可达性分析

可达性分析工作必须要在能保障一致性的快照中进行,因此必须停止用户进程(STW)。如果用户进程被停止,那不会产生任何问题。但如果用户进程和GC进程并发进行,就会出现两种后果:
  • 错误地标记已经消亡的对象
  • 将存活的对象标记为消亡

三色标记
使用三色标记(Tri-color Marking)来解释并发的可达性分析:
  • 白色:对象未被垃圾收集器访问(未扫描)。
  • 黑色:对象已被垃圾收集器访问,且该对象所有引用已扫描过。(安全存活、扫描完毕)。
  • 灰色:对象被访问过,但对应至少还有一个引用没有扫描过。(正在扫描)。
notion image
notion image
但如果用户线程在并发标记进行时修改了引用关系,如下情况会出现存活对象消亡的现象:
notion image
notion image

对象消失的原因
  1. 添加了一条或多条从黑色到白色的新引用
  1. 删除了全部从灰色到白色的旧引用(直接或间接)

对象消失的解决方案
  1. 增量更新(Increamenttal Update,CMS 使用):记录下新插入的引用,并发扫描完毕后,重新以记录下的引用关系的黑色对象为根扫描。即黑色一旦插入了新的到白色的引用,就变成了灰色。
  1. 原始快照(Snapshot At The Beginning,SATB,G1、Shenandoah使用):灰色对象要删除指向白色对象的引用时,将该引用记录下来,扫描完毕后,再从被记录下的引用的灰色对象开始重新扫描。

5. 垃圾收集算法(清除阶段)

学会了如何判定无效对象、无用类、废弃常量之后,剩余工作就是回收这些垃圾。常见的垃圾收集算法有以下几个:

5.1 标记-清除算法(Mark-Sweep)

标记的过程是:遍历所有的 GC Roots,然后将所有 GC Roots 可达的对象标记为存活的对象,一般是在对象头记录。
清除的过程是:从头到尾线性遍历堆中所有的对象,将没有标记的对象全部清除掉。与此同时,清除那些被标记过的对象的标记,以便下次的垃圾回收。
这种方法有两个不足
  • 效率问题:标记和清除两个过程的效率都不高,在 GC 的时候需要 STW,导致用户体验差。
  • 空间问题:标记清除之后会产生大量不连续的内存碎片,需要维护一个空闲列表。碎片太多可能导致以后需要分配较大对象时,无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。
何为清除:所谓的清除并不是真的置空,而是把需要清除的对象地址保存在空闲的地址列表里,下次有新对象需要加载时,判断垃圾的位置空间是否够,如果够就存放。

5.2 复制算法(Copying,新生代)

为了解决效率问题,“复制”收集算法出现了。它将可用内存按容量划分为大小相等的两块,每次只使用其中的一块。当这一块内存用完,需要进行垃圾收集时,就将存活者的对象复制到另一块上面,然后将第一块内存全部清除。这种算法有优有劣:
  • 优点:不会有内存碎片的问题;没有标记和清除的过程,实现简单高效。
  • 缺点:内存缩小为原来的一半,浪费空间。对于 G1 这种拆分为大量 region 的垃圾收集器,复制而不是移动,意味着垃圾收集器需要维护 region 之间的引用关系,不管是内存占用或者时间开销也不小。
为了解决空间利用率问题,可以将内存分为三块: Eden、From Survivor、To Survivor,比例是 8:1:1,每次使用 Eden 和其中一块 Survivor。回收时,将 Eden 和 Survivor 中还存活的对象一次性复制到另外一块 Survivor 空间上,最后清理掉 Eden 和刚才使用的 Survivor 空间。这样只有 10% 的内存被浪费。
但是我们无法保证每次回收都只有不多于 10% 的对象存活,当 Survivor 空间不够,需要依赖其他内存(指老年代)进行分配担保

5.3 标记-整理算法(Mark-Compact,老年代)

标记-整理算法(也称标记-压缩算法)是一种针对老年代的垃圾收集算法。老年代的对象一般寿命比较长,因此每次垃圾回收会有大量对象存活,如果采用复制算法,每次需要复制大量存活的对象,效率很低。
标记:它的第一个阶段与标记-清除算法是一模一样的,均是遍历 GC Roots,然后将存活的对象标记。
整理:移动所有存活的对象,且按照内存地址次序依次排列,然后将末端内存地址以后(边界外)的内存全部回收。因此,第二阶段才称为整理阶段。
最终效果等同于标记-清除算法执行完成后,再进行一次内存碎片整理。与标记-清除算法本质的区别是:标记-清除算法是非移动式的算法,而标记-整理算法是移动式的。
是否移动回收后的存活对象是一项优缺点并存的风险决策。
优点:
  • 消除了标记-清除算法内存区域分散的缺点。
  • 消除了复制算法中,内存折损的代价。
缺点:
  • 从效率上来讲,标记-整理算法要低于复制算法。
  • 移动对象的同时,如果对象被其他对象引用,则还需要调整引用的地址。
  • 移动的过程中,需要全程暂停用户应用程序,即 STW。

5.4 分代收集算法

不同生命周期的对象可以采取不同的收集方式,以便提高回收效率。根据对象存活周期的不同,将内存划分为几块。一般是把 Java 堆分为新生代和老年代,针对各个年代的特点采用最适当的收集算法。几乎所有的垃圾收集器都采用分代收集算法执行垃圾回收的。
在 HotSpot VM 中:
  • 新生代(对象生命周期短、存活率低、回收频繁):复制算法。
  • 老年代(区域较大、对象生命周期长、存活率高、回收不及新生代频繁):标记-清除算法、标记-整理算法。

5.5 增量收集算法

增量收集算法的思想是:每次 GC 线程只收集一小块区域的内存空间,接着切换到应用程序线程,依次反复,直到 GC 完成。
通过对线程间冲突的妥善管理,允许 GC 线程以分阶段的方式完成标记、清理或复制工作。
缺点:线程和上下文的切换导致系统吞吐量的下降。

5.6 分区算法

为了控制 GC 产生的停顿时间,将一块大的内存区域分割成多个小块,根据目标的停顿时间,每次合理的回收若干个小区间,而不是整个堆空间,从而减少一次 GC 所产生的停顿时间。
分代算法是将对象按照生命周期长短划分为两个部分,而分区算法是将整个堆划分为连续的不同的小区间。每一个小区间都独立使用,独立回收,这种算法的好处是可以控制一次回收多少个小区间。