本文主要翻译自论文Garbage-First garbage collection，通过该论文大概了解了G1收集器的工作原理，也理解了原先不是特别明白的Rset，所以翻译一下算是一个笔记，大部分是原文逐字翻译，省略了不太相关的内容，对于自己阅读时理解困难的点也加入了自己的理解，肯定存在一些错误的地方，如果有读者发现还请指出。

摘要

G1是一种面向服务端的垃圾收集器，主要用于在多处理器、大内存的服务器中尽可能的提供弱实时(soft real-time)、高吞吐量的垃圾收集。基于整个堆(heap)的操作，比如全局标记(global marking)等都采用和工作线程(mutation，后续以Mutator表示工作线程)并发方式来避免因为较大的堆或者较多的存活数据造成的长时间中断。并发标记采用压缩式的evacuation(该词不好翻译，本人感觉翻译为迁移较准确，实际上该操作就是将待回收分区中的存活数据迁移或复制到新的分区中)实现垃圾回收和分区的年龄增长。迁移也是通过多个线程并行来提高吞吐量。

1 引言

Java语言常常用来编写服务端的大型应用。这些应用的特点就是拥有较大的存活数据、多线程，并且运行在强劲的多处理器上。很明显，对于这些应用来说，吞吐量十分重要。除此之外，这些应用也会有一定的响应时间要求，例如电信提供商的呼叫处理程序，如果延迟较大会让顾客感到不满。

JLS采用垃圾收集(garbage collection)来回收无用的存储。传统的"stop-word"式垃圾收集器会影响应用的响应性，所以需要并发以及增量式的垃圾回收器。

这些垃圾收集器为了减少停顿时间往往会牺牲一定的吞吐量。因此，我们允许用户指定弱实时目标(soft real-time goal)，比如在y ms的时间片内，因垃圾回收造成的停顿不允许超过x ms。通过指定这样明确的目标，垃圾收集器可以尽可能较少停顿时间以及停顿频率，但也不至于降低吞吐量或者增加垃圾收集的周期(footprint)。这篇文章介绍的G1垃圾收集算法就致力于在拥有较大内存、较高分配率(allocation rate)、多处理器的机器上满足这样的弱实时目标，并且维持较高的吞吐量。

G1垃圾收集器通过多种技术来达到这些目标：整个堆被分成一些列大小相等的区(regions)，并且采用记忆集(remembered sets，后续记为Rset)记录指向分区的应用，这些记忆集可从老年代指向年轻代，反之也成立（存在一些例外情况，后续会介绍），双向的记忆集实现了对任意分区的垃圾收集。为了保持Rset状态最新，Murtator采用特殊的写屏障(write barriers)创建Rset更新日志记录(log)，这些记录由一个并发的线程处理，依次保持较小的垃圾收集时间。

G1垃圾收集器使用snapshot-at-the-beginning(SATB)并发标记算法，SATB周期性的分析全局可达性，确保了一定的完整性—所有垃圾最终都可被识别出。并发标记同时也会统计每个分区的存活数据数量。这些信息可用于指导选择那些分区进行垃圾回收：那些具有较少存活数据、较多垃圾的分区会被更高效的进行垃圾收集，这也是"Garbage-First"名称由来。SATB标记算法同样只会引入较少的停顿。

G1垃圾收集算法采用了一种新型机制来达到实时目标。目前存在的硬实时垃圾收集器为了满足硬实时约束在复制单个对象的粒度上进行收集中断，这引入了一定时间和空间的开销。相反地，G1在分区这种更粗的粒度上进行对象拷贝（其实就是evacuation）。G1垃圾收集器基于可以快速衡量的分区的某些属性提供了评估分区回收代价(cost)的精确模型，因此垃圾收集器可以挑选那些可以在给定停顿时间进行回收的分区（至少大部分时间可以满足）。G1垃圾收集器的目标就是抛弃对这种硬实时的保证，尽最大努力达到软实时目标，并保证较好的吞吐量和空间利用率，这也是许多应用程序所要求的折中。

