三色标记算法

多标-浮动垃圾

H

E

B

C

黑色

G

1. 初始化状态，白色里面是所有的数据

白色

GC Root

A

F

假设GC线程已经遍历到E（变为灰色了），此时应用线程先执行了：var G = objE.fieldG; objE.fieldG = null;  // 灰色E 断开引用 白色G objD.fieldG = G;  // 黑色D 引用 白色G此时切回GC线程继续跑，因为E已经没有对G的引用了，所以不会将G放到灰色集合；尽管因为D重新引用了G，但因为D已经是黑色了，不会再重新做遍历处理。最终导致的结果是：G会一直停留在白色集合中，最后被当作垃圾进行清除。这直接影响到了应用程序的正确性，是不可接受的。不难分析，漏标只有同时满足以下两个条件时才会发生：条件一：灰色对象 断开了 白色对象的引用（直接或间接的引用）；即灰色对象 原来成员变量的引用 发生了变化。条件二：黑色对象 重新引用了 该白色对象；即黑色对象 成员变量增加了 新的引用。从代码的角度看：var G = objE.fieldG; // 1.读objE.fieldG = null;  // 2.写objD.fieldG = G;     // 3.写1. 读取 对象E的成员变量fieldG的引用值，即对象G；2. 对象E 往其成员变量fieldG，写入 null值。3. 对象D 往其成员变量fieldG，写入 对象G ；我们只要在上面这三步中的任意一步中做一些“手脚”，将对象G记录起来，然后作为灰色对象再进行遍历即可。比如放到一个特定的集合，等初始的GC Roots遍历完（并发标记），该集合的对象 遍历即可（重新标记）。重新标记通常是需要STW的，因为应用程序一直在跑的话，该集合可能会一直增加新的对象，导致永远都跑不完。当然，并发标记期间也可以将该集合中的大部分先跑了，从而缩短重新标记STW的时间，这个是优化问题了。写屏障用于拦截第二和第三步；而读屏障则是拦截第一步。它们的拦截的目的很简单：就是在读写前后，将对象G给记录下来。

引用

D

将F、G都标记为黑色。

漏标-浮动垃圾

灰色

①

断开

2. 可达性分析算法，当达到A，D时标记为灰色状态。

1. 假设已经遍历到E（变为灰色了），此时应用执行了 objD.fieldE = null2. 此刻之后，对象E/F/G是“应该”被回收的。然而因为E已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即本轮GC不会回收这部分内存。这部分本应该回收但是没有回收到的内存，被称之为“浮动垃圾”。浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除。另外，针对并发标记开始后的新对象，通常的做法是直接全部当成黑色，本轮不会进行清除。这部分对象期间可能会变为垃圾，这也算是浮动垃圾的一部分。

②

当标记为E为访问的对象后，E对象不在被引用，E后面的对象断开引用G，这时候进行标记，标记时G被引用到了D上面，我们发现D其实已经被标记为黑色了，所以不会从新标记D了。

2.E节点已经访问过，并且E节点引用的F，G节点也已经访问过，所以直接标记为黑色。由于F，G节点刚访问还未访问他引用的节点所以标记为灰色。

③

⑤

假设现在有白、灰、黑三个集合（表示当前对象的颜色），其遍历访问过程为：初始时，所有对象都在 【白色集合】中；将GC Roots 直接引用到的对象 挪到 【灰色集合】中；从灰色集合中获取对象：3.1. 将本对象 引用到的 其他对象 全部挪到 【灰色集合】中；3.2. 将本对象 挪到 【黑色集合】里面。重复步骤3，直至【灰色集合】为空时结束。结束后，仍在【白色集合】的对象即为GC Roots 不可达，可以进行回收。

④

当标记为E为访问的对象后，E对象不在被引用，E后面的对象会继续标记，这部分内容称之为浮动垃圾，会在下一次进行回收。