垃圾收集器与内存分配策略
4. 垃圾收集算法
-
分类
-
引用计数式垃圾收集（Reference Counting GC）
- 也称直接垃圾收集
- 由于引用计数式垃圾收集算法在主流Java虚拟机中均未涉及， 所以暂不讲解
-
追踪式垃圾收集（Trancing GC）
- 也称间接垃圾收集
- 以下所有算法均属于追踪式垃圾收集的范畴
-
-
分代收集理论
当前商业虚拟机的垃圾收集器，大多数遵循“分代收集”（Generational Collection）的理论进行设计。
-
定义
-
分代收集名为理论，实质是一套符合大多数程序运行实际情况的经验法则，其建立在两个分代假说之上：
- 弱分代假说（Weak Generational Hypothesis），绝大数对象都是朝生夕灭
- 强分代假说（Strong Generational Hypothesis），熬过越多次垃圾收集过程的对象就越难以消亡
-
-
具体内容
-
收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄分配到不同的区域之中储存。
年龄：对象熬过垃圾收集过程的次数。
如果一个区域中大多数对象都是朝生夕死，那么把他们集中在一起，每次回收只关注如何保留少量存活而不是去标记那些大量将要被回收的对象，就能以较低的代价回收大量的空间
如果剩下的都是难以消亡的对象，那把它们集中放在一起，使用较低的频率来回收这个区域，这样兼顾了垃圾收集的时间开销和内存空间的有效利用
-
-
垃圾收集器分类
-
根据收集区域划分
- Minor GC（新生代收集），指目标只是新生代的垃圾收集
- Major GC（老年代收集），指目标只是老年代的垃圾收集
- Mixed GC（混合收集），指目标是收集整个新生代以及部分老年代的垃圾收集
- Full GC（整堆收集），收集整个Java堆和方法区的垃圾收集
-
根据针对区域对象划分
- 标记-复制算法
- 标记-清除算法
- 标记-整理算法
-
-
分代收集理论发展
分代收集并非只是简单划分一下内存区域那么容易，它至少存在一个明显的困难：对象不是孤立的，对象之间会存在跨代引用。为了保证可达性分析结果正确，需要在固定GC Root外，遍历整个老年代的所有对象，这样会带来很大的性能负担。
-
对分代收集理论添加第三条经验法则：
- 跨代引用假说（Intergenerational Reference Hypothesis）：跨代引用相对于同代引用来说，仅占极少数
-
具体内容
- 第三条假说其实是可以根据前两条假说的隐含推论，存在互相引用的两个对象是应该倾向于同时生存或同时消亡
- 依据此假说，不应该为少量的跨代引用去扫描整个老年代，也不必浪费空间记录每个对象是否存在及存在哪些跨代引用
- 只需在新生代上建立一个全局的数据结构（记忆集），把老年代划分为若干小块，标识出老年代的哪一块内存会存在跨代引用，发生Minor GC时，只有包含跨代引用的小块内存的对象才会加入到GC Root中进行扫描，进行可达性分析
- 因此需要在对象改变引用关系时维护记录数据的正确性，这样会增加开销，但比起扫描整个老年代仍是划算的
-
-
-
标记-清除算法
-
诞生
- 最早出现也是最基础的垃圾收集算法
- 1960年由Lisp之父John McCarthy提出
-
原理
- 算法分为“标记”和“清除”两个阶段
- 首先标记出所有需要回收的对象，在标记完成后，统一回收掉所有被标记的对象
- 反过来，标记存活的对象，统一回收所有未被标记的对象
标记-清除算法示意图-
缺陷
-
执行效率不稳定
- 如果堆中包含大量对象，而且其中大部分需要回收，这就需要进行大量标记和清除动作，导致标记和清除过程的执行效率随着对象数量的增长而降低
-
内存空间碎片化
- 标记、清除后会产生大量不连续的内存碎片，空间碎片太多可能导致程序在分配较大对象时无法找到足够连续内存而提前触发另一次垃圾收集动作
-
-
-
标记-复制算法
-
解决问题
- 解决标记-清除算法面对大量可回收对象时执行效率低的问题
-
诞生
- 1969年Fenichel提出了一种称为“半区复制”（Semispace Copying）的垃圾收集算法
-
原理
- 将可用内存按容量划分为大小相等的两块，每次只使用其中的一块
- 当这一块的内存用完，就将还存活的对象复制到另一块上面，然后把之前使用过的内存空间一次清理掉
- 每次都是针对整个半区进行内存回收，分配内存时也就不用考虑由空间碎片的复杂情况
标记-复制算法示意图-
缺陷
- 这种算法会产生大量的内存间复制的开销
- 将可用内存缩小为原来的一半，空间浪费太多
-
更优化的半区复制分代策略--Apple式回收
- 把新生代分为一块较大的Eden空间和两块较小的Survivor空间，每次分配内存只使用Eden和其中一块Survivor
- 当发生垃圾收集，将Eden和Survivor中仍存活的对象一次性复制到另一块Survivor空间上，然后直接清理掉Eden和已用过的那块Survivor空间
- HotSpot虚拟机默认Eden和Survivor的大小比例是8：1，也就是每次新生代中可用的空间为整个新生代容量的90%，只有一个Survivor空间（10%新生代）会被浪费
- 当Survivor空间不足以容纳一次Minor GC之后存活的对象时，就需要依赖其他内存区域（实际上大多就是老年代）进行分配担保（Handle Promotion）
-
-
标记-整理算法
-
解决问题
- 解决标记-复制算法在对象存活较高时需要进行较多复制操作而效率降低的问题
- 另外，如果不想浪费50%的空间，就需要额外的空间进行分配担保，应对被使用内存中所有对象都存活的极端情况，标记-整理算法也解决了这个问题
-
诞生
- 标记-复制算法不适合老年代
- 1974年Edward Lueders提出了另一种有针对性地“标记-整理”（Mark-Compact）算法
-
原理
- 标记过程与标记-清除算法一样
- 而后让所有存活的对象都向内存空间一端移动，然后直接清除边界以外的内存
标记-整理算法示意图-
缺陷
- 在老年代每次回收都有大量对象存活，标记-整理算法移动存活对象并更新所用引用这些对象的地方，会是极为负重的操作
- 而且移动对象操作必须全程暂停用户应用程序才能进行，描述为“Stop The World”
-
标记-清除算法和标记-整理算法风险决策
标记-清除算法，不移动和整理存活对象，内存分配时会更复杂，因内存分配和访问相比垃圾收集频率要高得多，会更加影响应用程序吞吐量；CMS收集器采用该算法
-
标记-整理算法，移动和整理存活对象，内存回收时会更复杂，但就吞吐量来说，该算法更划算；Paralle1 Scavenge收集器采用该算法
吞吐量：实质是赋值器（Mutator，可以理解为使用垃圾收集的用户程序，为了便于理解，多数地方用“用户程序”或“用户线程”代替）与收集器的效率总和。
-
“和稀泥”式解决方案
- 让虚拟机平时多数时间都采用标记-清除算法，暂时容忍内存碎片的存在，直到内存空间的碎片化程度已经大到影响对象分配时，再采用标记-整理算法收集一次，以获得规整的内存空间
-
