A Generational Mostly-concurrent Garbage Collector
(题目不知道咋翻，算了)，论文发布在2000年
注：本文讲的不完全是CMS垃圾收集器，其实讲的是并发垃圾收集器的思路。
而Java中的并发垃圾收集器包含CMS和G1。
Mostly-concurrent：不知道咋翻译，这里就翻译成近似并发
mutator：也不知道咋翻译，就按照软件给我叫突变器吧，类似于JVM的用户运行程序
看到个博客，讲的挺好的
https://www.cnblogs.com/Leo_wl/p/5393300.html
译者总结
CMS的垃圾收集算法没有选择Mark-Compact的方式，是因为Compact后，要修改所有指向该对象的引用，这个操作无法并发进行。
导致CMS老年代的内存分配是使用Free-List的方式进行分配，类似于伙伴关系算法。
接着1的说，在年轻代的收集中，对象晋升时，需要把对象复制到老年代。但是因为使用Free-List的方式，这种复制很慢。官方注意到晋升时，垃圾收集器线程和突变器线程都是暂停的，所以让CMS进行了优化，支持了线性分配模式，这种模式下，使用线性分配来进行对象晋升复制。（论文中似乎没有写出具体的实现方式）
卡表：CMS中的卡表有两个作用，或者说其实CMS运用了两个卡表，作用却是不同的。
- 用来标记老年代指向新生代对象的页，这样新生代收集的时候，也要Mark被老年代对象引用的新生代对象
- 垃圾收集的并发收集阶段，如果这个时候对象的引用产生了变化，通过写屏障，把对象的页对应的卡表的位置，置为脏页，让重新标记阶段扫描这些脏页的对象。
标记对象时，CMS使用一系列的BitMap，每一个Bit表示地址的4Byte，也就是一个对象的位置，来记录初始标记阶段从GCRoot可直接到达的对象的地址。
这样比使用容器存储这些对象的引用更省空间
并发标记阶段，突变器新分配的对象，可以是unmark的，因为重新标记阶段肯定会标记到这个对象。
但是在并发收集阶段，突变器新分配的对象，应该是mark的，防止被收集掉。
重新标记阶段，是假定并发标记阶段，引用产生变化的对象不会很多。但是如果很多的话，就会造成STW的时间过长，使用并发预清理来应对这个情况。
并发预清理，就是查看在并发标记阶段，查看卡表，对dirty的表项进行处理，然后置为clean。
这样即使降低在重新标记阶段要处理的卡表项过多。
摘要
本文报告了我们在Java编程语言的高性能虚拟机背景下实现的近似并发增量垃圾收集器的经验。
该垃圾收集器基于Boehm等人的 “近似并行（parallel） “收集算法，可以作为分代内存系统的老年代代垃圾收集器。
我们重写了目前的分代垃圾收集的写屏障代码，使之也可以识别在并发标记期间被修改的对象。
这些对象必须重新扫描，以确保并发标记阶段标记所有的活对象。
这种算法最大限度地减少了垃圾收集的暂停时间，同时对垃圾收集的平均暂停时间和整体执行时间只有很小的影响。
我们将用实验结果来支持我们的观点，包括合成基准和真实程序。
1. 介绍
在20世纪50年代末，依靠垃圾回收的编程语言就已经存在了。
尽管垃圾回收对程序的简单性和健壮性的好处是众所周知的并且也是被认同的，但大多数软件开发者仍然依赖于传统的显式内存管理，这主要是出于对性能的考虑。
直到最近Java语言被广泛接受，才使垃圾收集进入主流，并在大型系统中得到应用。
开发者对垃圾收集持怀疑态度，原因有二：吞吐量和延迟。
也就是说，他们担心收集垃圾会减慢其系统的性能，或者导致长时间的暂停，或者两者兼而有之。
计算能力的大幅提高并没有消除这些担忧，因为这些担忧通常会被内存需求的相应增加所抵消。
分代垃圾收集技术可以解决这两个性能问题。
他们根据对象的年龄将堆分成几代。将集中收集在 “年轻 “一代的垃圾会增加吞吐量，因为(在大多数程序中)年轻的对象更有可能是垃圾，所以每单位的收集工作可以回收更多的可用空间。
由于年轻一代相对于总的堆大小来说通常是很小的，所以年轻一代的收集工作通常是短暂的，从而解决了延迟的问题。
然而，在足够多的年轻一代收集中存活下来的对象被认为是长寿命的，并被 “推广 “到老一代。
即使老一代通常比较大，但最终还是会被填满，需要垃圾回收。老一代收集的延迟和吞吐量与全堆收集类似，因此，分代技术只能推迟而不能解决这个问题。
在本文中，我们提出了一种垃圾收集算法，该算法被设计成工作在分代内存系统的老年代。
它试图减少最坏情况下的垃圾收集暂停时间，同时利用分代系统的优势。
它是对Boehm等人的 “近似并行 “算法的改编。
它通常与突变器（mutator）并发运行，只是偶尔会短时间暂停突变器（mutator）。
1.1 术语说明
在本文中，如果一个收集器能够与突变器（mutator）交错运行，或者真正地并发执行，或者通过小的增量工作即可以在频繁的操作（如对象分配）上搭载，我们称它为并发收集器。
相对于并行收集器而言，并行收集器使用多个合作线程来完成收集，因此可以在共享内存多处理器上实现并行加速。
不幸的是，这个术语与Boehm等人使用的术语发生冲突，因为他们用 “并行 “来表示我们命名为 “并发 “的概念。
这个选择是歧义的；一个当地传统导致了我们的选择。因此，我们用 “近似并发 “来表示Boehm等人所说的 “近似并行”。
1.2 论文概览
第2节简要介绍了我们的实现和实验所基于的平台，第3节介绍了最初的近似并发算法。第4节描述了我们对该算法的调整，第5节包含了我们为了评估我们的实现而进行的实验结果。
最后，第6节给出了增量垃圾收集器的相关工作，第7节给出了结论和未来工作。
2. 实验平台
Sun Microsystems Laboratories Virtual Machine for Research，以下简称ResearchVM，是Sun Microsystems开发的高性能Java虚拟机。
这个虚拟机之前被称为 “Exact VM”，并已被整合到产品中；例如，用于Solaris操作环境的Java 2 SDK (1.2.1 05)生产版1就采用了优化的即时编译器[8]和快速同步机制[2]。
更为重要的是，它具有高性能的精确（即非保守[6]，也称为精确）内存管理[1]。
内存系统与虚拟机的其他部分通过一个定义良好的GC接口[27]分开。
这个接口允许不同的垃圾收集器被 “接入”，而不需要改变系统的其他部分。
目前已经构建了多种实现该接口的收集器。
除了GC接口之外，还有第二层，称为分代框架，方便实现分代垃圾收集器。
其中一位作者学会了这些接口，并在几周内实现了一个垃圾收集器，所以有一些证据表明，实现上述接口是比较容易的。
3. 近似收集
Boehm等人提出的最初的近似并发算法，是一种并发的 “三色 “收集器。
它使用写屏障使堆对象的字段更新，使包含对象呈灰色。
它的主要创新之处在于，它通过允许根位置（globals、栈、寄存器）（通常比堆位置更新更频繁）被写入，而不使用屏障来维持三色不变，从而以完全的并发性换取更好的吞吐量。
算法会暂停突变器来正确处理根基（Root）的问题，但通常只是短时间的。详细来说，该算法由四个阶段组成：
初始标记暂停。暂停所有的突变器，并记录所有从系统的根（globals、栈、寄存器）直接到达的对象。
并发标记阶段。恢复突变器操作。同时，启动并发标记阶段，标记可触及对象的闭包。这个闭包不保证标记结束时，能标记到所有可达到对象，因为突变器对引用字段的并发更新可能会阻止标记阶段标记一些存活对象。
为了处理这个复杂的问题，算法还安排跟踪堆对象中引用字段的更新。这是突变者和垃圾收集器之间唯一的互动。
最后标记暂停。再次暂停突变器，从GC Roots开始标记，完成标记阶段，将标记对象中修改后的引用字段视为附加Roots。由于这类字段只包含并发标记阶段可能没有观察到的引用对象，这就确保了最后的过渡性闭包包括了最后标记阶段开始时可以到达的所有对象。它还可能包括一些在标记后变得无法触及的引用。这些垃圾将在下一个垃圾收集周期收集。
并发收集阶段。再次恢复突变器，并同时扫过堆，去掉未标记的对象。必须注意不要重新分配新对象。在这个阶段，这可以通过分配 “活 “的对象（即标记）来实现。（没看懂，盲猜大意是这个阶段的JVM分配的对象要自带Mark标记，避免被并发收集掉）
这个描述从Boehm等人给出的描述中抽象出来：跟踪单个修改字段是最细的跟踪粒度；注意这个粒度可以变粗，可以通过降低精度来换取更高效（或方便）的修改跟踪。
事实上，Boehm等人使用了相当粗的粒度，在4.2节中讨论过。
该算法假设堆对象中引用字段的在并发收集阶段变化的概率较低，否则，最后的标记阶段将不得不重新扫描许多脏的引用字段，导致长时间的、可能是破坏性的暂停。
即使有些程序会打破这种假设，但Boehm等人报告说，在实践中这种技术表现良好，特别是对于交互式应用。
3.1 一个具体案例
图1说明了近似并发算法的操作。
在这个简单的例子中，堆中包含7个对象，并被分成4页。
在最初的标记暂停期间（未图示），所有4页都被标记为干净，对象a被标记为有效，因为它可以从线程堆栈中到达。
图1a显示了并发标记阶段中途的堆。
物体b、c和e已被标记。
此时，突变器执行两次更新：对象g放弃对d的引用，对象b的引用字段指向c，用对d的引用覆盖，这些更新的结果如图1b所示。
另外要注意的是，更新后导致第1页和第3页被弄脏了。
图1c显示了并发标记阶段结束时的堆。
显然，标记是不完整的，因为一个标记的对象b指向一个未标记的对象d。
在最终标记暂停期间，将处理这个问题：重新扫描脏页（第1页和第3页）上的所有标记对象。
这就导致b被扫描，从而对象d被标记。
图1d显示了最后标记暂停后堆的状态，现在标记已经完成。
随后将同时进行扫尾阶段，并将回收未标记的对象f。
在垃圾收集周期开始时无法到达的对象，如f，保证被回收。
但是，像c这样的对象，如果在一个收集周期内变得无法到达，就不能保证在该周期内收集，而是会在下一个周期内收集。
4. 分代系统中近似并发垃圾收集
本节详细介绍了我们的分代近似并发垃圾收集器，并记录了我们在其设计和实现过程中的一些具体方案。
我们也会尽量提出可能更适合不同系统的替代解决方案。
我们设计的垃圾收集器大部分方面都与使用该垃圾收集器作用于哪一代无关，我们将首先讲解这些。
稍后，我们将描述在分代的背景下使用该收集器的具体特性。
4.1 内存分配器
对于老年代，ResearchVM的默认配置使用的是标记扫描收集，并进行压实（compaction）传递，以实现后面的高效分配。
我们将把这个收集器的实现称为mark-compact。
压实也带来对象重定位问题，即需要更新对重定位对象的引用，这种引用更新很难并发进行。
因此，近似并发垃圾收集不会尝试对象重新定位。
因此，它的分配器使用了自由列表（free lists），按对象的大小进行隔离，对于小对象（最多100个4字节的字），每个大小的对象有一个自由列表，对于大对象，每个大小的组有一个自由列表（这些组是用类似斐波那契的序列选择的）。
有人会觉得可以使用一个更智能的分配器，在速度/碎片化之间进行更好的权衡。
事实上，Johnstone和Wilson宣称，分离式自由列表分配策略是导致最严重的碎片化的策略之一。
然而，这项工作假设了显式的 “在线 “再分配，正如C的malloc/free接口所代表的那样。
在 “离线 “的垃圾收集器中，用一个遍历整个堆的清扫阶段来凝聚连续的空闲区域以减少碎片，是比较容易和有效的。
4.2 使用卡表
分代垃圾收集需要跟踪从老一代对象到年轻一代对象的引用。
这对于正确性来说是必要的，因为一些年轻一代的对象可能是无法到达的，除非通过这种引用。
需要一个比简单地遍历整个老一代更好的方案，因为那样会使年轻一代集合的工作类似于整个堆的集合的工作。
使用了几种方案来跟踪这种老年代到新生代的对象引用后，我们在成本/精度上进行了不同的权衡。
最终ResearchVM的分代框架（见第2节）使用卡表来进行这种跟踪。
卡表是一个数组，每个条目对应于堆的一个子区域，称为卡。
通过突变器代码对堆对象内的引用字段的每一次更新都会执行一个写屏障，将包含引用字段的卡表条目对应的卡设置为脏值，
在编译后的突变器代码中，我们采用了Ho ̈lzle提出的两指令写屏障，卡表更新的额外代码可以相当高效。
我们如此设计的一个根本原因是利用这种让人开心的巧合，即这种基于卡表的高效写屏障，几乎不需要修改就可以用来执行近似并发收集所需的引用更新跟踪。因此，对老年代使用近似并发收集，除了已经产生的分代写屏障外，不会增加额外的突变器开销。
Boehm等人使用虚拟内存保护技术来跟踪指针更新，粒度是虚拟内存页粒度：一个 “脏 “页包含一个或多个被修改的引用字段。与这种方法相比，使用基于卡表的写屏障有几个优点。
- 开销少：在大多数操作系统中，调用自定义处理程序进行内存保护陷阱的成本相当高。Hosking和Moss发现使用五条指令的卡片标记屏障比基于页保护的屏障更有效率；ResearchVM中使用的两条或三条指令的实现仍然会更有效率。
- 更细粒度的信息。卡表的粒度可以根据精度/空间开销的权衡来选择。虚拟内存保护方案中的 “卡表大小 “就是页面大小，选择这个大小是因为系统优化，比如磁盘传输的效率，而这些系统属性与垃圾收集的考虑完全无关。一般来说，这些优化会导致页面大于参考更新跟踪的最佳值，通常至少为4KB。相比之下，ResearchVM的卡片大小是512字节。
- 更准确的类型信息。ResearchVM只在一张卡上的引用字段更新时才会对该卡进行脏化处理。基于虚拟内存的系统无法区分标量字段和引用字段的更新，因此可能会弄脏更多的页面，而不是跟踪修改后的指针所需要的。此外，他们的方法在其他地方也是保守的：它假设所有的字（理解是char*）都是潜在的指针。
Hosking、Moss和Stefanovic详细讨论了软件和基于页保护的屏障实现之间的权衡。他们的基本结论是，软件机制比使用虚拟内存保护的机制更有效。
平心而论，我们应该注意到，Boehm等人的系统试图满足我们系统中不存在的另一个约束：在没有编译器支持的情况下，完成不合作语言（C和C++）的垃圾收集。这个约束导致了保守的收集方案[6]，而近似并发扩展正是基于这个方案，同时也有利于使用虚拟内存技术进行引用更新跟踪，因为这个技术不需要修改突变器代码。
根据分代近似并发算法的需要，对卡表进行调整是很直接的。事实上，正如上面所讨论的，写屏障和卡表数据结构都没有改变。然而，我们仔细地注意到，卡表被两个可能同时运行的垃圾收集算法以微妙的不同方式使用。
近似并发算法需要跟踪自当前标记阶段开始以来更新的所有引用
而年轻一代的垃圾收集需要识别所有老年代到年轻代的指针。
在基础分代系统中，年轻代集合扫描所有脏的旧的卡表，搜索进入年轻代的指针。如果没有找到，在下一次采集中就不需要扫描这张卡，所以这张卡被标记为干净。在年轻代垃圾收集清理脏卡之前，必须记录该卡已被修改的信息，以备近似并发收集器使用。
这是通过添加一个新的数据结构，the mod union table来实现的，如图2所示，之所以如此命名，是因为它代表了并发标记过程中发生的每一次年轻代垃圾收集之间修改的卡表条目的联合。
卡表本身在ResearchVM中每个条目都包含一个字节；这就允许使用字节存储来快速实现写屏障。
另一方面，mod-union表是一个位向量，每个条目只有一个位。
因此，它在卡表之外增加了很少的空间开销，并且还能在卡表条目很少的时候快速遍历找到修改过的卡表条目。
我们在mod union和卡片表上维护了一个不变性：任何包含自当前并发标记阶段开始以来被修改的引用的卡表条目，要么在mod union表中被设置了位，要么在卡片表中被标记为dirty，或者两者都有。
这个不变性是由年轻代的集合来维护的，它在扫描这些脏卡之前，会设置卡表中所有脏卡的mod union位。
4.3 标记对象
我们的并发垃圾收集器使用了一系列外部的标记位（bitmap)。
对于堆中每4个字节，这个bitmap使用1bit与之对应。
这种使用外部标记位，而不是对象头中的内部标记位，可以防止突变器和收集器同时使用对象头，对对方造成干扰。
译者：这个用来表示地址，间接的表示某个对象
根扫描是一个有趣的设计，因为它受到两个相互矛盾的问题的影响。
如我们在第3节中所描述的，近似并发算法扫描根的时候，突变器会被暂停。
因此，我们希望这个过程尽可能的快。
另一方面，任何标记过程都需要对已经标记但尚未扫描的对象集（以下简称待扫描集）进行记录。
通常，这个集合是用堆外的一些数据结构来表示的，例如堆栈或队列。
一个最小化STW时间的策略是简单地把所有从GCRoots可以直接到达的对象放在这个外部数据结构中。
然而，由于垃圾回收的目的是在内存是稀缺资源的情况下回收内存，所以这种外部数据结构的大小始终是重要的关注点。
由于Java语言是多线程的，所以根集可能包括许多线程的寄存器和堆栈。
在我们的分代系统中，除了被收集的对象外，其他代的对象也被认为是根。
所以根集的内存占用可能相当大。
译者：这就导致GCRoots可直接到达的对象可能相当多，需要消耗太多的额外内存，所以这个方案不适合。
另一种能使空间成本最小化的策略是，在处理根时，立即标记所有可从根到达的对象。
许多对象可能是可以从根部到达的，但我们每次都将这些对象放在待扫描集合中，在任何给定的时间都将这个数据结构（因为根部）所需的空间最小化。
虽然这种策略适用于非并发收集，但与大部分并发算法不兼容，因为它将所有标记作为根扫描的一部分来完成。
译者：就是迭代GCRoot，慢慢迭代完，局限性很大
我们使用了这两种方法之间的折衷方案。
译者：其实不算是这种方案，就是优化了第一种方案的存储模式
折衷方案是利用外部标记位的优点。
根扫描只是简单地标记从根部直接到达的对象。
通过使用标记位向量来表示待扫描的集合，这最大限度地减少了STW的时间，并且没有额外的空间成本。
因此，并发标记阶段包括对堆的线性遍历，搜索标记位，找出活对象。这个过程的成本与堆大小成正比，和活的数据量无关，但由于清理阶段的存在，整体算法的复杂度已经不低）。
每找到一个活对象cur，我们就把cur推到一个待扫描的栈中，然后进入一个循环，从这个栈中弹出对象，并扫描它们的引用，直到栈为空。
对一个引用值ref的扫描过程（进入近似并发阶段）工作原理如下：
如果 ref 指向 cur 的前面，那么对应的对象就会被简单地标记，而不会被推到堆栈上；它将在线性遍历的后面被访问。
如果 ref 指向 cur 后面，则对应的对象既被标记，又被推到栈上。
图3说明了这个过程。标记遍历刚刚发现了一个标记对象c，其地址成为cur的值。扫描c发现了两个引用，分别是a和e。对对象e进行简单的标记，因为它的地址在cur之后。对象a在cur之前，所以它既被标记又被扫描。这将导致b，它也在cur之前，所以它也被标记和扫描。然而，对象b对d的引用只导致d被标记，因为它在cur之后，因此将在后面的遍历中被扫描。
这种技术减少了对待扫描栈的需求，因为从根集直接到达的对象永远不会超过一个。
这种方法的一个潜在缺点是线性遍历搜索活的对象，这使得标记的算法复杂度包含一个与堆的大小成正比的成分，而不仅仅是指针图中的节点和边的数量。
只有当搜索标记对象的成本大于扫描它们时的成本时，这才是一个实际的问题，但是只有在活对象稀疏的情况下才会出现这种情况。
需要注意的是，如果活对象是稀疏的，使用位图可以通过检测位向量中的零字，有效地跳过没有活物体的大区域。Printezis在磁盘垃圾收集器中使用了类似的技术。
清理阶段
当并发标记阶段完成后，清理阶段必须识别所有不可达的对象，回收他们的内存占用。
内存分配过程通常会切分一个空闲的内存块，分成2块，包括已经分配的内存块和剩下的空闲内存块，切分后的2块都比之前的空闲内存块小。
因此，为了防止平均内存块的大小不断的减小，清理阶段还必须执行某种形式的合并，即把一系列空闲内存块合并成一个大的空间内存块。
在一个非并发垃圾收集器中，如果使用了free-list的方案，通过丢弃现有的free-list，在清理阶段重新构造他们的方法，清理和合并就很容易完成。
但是在并发收集器中，这种方式就行不通了，因为在并发收集器中，在并发收集阶段，也要能够分配新的内存出去。
并发分配在两个方面使清理变得复杂。
首先，一个突变器线程可能正试图从一个空闲列表中分配内存，而清理进程正试图向该空闲列表中添加。
这种问题用互斥锁相当容易处理。
更微妙的是，清扫进程也可能与突变器线程竞争从空闲列表中移除内存块。
考虑一个块a、b和c相邻的情况。块b在空闲列表上；块a和块c曾被分配到包含对象，但都被发现无法到达。
我们希望将凝聚的块abc放到一个自由列表上。
然而，要做到这一点，我们必须首先将块b从它的空闲列表中删除，否则块b可能会被清理线程和分配线程同时使用。
互斥锁仍然可以处理这种竞争。
但是，请注意，这种情况对堆的自由列表数据结构提出了新的要求：
我们必须能够从其自由列表中删除一个任意块。分配可以从自由列表中删除对象，但只能在列表的头部删除。
当自由块只从头部被删除时，单链自由列表是高效的，而任意块的删除则更倾向于双链自由列表，它允许在恒定而非线性的时间内完成这一操作。
请注意，这不会增加任何空间开销，因为当一个块被分配时，相同的内存被用来包含对象信息，而当它没有被分配时，自由列表链接被用来包含对象信息。
4.5 垃圾收集线程
我们的系统使用一个专门的垃圾收集线程。
这种方法使我们可以利用多个CPU。
例如，一个单线程程序可以在双处理器机器上运行，并且大部分垃圾收集工作在第二个处理器上完成。
同样，收集活动可以在突变器处于非活动状态时进行，例如，在执行I/O时。
相比之下，Boehm等人以增量的方式形成收集功能，”搭载 “在由突变器线程执行的频繁操作上，例如对象分配。
我们认为选择这种方法是为了增加可移植性。
我们还决定将垃圾收集器线程标记为 “假的 “突变器线程，这意味着它在年轻代收集过程中被暂停。这有两个好处：它不会减慢需要快速收集的年轻一代的收集速度，而且它能最大限度地减少与系统其他部分的同步。
4.6 与年轻代垃圾回收的交互
有一些方法可以让我们的近似并发垃圾收集器被优化或修改为在分代收集器中为老年代工作。
首先，我们认识到，对于大多数程序来说，老年代的大部分分配是由于年轻一代的晋升。
（其余的是由老年代中的突变器 “直接 “分配，这通常只发生在太大而无法在年轻一代中分配的对象上）。
而晋升发生在mutator线程和并发垃圾收集器线程被暂停的时候，这一点简化了垃圾收集器的设计。
我们利用这种简化，在年轻代垃圾收集期间支持线性分配模式。
线性分配比基于自由列表的分配快得多（特别是当使用双向自由列表时），因为比较和修改的指针较少。
当线性分配模式生效时，只要有足够大的自由块存在，我们就会对小的分配请求保持线性分配。
这大大加快了晋升的分配速度，而晋升可能是年轻一代垃圾收集成本的主要组成部分。
在ResearchVM的默认配置中，使用压实（compact）收集方式的老年代的方案简化了年轻代收集所需的一个函数的实现。
Cheney式复制收集最优雅的一个方面是，仍然要扫描的对象集是连续的。
在一个分代系统中，一些from空间的对象可能被复制到to空间，而另一些可能被晋升到老年代，被晋升的对象也是待扫描集的一部分。
当老年代的系统使用压实，从而使用线性分配时，被晋升但尚未扫描的对象集是连续的。
但是，在非压实收集器中，被晋升的对象可能不连续。
这使得定位它们以便扫描它们的问题变得复杂。
我们通过用一个双向链表来表示被晋升但未扫描的对象集来解决这个问题。
每一个被晋升的对象都是从年轻一代的当前from区域中推广出来的，而对象的from区域版本包含一个转发指针，指向对象在老年代的新地址。
这些被推广对象的to空间副本被用作链接列表的 “节点”。
转发指针表示该集合的元素，随后的头字被用作 “下一个 “字段。
（没看懂这段）
4.7 控制启发式方法
图4显示了垃圾收集器线程执行的伪代码。
第一条语句初始化initFrac，即启动新的收集周期的堆占用阈值。
在ResearchVM收集器框架中，用户指定一个所需的堆占用率（heapOccupancyFrac）来控制堆使用。
在程序的稳定状态下，这个分数在一个收集周期结束时被占用；
当空闲空间的分数 allocBeforeCycleFrac 被分配完毕后，我们就会启动一个新的周期。
线程定期唤醒（SLEEP_INTERVAL设置为50毫秒）并检查堆内存占用率。如果已经达到initFrac，则新的循环开始，初始标记暂停。然后是并发标记阶段，接着是并发预清理（见4.9节），最后是标记暂停（见3节）。最后，这个循环由并发清除阶段完成，该阶段回收所有未标记的对象。
实际上，测试会保护最后标记暂停和并发清扫的执行：如果标记的堆占用率已经太高，清除将无法回收足够的存储空间来证明其消耗成本。所以，如果标记的堆的分数超过98%，这两步都不会执行。
译者：难道说的就是CMS并发失败时，调用单线程垃圾收集器，STW的进行FullGC
需要注意的是，”最大暂停时间 “本身并不能充分衡量垃圾收集器对系统的影响。考虑一个增量系统，将GC暂停时间限制在一个相对较小的最大值，比如50毫秒。
在一个单核处理器上，这可能仍然允许垃圾收集器大幅度的影响系统：如果在每个GC暂停之间只做了10毫秒的突变器工作，用户将观察到程序在垃圾收集过程中只以其正常速度的20%运行。
我们在后面介绍的测量是在多处理器上进行的，有一个额外的处理器可用于垃圾收集工作，因此忽略了这个问题。然而，该实现确实有一套启发式方法，旨在控制单处理器上的GC入侵。
These heuristics view concurrent collection as a race in which the collector is trying to finish collection before mutator activity allocates the free space available at the start of the collection。
（这句好难翻，原文摘出来你们自己看吧）
收集器线程以一系列的步骤完成标记和清除，每一步之后都会在一个由收集和分配的相对进度决定的时期内睡觉。突变器填充内存的速度越快，那么收集活动发生的频率就越高。
偶尔，尽管有这些启发式方法或有额外的处理器可用，但收集器线程会 “输掉比赛”：突变器线程等待一个并发收集才能继续运行。
当这种情况发生时，收集线程的剩余部分就会被非并发地执行。这将导致更长的停顿，但通常比在STW的情况下执行整个垃圾收集更短。
另外，我们可以选择在这种情况下扩大堆；
我们正在探索启发式方法来控制这种行为。
4.8 并发问题
我们已经提到了几个并发问题；例如，上一节讨论了老年代分配和清理之间的并发管理。
本节将探讨仍然存在的问题。
正如前面所讨论的，由于我们希望大部分的老年代分配是因为在年轻代收集过程由于对象晋升完成的，因此在年轻代收集过程中暂停老年代收集的决定（见第4.5节）处理了许多这样的问题。
但并不是所有的，突变器线程仍然可能偶尔直接在老年代中分配对象，而且在其数据结构不一致的关键部分，老一代收集线程必须不被打断进行年轻代收集。
老年代的对象分配，无论是直接分配还是晋升分配，都会带来两个问题。
首先，如果后台垃圾收集器处于清理阶段，我们不仅要保证对空闲列表的访问一致，还要保证对标记位的访问一致。
如果在清理期间分配了空闲块b，我们必须防止清理线程将b认为是已分配但未标记的块。
因此，在清除过程中，我们使用分配活的策略：已分配的块在位图中被标记为活块。
这种标记必须与清除线程对标记位的检查相协调。
我们也会在并发标记期间进行活对象分配，但原因有些不同。
一个可行的替代策略是分配未被标记的对象。
最后的标记暂停阶段仍然会达到一个正确的闭包：如果一个在标记期间分配的对象在标记结束时是可以到达的，那么存在着从根到标记结束时的对象的一些路径。
每一条这样的路径要么完全由标记期间分配的未标记对象组成，要么至少包含一个标记对象。
在前一种情况下，最后的标记暂停肯定会标记对象。在后一种情况下，考虑路径中的最后一个标记对象。它一定是在扫描后（因此在它被标记后）被修改成为路径的一部分，否则路径上的下一个对象将被标记为扫描的一部分。
因此，使其成为路径的一部分的修改使该对象成为脏对象。
所以，路径上最后一个被标记的对象一定是脏的，也就是说，并发标记期间分配的对象，最后肯定会被标记到。
译者：这里还有一段，大致意思是在并发标记阶段，即使新分配的对象是unmark的，也没事。但是由于在重新标记阶段会浪费一些时间进行mark，所以系统设计中，新分配的对象还是设置为marked的
4.9 并发预清理
我们在第3节中指出，高效的近似并发收集需要堆对象的引用字段具有较低的突变率。
一个突变率高的程序会创建许多脏对象，这些脏对象必须在最后的标记暂停期间重新扫描，这使得这个暂停对程序的影响很大。
我们已经开发了一种叫做并发预清理的技术，可以部分缓解这个问题。
观察到的情况相当简单：在最后的标记阶段，针对脏对象所做的很多工作都可以在之前进行，只要以一种谨慎的方式完成，以保持正确性。
在并发标记结束时，有些对象集是脏的。在不停止突变器的情况下，我们找到所有这样的脏对象；对于每一个对象，我们将该对象进行标记，然后将对应的卡表标记为clean。
由于任何进一步的突变器更新仍然会弄脏相应的对象，并且需要在最后的标记阶段对其进行处理，因此保持了正确性。
然而，我们希望的是，并发清理过程所花费的时间将大大少于之前的并发标记阶段，允许更少的时间给突变器弄脏对象。
因此，最后的标记阶段需要做的非并发工作就会减少。第5.3节将衡量这种技术的有效性。
在进一步的实验中（不包括在这些措施中），我们以两种方式扩展了并发预清洗。
首先，预清洗的最初实现只在mod-union表上工作，假设两个年轻代垃圾收集之间反映在卡片表上的修改数量相对较少。
事实证明，这对于具有高指针突变率的现实世界程序来说并不正确。因此，我们将该技术扩展到也对卡表进行预清理。
这需要创建一个新的卡表值：脏卡被改为预清洁，它被分代垃圾收集认为是脏的，但在最后的标记阶段被认为是干净的。
其次，只要遇到的脏卡数量减少一个足够的系数（目前是1/3），或者直到这个数量足够小（目前是小于1000），我们就会迭代预清洗过程。
这两个扩展在满足5.4节讨论的电信应用需求方面是有用的。
五. 实验结果
略了，实在是不想翻译了
