啃G1的时候，SATB(Snapshot At The Beginning)这个术语看我的很是迷糊。简略解释是：“GC开始时对象关联的快照”，但这个解释……貌似有点歧义。查阅了不少材料，也全都一笔带过不解释

上面联合一些前置的垃圾回收常识，总结一下我对SATB的一些了解

前置常识

增量式垃圾回收

增量（incremental）式垃圾回收，是指GC和Mutator交替运行的一种垃圾回收工作形式，如下图所示

Hotsopt中的G1就是一款增量式的垃圾回收器，老一代的CMS也有增量模式。在增量式垃圾回收下，能够升高Mutator的暂停工夫，只是吞吐量没那么高

三色标记法

三色标记法（Tri-color marking）是Edsger W. Dijkstra 等人提出的，在增量式垃圾回收里十分有用，用于标记GC过程中不同阶段的对象的状态。

  • 红色：还未搜寻过的对象
  • 灰色：正在搜寻的对象
  • 彩色：搜寻实现的对象
GC 开始运行前所有的对象都是红色。GC 一开始运行，所有从根能达到的对象都会被标记，而后被堆到栈里。GC 只是发现了这样的对象，但还没有搜寻完它们，所以这些对象就 成了灰色对象。

灰色对象会被顺次从栈中取出，其子对象也会被涂成灰色。当其所有的子对象都被涂成 灰色时，对象就会被涂成彩色。 当 GC 完结时曾经不存在灰色对象了，流动对象全副为彩色，垃圾则为红色。 这就是三色标记算法的概念。

有一点须要咱们留神，那就是为了体现彩色对象和灰色对象，不肯定要在对象头里设置标记（事实上也有通过标记来体现彩色对象和灰色对象的状况）。 在这里咱们依据对象的状况，更抽象地把对象用三个色彩体现进去。每个对象是什么样的状 况，意味着什么色彩，这些都依据算法的不同而不同。

比方在增量式的标记-革除(Mark-Sweep)算法中，能够分为以下3个阶段：

  1. 根查找阶段
  2. 标记阶段
  3. 革除阶段

在根查找阶段，把所有能从根间接援用的对象标记为灰色。在标记阶段查找灰色对象，将其援用的对象也标记为灰色，查找完结（tracing实现）后将灰色对象标记为彩色。在最初的革除阶段，将彩色对象再标记为红色

标记脱漏

如果在标记阶段执行一半暂停后，Mutator更新了对象的援用关系，就可能会导致流动对象（reachable objects）的“标记脱漏”，一旦产生了标记脱漏，就可能会在最初的革除阶段造成误回收流动对象的重大问题
**
比方上面这个场景，在标记过程中暂停之后，Mutator批改了援用关系：

(a)是刚暂停的状态，A被标记为彩色，B被标记为灰色，接下来会对B进行遍历。此时继续执行Mutator

在(b)中，Mutator将A->B的援用，批改为A->C，而后删除了B->C的援用关系，原本是A->B->C，变成了A-C，就成了(c)图的状况

这个时候如果进行从新标记阶段就会呈现问题：B原本是灰色对象，通过遍历后就被标记为了彩色。尽管此时C是流动对象，但也不会进行搜寻了，因为没有一个灰色对象关联它，所以C就不会被标记为流动对象；那么在最初的革除阶段时，就会造成误革除。这种状况就成为标记脱漏

在下面这个例子里，造成标记脱漏的要害起因是，B->C的援用被移除了

写入屏障

写入屏障(Write Barrier)在GC里并不是一个具体的算法，只是一个“形象”，其作用是在对象援用更新时减少一个“屏障”，在屏障中做一些加强操作。

上面是一段Edsger W. Dijkstra 等人提出的写入屏障实现（伪代码），在更新对象之间的援用时，须要调用write_barrier函数，从而实现“屏障”的性能。

write_barrier(obj, field, newobj){    if(newobj.mark == FALSE)        //标记新对象         newobj.mark = TRUE        //将新对象记录至标记栈        push(newobj, $mark_stack)    *field = newobj}

在write_barrier函数中，更新援用的同时，将新对象标记后再记录至标记栈里，这样的话在待会的革除阶段，产生援用变动的对象流动对象也会被失常的标记了

通过这个写入屏障的形式，就能够解决下面的标记脱漏问题，因为记录了新的援用对象，新的援用对象也会被标记为流动对象，就不会呈现标记脱漏了

汤浅太一 的算法

汤浅太一 在1990年开发了另一种增量垃圾回收算法，应用汤浅太一的写入屏障算法的GC也称为“Snapshot GC”。

这是因为这种算法是以 GC 开始时对象间的援用关系（snapshot）为根底来执行 GC 的。因而，依据汤浅的算法，在 GC 开始时回收垃圾，保留 GC 开始时的流动对象和 GC 执行过程中被调配的对象。

刚看这段时有点乱，SATB/Snapshot GC/Write Barrier几个概念有点混同了

这里说的汤浅太一的算法，只是指GC中写入屏障的另一种实现，和Edsger W. Dijkstra 等人提出不同。

“GC 开始时对象间的援用关系（snapshot）”这个也并不是说在标记阶段前，再新增一个快照的流程去记录援用关系，Snapshot的数据，都是在写入屏障中增加的
**
上面是汤浅太一 的写入屏障实现的伪代码，和下面介绍的写入屏障不同，在这个版本里，标记并增加到标记栈的对象变成了oldobj，所以才会称之为"Snapshot"，如果是记录newobj可就不能叫"Snapshot"了

write_barrier(obj, field, newobj){     oldobj = *field    if(gc_phase == GC_MARK && oldobj.mark == FALSE)         //标记老对象        oldobj.mark = TRUE         //将老对象记录至标记栈        push(oldobj, $mark_stack)    *field = newobj}

通过写入屏障，记录援用变动前的对象（关系），从而形成“快照”。在汤浅的算法中，下面的ABC援用例子过程是这样：

在B->C的援用删除后，将C（oldobj）也标记为灰色，这样在标记阶段时，C还是会被遍历，这样就防止了标记脱漏的问题。这种在援用更新时标记“老对象”的形式，才是“快照”的要害

G1 GC中的SATB

Hotspot G1 GC中的SATB，是汤浅太一写屏障算法的增强版，其外围还是基于写屏障来实现的“快照”，记录援用更新前的“老对象”

参考

  • Taiichi Yuasa, _Real-time garbage collection on general-purpose machines_, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990
  • 《垃圾回收的算法与实现》 中村成洋 , 相川光 , 竹内郁雄 (作者) 丁灵 (译者)
  • 《深刻Java虚拟机：JVM G1GC的算法与实现》中村成洋 (作者) 吴炎昌 , 杨文轩 (译者)
  • HotSpot VM 求教G1算法的原理 - 材料 - 高级语言虚拟机 - ITeye群组