常见的垃圾回收算法及细节实现_垃圾回收算法与实现 垃圾回收算法手册

分代收集理论

目前主流的虚拟机的垃圾收集器大多都遵循了“分代收集理论”进行设计。实际上是建立在两个假说的基础上的：

• 弱分代假说（Weak Generational Hy pothesis）：绝大多数对象都是朝生夕死（用完即可扔~）
• 强分代假说（Strong Generational Hy pothesis）：经过多次垃圾回收都没有被回收掉的对象就越不容易被回收

基于上边这两种假说，收集器应该将Java堆划分为不同的区域，然后回收对象依据其年龄生活在不同的区域。也就是将朝生夕死，难以熬过前几次垃圾收集的对象放到一个区域，这个区域只需要关注那些存活的对象，而不需要去管那些大量即将要被回收的对象；将经过多次垃圾回收都没被回收掉的对象放到一个区域，由于这个区域的对象很难被回收掉，因此可以使用较低的频率来回收这个区域。这样就同时兼顾了垃圾收集的时间开销和内存空间的有效利用。
​

后边讲解的“标记-清除”、“标记-复制”、“标记-整理”算法都是基于这个分代理论来设计的。但是分代收集有一个很明显的问题，就是“跨代引用”问题。解决“跨代引用”可以通过在收集新生代时遍历所有的老年代对象来确保对象是可回收的，但无疑会为内存回收带来很大的性能负担。因此引出了第三条经验法则：

• 跨代引用假说：跨代引用相对于同代引用来说占极少数

存在相互引用的对象应该是同时生存或者消亡的。例如，某个新生代的对象被老年代的对象引用，在新生代垃圾回收时，由于存在跨代引用，因此新生代的对象不能被回收，当多次回收后新生代的对象也会被提升到老年代中，跨代引用也随之消失了。

这条假说告诉我们不需要为了解决跨代引用而去扫描整个老年代所有的对象，也不必浪费空间专门记录新生代有哪些对象存在跨代引用，只需要在新生代中建立一个全局的数据结构（“记忆集”），这个结构把老年代划分为若干个区域，标识出老年代哪一块内存可能存在跨代引用，此后在发生Minor GC时，只有包含了跨代引用关系的小块内存里的对象才会被假如GC Roots进行扫描，这种办法需要在对象改变了引用关系的时维护记录数据的正确性。
​

• Minor GC/Yong GC：新生代收集吗，只是收集新生代
• Major GC/Old GC：老年代收集，指目标只是老年代的垃圾收集。目前只有CMS垃圾收集器会有单独收集老年代的行为。
• Mixed GC：收集整个新生代和部分老年代，目前只有G1垃圾收集器会有这种行为
• Full GC：整堆收集，收集整个Java堆和方法区的垃圾收集。
  

常见垃圾收集算法

标记清除算法

分为“标记”和“清除”两个阶段：首先标记出所有需要回收的对象，在标记完成后，统一回收掉所有被标记的对象，也可以反过来。
缺点：

1. 执行效率不稳定，如果Java堆中包含大量对象，而且大部分是需要回收的，这时必须进行大量的标记和清除的动作，导致标记和清除两个过程的执行效率都是随对象数量增长而下降；
2. 内存空间的碎片化问题，标记-清除之后会产生大量不连续的空间碎片，空间碎片太多可能会导致大对象分配内存时无法找到足够连续的内存而不得不触发一次垃圾回收动作。

标记复制算法

为了解决标记-清除算法在面对大量可回收对象时执行效率低的问题，69年有人提出了“半区复制”的垃圾收集算法，它将可用内存划分为两块，每次只使用其中的一块，当这一块用完了就将存活的对象复制到另一块上，再把已使用的内存空间一次性清理掉。
缺点：

1. 如果内存中剩余存活的对象较多，那么这种算法将产生大量的内存复制开销，因此这种算法不适合老年代，对于存活的只是很小一部分对象的情况就很合适了，并且每次只使用一半内存，复制过去也不用考虑空间碎片的问题，只需要顺序分配内存即可。
2. 只能使用一半内存，空间浪费。
3. 需要停顿用户线程来标记、清理可回收对象，停顿时间相对于下边讲的“标记-整理”算法停顿时间要短

标记整理算法

由于“标记-复制”算法在对象存活较多情况下，复制开销较大，因此不适合在对象不易被回收的老年代使用，更关键的是，由于复制算法会浪费一半的空间使用，对于老年代这种大部分对象都是不会被回收的区域，一般不会选复制算法。
针对老年代对象的特征，74年提出了另外一种有针对性的“标记-整理（Mark Compact）”算法，其中的标记过程与“标记-清除”算法的标记过程是相同的，但后续步骤不是直接将可回收对象回收，而是将存活对象都向内存空间另一端移动，然后直接清理掉边界以外的内存。


两种算法的本质差异在于，前一种是非移动式的回收算法，后一种是移动式的回收算法。
是否移动回收后存活的对象是一项优缺点并存的风险决策：

• 如果移动对象，在老年代这种每次收集都有大量存活对象的区域，移动存活对象并更新所有引用这些对象的地方将会是一种极为负重的操作，而且这种对象移动操作必须STW才可以（最新的ZGC和Shenandoah收集器使用读屏障技术实现了整理过程与用户线程的并发执行）
• 如果不移动对象，那么面对这种大量不连续的内存空间就只能依赖更为复杂的内存分配器和内存访问器来解决，但是针对内存访问的操作，增加额外的负担，势必会影响程序的吞吐量。

