当前主流的商用程序语言（Java、C#，上溯至前面提到的古老的Lisp）的内存管理子系统，都是通过可达性分析（Reachability Analysis）算法来判定对象是否存活的。这个算法的基本思路就是通过一系列称为“GC Roots”的根对象作为起始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程所走过的路径称为“引用链”（Reference Chain），如果某个对象到GC Roots间没有任何引用链相连，或者用图论的话来说就是从GC Roots到这个对象不可达时，则证明此对象是不可能再被使用的。

枚举根节点

根节点也叫GC roots，枚举根节点是可达性分析的第一步，根节点一定是“可达”的，有了根节点，我们就可以顺着根节点往下分析对象是否可达。

GC roots

什么是GC roots

用大白话来讲，就是在这一次垃圾收集中一定不会被回收的对象的引用，

为什么一定是对象的引用呢，首先我们要收集的是堆，栈不用回收，因为栈会随着进程退出自动回收。堆是存放对象的地方，所以我们要找到是一定会生存下来的对象的引用。

GC roots有哪些

• 在虚拟机栈（栈帧中的本地变量表）中引用的对象，譬如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等，栈还存在说明线程没有退出，那么栈内引用的对象肯定是存活的；
• 在方法区中类静态属性引用的对象，譬如Java类的引用类型静态变量，静态变量和类的生命周期是一致的，所以方法去中的静态变量肯定是存活的；
• 在方法区中常量引用的对象，譬如字符串常量池（String Table）里的引用；
• 在本地方法栈中JNI（即通常所说的Native方法）引用的对象，本地方法栈和虚拟机栈的原理是一样的；
• Java虚拟机内部的引用，如基本数据类型对应的Class对象，一些常驻的异常对象（比如NullPointExcepiton、OutOfMemoryError）等，还有系统类加载器；
• 所有被同步锁（synchronized关键字）持有的对象；
• 反映Java虚拟机内部情况的JMXBean、JVMTI中注册的回调、本地代码缓存；

注意：上述并不是所有GC roots，还有一些情况不一一列举，主要是理解什么对象会成为GC roots。

Stop The World

在枚举GC roots的时候必须要停顿所有的用户线程，也就是所谓的STW(Stop The World)这样做是为什么呢？因为我们必须要保证完整的枚举出所有的GC roots，如果不停顿用户线程，用户线程在我们枚举GC roots的时候又新增的新的GC roots，可能就会导致漏掉GC roots，造成回收错误的对象，这是很严重的。

这里可能会有另外一个问题，就是即使这里完整的枚举出了GC roots，当用户线程恢复执行的时候仍然会有新的GC roots产生。这种情况确实有可能发生，针对这种情况会采用增量更新的方式来处理。

当所有的用户线程都进入中断的时候，JVM就可以开始操作了。那我们要怎么让用户线程停下来呢？

中断策略

有两种思路让用户线程停下来。

抢占式中断

先让所有的用户线程都停下来，如果有线程不在安全点，就恢复线程，让他跑到安全点再停下来。

当前已经没有虚拟机使用这种方式了，为什么呢？

主动中断

虚拟机设置一个中断标识，当用户线程执行到安全点的时候主动检查这个标识，如果中断标识为真，则将自己挂起。

这两种中断方式都需要使用到一个叫安全点的概念，安全点是什么？

安全点（Safe Point）和安全区域（Safe Region）

安全点（Safe Point）

安全点实际上就是JVM选定的一些位置，用户线程执行到这些位置，就会检查JVM设置的中断标识，如果中断标识为空，线程就挂起自己。

那安全点是怎么选定的呢？在《深入理解Java虚拟机》书中提到了安全点位置的选择标准是：是否能让程序长时间执行；所以会在方法调用、循环跳转、异常跳转等处才会产生安全点。

为什么要选一些地方作为安全点呢？每条指令都检查不行吗？实际上也行，但是主要出于性能考虑，所以选定一些地方作为安全点。