2 数据结构/机制

这节介绍G1使用的数据结构和相关机制。

2.1 堆布局/分区/分配

G1垃圾收集器将整个堆分成许多同等大小的区，每个区都包含连续范围的虚拟内存空间。在堆分区中进行分配就是增大top划定的已分配和未分配空间的边界。当前正在分配的分区称为当前分配分区(current allocation region)。因为我们主要关注多线程处理器，每个Mutator线程都通过CAS操作从堆中分配一个线程本地分配缓冲(thread-local allocation buffers，TLAB)，并在运行过程中将线程产生的新对象分配在自己的缓冲中，以此较少分配过程中的竞争。当当前分配分区被填满，会选择一个新的分区进行分配。空闲的分区会通过链表组织起来，这样可以使得新分区的选择在常量时间内完成。

大型对象也会可以直接分配在当前分配分区中，在TLAB之外。那些超过堆分区3/4大小的对象被称为巨型(humongous)对象，巨型对象会被分配在专用的若干连续分区中，这些分区只会用于分配巨型对象。

2.2 记忆集(Rset)的维护

每个分区都一个Rset，用来记录引用该分区内（存活）对象的位置(pointers)。维护这些对象就要求Mutator线程在修改可能造成跨分区引用时通知垃圾收集器。这些通知通过card table实现：堆中的每512字节映射为card table中的一个字节入口(entry)。每个线程也有一个关联的Rset log，用来记录对card的修改，每个线程当前log满了之后，会放到全局log中，所以还有一系列的filled RS buffers.

Rset本身也是 一种card集合(hash tables)，实际上因为并发，为了减少并发冲突，每个分区都会关联多个card tables。每个分区逻辑上的Rset就是这些card tables集合。

每次引用(pointers)写之后都会执行记忆集写屏障(Rset write barrier)。例如代码里执行了引用写操作x.f = y，寄存器rX、rY保存了x、y的地址，那么这个写操作之后的屏障伪代码如下:

1| rTmp : = rX XOR rY
2| rTmp := rTmp >> LogOfHeapRegionSize
3| //Below is a conditional move instr
4| rTmp := (rY == NULL) then 0 else rTmp
5| if(rTmp == 0) goto filtered
6| call rs_enqueue(rX)
7| filtered:

如果写操作之后x.f指向的对象y和x在一个分区中，即不是跨分区引用，那么这样的写操作就不用记录到Rset中。上述伪代码中行1、行2异或操作和移位操作之后rTmp=0就表示x和y在同一分区。行4过滤了空指针。如果这次写操作通过了这些过滤条件，那么就表示此次写操作时一次跨分区写。rs_enqueue首先会读rX所在对象的card table入口(entry)，如果该入口已经是脏状态的(dirty)，那么操作结束，不用再次置脏，这个判断避免了多次写同一位置造成的多次更新。如果入口不是脏状态，那么会置其为脏状态，然后会把指向该card的指针放入该线程的Rset log中。如果线程Rset log满了(默认放256个元素)，那么该log会被加入到全局满缓冲(global set of filled buffers)中，然后再为该线程分配一个新的缓冲区。

一旦全局满缓冲中包含的满缓冲个数达到了配置的阈值(默认5)之后，等待的并发记忆集线程(concurrent remembered set thread)会开始进行处理。并发记忆集线程将全局缓冲当做一个队列进行处理，直到全局满缓冲中的缓冲数量减少到阈值的1/4。对于全局满缓冲中的每个缓冲，处理线程会依次处理该缓冲中的每个card table指针。那些指向被频繁引用对象的card被认为是hot的，为了避免频繁处理这样的card，G1垃圾收集器尝试识别这些频繁被写地址所在的card，并且将对该地址的处理推迟到下一迁移阶段(evacuation pause)。G1通过增加另外一个card table来记录自从上次迁移阶段之后card变为脏状态的次数来识别hot card。每次处理card时都会递增该card的变脏次数，一旦次数超过了配置的阈值(默认4)，那么机会将该card加入到称为hot queue(默认大小为1k)的特殊缓冲中。hot queue会在每次迁移阶段开始时被处理，所以在迁移阶段结束时hot queue会变空。如果hot queue满了，那么会从其中淘汰一个card并进行处理。

