JVM 垃圾收集算法理论

垃圾收集算法的实现涉及大量程序细节,且各个平台的虚拟机操作内存的方法都有差异。本文暂不过多讨论算法实现,只重点介绍分代收集理论和几种算法思想及其发展过程。

从如何判定对象消亡的角度出发,垃圾收集算法可以划分为“引用计数式垃圾收集” (Reference Counting GC) 和“追踪式垃圾收集” (Tracing GC) 两大类,本节介绍的所有算法均属于追踪式垃圾收集的范畴。

1 分代收集理论

1.1 收集类型划分

当前商业虚拟机的垃圾收集器,大多数都遵循了“分代收集”的理论进行设计,按照不同的年代或区域划分,可以概括为以下几种收集方式:

  • 部分收集 (Partial GC):指目标不是完整收集整个 Java 堆的垃圾收集,其中又分为:
    • 新生代收集 (Minor GC/Young GC):指目标只是新生代的垃圾收集。
    • 老年代收集 (Major GC/Old GC):指目标只是老年代的垃圾收集。

      目前只有 CMS 收集器会有单独收集老年代的行为。另外请注意 “Major GC” 这个说法现在有点混淆,在不同资料上常有不同所指,需按上下文区分到底是指老年代的收集还是整堆收集。

  • 混合收集 (Mixed GC):指目标是收集整个新生代以及部分老年代的垃圾收集。

    目前只有 G1 收集器会有这种行为。

  • 整堆收集 (Full GC):收集整个 Java 堆和方法区的垃圾收集。

1.2 分代假说

分代收集名为理论,实质是一套符合大多数程序运行实际情况的经验法则,它建立在两个分代假说之上:

  1. 弱分代假说 (Weak Generational Hypothesis):绝大多数对象都是朝生夕灭的。

  2. 强分代假说 (Strong Generational Hypothesis):熬过越多次垃圾收集过程的对象就越难以消亡。

    这两个分代假说共同奠定了多款常用的垃圾收集器的设计原则:

    • 将 Java 堆划分为不同的区域,将回收对象根据其年龄分配到不同的区域存储。
      • 如果一个区域中大多数对象朝生夕灭,难以熬过垃圾收集过程,将它们集中存储可以以较低的代价回收大量空间;
      • 如果剩下的对象难以消亡,集中存储也能降低垃圾收集的频率,兼顾时间和空间的效率。
    • 划分 Java 堆的不同区域之后,垃圾收集器可以每次只回收其中某一个或几个区域,进而划分出 “Minor GC”、“Major GC” 和 “Full GC” 等回收类型;同时也可以针对不同的区域使用与存储对象生命周期特征相匹配的垃圾收集算法,比如“标记-复制算法”、“标记-清除算法”、“标记-整理算法”等。

    把分代收集理论具体放到现在的商用 Java 虚拟机里,设计者一般至少会把 Java 堆划分为新生代 (Young Generation) 和老年代 (Old Generation) 两个区域。顾名思义,在新生代中,每次垃圾收集时都会有大批对象死去,而每次回收后存活的少量对象,将会逐步晋升到老年代中存放。

    注释
    HotSpot 虚拟机源码里存在着一些名为 *Generation 的实现,如 DefNewGenerationParNewGeneration 等,这些就是 HotSpot 的“分代式垃圾收集器框架”。原本 HotSpot 鼓励开发者尽量在这个框架内开发新的垃圾收集器,但除了最早期的两组四款收集器之外,后来的开发者并没有继续遵循规范。导致此事的原因有很多,最根本的是分代收集理论仍在不断发展之中,如何实现也有许多细节可以改进,被既定的代码框架约束反而不便。

    经过仔细思考,我们会发现分代收集并不是简单地划分内存区域那么容易。它存在一个明显的困难,就是对象之间存在跨代引用。当执行只局限于新生代区域内的收集 (Minor GC) 时,新生代中的对象可能被老年代所引用。为了找出该区域中的存活对象,就需要在固定的 GC Roots 之外,额外遍历整个老年代中所有对象来确保可达性分析结果的正确性。反过来 1 也是一样。虽然理论上遍历整个老年代所有对象的方案可行,但这无疑会为内存回收带来很大的性能负担。

    为了解决这个问题,就需要对分代收集理论添加第三条经验法则:

  3. 跨代引用假说 (Intergenerational Reference Hypothesis):跨代引用相对于同代引用来说仅占极少数。

    这其实是根据前两条假说进行的逻辑推理得出的隐含推论:存在互相引用关系的两个对象应倾向于同时生存或消亡。例如,如果某个新生代对象存在跨代引用,由于老年代对象难以消亡,该引用会使得新生代对象在收集时同样存活,进而在年龄增长后晋升到老年代,此时跨代引用也会随之消除。

    依据这条假说,我们就不应再为了少量的跨代引用去扫描整个老年代,也不必浪费空间专门记录每一个对象是否存在及存在哪些跨代引用。而是在新生代上建立一个全局的数据结构,称为“记忆集”(Remembered Set),该结构把老年代划分成若干小块,标识出老年代的哪一块内存会存在跨代引用。此后,当发生 Minor GC 时,只有包含了跨代引用的小块内存里的对象才会被加入到 GC Roots 进行扫描。虽然这种方法需要在对象改变引用关系(如将自己或者某个属性赋值)时维护记录数据的正确性,会增加一些运行时的开销,但比起收集时扫描整个老年代来说仍然是划算的。

