垃圾回收算法
从如何判定对象消亡的角度出发, 垃圾收集算法可以划分为“引用计数器垃圾收集”(Reference Counting GC)和“追踪式垃圾收集”(Tracing GC)两大类. 这两类也常被称作“直接垃圾收集“和”间接垃圾收集“. 但是引用计数式垃圾收集算法在主流Java虚拟机中均为涉及.
分代收集理论
分代收集理论建立在两个分代假说之上:
- 弱分代假说(Weak Generational Hypothesis) 绝大多数对象都是朝生夕灭的.
- 强分代假说(Strong Generational Hypothesis) 熬过越多次垃圾收集过程的对象就越难以消亡.
这两个假说奠定了多款常用垃圾收集器的设计原则: 收集器应该将Java堆划分出不同的区域, 然后将回收对象依据其年龄(对象熬过垃圾收集过程的次数)分配到不同的区域之中. — 如果一个区域中大多数对象都是朝生夕灭,难以熬过垃圾收集过程的话,那
么把它们集中放在一起,每次回收时只关注如何保留少量存活而不是去标记那些大量将要被回收的对象, 就能以较低代价回收到大量的空间;如果剩下的都是难以消亡的对象,那把它们集中放在一块, 虚拟机便可以使用较低的频率来回收这个区域,这就同时兼顾了垃圾收集的时间开销和内存的空间有效利用
一般会把Java堆划分为新生代(Young Generation)和老年代(Old Generation)两个区域, 在新生代中,每次垃圾收集时都有大批对象死去,而每次回收后存活的少量对象,将会逐步晋升到老年代中存放.
当对新生代区域进行一次回收时,新生代中的对象完全有可能被老年代所引用,为了找出该区域的存活对象,需要在原有的GC Roots之外再额外遍历整个老年代中所有对象,这样才能确保结果准确. 反过来回收老年代时也需要引用整个新生代. 这样会对内存带来很大的性能负担. 但我们根据经验可以在原有但假说之上再添加一条:
- 跨代引用假说(Intergenerational Reference Hypothesis) : 跨代引用相对于同代引用来说仅占极少数.
依据这条假说, 我们就不应再为了少量的跨代引用去扫描整个老年代,也不必浪费空间专门记录每一个对象是否存在及存在哪些跨代引用, 只需在新生代上建立一个全局的数据结构(称为 记忆集 Remembered Set), 这个结构把老年代划分为若干小块, 标识出老年代的哪一块内存会存在跨代引用. 当进行垃圾回收时, 只需要将存在跨代引用的这一小块内存中的对象加入GC Roots中即可. — 这种方法需要对象在改变引用关系时维护记录数据的正确性.
几种垃圾回收的名词:
- 部分收集(Partial GC)
- 新生代收集(Minor GC/Young GC) : 只针对新生代进行收集
- 老年代收集(Major GC/Old GC) : 只针对老年代进行收集
- 混合收集(Mixed GC) : 收集整个新生代和部分老年代. 目前只有G1收集器有这种行为.
- 整堆收集(Full GC): 收集整个Java堆和方法区
标记-清除算法
该算法分为标记和清除两个阶段
- 标记出所有需要回收的对象,
- 标记完成后回收掉所有被标记的对象
也可以反过来, 标记时标记要保留的对象, 回收时回收没被标记过的对象.
该算法简单, 后续的算法也大多基于此算法改进. 该算法的主要缺点有两个:
- 执行效率不稳定, 如果Java堆中包含大量对象,并且大部分是需要回收的,这时就必须进行大量的标记和清除工作, 标记和清除过程的效率随对象数量增加而降低.
- 内存空间的碎片化问题, 清除后会造成大量不连续的内存碎片, 这会导致在分配较大对象时无法找到足够的连续内存而又一次触发垃圾回收
标记-复制算法
将可用内存按容量划分为大小相等的两块,每次只使用其中的一块,当这一块的内存用完时,将还存活的对象复制到另一块中去, 然后再将刚刚这块内存一次清除掉, 在复制对象时也可以解决空间碎片的问题.
该算法的缺点是:
- 如果内存中大多数对象都是存活的, 这种算法会产生大量内存间复制的开销.
- 内存空间缩减为了原来的一半, 空间浪费太多.
优化的半区复制分代策略
将新生代划分为一块较大的Eden空间和两块较小的Survivor空间, 每次分配内存只使用Eden和其中一块Survivor. 当发送垃圾搜集时, 将Eden和Survivor中仍然存活的对象一次性复制到另外一块Survivor空间上. 然后直接清理掉Eden和刚刚用到的Survivor空间.
HotSpot虚拟机默认Eden和Survivor的大小比例为8:1. 每次新生代中可用内存空间为整个新生代容量的90%. 只有10%的空间(一个Survivor)被浪费了.
但是我们无法确定一个Survivor空间(10%)能否满足存活对象所需占有的空间. 当Survivor空间不足以容纳一次Minor GC之后存活的对象时, 就需要依赖其他内存区域(大多是老年代)进行分配担保.
标记-整理算法
标记-复制算法在对象存活率较高时需要进行较多的复制操作, 导致效率降低. 关键的是, 如果不想浪费50%的空间, 就需要有额外的空间进行分配担保, 以应对被使用的内存中所有对象都100%存活的极端情况. 所以这种算法不能在老年代中使用.
标记-整理算法: 标记过程与之前一样, 后续的步骤不是直接对可回收对象进行整理, 而是让所有存活的对象都向内存空间一端移动, 然后直接清理掉边界以外的内存.
标记-清除算法与标记-整理算法的本质差异在于前者是一种非移动式的回收算法, 而后者是移动式的.
是否移动回收后的存活对象是一项优缺点并存的风险决策:
- 如果移动存活对象,尤其是在老年代这种每次回收都有大量对象存活区域,移动存活对象并更新所有引用这些对象的地方将会是一种极为负重的操作,而且这种对象移动操作必须全程暂停用户应用程序才能进行
- 如果跟标记-清除算法不考虑移动和整理存活对象的话, 空间碎片化问题只能依赖更为复制的方案(譬如, 分区空闲分配链表)来解决,这样会影响应用程序的吞吐量.
基于以上两点, 是否移动对象都存在弊端, 移动则内存回收时会更复杂, 不移动则内存分配时会更复杂. 从垃圾收集的停顿时间来看, 不移动对象停顿时间会更短, 甚至可以不需要停顿,但是从整个程序的吞吐量来看,移动对象会更划算. HotSpot虚拟机里面关注吞吐量的ParallelScavenge收集器是基于标记-整理算法的, 而关注延迟的CM S收集器则是基于标记-清除算法的.