综上，并发记忆集线程会处理那些不是hot的card以及从hot queue淘汰处理的card。在处理一个card时，首先会将该card table对应的入口状态置为clean，这样其他的线程如果再次写该card入口对应的地址时就可以再次置其为脏状态并且会被重新放入log中。然后并发记忆集线程会检查该card入口对应的所有对象的所有引用(对象的域可能也是引用)，找到那些可能造成该card被置为脏状态的引用修改，并找出那些具有指向其他分区的指针，如果找到了，那么该card会被插入到被引用对象所在分区的Rset中(注意：某个分区的Rset记录了引用该分区中对象的其他分区的card)。

我们只是用了单个的并发记忆集线程，当有空闲处理器时会并发执行Rset处理工作。如果该线程没有能力及时处理Rset缓冲，即处理速度没有Mutator线程写缓冲的速度快，那么该缓冲会变得特别大。为此，我们限制了该缓冲的大小，Mutator也会被加入进来处理来不及处理的缓冲。

2.3 迁移阶段(Evacuation Pauses)

在一个恰当的时机，我们会暂停所有的Mutator线程，开始迁移阶段。在迁移阶段，我们会将挑选的collection set分区中的存活对象复制到堆中的另一个分区中，并释放collection set分区的空间。迁移阶段的存在是为了对空间进行压缩(压缩空间碎片)，对象的移动对于Mutator来说必须是原子的。在并发环境中维护这种原子特性是cost比较大，所以迁移阶段使用STW(stop the word)方式进行。

在一个多处理器、多线程的应用中使用串行的垃圾收集器肯能会造成性能瓶颈，因此我们会尽可能的采用多线程并发的进行迁移操作。

迁移操作的第一步是串行的选择合适的collection set。然后，迁移阶段的主要操作开始进行，GC线程开始扫描未来得及处理的Rset缓冲以更新分区的Rset、扫描Rset以及其他根节点来确定存活对象，最后迁移那些存活的对象到新的分区中。这些动作之间并没有进行显示的同步，但是要保证每个操作都只会一个线程处理。

为了加快迁移时的并发分配，我们采用了GCLABs并且多个线程会尝试对同一个待回收的分区进行迁移指针安装，安装的唯一成功者会负责复制和扫描该分区中的对象，负责对其进行迁移和回收。为了实现负载均衡，采用了工作密取work stealing机制。

图1 Remembered Set Operation.png

如上面图一所示，分区R1的记忆集记录了分区R0、R1对其分区中对象的引用，分区R1被迁移到了分区R3中，分区R0中的对象a因为是垃圾所以被回收，所以R3分区的Rset只记录了分区R2中依然存活的c对b的引用。分区R0中的对象被识别为垃圾是在并发标记(concurrent marking)阶段进行的。

2.4 分代的G1

分代的垃圾回收算法具有许多优点，新分配的对象较老对象(存活时间长的对象)更有可能是垃圾，新分配对象也更有可能引用其他分区中的对象，造成需要更新其他分区的Rset，因为新分配对象经常需要进行初始化。我们可以在G1垃圾收集中利用这些特点。当一个分区被选为某个Mutator线程当前分配的分区时，我们可以标识其为young分区，这会将该分区被选进下一轮迁移的collection set。可达的（不是垃圾）的新对象在被迁移后被扫描出来（这里论文里没有说目的，个人理解可能是为了更新该分区的Rset）。

注意，collection set可以同时包含young和non-young分区。G1垃圾回收有两种模式：分代的(generational)和完全的(pure)G1，分代模式是默认模式。

