[toc]

概述

本文抛开具体的垃圾收集器，介绍追踪式垃圾收集（采用引用计数）的常见算法
关于对象引用的相关内容见:内存对象

垃圾收集算法

分代收集

收集器将内存划分出不同的区域，然后将回收对象依据其年龄（经历过几次垃圾回收）分配到不同区域中进行存储
这样的好处是，针对不同区域的特性可以采用不同的算法，以较低的代价获取较好的回收效果，例如

• 当一个区域的大多数对象都是朝生夕灭时，我们只需要去关注少量的可以存活的对象，而不是去标记那些大量的将要被回收的对象
• 当一个区域的大多数对象都是难以消亡的对象，那就以较低的频率来处理这块区域，提高每次收集的效率

下文中提到的标记-清除、标记-复制等算法，就是针对不同区域安排和区域对象存亡特征发展出来的具体收集策略
此外，需要额外提及的是，上文显然是理想情况，我们即使根据对象存亡特征将内存划分为不同区域，实际上进行回收时，由于存在跨区域引用，因此无法仅根据本区域的对象信息进行收集；但根据跨代引用假说，跨代引用相对于同代引用来说，仅占极小的比例
例如，我们将内存划分成2个区域，其中区域1中99%的对象都被本区域中的对象引用，仅存在1%的对象，它们被区域2中的对象引用。那我们显然不应该为了这个1%的被引用的对象，去扫描整个区域2，也没必要在对象体中专门浪费空间来记录是否存在及存在哪些跨区域的引用。只需要通过某种全局的数据结构（记忆集、Remembered Set）来记录相关的信息，后续我们也会提到具体做法
在目前常见的Java虚拟机里，一般会把Java堆划分成新生代和老年代两个区域。在新生代中，每次收集都会有大量对象死去，仅存活少量对象；而每次回收后存活的少量对象，将会根据年龄逐步晋升到老年代中存放

标记-清除算法

该算法首先标记出所有需要回收的对象，在标记完成后，再统一回收掉所有被标记的对象（也可标记存活的对象）
这是最基础的收集算法，后续的收集算法大多是以它为基础，对其缺点进行改进而产生的
主要缺点：

1. 执行效率不稳定，标记能喝清除两个动作的效率都随着对象数量的增长而降低
2. 直接清除产生大量不连续的内存碎片，从而可能在后续分配较大对象时，在明明总剩余内存够的情况下，提前触发另一次垃圾收集行为

标记-复制算法

标记-复制算法是为了解决标记-清除算法面对大量可回收对象时，执行效率低的问题而提出来的，下面基于Andrew Appel提出的策略进行介绍
在大多数对象都是朝生夕死的区域（上文提及过），将该区域的空间进一步划分为三块空间，其中一块内存较大的叫Eden空间、两块较小的叫Survivor空间，它们的大小比例为8:1:1
每次分配内存时，只使用Eden空间和其中一块Survivor空间，当内存申请失败，需要进行垃圾回收时，首先还是进行对象标记，找出存活对象后，将存活对象一次性复制到另一块Survivor空间，并清理掉Eden空间和已使用过的Survivor空间
此外，由于无法保证每次回收都只有不超过区域大小10%的对象存活，Appel还设计了分配担保的策略：如果另一块Survivor空间没有足够空间存放本次垃圾收集剩余的存活对象，这些对象将直接进入老年代

标记-整理算法

当对象存活率较高时，标记-复制算法会需要进行较多的对象复制操作，同时除非将该区域划分成50%-50%大小的两块空间，否则就会像上文Appel式回收中提到的，需要额外的空间进行担保，处理极端情况，因此在老年代中不适合使用标记-复制算法
针对老年代的存亡特征，Edward Lueders提出了标记-整理算法：在标记完对象之后，让所有存活的对象都向内存一端移动，全部对象移动完成后，直接清理掉边界以外的内存
与标记-清除算法相比，标记-复制和标记-整理算法在标记阶段完成后，都需要移动存活对象，并且更新所有对这些对象的引用，这个操作是相对较重的操作，并且操作时需要暂停所有的用户线程（Stop the World）。而如果不移动存活对象，则需要更为复杂的内存分配器和内存访问器来解决碎片内存的问题，因此到底采用哪种做法，是根据收集器主要希望解决的问题来决定。例如更关注吞吐量的Parallel Scavenge收集器是基于标记-整理算法，而更关注gc延迟的CMS收集器则是基于标记-清除算法（当内存碎片化比较严重时，再采用一次标记-整理算法）

算法细节实现

根节点枚举

可达性分析指的是从GC Roots集合为根，根据引用链标记所有存活对象。其中引用链查找这一步已经可以跟用户线程并发执行，但是根节点枚举这一步需要暂停所有用户线程（STW）
在大应用中，可能光方法区就是几十上百兆，若需要扫描所有的GC Roots来获取引用链分析的根节点，那造成的停顿时间还是不可接受，因此在HotSpot的虚拟机实现中，当用户线程都暂停之后，虚拟机只需要通过一组成为OopMap的数据结构，就可以知道哪些地方存放着对象引用，从而可以较快地获取到引用链分析的根节点。当类加载完成后，虚拟机就会计算出该类的对象，在什么偏移量上有什么类型的数据，同时在即时编译的过程中，也会记录栈和寄存器里哪些位置存放的是引用，从而减小根节点枚举的扫描量

