垃圾收集（Garbage Collection）简称GC，它让开发人员不用再去关注对象的释放，一切都显得那么“自动和智能”。GC的发展历史远比Java要久远，但JVM中的GC，绝对是其中最耀眼的一颗星星。
伟人 John McCarthy 思考提出垃圾收集应该完成的三个事情：
- 那些内存需要回收？
- 如何回收？
- 什么时候回收？
本文也将从前两点出发，总结所学。
对象是否死亡
GC的第一步便是确定那些对象的内存需要收集，主流有两种算法，引用计数法和可达性分析法。
引用计数法（Reference Counting）
又被成为直接垃圾收集，引用计数式垃圾收集（Reference Counting GC）
过程描述：通过给对象增加一个引用计数器，它被引用时，增加这个计数器。不再引用时减少。如果为0则表示没有被引用可以回收。
存在问题：单纯的引用计数，无法解决循环依赖问题，A引用了B，B又引用了A。需要大量额外的处理工作才能够保证正确工作。
使用语言：ActionScript3、Python和Squirrel
当然，JVM中的GC并没有采用这种方式。
可达性分析算法（Reachability Analysis）
又被称为间接式垃圾收集，追踪式垃圾收集（Tracing GC）
- 过程描述：通过一系列“GC Root”的根对象作为起始节点集合，从这些节点开始根据引用关系向下搜索，过程中经过的路径称为“引用链（Reference Chain）”，如果一个对象到GC Root间没有任何引用链，即GC Root到这个对象不可达，不能再被使用了。
- 存在问题：相比于引用计数法，要复杂，其中也有诸多问题需要去解决，下文会讲Hotspot的具体实现，Hotspot是如何解决这些问题的。
- 使用语言：Java和C#
在Java体系中，固定可作为GC Root的对象有一下几种：
- 虚拟机栈，栈帧中的本地变量表记录的引用类型。
- 方法区中类静态属性引用的对象和常量引用的对象。（JDK7开始将静态变量存在了堆里面）
- 本地方法栈，Native方法中引用的对象。
- Java虚拟机内部的饮用，例如Class对象，一些常驻的异常（NPE，OOM等）
- 所有被同步锁（sychronized）持有的对象
- 反应JVM内部情况的JMXBean，JVMTI中注册的回调，本地代码缓存等。
在Java中如果宣布一个对象死亡，至少要两次标记。如果发现GC Root到这个对象不可达，这个对象将会被第一次标记。之后进行一次筛选，判断是否有必要执行finalize()方法，如果判断为需要那这个对象，将会放置在一个名为F-Queue的队列中，稍后由一条虚拟机自动建立的、低调度优先级的Finalier线程去执行它们的finalize()方法。这里的“执行”是指虚拟机会触发这个方法，但并不承诺一定会等待它运行结束。在finalize()方法中，对象可以拯救自己（和引用链上任何一个对象建立联系即可）。finalize()方法只会被系统自动调用一次，下一次回收时，这个方法就不会再次执行了。
方法区的回收
《Java虚拟机规范》中提到过可以不要求虚拟机在方法区中实现垃圾收集，实际也确实有未实现或未完整实现方法区类型卸载的收集器存在，例如 JDK11时期的ZGC收集器，就不支持类卸载。由于收集条件苛刻，对于方法区的收集行性价比是比较低的。
方法区回收主要两部分内容：废弃的常量和不再使用的类型。
对于常量来说，确定是否需要回收掉比较简单。但是判断一个类是否不能再被使用就比较苛刻了。类型的回收必须满足下面三个条件：
- 该类所有实例已经被回收。
- 加载该类的类加载器已经被回收。
- 该类对应的java.lang.Class对象没有被任何地方引用。
HotSpot虚拟机提供了-Xnoclassgc参数进行控制，还可以使用-verbos:class以及-XX:TraceClassLoading来查看类加载和卸载信息。
分代收集理论和三大垃圾收集算法
这一块内容应该属于，“如何做”的宏观理论基础部分。
分代收集理论
包括了三条假说：
- 弱分代假说（Weak Generational Hypothesis）：绝大数对象都是朝生夕灭。
- 强分代假说（Strong Generational Hypothesis）：熬过越多次垃圾收集过程的对象就越难以消亡。
依据这两个假说，于是大部分垃圾收集器，将堆空间分为了：老年代（Old Generation）和新生代（New Generation）。针对不同区域的垃圾收集动作也有了不同的名次，Minor GC（新生代），Major GC（老年代）和Full GC（整个堆）。又可以根据分代的特点采用不同的垃圾收集算法。标记清楚法、标记整理法和复制算法。
- 跨代引用假说（Intergenerational Reference Hypothesis）：跨代引用相对于同代引用来说仅占极少数。
依据这个假说，我们不应该因为年轻代极少数跨代引用去扫描整个老年代，也不需要浪费内存记录每一个对象是否存在跨代引用。只需要在年轻代上建立一个叫做“记忆集（Remenbered Set）”的数据结构，这个结构将老年代分为若干个小块，表示老年代哪一个小块存在跨代引用。
Partial GC：表示部分收集并不完整收集整个Java堆。其中又分为
Minor GC/Young GC：指针对新生代的回收
Major GC/Old GC：指针对老年代的回收，目前只有CMS收集器会有单独收集老年代的行为。在不同资料上有混淆，Major GC也可能代表整堆收集。
Mixed GC：收集部分的新生代和老年代，目前只有G1有这种行为。
Full GC：收集整个Java堆和方法区的垃圾收集。
三种垃圾收集算法
- 标记-清楚算法：分为标记和清除两个阶段。缺点有两个，1.不稳定，存在大量死亡对象时，要大量的标记和清理工作。2.清理完毕之后，会留下大量的内存碎片，不利于大对象的分配。
- 标记-复制算法：将内存分为大小相同的两块，每次使用其中一块，清理时，将存活对象复制到另外一块上，然后使用这一块进行内存分配操作。简单高效，但需要浪费一部分类型。但根据对象“朝生夕灭”的特点做优化，分成一大块Eden和两小块Survivor空间，同时使用Eden和其中一块Survivor做分配操作，清理时将这两块存活对象，复制到剩下的一块Survivor空间上，然后在Eden和这块Survivor上做分配操作。
- 标记-整理算法：与标记-清楚不同的是，第二部做移动操作，并不是清理操作。移动操作必须要更新所有引用这些对象的地方。这个过程需要全程暂停用户应用程序才能进行
总的来说，标记-复制算法，简单高效，Eden+2 Survivor的方式有可以减少内存的浪费，适合收集后仅存在少部分对象的场合，因此是新生代收集的首选。标记-清楚和标记-复制算法，个有优略，清楚算法会导致大量的内存碎片，大量内存碎片会导致分配大对象时，没有多余空间，又一次触发GC，速度快了，频率也高了，吞吐量低了，但比起移动对象要更高效。标记-整理，虽然效率低，但由于整理内存，可以腾出更大的连续空间，总体来说吞吐量更高。因此对于追求高吞吐量的Parallel Scavenge收集器来说采用标记-整理，追求低延时的CMS来说采用标记-清理。当然在内存碎片过多的情况下，CMS也会采用标记-整理的方式来处理。
Hotspot垃圾回收的细节
这部分应该属于“如何做”的实现细节层面。
枚举根节点
追踪式GC的第一步就是把所有的GC Root对象给枚举出来，迄今为止，任何一款收集器都需要在进行这一步时，Stop The Word。但HotStop使用了一组称为OoPMap（Ordinary Object Pointer Map)的数据结构，大大缩短了枚举过程。一旦类加载动作完成的时候，HotSpot就会把对象内什么偏移量上是什么数据类型给计算出来，即时编译过程中，也会在特定位置记录下栈里和寄存器里那些位置是饮用。这样收集器在扫描的时候，就不需要扫描整片内存。借助于OopMap结构，可以快速完成根节点的枚举，虽然会STW，但这一步是飞快的。
Oop：普通对象指针
借助于OopMap实现获取到一些内存信息，准确定位的收集方式，又可以叫做准确式GC，与之对应的是保守式GC，保守式GC需要扫描整个内存空间。
安全点
导致OopMap变化的指令非常多，如果为所有指令都生成对应的OopMap，那将会有巨大内存开销。实际上，只会在特定位置记录这些信息，这些特定位置就被称为“安全点（Safepoint）”，在安全点的设定下，垃圾收集时必须让所有线程都到达安全点才能够进行垃圾收集。安全点不能太少，导致垃圾收集器长时间等，也不能太多，增加内存负担。安全点基本上是以“是否具有让程序长时间执行的特征”选定。例如，方法调用，循环跳转，异常跳转等。
在垃圾收集时，让线程在安全点停顿下来有两种方式
- 抢先式中断（Preemptive Suspension）：垃圾收集时，系统首先将所有用户县城全部中断，如果发现有用户县城中断的地方不在安全点上，就恢复这个线程继续执行，让它一会在重新中断，直到跑到安全点上。
- 主动式中断（Voluntary Suspension）：仅仅设置一个标志位，各个线程执行过程时，不停地主动去轮询这个标志，一旦发现标志为真时，就将自己在最近的安全点上主动中断挂起。轮询标志的地方和安全点是重合的。另外还要加上所有创建对象和其他需要在Java堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配对象。
轮询操作是通过test指令实现的，将需要暂停用户线程时，虚拟机将0x160100内存页设置为不可读，那线程执行到test指令时就会产生一个自陷异常信号，然后在预先注册的异常处理器中挂起县城实现等待。
安全区域
安全区域能够确保在某一段代码片段中，引用关系不会发生变化，因此在安全区域的任何地方开始垃圾回收都是安全的。 安全区域的引入是为了解决sleep状态或者blocked状态的线程无法相应虚拟机的中断请求，走到最近安全点挂起自己。
当用户线程进入到安全区域，首先标识自己已经进入了安全区域，当这段时间内虚拟机要发起垃圾收集就不必管处于安全区域的用户线程。当线程离开安全区域是，则要检查虚拟机是否已经完成了根节点的枚举。
记忆集和卡表
前面说到的分代会引来跨分代引用问（详细看上面提到的“跨分代假说”）。为了解决这个问题，在新生代中引入了记忆集（Remembered Set）的数据结构，用来避免对整个老年代的扫描。
记忆集是一种记录从非收集区域指向收集区域的指针集合，一种抽象的数据结构。具体实现上根据记录精度分为：
- 字节精度：每个记录精确到一个机器字长，该字包含了跨代指针。
- 对象精度：每个记录精确到对象，这个对象包含了跨代指针。
- 卡精度：每个记录精确到一块内存区域，该区域内含有跨代指针。
卡表是卡精度版本的记忆集实现，本质上是一个数组。每512字节为一个卡页，对应数组的一个元素，如果在这个卡页中，存在一个或更多跨代指针，对应数组元素标识为1，表示这个是个脏卡页，没有标识为0.这样只需要将变脏的卡页加入到GC Roots中一并扫描即可。
卡表在并发条件下存在“伪共享（False Sharing）”问题。避免伪共享问题的一种简单解决方式就是，先检查卡表标记，只有在未被标记情况下，才会更改。JDK7之后，增加了-XX:UseCondCardMark参数用来决定是否开启卡表更新条件判断。
伪共享问题，现代中央处理器缓存是以缓存行（Cache Line）为单位的，当多个线程修相互独立的变量时，如果这些变量恰好共享一个缓存行，就会彼此影响（写会，失效和同步）而导致性能降低。
卡表本身是通过写屏障来维护的。
写屏障和读屏障
区别于内存屏障
写屏障可以看作是在虚拟机层面对“引用类型字段赋值”这个动作的AOP切面，在引用对象赋值时，产生一个环形（Around）通知，用于执行额外的操作。
并发的可达性分析
枚举GC Root在OopMap的协助下，是一个非常快的过程。但可达性分析的过程却与堆的大小有密切关系，堆越大整个过程就会越复杂。
可达性分析本质上是对 对象引用关系 图的遍历，遍历过程应该在一个能保证一致性的快照上进行。为了描述清楚遍历过程，引入三色标记（Tri-color Marking）作为辅助工具。
三色标记
- 白色：表示对象尚未被垃圾收集器访问过，开始阶段所有对象都是白色，如果结束之后对象仍然是白色的表示不可达。
- 灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少有一个引用还没有被扫描完毕。
- 黑色：表示对象已经被收集器访问过，并且它的所有引用也都已经扫描过了。一个对象不能够直接从白色变为黑色，必须由灰色变成黑色。
整个可达性分析过程可以看作是，引用图从白色逐渐变成黑色的过程。
可达性分析的过程中如果同时有用户线程同时在修改，会导致两种情况。
- 已经被可达性分析线程标记为存活（黑色）的对象，被同时执行的用户线程给改变了引用消亡了。产生了浮动垃圾。
- 已经被可达性分析线程标记为消亡（白色）的对象，被同时执行的用户线程给重新引用了，这样导致对象消失了。
对于第一种“浮动垃圾”来说可以接受，因为在下一次回收时，就会被处理掉，但是第二种就会引发程序错误。
Wilson 1994年在理论上证明，只有在下面两个条件同时满足时，会产生“对象消失”的问题。
- 赋值器插入了一条或多条从黑色对象到白色的新引用。
- 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。
由此产生了两个方案
- 增量更新（Incremental Update），破坏的是第一个条件，当黑色对象插入指向白色对象的饮用关系时，将这个插入的引用记录下来，等并发扫描结束之后，在将这些记录，以黑色对象为根再扫一次。理解为如果黑色插入了白色，它就变成灰色重新扫描。CMS是基于增量更新做并发标记的。
- 原始快照（Snapshot At The Beginning，STAB），灰色对象删除指向白色对象的引用，就把这个删除的引用记录下来，等并发标记结束后，再以灰色对象为根，扫描一下。可以理解为，删除不管用，还是以最开始的快照为主。G1、Shennandoah则是利用原始快照来实现的。
以上的两种方案记录插入或者删除的引用变量，都是利用写屏障来实现的。