分代模式还有两个子模式：迁移阶段可选择只迁移young分区（fully），也可选择同时迁移young和non-young分区（partially）。fully模式会且只会将所有的young分区加入到collection set中，partially则会将所有的young分区加入到collection set中，在满足软实时要求的同时（停顿时间允许是）也可能会将non-young分区加入到collection set中进行迁移。

2.5 并发标记

并发标记是G1垃圾回收中一个非常重要的阶段。并发标记过程不要求选择分区作为collection set的顺序性。它会提供分区中存活数据的相关信息，依次来达到垃圾优先的回收策略。

G1使用了snapshot-at-the-begining(SATB)算法进行并发标记。采用这种方式通过在标记开始时对对象图进行快照，保证了在标记开始时被识别为垃圾的对象始终为垃圾对象（这是这段翻译的字面意思，但是个人理解应该是在开始时快照图中的存活对象在整个标记结束后依然是存活对象，即使其在标记过程中已经变为不可达，后面介绍的marking write barrier就是为了保证这点）。在标记期间分配的对象需要保证其存活性。这些对象需要被标记为存活对象，但是不需要被跟踪(traced)，因为它们不是开始时快照对象图中的对象，这极大地减少了并发标记的代价。

2.5.1 标记数据结构

我们维护了两个标记位图（每个分区都会维护两个位图），分别被称为previous和next。previous位图是上一次标记结束之后的位图，记录上次标记结束之后的存活对象。next位图可能正在构建中。每次标记结束之后previous和next位图会交换身份，next位图会变成下一轮的previous维护，同时会构建下一轮的next位图。位图中的每一位都记录了某个对象的起始地址。

2.5.2 初始标记阶段/并发标记

标记周期的第一阶段是清除所有分区的next位图。然后初始标记阶段会停止所有的Mutator线程，并且会标记所有从根节点出发直接可达的对象(在分代模式GC中，初始标记会附在一个全young collection set的迁移操作中完成)。每个分区都会有连个top at mark start（TAMS）变量，一个记录previous位图位置，一个记录next位图位置。后面会使用previous TAMS和next TAMS变量代替这两个变量。这两个变量用于区分标记过程中分配的对象，这样不会因为标记时的分片操作减慢位图的更新。

图2 Implicit marking via TAMS variables.png

如图2所示，初始标记阶段会遍历所有的分区，将每个分区当前分配在位图中的位置top复制到next TAMS中。图2中的A和D正是在复制top，B和E显示了在标记过程中分配的对象会在next TAMS变量之上，会被直接视为存活对象。

所有top被复制到next TAMS之后，Mutator线程重新启动，标记周期的并发阶段也随之启动。

2.5.3 并发标记写屏障

并发标记开始做的堆快照可能会被Mutator修改。也许会将原先快照中存活的对象变成不再存活的对象，这破坏了SATB算法的原则。因此SATB算法要求Mutator线程在覆盖某一引用时记录该引用之前指向的对象（这样可以保证之前引用的对象依然可达）。下面我们列出了标记写屏障在rX地址便宜FieldOffset处的引用赋值为rY（即x.a = y）是的伪代码：

1| rTmp := load(rThread + MarkingInProgressOffset)
2| if(!rTmp) goto filtered
3| rTmp := load(rX + FieldOffset)
4| if(rTmp == null) goto filtered
5| call satb_enqueue(rTmp)
6| filtered:

在执行完上面伪代码的逻辑后，会执行指针存储操作[rX, FieldOffset] := rY，将rX起偏移FieldOffset处的应用指向rY地址上的对象。伪代码中的1、2行用于确定当前是否在并发标记过程中，如果不是则不用执行下面的记录工作，在许多应用中，这一步可以避免大部分的屏障的执行。行3用于获取rX起偏移FieldOffset处的对象，行4用于过滤空对象。在许多应用中，指针通常为会初始化为预定义的空引用，因此这样可以过滤许多的null值。