但实际上安全点并没有这么简单，可以参考：https://tech.dewu.com/article?id=47

安全区域（Safe Region）

有了安全点，为啥还要搞个安全区域呢？

想想这样一个场景，某一个线程处于blocked状态，blocked的时候因为JVM没有设置中断，所以他并没有进入安全点，也没有更新OopMap，此时JVM要进入中断，但是这个线程不知道要blocked到什么时候，也不能说随意唤醒他，这就麻烦了。

所以增加了安全区域的概念，在这个区域内，线程执行不会导致OopMap变更。

线程在进入安全区域的时候，主动上报自己已经进入安全区域，并且更新OopMap；在离开安全区域的时候要检查中断标识，同时再上报自己离开安全区域。

所以JVM在设置中断的时候就可以忽略处在安全区域的用户线程，因为他们当下一定不会执行导致OopMap变更的操作。

从上面的标识可以看出，线程阻塞的操作一定是安全区域，毕竟阻塞的线程无法执行任何操作。

总结来说：安全点是用户线程被动的检查JVM设置的中断标识，然后决定自己该怎么做；安全区域是用户线程主动的上报自己的状态给JVM。

并发标记

并发标记是可达性分析的第二步，这一步是顺着上一步找到的根节点，一个一个的标记出所有应该存活的对象，没有被标记的对象，那自然就是应该是被回收的对象。

先来看看是如何标记的

三色标记（Tri-color Marking）

使用三色标记法来解释对象是怎么遍历的，把遍历对象图过程中遇到的对象，按照“是否访问过”这个条件标记成以下三种颜色：

• 白色： 表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。
• 黑色： 表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接（不经过灰色对象）指向某个白色对象。
• 灰色： 表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

这样扫描下来，非常清晰的就发现了可回收的对象，可事实是并没有这么简单，上面说过标记过程和用户线程是并发执行的，所以在标记过程中，对象的引用关系并不是一成不变的。

并发标记的问题

收集器在对象图上标记颜色，同时用户线程在修改引用关系——即修改对象图的结构，这样可能出现两种后果。一种是把原本消亡的对象错误标记为存活，这不是好事，但其实是可以容忍的，只不过产生了一点逃过本次收集的浮动垃圾而已，下次收集清理掉就好。另一种是把原本存活的对象错误标记为已消亡，这就是非常致命的后果了，程序肯定会因此发生错误。

Wilson于1994年在理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”的问题，即原本应该是黑色的对象被误标为白色：

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

因此，我们要解决并发扫描时的对象消失问题，只需破坏这两个条件的任意一个即可。由此分别产生了两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。

增量更新要破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。

原始快照要破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。

以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。在HotSpot虚拟机中，增量更新和原始快照这两种解决方案都有实际应用，譬如，CMS是基于增量更新来做并发标记的，G1、Shenandoah则是用原始快照来实现。

无论是采用哪种方案，在并发标记阶段都无法完全完成对象标记。

重新标记（最终标记）

所以我们需要对并发标记阶段出现的变化再做一次确认。

并发标记无法完全完成标记的原因是和用户线程并发，用户线程在持续不断的修改对象的引用关系导致的。

但是也不要紧，并发标记的目的已经达成了，并发标记阶段已经完成了绝大部分的对象标记。所以我们在重新标记的阶段只需要标记少部分在并发标记是发生了变更的对象。

这时候为了完全标记完对象，必须再次Stop The World，确保对象的引用关系不发生变化。

并发清理

当标记完成以后，被识别为已经死亡的对象是无法再次建立连接的（不是绝对，对象在被回收之前，还有拯救自己的机会，不过不建议使用这种方式），所以我们在清理对象的时候不需要再次停止用户线程了，可以直接清理。

参考资料

《深入理解Java虚拟机：JVM的高级特性和最佳实践》