1、三色标记算法
1、提到并发标记，我们不得不了解并发标记的三色标记算法。它是描述追踪式回收器的一种有效的方法，利用它可以推演回收器的正确性。
2、我们将对象分成三种类型：
1、黑色：根对象，或者该对象与它的子对象都被扫描过（对象被标记了，且它的所有field也被标记完了）。
2、灰色：对象本身被扫描，但还没扫描完该对象中的子对象（它的field还没有被标记或标记完）。
3、白色：未被扫描对象，扫描完成所有对象之后，最终为白色的为不可达对象，既垃圾对象（对象没有被标记到）。
3、三色标记算法的过程
从GC root出发遍历heap，针对可达对象先标记白色为灰色，然后标记灰色为黑色，遍历完成之后所有可达对象都是黑色的，所有白色都是可以回收的
4、下面来看一下三色标记算法的整个图解过程：
-
根对象被置为黑色，子对象被置为灰色。如下图：
image.png
其中可以看到灰色对象是已经被扫描过了，但是灰色对象里面所引用的子对象还未被扫描，所以可以看到灰色对象指向了未被扫描过的白色对象。
-
继续由灰色遍历，将已扫描了子对象的对象置为黑色，如下：
image.png
可以看到由于灰色里面的子对象已经被扫描过了，所以原灰色对象就变成了黑色了，而它所引用的白色对象由于被扫描到了，所以白色变成了灰色了。
-
遍历了所有可达的对象后，所有可达的对象都变成了黑色。不可达的对象既为白色，需要被清理：
image.png
5、对象丢失问题（漏标）
但是如果在标记过程中，应用程序也在运行，那么对象的指针就有可能改变。这样的话，我们就会遇到一个问题：对象丢失问题。那问题是如何产生的呢，下面来说一下。
-
当垃圾收集器扫描到下面情况时：
image.png
- 由于在GC扫描时应用程序线程也在同步执行，这时候应用程序执行了以下操作：
A.c = C
B.c = null -
这样， 对象的状态图变成如下情形：
image.png
-
这时候垃圾收集器再标记扫描的时候就会变成下图这样：
image.png
- 由于A变成了黑色，垃圾收信器是永远不会再扫描它了，因为垃圾回收器认为A里面的所有子对象都已经扫描完了，而问题就来了，此时C是白色，被认为是垃圾需要清理掉，显示这是不合理的，明明C是一个正常可用的对象。
6、SATB（解决漏标的情况）
在G1中，使用的是SATB(Snapshot-At-The-Beginning)的方式，删除的时候记录所有的对象。
它有3个步骤【重要！】：
1、在开始标记的时候生成一个快照图，标记存活对象。
2、在并发标记的时候，write barrier【写屏障】里把所有旧的引用所指向的对象都变成非白的。
①：对于从gray对象移除的目标引用对象标记为gray，将所有既将被删除的引用关系的旧引用记录下来，最后以这些旧引用为根重新扫描一遍。
②：对于black引用的新产生的对象标记为blcak，将所有新增的引用关系，然后根据这些引用关系为根重新扫描一遍。
3、可能存在浮动垃圾，将在下次被收集。
漏标与误标
误标没什么关系，顶多造成浮动垃圾，在下次gc还是可以回收的，但是漏标的后果是致命的，把本应该存活的对象给回收了，从而影响的程序的正确性。
网友评论