satb_enqueue操作将rX起偏移FieldOffset原先的值记录到当前线程的标记缓冲(current marking buffer)中，和记忆集缓冲一样，如果标记缓冲满了，该线程的标记缓冲会被加入到全局满标记缓冲中。并发标记线程会定时检查全局满标记缓冲的大小，如果过大则会终止对堆的遍历处理，而去处理标记缓冲。

这里的写屏障主要是为了令SATB开始时快照中的可达对象，在并发Mutator线程修改之后依然可达，比如在快照中x=y，但是因为标记时并发的，所以在标记过程中可能Mutator会执行x=z，那么此时原先x指向的y对象可能会变成不可达的对象，所以通过标记写屏障在x=z实际赋值之前，将x原先指向的y记录到buffer中，然后再执行x=z的实际赋值。这样y依然可以算作的存活的（可达的），保证了快照的性质。

2.5.4 最终标记阶段(Final Marking Pause)

当所有被标记的对象都被扫描过，以及所有处理了所有的并发标记写屏障写的buffer之后并发标记就完成了。扫描所有的标记对象很容易判断是否完成，但是因为Mutator线程在填满缓冲之前不会将缓冲放入全局缓冲中，而并发线程只会处理全局缓冲中的log，所以后面一项不是那么容易判断是否完成。并发标记采用STW方式正是为了能够可靠的正确的判断缓冲是否全部完成。采用STW方式，所有全局满缓冲中未处理的缓冲将会被正常处理，未填满的缓冲也会按同种方式被处理。这些处理是并发处理的，所以能够避免过多的Mutator未满并发标记写屏障缓冲造成的长时间停顿。

2.5.5 存活数据统计(Counting)和清理

并发标记会同一每个分区被标记的对象数量。一开始，这个操作会被作为标记的一部分进行。但是迁移阶段在迁移存活对象时也必须更新每个分区的存活对象数量，当使用多线程进行迁移操作时，多个线程可能会同时将存活对象迁移到同一个分区中，因此更新该迁入分区的存活对象数量可能会形成多线程竞争。也许存在许多相关技术可以解决这个问题，但是即使只有一个线程更新分区的存活对象数量也会造成较多的cost。因此，当最终标记阶段(Final marking)结束之后，GC线程会重新扫描每个分区，统计在当前标记TAMS变量之下的对象。这好像是清理阶段(sweeping phase)的工作，但是注意我们此时扫描存活数据仅仅通过扫描标记位图实现，而不是遍历所有的垃圾对象。

就如在2.6节会介绍的，迁移阶段中可能会存在某个标记线程正在更新分区的next TAMS时进行，所以最后需要一个STW的清理阶段(cleanup pause)去完成最终的计数(counting)过程。最终的清理阶段也会通过若干种方式完成标记工作。在这个阶段，previous和next位图会交换身份：最新完成标记的位图会变成previous位图。另外，因为标记已经完成，每个分区next TAMS变量值会被拷贝到该分区的previous TAMS变量中，如上面图2中C和F所示。存活数据信息需要在previous位图和previous TAMS变量中查询，所以标记之后新生成的标记信息将被用来决定对象是否存活。在上图2中，浅灰色是扫描到的垃圾(dead)对象，D和E中显示了上一次完成标记之后的信息是如何用于正在进行中的新一轮标记阶段的。

最终，清理阶段(cleanup pause)会根据期望的GC效率(expected GC efficiency)对分区进行排序。这里使用标记阶段估计的可回收垃圾数量除以回收该分区的代价(cost)作为评价标准。这里的代价和若干个因素有关，比如对迁移存活数据代价的估计、遍历该分区的Rset的代价等(3.2.1会讨论评估分区回收代价相关内容)。这里对分区的排序只是选择Collection set的一个初始排序，就像3.3所述，代价的预估会随着时间变化，所以这里的预估只是一个初始预估。

那些不包含任何存活数据的分区会在这个阶段被直接回收掉。对于某些应用来说，这一步可以回收相当比例的垃圾。

