关于jvm虚拟机:分代收集理论与垃圾回收算法

垃圾回收算法

垃圾收集算法的实现波及大量的程序细节，且各个平台的虚拟机操作内存的办法都有差别，此处咱们暂不过多探讨算法实现，只重点介绍 分代收集实践和几种算法思维 及其倒退过程。

从如何断定对象沦亡的角度登程，垃圾收集算法能够划分为：

• “援用计数式垃圾收集”（Reference Counting GC），也常被称作“间接垃圾收集”
• “追踪式垃圾收集”（Tracing GC），也常被称作“间接垃圾收集”

因为援用计数式垃圾收集算法在支流 Java 虚拟机中均未波及，所以上面介绍的所有算法均属于追踪式垃圾收集的领域。

分代收集实践

强、弱分代假说

以后商业虚拟机的垃圾收集器，大多数都遵循了 “分代收集”（Generational Collection） 的实践 [1] 进行设计，分代收集名为实践，本质是一套合乎大多数程序运行理论状况的教训法令，它建设在两个分代假说之上：

1. 弱分代假说（Weak Generational Hypothesis）：绝大多数对象都是朝生夕灭的。
2. 强分代假说（Strong Generational Hypothesis）：熬过越屡次垃圾收集过程的对象就越难以沦亡。

[1]值得注意的是，分代收集实践也有其缺点，最新呈现（或在试验中）的几款垃圾收集器都展现出了面向全区域收集设计的思维，或者能够反对全区域不分代的收集的工作模式。

这两个分代假说独特奠定了 多款罕用的垃圾收集器的统一的设计准则：

1. 收集器应该将 Java 堆划分出不同的区域，而后将回收对象根据其年龄（年龄即对象熬过垃圾收集过程的次数）调配到不同的区域之中存储。（分代解决）
2. 如果一个区域中大多数对象都是朝生夕灭，那么每次回收时只须关注如何保留大量存活的对象，就能以较低代价回收到大量的空间；（解决新生代）
3. 如果一个区域中大多数对象都是难以沦亡的，那么虚拟机便能够应用较低的频率来回收这个区域，这就同时兼顾了垃圾收集的工夫开销和内存的空间无效利用。（解决老年代）

在 Java 堆划分出不同的区域之后：

• 垃圾收集器才能够每次只回收其中某一个或者某些局部的区域——因此才有了“Minor GC”“Major GC”“Full GC”这样的 回收类型的划分；
• 针对不同的区域应用相匹配的垃圾收集算法——因此倒退出了“标记 - 复制算法”“标记 - 革除算法”“标记 - 整顿算法”等 针对性的垃圾收集算法。

把分代收集实践具体放到当初的商用 Java 虚拟机里，设计者个别至多会把 Java 堆划分为 新生代（Young Generation）和 老年代（Old Generation）两个区域。顾名思义，在新生代中，每次垃圾收集时都发现有少量对象死去，而每次回收后存活的大量对象，将会逐渐降职到老年代中寄存。

跨代援用假说

但不同区域的对象不是孤立的，对象之间会存在跨代援用，比方新生代中的对象齐全有可能被老年代中的对象援用。所以如果只须要进行新生代的一次垃圾收集，为确保可达性剖析正确，就还须要遍历整个老年代中的所有对象，反之也一样[2]。但遍历所有的老年代对象的计划会带来很大的性能累赘，为了解决这个问题，就须要应用第三条教训法令：

1. 跨代援用假说（Intergenerational Reference Hypothesis）：跨代援用绝对于同代援用来说仅占极少数。

[2]通常能独自产生收集行为的只是新生代，所以这里“反过来”的状况只是实践上容许，实际上除了 CMS 收集器，其余都不存在只针对老年代的收集。

根据这条假说，咱们就不应再为了大量的跨代援用去扫描整个老年代，也不用节约空间专门记录每一个对象是否存在及存在哪些跨代援用，只需在新生代上建设一个全局的数据结构（该构造被称为“记忆集”，Remembered Set），这个构造把老年代划分成若干小块，标识出老年代的哪一块内存会存在跨代援用。尔后当产生 Minor GC 时（指新生代的垃圾收集），只有蕴含了跨代援用的小块内存里的对象才会被退出到 GC Roots 进行扫描。尽管这种办法须要在对象扭转援用关系（如将本人或者某个属性赋值）时保护记录数据的正确性，会减少一些运行时的开销，但比起收集时扫描整个老年代来说依然是划算的。

为防止产生混同，这里对立定义一下 回收类型的划分：

• 局部收集（Partial GC）：指指标不是残缺收集整个 Java 堆的垃圾收集，其中又分为：

  • 新生代收集（Minor GC/Young GC）：指指标只是新生代的垃圾收集。
  • 老年代收集（Major GC/Old GC）：指指标只是老年代的垃圾收集。目前只有 CMS 收集器会有独自收集老年代的行为。另外请留神“Major GC”这个说法在不同材料上常有不同所指，需按上下文辨别到底是指老年代的收集还是整堆收集。
