Back
Featured image of post JVM 学习笔记 05 - 垃圾清除算法

JVM 学习笔记 05 - 垃圾清除算法

JVM 学习笔记,在判定对象已经成为垃圾时,如何将它们扫地出门?

上篇文章我们讲解了如何判定对象已经成为垃圾,本文将介绍 JVM 如何清除它们。

之前已经说过,判定对象是否死亡可以通过引用记数或可达性分析。所以对应的清除算法也可以分为两大类:

  • 引用计数式垃圾收集 Reference Counting GC
  • 追踪式垃圾收集 Tracing GC

由于我们是 JVM 学习笔记,JVM 的主流实现基本上是 Tracing GC,因此就不介绍另一种了。

分代收集理论

分代收集(Generational Collection)理论是最广泛应用的垃圾收集理论,建立在两个分代假说之上:

  1. 弱分代假说(Weak Generational Hypothesis):大多数对象朝生夕灭
  2. 强分代假说(Strong Generational Hypothesis):熬过越多次 GC 的对象,越难以消亡

因此,很容易想到将内存划分为多个区域,针对不同区域的特点,优化收集算法。很多 JVM GC 就是这么做的。

譬如,可以将 Heap 分为新生代和老年代。很多对象在新生代中就会死去,而熬过 GC 的对象,就可以逐步放到老年代中管理。所以,JVM 可以每次只回收其中某一个或者某些部分的区域。从而还出现了「Minor GC」「Major GC」「Full GC」这样的划分。

然而这样的模型仍然是不完备的。比如,现在要进行一次 Minor GC(只清除新生代),但新生代中的对象却可能被老年代所引用。为了找出新生代的存活对象,却不得不在 GC Roots 之外,额外搜讯老年代中所有对象,来确保可达性分析的正确性,反之亦然。为了避免造成极大的性能损失,还需要第三条假说:

  1. 跨代引用假说(Intergenerational Reference Hypothesis):跨代引用对比同代引用,少之又少

基于 1、2 两条假说,推出这条很自然:两个存在引用关系的对象,倾向于同生同死。比如,如果某个新生代对象存在跨代引用,由于老年代对象难以消亡,所以新生代也会逐渐晋升到老年代中,跨代引用也就被消除了。

因此 Minor GC 时,就不必扫描整个老年代,而是只扫描相关的区域。这样就可以极大减少运行时开销。

后续会使用的 GC Term:

  • Partial GC:不完整收集整个 Heap 的 GC
    • Minor GC / Young GC:只收集新生代
    • Major GC / Old GC:本文中指只收集老年代,然而这个说法常常和 Full GC 混淆,需要根据上下文判断。
    • Mixed GC:混合收集新生代和老年代。
  • Full GC:收集整个 Heap 和方法区。

清除算法

标记-清除

最基础的 GC 算法是「标记-清除」(Mark-Sweep)。分为「标记」、「清除」两个阶段。首先标记出所有需要回收的对象,然后统一回收。标记过程之前已经讲过了。

如图:

标记-清除垃圾回收算法

他的缺点很明显:

  1. 效率低,JVM 需要大量的标记和清除操作,随着对象数量增长,速度会极速下降
  2. 内存空间碎片化,会产生大量不连续的内存空间,导致内存利用率不高

标记-复制

标记-复制(mark-copying)算法将内存分为两块。若一块内存用毕,就对这块区域进行一次垃圾收集,将还存活的对象复制到另一块区域上。每次只使用一块,并将另一块内存保留。

标记-复制垃圾回收算法

若回收时多数对象都是存活的,这将会产生大量复制开销。但如果多数对象都是死亡的,那么复制开销就很低。同时,也毋须考虑碎片化问题,因为会直接清除一个区块的内存。当然,缺点也显而易见,这浪费了一半的内存

回想一下分代假设:1. 大多数对象朝生夕灭;2. 熬过越多次 GC 的对象,越难以消亡。

因此对于新生代中的对象,就非常适合 Mark-Copy 算法。

在 1989 年,Andrew Appel 就提出了将 Mark-Copy 优化后的策略。将新生代分为较大的一块 Eden 和两块 Survivor。分配时使用 Eden 和一块 Survivor。GC 时,将 Eden 和其中一块 Survivor 内存区域中的存活对象,复制到另一块 Survivor 空间上。HotSpot VM 默认的比例为 \(\text{Eden}:\text{Survivor}=8:1\) 。也就是说,只有 \(10\%\) 的内存会被浪费(因为有两块 Survivor,最终比例是 \(8:1:1\))。

此外,还需要考虑到大量创建对象的极端情况。因此就有分配担保(Handle Promotion)机制。可以直接将新对象放入老年代,避免反复收集。具体细节,会在以后详解。

标记-整理

标记-复制算法固然能在新生代大放光彩,然而若在老年代,对象存活率较高,较多的复制操作会让性能骤降。

针对老年代特征,可以使用标记-整理(Mark-Compact)算法。其机制就是在标记-清楚基础之上,增加一个移动内存的步骤。

标记-整理垃圾回收算法

然而,移动存活对象的代价是很高的,尤其是老年代这种大区块。移动存活对象并更新引用是一项沉重、耗时的操作,必须停止整个程序进行 GC,i.e. stop the world. 极大影响程序的响应速度

如果你玩过 Minecraft Java 版,那么你很有可能已经经历过其中的酸爽了。程序占用的内存到达了 JVM 设置的上限。反复地经历新对象创建和 Full GC 循环,反复停止整个程序[^1]。(这种情况也被某些人叫做「内存抖动」)体现在游戏中,就是每隔几秒画面静止一下,体验非常差。

当然,这里是指多数 GC 会停止整个程序。较新的一些 GC,如 ZGC,可以通过其他手段避免暂停全局。

然而,若不 Compact,空间碎片化问题同样恼人。可以使用分区等方式将物理上不连续的内存,化为逻辑上连续的。(硬盘正是这么做的)但这会降低程序的吞吐量

那么,本篇文章就到这里。下篇文章会介绍 HotSpot VM 实现的细节。

comments powered by Disqus