枚举根节点的效率

枚举根节点是必须要停顿用户线程的会引起 stop the world，如果按照上文所说的所有 GCRoots 去主动遍历它们，将会是一个相当耗时的过程，显然这是不可接受的。而实际上 Java 虚拟机并不是采用这种方式去寻找 GCRoots 的。
Java 虚拟机是使用一组称为 OopMap 的数据结构来主动记录 GCRoots 的。一旦类加载动作完成的时候，虚拟机就会把对象内什么偏移量上是什么类型的数据计算出来，在即时编译过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用。这样收集器在扫描时就可以直接得知这些信息了，并不需要真正一个不漏地从方法区等 GC Roots 开始查找。
这样就很好的解决了遍历各 GCRoots 的耗时操作，大大减少了 stop the world 的时间，于是又引出了另一个问题记录 OopMap 的时机。

记录根节点的时机

上文提到 OopMap 结构可以用来提升枚举根节点的效率，但是虚拟机并不是每执行一条指令就生成一个 OopMap 而是会在执行到特定的位置时生成对应的 OopMap 而一个特定的位置就被成为——安全点。有了安全点的设定，也就决定了用户程序执行时并非在代码指令流的任意位置都能够停顿下来开始垃圾收集，而是强制要求必须执行到达安全点后才能够暂停。

安全点

安全点位置的选取是以“是否具有让程序长时间执行的特征”为依据来进行选择的，而长时间执行一般包括：方法调用、循环跳转、异常跳转等。在这些指令执行后程序需要执行一系列指令，因此只有在具有这些功能的指令才会产生安全点。当代垃圾收集器在垃圾收集需要中断线程式都是采用主动式中断的方式，即在需要进行垃圾回收中断线程时，会给线程设置一个中断标记，当线程执行到安全点时，会不断轮询这个标记，当发现标记为真，这个时候就会主动中断挂起自己，并记录 OopMap 相关信息。

安全区域

虽然安全点已经完美解决了线程中断和根节点记录的问题，但是这个只能解决运行的线程的中断和记录的问题，如果线程此时在 sleep 或者被 block 都无法主动完成上述过程的，因此这就引入了安全区域的概念。安全区域是指能够确保在某一段代码片段之中，引用关系不会发生变化，在这个区域的任何位置进行垃圾收集大都是安全的的。有了安全区域，当线程执行到安全区域时，首先会标识自己进入了安全区域，这样在垃圾收集时就不用担心垃圾收集的问题了，可以安全完成收集工作。当线程要离开安全区域时，它需要检查虚拟机是否完成了枚举根节点的工作，如果完成了线程才可以继续执行，否则就需要等待虚拟机完成。

跨代引用

跨代引用问题其实并不是只有进行了分代收集的垃圾收集器独有的问题，只要进行部分区域收集的垃圾收集器都会存在跨代引用的问题。Java 虚拟机解决跨代引用的问题是通过一个叫记忆集的结构，记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。也就是在收集区域中有对象被非收集区域引用，因此这种对象不能被回收，需要记录下来作为 GCRoots 的一部分。目前最常用的记忆集的实现是一种叫“卡表”的结构，它也是目前最常用的一种记忆集的实现，可以把记忆集和卡表的关系理解为，Map 和 HashMap 的关系。

卡表与卡页

卡表一般可以使用一个字节数组表示，其中字节数组中的每个元素都对应着被其标识的内存区域中的一块特定的大小的内存块，这个内存块被称作卡页，卡页的大小一般为 2 的 N 次幂的字节数。
卡表与卡页的对应关系如下：
在 Java 虚拟机中卡页的大小为 2 的 9 次幂，即每个卡页为 512 字节。

1411695536795_.pic.jpg

如果在卡页中的对象存在跨代引用的，就会将这个卡页标记为脏页标识为 1，不存在跨代引用的就标识为 0，在垃圾收集时，只需要筛选出卡表中变脏的元素，就能知道哪些卡页存在跨代引用，将其加入 GCRoots 中一起扫描即可。

写屏障

卡表能很好的解决跨代引用问题了，但是随之而来的就是如何维护卡表的问题，如何将卡表中的元素变脏就成了一个必须要考虑的问题了，Java 虚拟机就是通过写屏障来处理的。这里需要区分写屏障和低延迟收集器的读屏障以及防止内存重排的内存屏障区分开来。写屏障可以看作虚拟机在操作“引用类型字段赋值”时所做的一个 AOP 切面，会在给引用类型的字段赋值时产生一个环形通知，从而进行一些必要的操作。由于 AOP 的特性，故存在写前屏障和写后屏障两种，在 G1 之前其他收集器只用到了写后屏障。也就是在给对象赋值后会进行卡表脏页的标记工作。虽然每次赋值操作都会进行卡表处理，会有性能的损耗，但是比垃圾收集时去扫描整个老年代陈本还是低很多的。这里还需要注意一个问题就是伪共享问题，因为卡表结构是一个字节数组，由于数组是连续分配在内存中的，因此需要处理为共享的问题，不然会对性能有比较大的影响。

并发中的可达性分析

在上文中提高，收集器在判断对象是否“存活”，用的是可达性分析算法来判断的。而可达性分析就要求整个过程必须要保证对象在一个能保障一致性的快照中进行分析才是准确的，这就要求必须要冻结所有的用户线程，得 stop the world。这样就会严重影响用户的体验，而且在堆比较大的情况下，这个停顿的时间会很长，因此就出现了一种可并发收集的收集器，也就是在可达性分析时，并不停顿用户线程，让用户线程和垃圾收集动作并发执行，这就引出了一种标记算法——三色标记法。

三色标记法

三色标记法，会根据“是否访问过这个对象”将其标记为三种颜色即：
白色：表示尚未被垃圾收集器访问过的。在可达性分析开始阶段所有的对象都是白色的，如果分析结束后对象仍是白色，说明此对象不可达，可以被回收。
黑色：表示此对象已经被垃圾收集器访问过了，并且这个对象所有引用的对象也都已经被扫描过了，因此它是存活的，不可被回收。也就是黑色对象不可能直接指向一个白色的对象，因为黑色对象的所有引用都被扫描了，而白色是没有扫描的对象。
灰色：表示此对象已经被垃圾收集器访问过了，但是这个对象引用的对象中，存在没有被垃圾收集器访问的对象，也就是其可以引用白色的对象。
下面是用户线程和垃圾收集线程并发进行的过程描述：

1421695539580_.pic.jpg

从上面的图示中可知，如果一个被引用的对象标记为白色时会存在“对象消失”的严重问题，即本来应该是黑色的的对象被误标记为白色了。而要出现这种情况，必须同时满足下面两个条件时才有可能发生：
1、赋值器插入了一条或多条从黑色对象到白色的对象的新引用；
2、赋值器删除了全部从灰色的对象到该白色对象的直接或者间接引用。
因此要解决上述问题只需要破坏两个条件中的一个即可，因此就产生了两种解决方法即增量更新和原始快照。

增量更新

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

原始快照

原始快照破坏的是第二个条件，当灰色的对象要删除指向白色对象的引用时，就将这个要删除掉的引用记录下来，在并发扫描就结束之后，再以这些记录过引用关系的灰色对象为根，重新扫描一次。也可以简化理解为：无论引用关系删除与否，都会按照刚刚开始扫描那一刻的的对象图快照来进行搜索。也就是将删除前的引用关系记录下来，重新扫描的时候被删除的对象还是会被扫描到。
引用关系记录的插入和删除虚拟机都是通过写屏障实现的。CMS 使用的是增量更新，G1 和 Shenandoah 是使用原始快照。