基于以上两点，是否移动对象都存在弊端，移动则回收更为复杂，不移动则分配内存更为复杂，从垃圾回收的停顿时间看，不移动对象的停顿时间更短，甚至可以不需要停顿，但是从整个程序的吞吐量来讲，移动对象更划算。即时不移动对象会使得收集器的效率更高些，但因内存分配比垃圾收集的频率要高的多，这部分的耗时增加，整体的吞吐量还是降低的，HotSpot虚拟机里关注吞吐量的Parall Scavenge收集器是基于标记-整理算法的，而关注延迟的CMS收集器则是基于标记-清除的。
还有一种办法就是可以不在内存分配和访问上增太大额外负担，做法是让虚拟机平时多数时间都采用“标记-清除”算法，暂时容忍内存碎片的存在，直到影响到对象分配内存时，再使用“标记-整理”算法收集一次，以获得规整的内存空间，CMS垃圾收集器面临空间碎片过多时就是使用这种办法。

算法实现细节

GC Roots根节点枚举

问题

枚举所有的GC Roots耗时问题，根节点枚举时为了保证对象引用关系的一致性，需要STW。

解决方案，如何做才能不需要遍历所有的GC Roots

由于虚拟机垃圾收集都是准确式收集，虚拟机知道哪些地方存着对象引用，HotSpot中采用了OOP Map的数据结构，也就是在扫描的时候就可以直接从OOP Map中获取到哪些位置有引用，就不需要遍历所有的GC Roots了。

安全点

问题

对象之间的引用关系变化非常多，导致OOP Map内容变化的指令非常多，也不可能为每一条指令生成一个OOP Map。

解决方案，如果做到避免对象之间的引用关系频繁变化影响GC呢？

HotSpot没有为每条指令都生成OOP Map，只是在“特定位置”记录这些信息，这些位置被称为“安全点（Safe Point）”。

作用

“安全点”的目的就是告诉用户的程序不是在任意位置都能暂停下来进行垃圾收集。

选取

• 安全点的选取不能太少，因为会导致垃圾收集程序等待时间太长
• 安全点的选取位置在《深入理解Java虚拟机》里是这么说的，“是否具有让程序长时间执行的特征 ”为标准进行选定，由于程序每条指令的执行时间都很短暂，程序不可能指令流太长就长时间执行，“长时间执行”最明显的特征就是**指令序列的复用，如“方法调用”、“循环跳转”、“异常跳转”**等，
  

如何在垃圾收集时让所有的线程都跑到最近的安全点停顿下来

• 抢断式（不需要用户线程配合）
  • 在垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地方不在安全点上，则让这条线程继续执行，直到跑到安全点上（几乎没有虚拟机实现使用这种方式）
• 主动式（需要用户线程配合）
  • 不主动去中断用户线程，设置一个标志位，用户线程不断的去轮询这个标志位，一旦发现标志位为真时自己就在最近的安全点挂起，标志位与安全点是重合的，另外HotSpot还考虑到在创建对象或者为对象分配内存的位置加上标志位，为了检查是否即将要发生垃圾收集，避免没有足够的内存进行内存分配新对象。

安全区域

只有安全点似乎很完美的解决了在进行垃圾回收之前停顿用户线程，安全点机制保证了程序执行时，在不长的时间内就会安全点，但是假如程序不执行呢，例如用户线程处于Sleep或者Blocked状态， 这时候线程就没办法响应虚拟机的中断请求，但是虚拟机也不能一直干等着用户线程执行，因此就引入了安全区域，安全区域能确保在某一段代码片段中，引用关系不会发生变化。因此在这个区域任何位置开始垃圾收集都是安全的。

并发的可达性分析

GC Roots对象遍历一致性快照

可达性分析目前是主流的垃圾收集器使用的判断对象是否存活的算法，但是这个算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，意味着必须要STW才可以，上边已经讲过了根节点枚举通过Oop Map的优化，停顿时间已经减小很多了，但是从GC Roos往下遍历对象的时间是随着堆内存的大小正比例增长的（堆内存越大，对象越多，对象之间的关系越复杂，那这个过程所花的时间就越长），这里为何必须在一个能保障一致性的快照上的才能进行遍历，大家自行查询三色标记相关资料即可。

三色标记

这里做简单描述：假设黑色为已经遍历过并且可达的对象，灰色为已经被遍历过，白色为待遍历或者遍历过但仍不可达对象，但是这个对象上至少存在一个引用还没有被扫描过，下图中引用C对象的有E和D，在遍历过程中，D和C的引用被断开了，因此E和D仍为白色，但是遍历完C所有的引用对象后，D对象的引用关系发生了变化，被用户线程修改为被B引用，但是标记线程又不会再标记一次，因此D对象就会被回收掉，这样就出现大问题了，被使用的对象突然被回收了，是不是很可怕，因此GC Roots遍历过程需要在一个能保障一致性快照上才可以。
​

解决办法

目前大多数垃圾收集器都是用可达性分析算法，如果在GC Roots对象遍历过程中必须STW，这种情况就会影响大部分垃圾收集器，如果能减少这部分的停顿时间，带来的收益将是巨大的。
在上边的三色标记中我们发现导致并发标记的原因有：

• 用户线程将黑色对象引用指向白色对象
• 用户线程将灰色对象与白色对象的引用断开

因此分别产生了两种解决方案：

增量更新

增量更新要解决的是第一种情况，当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束后，再讲这些记录过的引用关系中的黑色对象为根，重新扫描一遍，也就是说黑色对象只要指向白色对象，那黑色对象就变为灰色对象。

原始快照

原始快照要解决的是第二种情况，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束后，再将这些记录过得引用关系中的灰色对象为根，重新扫描一遍，这里可以理解为，无论引用关系是否删除，都会按照刚刚开始扫描那一刻的对象快照来进行搜索。
​

以上两种版方案虚拟机都是通过写屏障来实现的，两种方案都有应用，比如CMS是基于增量更新来做并发标记，G1、Shenandoah这是使用原始快照。