• 混合收集（Mixed GC）：指指标是收集整个新生代以及局部老年代的垃圾收集。目前只有 G1 收集器会有这种行为。
• 整堆收集（Full GC）：收集整个 Java 堆和办法区的垃圾收集。

标记 - 革除算法

最早呈现也是最根底的垃圾收集算法是“标记 - 革除”（Mark-Sweep）算法，在 1960 年由 Lisp 之父 John McCarthy 所提出。

算法分为“标记”和“革除”两个阶段：

• 首先标记出所有须要回收的对象，在标记实现后，对立回收掉所有被标记的对象
• 也能够反过来，标记存活的对象，对立回收所有未被标记的对象。

所以不论标记的是什么对象，革除的始终是垃圾对象。标记过程就是对象是否属于垃圾的断定过程，即可达性剖析算法的过程。

后续的收集算法大多都是以标记 - 革除算法为根底，对其毛病进行改良而失去的。它的次要毛病有两个：

1. 执行效率不稳固。如果 Java 堆中蕴含大量对象，且其中大部分是须要被回收的，就必须进行大量标记和革除的动作，导致标记和革除两个过程的执行效率都随对象数量增长而升高；
2. 内存空间的碎片化。标记、革除之后会产生大量不间断的内存碎片，空间碎片太多可能会导致当当前在程序运行过程中须要调配较大对象时无奈找到足够的间断内存而不得不提前触发另一次垃圾收集动作。

标记 - 复制算法

标记 - 复制算法常被简称为复制算法。

半区复制

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

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

半区复制算法的长处：

1. 对于少数对象都是可回收的状况，算法须要复制的就是占多数的存活对象，执行效率高
2. 每次都是针对整个半区进行内存回收，分配内存时也就不必思考有空间碎片的简单状况，只有挪动堆顶指针，按程序调配即可。

当初的商用 Java 虚拟机大多都优先采纳了这种收集算法去回收新生代，不过并不需要依照 1∶1 的比例来划分新生代的内存空间。

Appel 式回收

在 1989 年，Andrew Appel 针对具备“朝生夕灭”特点的对象，提出了一种 更优化的半区复制分代策略，当初称为“Appel 式回收”。HotSpot 虚拟机的 Serial、ParNew 等新生代收集器均采纳了这种策略来设计新生代的内存布局[1]。Appel 式回收的具体做法是：

1. 把新生代分为一块较大的 Eden 空间和两块较小的 Survivor 空间，每次分配内存只应用 Eden 和其中一块 Survivor。
2. 产生垃圾收集时，将 Eden 和 Survivor 中依然存活的对象一次性复制到另外一块 Survivor 空间上，而后间接清理掉 Eden 和已用过的那块 Survivor 空间。

HotSpot 虚拟机默认 Eden 和 Survivor 的大小比例是 8∶1，也即每次新生代中可用内存空间为整个新生代容量的 90%（Eden 的 80% 加上一个 Survivor 的 10%），只有一个 Survivor 空间，即 10% 的新生代是会被“节约”的。

但任何人都没有方法百分百保障每次回收都只有不多于 10% 的对象存活，因而 Appel 式回收还有一个充当常见状况的 “逃生门”的平安设计，当 Survivor 空间不足以包容一次 Minor GC 之后存活的对象时，就须要依赖其余内存区域（实际上大多就是老年代）进行 调配担保（Handle Promotion）。

标记 - 整顿算法

老年代个别不能间接应用标记 - 革除算法，因为：

1. 标记 - 复制算法在对象存活率较高时就要进行较多的复制操作，效率将会升高。
2. 如果不想节约 50% 的空间，就须要有额定的空间进行调配担保，以应答所有对象都 100% 存活的极其状况

针对老年代对象的存亡特色，1974 年 Edward Lueders 提出了另外一种有针对性的“标记 - 整顿”（Mark-Compact）算法，其中的标记过程依然与“标记 - 革除”算法一样，但后续步骤不是间接对可回收对象进行清理，而是让所有存活的对象都向内存空间一端挪动，而后间接清理掉边界以外的内存。

标记 - 革除算法与标记 - 整顿算法的实质差别在于前者是一种非移动式的回收算法，而后者是移动式的。是否挪动回收后的存活对象是一项优缺点并存的危险决策：

