关于jvm:SATB的一些理解

啃 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 群组