2 标记-清除算法

标记-清除 (Mark-Sweep) 算法是最早出现也是最基础的垃圾收集算法,在 1960 年由 Lisp 之父 John McCarthy 所提出。它将垃圾收集过程分为两个阶段:标记阶段和清除阶段:

  • 标记阶段:垃圾收集器会遍历所有从根对象(如 GC Roots)开始的引用链,标记所有存活的对象。在这个阶段结束后,所有存活的对象都被标记为“存活”。
  • 清除阶段:垃圾收集器会遍历整个内存,将没有标记的对象视为垃圾,进行回收。在这个阶段结束后,所有未被标记的对象都被清除,只剩下了被标记的存活对象。

算法的执行过程如下图所示:

标记-清除算法示意图

标记-清除算法的优点是实现简单,但是它也存在一些问题:

  • 内存碎片化。标记-清除算法只是将垃圾对象标记为可回收的,并不会进行内存整理,所以回收后的内存空间会产生碎片化,导致后续的内存分配过程变得复杂。
  • 效率低下。标记-清除算法需要两次遍历整个内存空间,其中标记阶段需要遍历所有存活对象,耗时较长,而清除阶段需要遍历所有未被标记的对象,同样比较耗时。
  • 可能会出现存活对象被误判为垃圾的情况。由于标记-清除算法只是将垃圾对象标记为可回收的,而没有进行内存整理,所以有可能会将一些存活对象误判为垃圾,将其清除掉。

因此,标记-清除算法已经不是现代垃圾收集器的首选算法,而更多地作为一种理论基础。现代垃圾收集器通常采用复合算法,将多种垃圾收集算法结合起来使用,以达到更好的垃圾收集效果。

3 标记-复制算法

为了解决标记-清除算法面对大量可回收对象时执行效率低的问题,1969 年 Fenichel 提出了一种称为“半区复制” (Semispace Copying) 的垃圾收集算法。

它将可用内存按容量划分为大小相等的两块,每次只使用其中的一块。当这一块的内存用完了,就将还存活着的对象复制到另外一块上面,然后再把已使用过的内存空间一次清理掉。

算法的执行过程如下图所示:

标记-复制算法示意图

如果内存中多数对象都是存活的,这种算法将会产生大量的内存间复制的开销,但对于多数对象都是可回收的情况,算法需要复制的就是占少数的存活对象,而且每次都是针对整个半区进行内存回收,分配内存时也就不用考虑有空间碎片的复杂情况,只要移动堆顶指针,按顺序分配即可。这样实现简单,运行高效。不过其缺陷也显而易见,这种复制回收算法的代价是将可用内存缩小为了原来的一半,空间浪费太多。而且这种算法在对象存活率较高时需要进行较多的复制操作,效率会降低。在老年代,由于对象存活率较高,如果也采用复制算法,那就需要额外的空间进行分配担保,以应对被使用的内存中所有对象都 100% 存活的极端情况。因此,在老年代一般不能直接选用这种算法。

