三色算法和SATB算法

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还是可以回收的，但是漏标的后果是致命的，把本应该存活的对象给回收了，从而影响的程序的正确性。