安全点/区域

上文讲述了可以通过OopMap来枚举根节点，但是可能导致引用链根节点发生变更的语句其实是非常多的，如果需要在每次执行一条对应指令时就进行OopMap的更新操作，那不仅会带来更多的处理开销，同时也会导致OopMap所需要的存储空间变得非常大
事实上，HotSpot虚拟机只会在指令执行到特定位置时，进行OopMap的更新操作，这个位置就叫做安全点
安全点由虚拟机进行选取，需要满足“让程序长时间执行”这样的特征，实际上，一般安全点选取会在方法调用、循环跳转、异常跳转等发生指令序列复用的地方
为了让所有线程都停在安全点上，有两种方式：

• 抢先式中断：需要进行根节点枚举时，系统直接中断所有用户线程，然后检查一遍，让所有没有停在安全点上的线程恢复执行，过一段时间后再中断这些线程并重复刚刚的检查，直到所有线程都暂停在安全点
• 主动式中断：当需要枚举根节点时，系统仅仅设置一个标志位，各个线程在执行过程中会去不断轮询检查这个标志位，一旦发现被标记，就在最近的安全点停下来，一般来说轮询的位置与安全点的位置是重合的，此外还会在创建对象等需要发生内存分配的地方进行标志的轮询检查，避免因内存不够而分配失败

安全点的出现，可以让用户线程在执行状态时，快速进入可以STW然后枚举根节点的状态，但是如果某些线程处于Sleep或者Blocked状态时，无法响应虚拟机的中断请求，更不要提主动去检查标志位，从而无法在安全点中断挂起，因此引入了安全区的概念用于解决上述问题
安全区指的是，不会发生引用关系变更的代码片段，当用户线程执行到安全区时，会标志自己

记忆集与卡表

前面讲到，把内存划分为不同区域，会需要处理跨代引用的对象，记忆集就是用来解决这个问题的数据结构
记忆集记录了从非收集区域指向收集区域的指针集合，在jvm的具体实现中，记忆集记录了某一块非收集区域（不同粒度如字长精度、对象精度、卡精度等）是否存在有指向收集区域的指针
卡表则是基于卡精度的记忆集的具体实现：某块特定大小的内存块中，是否存在一个或多个对象的字段存在跨代指针，在垃圾回收时，我们只需要将那些存在跨代指针的内存块加入到GC Roots中进行扫描

写屏障

我们知道，引用的绑定与解除操作随时都在发生，那我们如何维护上文提到的卡表呢？
写屏障可以理解为“引用类型字段赋值”这个动作的aop切面，分为写前屏障和写后屏障，jvm的做法就是在写后屏障判断一下，如果发生了跨代引用，并且原来在卡表中没有标记，那就更新卡表

并发可达性分析

上文中所有主要描述了根节点枚举这一步会导致STW的操作，那么枚举完根节点之后，我们如何从根节点开始，根据引用关系扫描整个堆中的对象呢？
首先介绍一下三色图的概念：
白色：本对象在本次垃圾收集中未被收集器扫描过
灰色：本对象在本次垃圾收集中被收集器扫描过，但是存在至少一个本对象出去的引用，还没被扫描过
黑色：本对象在本次垃圾收集中被收集器扫描过，且所有本对象出去的引用都被扫描过
考虑刚完成根节点枚举的那个时刻：把堆中的对象看成点，引用关系看成单向边，那么对象及其引用关系即可看作一个有向图，在根节点枚举时被扫描出来的对象（点）为灰色，其余所有对象（点）为白色，现在以灰色点为起点开始遍历整张图，根据上文三色定义给所有的对象（点）上色，那么当整张图遍历完毕之后，整张图上的对象（点）都会被标记为黑色或者白色，而仍然为白色的对象（点）即为不可达对象，这些对象可以被回收
刚刚考虑的是静态的情况，也就是在扫描过程中，没有发生引用的增删情况，在实际情况下jvm进行扫描的同时，还会频繁的发生引用的变更，如果不做任何处理，会导致如下两种情况

1. 白色对象被标记为黑色，此情况问题不大，无非是逃过了本轮垃圾收集，下次再收集即可
2. 黑色对象被标记为白色，这种情况会导致不应该回收的对象被回收，是万万不能接受的

实际上，只有下面两个条件同时满足时，会发生黑色对象被标记为白色的情况

1. 赋值器插入了一条或者多条从黑色对象到白色对象的新引用
2. 赋值器删除了全部从灰色对象到该白色对象的直接或者间接引用

分析清楚后，我们只需要破坏其中的某个条件，就可以避免黑色对象被误标记为白色对象

• 增量更新法：新增黑色对象对白色对象的引用时，将引用记录下来，等并发扫描结束后，再以这些引用发起的黑色对象为根，重新扫描一遍
• 原始快照法：当灰色对象要删除对白色对象的引用关系时，将这些被删除的引用记录下来，当扫描结束后，以引用发起的灰色对象为根，重新扫描一遍
  以上两种都通过写屏障实现，cms基于增量更新，g1、shenandoah基于原始快照