2.6 迁移阶段和标记(Evacuation Pauses and Marking)

这节我们会讨论迁移阶段和并发标记阶段两种主要交互。

第一，迁移阶段不会迁移那些在标记阶段被断定为非存活对象。因为该对象已经dead，所以很显然该对象不会被任何根节点引用(直接或间接)，但是该对象可能会被其他dead引用。所以仅仅跟踪是那些存活对象的引用。从其他分区指向collection set分区中对象的跨分区引用会通过collection set分区的Rset被识别出来。通过Rset识别出的引用collection set分区内对象的dead对象也同样会被忽略，不会被迁移。

第二，当我们在迁移阶段迁移某一对象时，我们需要保证该对象被正确标记，如果需要的话可以同时参考previous和next位图，这里的机制有点复杂，但是限于篇幅，不再展开介绍。

我们允许在标记线程的工作栈非空时(意为标记线程还在进行标记，还未完成标记)进行迁移操作，如果不允许迁移操作在标记线程完成前开始的话，迁移阶段可能会被不可预知的推迟(影响垃圾回收，可能会造成full gc)。标记线程工作栈中的对象可能会引用collection set分区中的对象，因为这些工作栈中的对象正在被标记，所以在previous位图中，这些对象肯定是存活的，所以这些对象会同样被迁移。为了保证标记线程工作栈中的对象被正确处理，我们也会将标记线程工作栈中的对象作为根。

2.7 流行对象处理(Popular Object Handling)

所谓的流行对象时那种被很多对象引用的对象。这节讨论如何处理流行对象以达到如下目的：减小Rset大小以及更加高效的记忆集写屏障。

我们在堆靠前的位置维护了一些专门用来存放流行对象的分区。我们希望快速识别出流行对象并将它们隔离在这些前缀分区中，这些分区不会被选做collection set分区进行回收。

当我们并发的更新分区Rset时，如果某个分区的Rset大小超过了指定的阈值，那么该分区会进入流行对象处理阶段(popularity pause)，因为Rset过大通常意味着该分区存在流行对象被其他分区的对象多次引用。流行对象处理阶段首先计算该分区内每个大象大概被引用的次数，然后将那些被引用超过指定单个对象流行阈值的对象迁移到专门存放流行对象的前缀分区中。如果没有对象被引用次数达到阈值，则不会发生迁移动作，但是每个分区的阈值会被加倍，以避免该流行对象处理阶段不久后会再次被触发。

对流行对象的特殊处理有两个好处。因为我们不会迁移那些放在前缀分区中的流行对象，所以我们不用维护这些前缀分区的Rset。后面的实验证明这样会大大减少Rset的入口(entry)数量。我们通过过滤流行对象同样减少了Rset的处理开销。我们更新2.2节中的记忆集写屏障过滤空引用的代码如下：

if(rY < PopObjBoundary) goto filtered

该成这样会同时过滤空引用和流行对象。

当对流行对象进行特殊处理时，可能会带来相当大的收益，但是在某些应用中也有可能没有任何好处，所以这里的特殊处理需要选择使用。

3 启发式算法(Heuristics)

在前面的几节中我们定义了G1垃圾收集器中使用的相关技术，这一节我们介绍G1使用的启发式算法。

3.1 输入

G1垃圾收集器的基本前提是用户指定的两个参数：

1. 堆大小的上限。
2. 一个软实时目标，即用户指定时间分片(time slice)大小以及在该时间片内可以接受的最大GC停顿时间。

另外，用户也可以指定垃圾回收是否使用分代模式(generational model，2.4节)。在未来，我们希望可以动态指定该参数。

当我们在追求达到设定的最大停顿时间目标时，我们仅仅统计STW停顿，那些并发的操作不会算作垃圾回收耗时。在多处理器的机器上，我们也假定垃圾回收造成的开销是被所有Mutator线程“均摊”的。

3.2 满足软实时目标