3.1 优化复制算法

现今大部分商用 Java 虚拟机都倾向于采用标记-复制算法回收新生代,IBM 公司曾开展过一项研究,进一步量化了新生代中“朝生夕灭”对象的特点:据统计,有 98% 的对象无法熬过第一轮收集。因此,划分新生代内存空间的比例无需严格按照 1:1,而可以更加灵活。在 1989 年,Andrew Appel 针对这种具备“朝生夕灭”特点的对象,提出了半区复制分代策略的改进方案,现在被称为“Appel 式回收”。

HotSpot 虚拟机的 Serial、ParNew 等新生代收集器也独立研发了与之类似的策略来设计新生代的内存布局。具体做法是把新生代分为一块较大的 Eden 空间和两块较小的 Survivor 空间,每次分配内存只使用 Eden 和其中一块 Survivor。发生垃圾收集时,将 Eden 和用过的 Survivor 空间中仍然存活的对象一次性复制到另外一块 Survivor 空间上,然后直接清理掉 Eden 和已用过的那块 Survivor 空间。示意图如下:

HotSpot 标记-复制算法示意图

默认情况下,Eden 和 Survivor 的大小比例为 8:1,因此每次新生代中可用内存空间为整个新生代容量的 90%(Eden 的 80% 加上一个 Survivor 的 10%),但实际上每次回收存活的对象比例可能高于 10%。为应对这种情况,虚拟机实现了一种分配担保机制,当 Survivor 空间不足以容纳一次 Minor GC 后存活的对象时,会借用其他内存区域(通常是老年代)进行内存分配。

4 标记-整理算法

针对老年代对象的存亡特征,1974 年 Edward Lueders 提出了另外一种有针对性的标记-整理 (Mark-Compact) 算法。这种算法的标记过程仍然与标记-清除算法一样,但后续步骤不是直接对可回收对象进行清理,而是让所有存活的对象都向内存空间一端移动,然后直接清理掉边界以外的内存。示意图如下图所示:

标记-整理算法示意图

如果移动存活对象,尤其是在老年代这种每次回收都有大量对象存活区域,移动存活对象并更新所有引用这些对象的地方将会是一种极为负重的操作,而且这种对象移动操作必须全程暂停用户应用程序才能进行,这就更加让使用者不得不小心翼翼地权衡其弊端了,像这样的停顿被最初的虚拟机设计者形象地描述为 “Stop The World2"。

但如果跟标记-清除算法那样完全不考虑移动和整理存活对象的话,弥散于堆中的存活对象带来的空间碎片化问题就只能依赖更为复杂的内存分配器和内存访问器来解决,比如使用空闲列表来维护内存碎片。由于内存申请是 Java 程序中最频繁的操作,引入这种额外的操作势必会影响应用的吞吐量。

由上可知,移动或者不移动对象都有各自的利弊:移动则内存回收时会更复杂,不移动则内存分配时会更复杂。从垃圾收集的停顿时间来看,不移动对象停顿时间会更短,甚至可以不需要停顿,但是从整个程序的吞吐量 3 来看,移动对象会更划算。即使不移动对象会使得收集器的效率提升一些,但因为内存分配和访问相比垃圾收集频率要高得多,这部分的耗时增加,总吞吐量仍然是下降的。

另外,还有一种混合方案:虚拟机在平时多数时间采用标记-清除算法,暂时容忍内存碎片存在,直到内存空间碎片化程度超过阈值时,再采用标记-整理算法。基于标记-清除算法的 CMS 收集器面临空间碎片过多时采用的就是这种处理办法。


  1. 通常能单独发生收集行为的只是新生代,所以这里“反过来”的情况只是理论上允许,实际上除了 CMS 收集器,其他收集器都不存在只针对老年代的收集。 ↩︎

  2. 通常标记-清除算法也是需要停顿用户线程来标记、清理可回收对象的,只是停顿时间相对而言要来的短而已。 ↩︎

  3. 此语境中,吞吐量的实质是赋值器(Mutator,可以理解为使用垃圾收集的用户程序)与收集器的效率总和。 ↩︎


欢迎关注我的公众号,第一时间获取文章更新:

微信公众号

相关内容