并发的可达性分析
通过上文可知，JVM 默认使用可达性分析算法来判断对象是否死亡，而可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全程冻结用户线程的运行。 虽然 GC Roots 相较于 Java 堆对象来说只是很小的一部分，即使可以通过 OopMap 快速找到 GC Roots，它带来的停顿时间是非常短暂且相对固定的，可以理解为不会随着堆里面的对象的增加而增加。
但是从GC Roots再继续往下遍历对象图， 这一步骤的停顿时间就必定会与 Java 堆容量直接成正比例关系了： 堆越大， 存储的对象越多， 对象图结构越复杂， 要标记更多对象而产生的停顿时间自然就更长。
"标记"阶段是所有使用可达性分析算法的垃圾回收器都存在的阶段。如果能够削减"标记"过程这部分的停顿时间，那么收益将是系统性的。
所以并发标记要解决什么问题呢？
**就是要消减这一部分的停顿时间。那就是让垃圾回收器和用户线程同时运行，并发工作。**也就是我们说的并发标记的阶段。
在介绍并发标记前，首先需要介绍一个新的概念，“三色标记”。
什么是"三色标记"？《深入理解Java虚拟机(第三版)》中是这样描述的：
- 白色： 表示对象尚未被垃圾收集器访问过。 显然在可达性分析刚刚开始的阶段， 所有的对象都是白色的， 若在分析结束的阶段， 仍然是白色的对象， 即代表不可达。
- 黑色： 表示对象已经被垃圾收集器访问过， 且这个对象的所有引用都已经扫描过。 黑色的对象代表已经扫描过， 它是安全存活的， 如果有其他对象引用指向了黑色对象， 无须重新扫描一遍。 黑色对象不可能直接（不经过灰色对象） 指向某个白色对象。
- 灰色： 表示对象已经被垃圾收集器访问过， 但这个对象上至少存在一个引用还没有被扫描过。
如下图所示：
可以看到，灰色对象是黑色对象与白色对象之间的中间态。当标记过程结束后，只会有黑色和白色的对象，而白色的对象就是需要被回收的对象。
在可达性分析的扫描过程中，如果只有垃圾回收线程在工作，那肯定不会有任何问题。
但是垃圾回收器和用户线程同时运行呢？
垃圾回收器在对象图上面标记颜色，而同时用户线程在修改引用关系，引用关系修改了，那么对象图就变化了，这样就有可能出现两种后果：
- 一种是把原本消亡的对象错误的标记为存活，这不是好事，但是其实是可以容忍的，只不过产生了一点逃过本次回收的浮动垃圾而已，下次清理就可以。
- 一种是把原本存活的对象错误地标记为已消亡，这就是非常严重的后果了，一个程序还需要使用的
对象被回收了，那程序肯定会因此发生错误。
最终我们得知并发标记除了会产生浮动垃圾，还会出现"对象消失"的问题。
浮动垃圾的影响比较小，下次清理即可，关键是如何解决“对象消失”的问题。关于该问题，我们用图片来演示一下。
我们先看一下一次正常的标记过程：
首先是初始状态，很简单，只有 GC Roots 是黑色的。同时需要注意下面的图片的箭头方向，代表的是有向的，比如下图有两条引用链是：根节点->4->5->6 以及 根节点->4->5->7，注意对象2不在根节点的引用链上。
如果是正常扫描，则最后的图像展示如下：
因为灰色对象始终是介于黑色和白色之间的，当扫描完成后只会剩下白色和黑色。黑色对象是存活的对象，白色对象是消亡了，可以回收的对象。
那么来演示一下“对象消失”的情况：
对象5 和对象7之间是有引用关系的，如果在扫描途中，当扫描到对象5时，用户线程删除了这两者之间的引用关系（用虚线来表示取消了引用关系），转而将对象4和对象7关联起来。因为扫描是无法回头的，只能往下走，那么对象7就会被遗忘掉。
最终得到如下图示：
和之前分析的正常扫描结束的对象图对比，就能直观地看到，对象7会被当成垃圾回收。这样就出现了对象消失的情况。
怎么解决"对象消失"问题呢？
有一个大佬叫 Wilson，他在1994年在理论上证明了，当且仅当以下两个条件同时满足时，会产生"对象消失"的问题，原来应该是黑色的对象被误标为了白色：
- 条件一：赋值器插入了一条或者多条从黑色对象到白色对象的新引用。
- 条件二：赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。
注意：条件二中说的 该白色对象 指的就是条件一里面的白色对象。
所以，我们有理由相信：条件一和条件二是有先后顺序的，即必须是赋值器插入了一条或者多条从黑色对象到白色对象的新引用，然后赋值器又删除了全部从灰色对象到该白色对象的直接或间接引用。在这样的情况下，才会出现“对象消失”的情况。
目前有两种方案： 增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。
在HotSpot虚拟机中，CMS是基于增量更新来做并发标记的，G1则采用的是原始快照的方式。
什么是增量更新呢？
增量更新要破坏的是第一个条件（赋值器插入了一条或者多条从黑色对象到白色对象的新引用），当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。
可以简化的理解为：黑色对象一旦插入了指向白色对象的引用之后，它就变回了灰色对象。
什么是原始快照呢？
原始快照要破坏的是第二个条件（赋值器删除了全部从灰色对象到该白色对象的直接或间接引用），当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。
这个可以简化理解为：无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照开进行搜索。
需要注意的是，上面的介绍中无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。后文会详细介绍写屏障。
增量更新用的是写后屏障(Post-Write Barrier)，记录了所有新增的引用关系。
原始快照用的是写前屏障(Pre-Write Barrier)，将所有即将被删除的引用关系的旧引用记录下来。
垃圾收集算法
标记-清除算法
算法分为“标记”和“清除”阶段：在标记阶段，首先通过根节点，标记所有从根节点开始的可达对象。因此，未被标记的对象就是未被引用的垃圾对象。然后在清除阶段，清除所有未被标记的对象。它是最基础的收集算法，后续的算法都是对其不足进行改进得到。这种垃圾收集算法会带来两个明显的问题：
- 效率问题。回收的空间是不连续的，在对象的堆空间分配过程中，尤其是大对象的内存分配，不连续内存空间的工作效率要低于连续的空间。
- 空间碎片（标记清除后会产生大量不连续的碎片）
标记-复制算法
为了解决效率问题，“复制”收集算法出现了。它可以将内存分为大小相同的两块，每次使用其中的一块。当这一块的内存使用完后，就将还存活的对象复制到另一块去，然后再把使用的空间一次清理掉。这样就使每次的内存回收都是对内存区间的一半进行回收。
如果内存中多数对象都是存活的，这种算法将会产生大量的内存间复制的开销，但对于多数对象都是可回收的情况，复制算法需要复制的存活对象数量就会相对少。虽然该算法不会导致空间碎片的问题，但是它的代价却是将系统内存折半。
在后面介绍到的垃圾收集器，使用了复制算法的思想，新生代分为 eden 空间、from survivor、to survivor，其中 from 和 to 空间视为用于复制的两块大小相同、地位相等、且可进行角色互换的空间块。
标记-整理算法
标记-复制算法在对象存活率较高时就要进行较多的复制操作，效率将会降低。更关键的是，如果不想浪费50%的空间， 就需要有额外的空间进行分配担保，以应对被使用的内存中所有对象都100%存活的极端情况，所以在老年代一般不能直接选用这种算法。
根据老年代的特点提出的一种标记-整理算法，在标记-清除算法的基础上做了一些优化。和标记-清除算法一样，标记-整理算法也首先需要从根节点开始，对所有可达对象做一次标记，但之后，它并不是直接对可回收对象回收，而是让所有存活的对象向一端移动，然后直接清理掉端边界以外的内存。这种方法既避免了碎片的产生，由不需要两块相同的内存空间，因此性价比较高。
标记-整理算法的最终效果等同于标记-清除算法执行完成后，再进行一次内存碎片整理。
分代算法
当前虚拟机的垃圾收集都采用分代收集算法，这种算法没有什么新的思想，只是根据对象存活周期的不同将内存分为几块。一般将 Java 堆分为新生代和老年代，这样我们就可以根据各个年代的特点选择合适的垃圾收集算法。
比如在新生代中，每次收集都会有大量对象死去，所以可以选择标记-复制算法，只需要付出少量对象的复制成本就可以完成每次垃圾收集。而老年代的对象存活几率是比较高的，而且没有额外的空间对它进行分配担保，所以我们必须选择“标记-清除”或“标记-整理”算法进行垃圾收集。
总结
上文详细介绍了关于垃圾回收的基础知识，主要包括：
- 为什么要垃圾回收？
- 何时进行垃圾回收？
- 回收什么东西？
- 回收死亡的对象，那么如何判断对象已死亡？
- 可达性分析算法介绍，并发环境下存在的问题以及解决方案。
- 安全点与安全区域的介绍
- Stop-the-world
- 梳理现有的垃圾收集算法
下一讲会继续介绍垃圾收集器、JVM内存分配等内容，敬请期待。