软实时目标是垃圾回收时的主要约束（或目的）。我们需要明确的是G1垃圾回收算法并不是一个硬实时的垃圾收集器，我们只是尽最大可能的去满足软实时目标。为了满足软实时目标，我们需要保证两点：（1）保证单次停顿不能超过设定的目标，（2）在一个指定时间片内需要规划好停顿次数，次数太多也会造成不能满足设定的目标。下面我们将讨论如何满足这些条件。

3.2.1 预测迁移停顿时间

为了保证不超过指定的停顿时间上线，我们需要谨慎地挑选Collection Set分区以保证其可以按时完成回收。我们有一个可以预测将一个分区加入到Collection set进行回收的代价模型。在分代模型中，一定数量的young分区时被强制加入到Collection set中的，在完全年轻代模式(fully-young mode)中，Collection set中的所有分区都是年轻分区。因为一定数量的young分区时强制加入Collection set的，所以我们必须能够预测回收这些数量分区所需的时间。我们通过统计历史完全年轻代模式平均回收的代价来决定将多少两次迁移操作之间产生的年轻分区加入到Collection set中。

在部分年轻代回收模式(partially-young mode)中，我们会在时间允许的前提下加入一定数量的非young分区。当判断不能满足停顿时间要求时，我们会停止向collection set中添加分区。

在后面的场景中，我们用来评估迁移collection set 的代价如下：

公式中使用的符号含义如下：

• ：是对Collection set 进行回收的代价。
• ：是对所有形式停顿都一样的一种固定代价。
• ：是扫描一个card的平均代价，是为了更新Rset必须扫描的脏card数量。
• ：是扫描记录指向当前回收分区引用所在card的代价，是分区的记忆集Rset中的card入口(entry)数量。
• ：是按字节统计的迁移（和扫描）存活数据的代价，是分区中存活数据所占的大概字节数。

上面公式中的参数，，和决定于算法实现、应用运行的平台，也在一定程度上依赖于应用本身。在运行之初我们会比较保守的设定这些值以满足停顿时间要求，在程序的运行过程中我们会根据运行中的统计数据修正(refine)这些参数的取值。为了减少程序变化对这些参数取值的影响，我们为每个参数都统计了一系列的取值，然后使用一定的置信区间来调整参数。

剩下的参数，，以及和其他使用的参数都可以计算(至少是估计)出来。比如，分区中的存活数据字节数可以由当最后一次并发标记进行统计，最后一次并发标记通常会提供一个分区的字节数上限。我们会保守的使用这个上限作为分区字节数的一个估计值。对于在最后一次并发标记过程无法提供存活字节数的分区，我们根据统计最近分配分区的存活率(survival rates)来估计其存活字节数。为了尽可能准确的对存活字节数进行评估，我们会记录一系列的存活率，并根据用户指定的置信度进行预测。

对于并发标记引入的STW停顿，我们无法进行太多的控制，我们只能尽力的去最小化其带来的代价。

3.2.2 规划停顿时间以满足停顿时间要求(Scheduling Pauses to Meet a Real-Time Goal)

在上面我们介绍了怎么去满足停顿时间要求，为了满足停顿视角要求，需要做到的第二点是让GC停顿时间不超过对每个时间片的停顿时间要求。G1垃圾回收算法的一个重要特性时只要还有足够的空间，我们总是会推迟垃圾回收动作：我们会推迟标记、迁移动作，在需要时会扩充堆的大小直到达到设定的最大限制。当为了满足停顿时间要求而必须推迟某个年轻代迁移时，为了避免下一轮迁移操作超过时间限制，我们可以让Mutator将新分配的对象分配在非young分区中。对停顿时间的规划是通过记录最近一些列时间片内GC开始/GC停止时间以及该时间片内总的STW时间实现的。通过这些统计，我们可以轻松解决如下问题：

1. 在不超过停顿时间要求的条件下，当前可以停顿的最长时间是多少？
2. 最早何时可以进行一次新的STW停顿操作？

