三色标记法与一些零散的思考
三色抽象
三色抽象与BFS
GC的扫描过程是对可达对象的遍历，可以看作一种多源广度优先遍历。在广度优先遍历中，会使用队列存储遍历的进度，对应于三色抽象中的灰色节点。灰色节点和黑色节点的区别在于灰色节点是当前的扫描边界，它连接着可达的白色节点，灰色节点蕴含了扫描的进度信息。
上图是对三色抽象中不同节点的描述：
- 虚拟根节点：本不存在的节点，逻辑上为所有的根节点添加一个共同的上级节点以便描述；
- 根节点：标记起始节点，GC中一般是栈区对象；
- 已标记节点：从根节点可达且被标记为可达的节点；
- 标记进度：已标记节点的边界；
- 不可达节点：从根节点不可达的节点。
对于GC来说，正确最终标记结果应该是：可达节点不会被标记为不可达，不可达节点应尽量少地被标记为可达。对应于上图来说，就是最终除不可达区域的节点存在白色外，其它节点需全部标记为黑色，并且要使得不可达区域的节点尽可能多。
三色不变性
标记过程是在一个有向图（A指向B表示A引用了B）中进行，对于增量/并发GC而言，这个有向图在遍历的同时会发生改变（节点、边的新增或删除）。在增量/并发的环境中，只使用三色抽象是无法保证标记结果的正确性的。
若有向图经过一些变化，当一个白色节点被且仅被至少一个黑色节点（包括图中的虚拟根节点）和任意多个不可达白色节点所指向时，这一白色节点本身可达，但最终会被标记为不可达。这是因为这个白色节点被放在了标记进度过去的位置，而进度只能往未来继续，无法时光倒流向前回溯。
为了增量/并发（不能直接通过阻止节点或边的增减来避免这种错误），因此需要一些方法来防止这样的错误发生。在描述具体的方法之前，也许描述这些方法所具有的能力或特性更为重要。
以下是两种可以阻止错误发生的两种能力：
- 避免黑色节点指向白色节点。
- 黑色节点可以指向白色节点，但必须使得该白色节点对于任意一个灰色节点是可达的。
这两种能力被称为三色不变性，前者是强三色不变性，后者是弱三色不变性。有向图的动态变化实际上造成的是标记边界的不确定性，而三色不变性维系的是标记边界的确定性。
完美划分？
三色不变性实际保证的是可达节点不会被标记为不可达，但是不对不可达节点应尽量少地被标记为可达做出保证。那么有没有能够在有向图会动态变化的情况下，保证在某一时刻实现完美划分（所有可达节点是黑色，不可达节点是白色）的办法呢？