1. 如果挪动存活对象，挪动存活对象并更新所有援用这些对象的中央将会是一种极为负重的操作，而且这种 对象挪动操作必须全程暂停用户应用程序 能力进行[1]，这样的进展被最后的虚拟机设计者形象地形容为“Stop The World”[2]。
2. 但如果跟标记 - 革除算法那样齐全不思考挪动和整顿存活对象的话，弥散于堆中的存活对象导致的空间碎片化问题就只能依赖更为简单的内存分配器和内存拜访器来解决。譬如通过 “分区闲暇调配链表” 来解决内存调配问题（计算机硬盘存储大文件就不要求物理间断的磁盘空间，可能在碎片化的硬盘上存储和拜访就是通过硬盘分区表实现的）。内存的拜访是用户程序最频繁的操作，甚至都没有之一，如果在这个环节上减少了额定的累赘，势必会间接 影响应用程序的吞吐量。

【1】最新的 ZGC 和 Shenandoah 收集器应用读屏障（Read Barrier）技术实现了整顿过程与用户线程的并发执行
【2】通常标记 - 革除算法也是须要进展用户线程来标记、清理可回收对象的，只是进展工夫相对而言要来的短而已。

基于以上两点，是否挪动对象都存在弊病，挪动则内存回收时会更简单，不挪动则内存调配时会更简单。

从垃圾收集的进展工夫来看，不挪动对象进展工夫会更短，甚至能够不须要进展，然而从整个程序的吞吐量来看，挪动对象会更划算。HotSpot 虚拟机外面关注吞吐量的 Parallel Scavenge 收集器是基于标记 - 整顿算法的，而关注提早的 CMS 收集器则是基于标记 - 革除算法的，这也从侧面印证这点。

另外，还有一种 “和稀泥式”解决方案 能够不在内存调配和拜访上减少太大额外负担，做法是让虚拟机平时少数工夫都采纳标记 - 革除算法，临时容忍内存碎片的存在，直到内存空间的碎片化水平曾经大到影响对象调配时，再采纳标记 - 整顿算法收集一次，以取得规整的内存空间。后面提到的 基于标记 - 革除算法的 CMS 收集器面临空间碎片过多时采纳的就是这种解决方法。

集体总结

分代收集实践的三个假说是什么？

1. 弱分代假说（Weak Generational Hypothesis）：绝大多数对象都是朝生夕灭的。
2. 强分代假说（Strong Generational Hypothesis）：熬过越屡次垃圾收集过程的对象就越难以沦亡。
3. 跨代援用假说（Intergenerational Reference Hypothesis）：跨代援用绝对于同代援用来说仅占极少数。

三个分代假说的作用别离是什么？

1. 弱分代假说和强分代假说领导 Java 堆划分为了不同的区域，不同区域寄存不同年龄的对象，在不同区域上应用不同的垃圾收集算法。
2. 跨代援用假说领导咱们在进行新生代区域的垃圾收集时，不用为了大量的跨代援用去扫描整个老年代的对象，只须要扫描局部存在跨代援用的老年代的对象。

回收类型划分的个别定义是什么？

• 局部收集（Partial GC）：指指标不是残缺收集整个 Java 堆的垃圾收集，其中又分为：

  • 新生代收集（Minor GC/Young GC）：指指标只是新生代的垃圾收集。
  • 老年代收集（Major GC/Old GC）：指指标只是老年代的垃圾收集。目前只有 CMS 收集器会有独自收集老年代的行为。另外请留神“Major GC”这个说法在不同材料上常有不同所指，需按上下文辨别到底是指老年代的收集还是整堆收集。
• 混合收集（Mixed GC）：指指标是收集整个新生代以及局部老年代的垃圾收集。目前只有 G1 收集器会有这种行为。
• 整堆收集（Full GC）：收集整个 Java 堆和办法区的垃圾收集。

标记 - 革除算法的毛病？

• 执行效率不稳固。如果 Java 堆中蕴含大量对象，且其中大部分是须要被回收的，就必须进行大量标记和革除的动作，导致标记和革除两个过程的执行效率都随对象数量增长而升高；所以不适用于新生代，更适宜老年代。
• 标记、革除之后会产生大量不间断的内存碎片

标记 - 复制算法次要利用在哪局部空间？HotSpot 中的新生代内存默认是怎么划分的？

1. 标记 - 复制算法次要利用在堆的新生代。
2. Appel 式回收将新生代划分为一块 Eden 空间和两块 Survivor 空间，HotSpot 默认 Eden 和 Survivor 的大小比例是 8∶1。

标记 - 整顿算法的过程是怎么的？标记 - 整顿和标记 - 革除算法的区别是什么？

1. 标记整顿算法的标记过程与“标记 - 革除”算法一样，但后续步骤不是间接对可回收对象进行清理，而是让所有存活的对象都向内存空间一端挪动，而后间接清理掉边界以外的内存。

2. 标记 - 革除算法与标记 - 整顿算法的实质差别在于前者是一种非移动式的回收算法，而后者是移动式的。

   1. 挪动则内存回收时会更简单，进展工夫更长，但整个程序的吞吐量高。
   2. 不挪动则内存调配时会更简单，整个程序吞吐量低，但进展工夫更短。

参考资料

• 《深刻了解 Java 虚拟机（第三版）》