3.3 Collection set选择

这节我们讨论在部分young模式中如何选择加入到collection set中的分区。正如在2.5节提到的，回收一个分区的效率(efficiency)等于该分区中的垃圾数量除以回收这些垃圾的预估代价。我们使用和计算同样的方法来估计垃圾的数量。需要注意的是一个分区可能只有极少的存活数据，但是因为其Rset过大造成处理回收效率较低。我们的目标就是根据回收效率递减的顺序对所有可以回收的分区进行排序。

在标记阶段的最后我们会根据回收效率队分区进行排序。但是，因为回收分区的代价会随着应用的运行而改变，特别地，一个分区的Rset也会增长。在迁移阶段刚开始时，一些指定数量的可用分区会根据初始估计的回收效率进行排序，然后这些分区会根据运行改变后的效率估计被再次排序，此时，我们会认为这些分区是根据回收效率排好序的。

当估计的停顿时间会超过设定的限制或者没有多余的空间容纳迁移的存活数据时，我们会停止从排好序的分区中选择分区加入到collection set中。当然，在迁移失败时我们也有相关的机制进行处理。

3.4 迁移阶段初始化

分代的(generational)和完全的(pure)G1模式中迁移阶段初始化使用的启发式算法有很大的不同。

首先，则所有模式中，我们都会选择一个分区大小的一个比率作为hard margin，作为hard limt。因为我们采用迁移去回收分区，那么我们就必须保证有足够的空间去容纳需要迁移的存活数据。hard margin就是为了保证此空间的存在。因此，当前空间使用达到hard limit时，必须要进行一次迁移操作。当前hard margin 是一个常量，在未来该值应该可以动态调整。例如，如果我们知道了允许的最大停顿，知道迁移（复制）每个字节的代价，那么我们就可以知道在一定时间内迁移一定数量存活对象锁需要的最大空间。

在完全young的G1模式中，我们会持续的估计在可容忍的停顿时间内可以回收的分区数量，不管何时，只要应用分配了该数量的分区，就会启动一轮迁移操作。对于状态该变比较少(steady-state)的应用，这样的特性会让其迁移停顿具有一定的周期性。如果回收周期间隔大于指定的时间片(time slice)，那么我们就可以满足软实时要求。在部分young模式中，只要停顿时间允许，我们会频繁的启动迁移阶段。通过不超过停顿时间限制的情况下尽可能多的启动迁移阶段，可以减少加入到collection set中的young分区，从而可以增加加入到collection set中的non-young分区。

3.5 并发标记初始化

在分代模式中，出发并发标记的启发式算法是简单的。我们定义另一个soft margin ，以及soft limit 。在堆空间占用超过soft limit时，在停顿时间允许的情况下，我们会在一次停顿后尽可能早的进行并发标记初始化。和hard margin一样，soft margin目前也是一个常量，但是未来也会实现动态调整。设置soft limit的目的就是为了在并发标记完成时能够做到不超过前面设置的hard limit。

在完全young模式中，迁移阶段和并发阶段的交互更加有趣。我们会根据标记阶段提供的信息去最大化标记阶段和随之进行的一系列迁移阶段的累积效率(cumulative efficiency)。标记分区在一定代价之内也会分区内全部数据都是垃圾的分区进行回收。标记阶段之后的第一次回收的都是回收效率最高的分区，因此这样的回收会增大累积回收效率。后面的回收因为根据回收效率排序靠后，所以回收效率不是很高，会拉低累积回收效率，所以累积效率会先升高到一个最大值，然后开始下降。此时，我们会启动新一轮的标记阶段，对于应用状态变化不是特别大(steady-state)的应用，每次标记和随之进行的迁移阶段都是类似的，也有一定的周期性，总体上的迁移效率会类似于第一次回收的效率，也就是比较高的那一次。

4 仿真实验

(省略)

5 相关工作

(省略)

6 总结

(省略)