STAB算法

SATB算法思想简介

1. 并发标记之前先给Region内存打个快照，标记线程基于这个快照独立进行标记。应用线程不会直接修改这个快照中的对象，也就是说应用线程不会干扰标记线程的工作。
2. 应用线程新分配的对象都认为是活跃对象，实际在下一个并发标记周期进行标记。
3. 并发标记过程中已存在对象的引用关系变更在Remark阶段单独进行处理。在并发标记阶段如果有引用关系被删除，就记录下来，Remark阶段对这些引用关系被删除的重标记，这个破坏了步骤一，即灰色对象断开了白色对象引用的时候，记录下来，后面重新把这个白色对象标记成存活对象。

SATB明确将并发标记这一个大工程分成了三个模块，分别是对快照进行并发标记、对并发标记过程中新分配的对象全部标记为活跃、对并发标记过程中引用关系变更的对象单独进行处理。

 SATB算法实现

了解了SATB算法的核心思想之后，再来看看这个算法是如何实现的。G1回收器将堆内存分成一个一个Region，在Region中分配对象时，对象都是连续分配的。这里介绍两个指针：Bottom指针和Top指针，其中Bottom指针指向Region的初始位置，Top指针指向下一个对象分配的内存位置，如果有新的对象分配，就将Top指针向前移动。如下图所示：

 G1使用的SATB算法是基于内存快照的，那SATB算法具体怎么实现基于内存快照的标记呢？现在假设在标记之前Region如下：

这个时候要进行一轮完整的并发标记周期，按照上面的说法是要先给这个Region打个快照，这个快照实际上就是[Bottom, Top)现在这块内存区域。但是在并发标记周期内，因为有引用线程在分配对象，所以Top指针肯定会往前移动，所以为了将标记开始前Top这个位置记录下来，需要定义另一个指针TAMS（全称Top-At-Mart-Start）指向标记前Top这个位置，从Top-At-Mark-Start这个字面含义就可以理解是标记开始时Top指针所在位置，这样快照所代表的内存区域就是[Bottom, TAMS)这块，并发标记过程中标记线程就基于这块内存对象进行标记，后面Top指针就可以随意往前移动了。所以按照正常的逻辑应该是这样：

上图中Initial Marking刚开始的时候，Top指针和TAMS指针指向同一个内存位置，[Bottom, TAMS）这块内存区域有一个对应的bitmap，bitmap中每一位代表对应内存区域对象是否存活。经过并发标记之后，Remark开始的时候，Top指针因为应用线程有分配对象所以会向前移动，并发标记线程独立标记[Bottom, TAMS)这块内存区域对应的对象，标记后的结果使用bitmap表示（其中黑色方块表示对应对象被标记为活跃对象）。在并发标记过程中新生成的对象都分配在[TAMS, Top) 这块内存区域，G1算法会将这部分新生成的对象都认为是存活对象，这轮标记不处理这部分新生成对象，留到下一轮标记处理。
现在继续来看SATB算法如何处理并发标记过程中引用关系变更问题。在并发标记阶段，引用变更发生后通过写屏障会将这些变更记录并保存在一个队列里（satb_mark_queue），在remark阶段会扫描这个队列，通过这种方式，旧的引用所指向的对象就会被标记上，其子孙也会被递归标记上，这样就不会漏标记任何对象，snapshot的完整性也就得到了保证。
实际上介绍到这里基本上已经将SATB算法实现介绍的比较清楚了。下图是完整的两轮并发标记示意图（摘自网上）：

SATB算法 vs Incremental Update算法

G1的SATB算法在Remark阶段不需要暂停遍历整堆对象，只需要扫描satb_mark_queue，所以避免了这个阶段可能的长耗时。但是CMS垃圾回收器中增量更新算法因为无法知道哪些对象是并发标记阶段新增的，所以在Remark阶段需要重新扫描GC Roots标记整堆对象，这就可能带来不可控的长耗时暂停。