无停顿的GC算法<翻译>

本文主要是介绍无停顿的GC算法<翻译>，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

​ ·································译者：黄俊

摘要

现在对于响应时间敏感的应用受限于垃圾回收堆的大小。堆内存不断增加，GC暂停时间开始不断增加，导致了较高的响应时间。因此，一个可持续改进的，可伸缩的并发垃圾回收算法值得花时间去讨论它。

硅谷公司已经构建了一个可定制化的系统（CPU，芯片，主板，操作系统），使其能够在上运行特定的垃圾回收器的虚拟机。定制化的CPU包含读屏障【附录有我的通俗解释】指令。由于读屏障指令的存在我们可以构建一个高并发的，并行的，压缩GC算法（不需要stop world阶段）【附录有解释并行和并发】。这个无停顿的算法被设计来保证在GC的每个阶段，都让mutator 拥有着高吞吐量且不会中断mutator。

需要保证收集垃圾的速度大于分配内存的速度的基本要求，无停顿垃圾回收期从来不急于完成任何一个GC阶段。任何GC阶段都不会让mutator参与太多的事情。一些无停顿的算法拥有“自我修复”（注：就是引用的修正，一会儿你看到下面就知道了，别管这是啥- -）的能力，这将会降低mutator的开销，并且让mutator对GC状态不敏感。

我们介绍了无停顿GC算法，以及它所支持的硬件特性，并且给大家展示出运行持续工作负载时的开销、效率和暂停时间的数据。

【注意】：mutator 中文翻译叫突变体，但是这里指Mutator，至于为啥老外这么叫？因为这东西修改了堆内存和对象的引用，所以这么叫咯，习惯就好。

1、介绍

今天，许多企业的应用都运行在拥有垃圾回收的虚拟机上，如JVM，.NET。大部分应用都对于响应时间很敏感，例如，人们等待web页面的响应，或者信用卡的交易。不适时的GC暂停将会导致不能够接受的响应时间。对于这些应用程序，收集器以偶尔较差的响应时间（注：例如fullGC）为代价来换取平均较高的吞吐量这是不能接受的。

这些企业应用需要一个停顿时间短的垃圾回收器（让人们不能察觉的停顿时间：10-100ms）并且能够工作在非常大的java程序中（堆大小：100MB到100gb）且能够支撑很大的并发负载（100+个并发工作线程）。这样的收集器需要在长时间内执行一致且可预测的任务，而不是简单地在短时间内完成工作负载。

一些现代的垃圾回收器依赖于写屏障施加于Mutator对堆数据的写操作（注：想想对象的赋值，为啥需要写屏障？因为线程把对象引用修改了，我得告诉GC回收线程我改了这个引用吧，不然GC无感知的话，给你把对象干掉了，那就玩完了），通过写屏障来跟踪不同堆区域的对象引用。这可以高效的支持分代或基于区域的GC（G1,CMS等），并广泛用于许多垃圾收集语言，包括大多数生产环境的Java实现。另一方面，尽管已经有了大量的学术研究，但读屏障很少用于生产系统，因为它们通常给mutator带来很大的开销。

硅谷公司已经构建了一个可定制化的系统（CPU，芯片，主板，操作系统），使其能够在上面运行特定的垃圾回收器的虚拟机。定制化的CPU包含读屏障指令。由于读屏障指令的存在我们可以构建一个高并发的，并行的，压缩GC算法（不需要stop world阶段）。无停顿算法简单，高效（低mutator开销），并且无需要STW阶段。

2、相关工作

垃圾收集的概念已经存在很长时间了。我们不试图总结所有相关的内容GC工作，相反，我们建议读者参考几个GC调查报告和一些有亮点的文章。

GC暂停及其对Mutator不可预测的影响是并发收集器早期工作背后的驱动力。人们希望制作出专用的GC硬件，并且希望很快变得可行和普及。这项早期的工作需要很多广泛的、细粒度的同步操作，因此只有在专用硬件上才可行。GC硬件直到今天还在继续被提出。

使用通用的页面保护硬件来支持GC的想法的GC算法也有一段时间了。APPEL和OSSIA保护可能包含具有非转发指针的对象的页面(最初是所有页面)。访问一个受保护的页面将会导致OS陷入（陷入内核，上下文切换）GC通过转发该页上的所有指针来处理，并且之后清理页保护。Appel在内核模式下进行转发，Ossia使用第二个不受保护的虚拟地址来映射物理内存，以供GC使用。然而，我们的无停顿收集器只保护包含被移动对象的页面，而不是保护包含指向被移动对象的指针的页面。这是一个小得多的页面集，可以对页面进行增量保护。我们的读屏障允许我们拦截和纠正个别过时的引用，并避免阻塞Mutator来修正整个页面。我们也支持特殊的GC保护模式允许快速的、非内核模式的陷阱处理程序来处理受保护的页面。（注：专业词汇有点多，这里做一下解释，大家都知道OS为了保护内核和应用程序，分了两个态：内核态和用户态，而我们的JVM和GC都运行在用户态，而敏感操作都需要Trap到内核态执行，而陷入本身是非常耗时的，所以这里的设计为在用户态执行的trap称之为GC trap handler，也就是在用户态去执行GC的读屏障。Are U OK?？？）

增量收集器(通过引用计数)的概念也并不新鲜。增量收集器能够及时的进行垃圾回收以减少应用暂停时间，并且与应用程序一起工作。由于引用计数是昂贵的，而且实际上所有的屏障(引用计数通常涉及写屏障)都会变相的对Mutator产生一些成本，因此在降低屏障成本方面有着相当多的研究。还是那句话，在硬件中实现读屏障可以大大降低成本。在我们的例子中，成本大约是一个单周期ALU指令的成本。

增量式和低暂停时间收集器再次变得非常流行——部分原因是嵌入式设备的计算能力已经发展到可以在其上运行垃圾收集语言的程度。Metronome是一个现代的单处理器嵌入式系统的低暂停时间收集器的例子，并且Metronome报告的暂停时间确实比这里报告的小。但是，正如目前所描述的，Metronome是单线程的，大型的业务类应用程序有足够的mutator来淹没任何单线程收集器（这里指的是Mutator分配内存的速度大于单线程垃圾回收器回收的速度，那么想想会发生什么呢？）。无停顿回收器的回收线程是完全并行的，可以在任何时候添加GC工作线程。Metronome需要一个册子来预测未来运行应用程序的GC需求（注：也就是记账，预估Mutator需要多大的空间），在具有固定应用程序集的嵌入式系统中，很容易提供此册子(工程师运行有限的应用程序集并测量GC消耗)。当然，服务器通常没有固定的应用程序集，GC需求非常不可预测。在Metronome中Mutator的使用率约为50%。相比之下，我们的Mutator利用率接近98%，我们使用额外的CPU来完成收集工作。作为交换总要做点取舍，Metronome提供硬实时保证，而我们只提供软实时保证。（注：因为上面有册子由程序员来预估，人工基本不会出现差错，而机器就不一样了，再好的算法也不可能做到硬实时）

我们的读屏障用于baker风格的Relocate，在允许Mutator使用它之前加载被修正的值。我们把收集垃圾的工作集中在已知的大部分已经死亡的地区，类似于G1回收器。我们的Mark阶段使用增量更新样式，而不是Snapshot-At-The-Beginning (SATB)样式（注：G1用的SATB，会造成浮动垃圾）。SATB第一次做一个读操作的时候(通常是一系列依赖性的测试)需要一个适当昂贵的写屏障。无停顿收集器则不需要写屏障。

并发的GC回收器在大多数现代生产环境JVM中都是可用的。BEA的JRockit ，SUN的HotSpot和IBM的产品JVM都有并发收集器，我们使用每个供应商提供的最新可用的Java 1.4版本进行了测试。然而，在所有情况下，这些收集器都不是默认的。它们似乎不像并行收集器那样稳定，而且有时会在Mutator上增加大量开销。对于其中一些收集器情况更糟，事务吞吐量并不比默认收集器更好。

3、硬件支持

3.1 背景

Azul系统已经建立了一个自定义系统(CPU，芯片，板，和操作系统）专门运行特定的垃圾收集的虚拟机，比如基于SUN的HotSpot JVM。我们描述了实际的生产硬件，其中有实际成本的设计，开发和调试。因此，我们有强烈的欲望去设计简单而经济的硬件。最后，我们构建的定制的GC硬件非常小。

基本的CPU内核是一个64位的RISC（注：精简指令集），经过优化可以运行像Java这样的现代被管理的语言（内存管理等）。它是一个优秀的JIT对象，而不直接执行Java字节码。每个芯片都包含24个CPU，最多16个这样的芯片可以做到cache-coherent（缓存一致性）。在一个对称的内存空间中，最大的系统拥有384个CPU核心和256G内存（注：自行百度SMP和NUMA架构，这里不过多阐述）。该机器运行一个自定义操作系统，可以运行内存允许的任意数量的jvm。单个JVM可以动态扩展以使用所有CPU和所有可用内存。

硬件支持许多快速的用户模式陷阱处理程序。这些陷阱处理程序可以在几个时钟周期中进入和离开并且经常被GC算法使用;快速陷阱是关键（注：还记得我之前说的线程上下文切换么）。硬件还通过只在用户指定的指令上执行的中断来支持快速协作抢占机制。

3.2 操作系统层面的支持

硬件TLB（注：后备缓冲区，处于MMU内存管理单元中，用来缓存地址映射。为啥需要缓存？为了保护和内存的合理运用，操作系统和CPU都会采取保护模式来进行执行，那么程序的内存就分为：虚拟地址，线性地址，物理地址，那么在X86上一个虚拟地址，也就是进程看到的这个地址会被段地址解析生成线性地址，然后再由页表生成物理地址，ARM上只有分页哈，你要问我intel和AMD为啥这么玩？为了兼容。看看吧，这么困难的地址转换，为啥不搞个缓冲区来缓存呢。）支持额外的处于普通的用户模式和内核模式之间特权级别的GC模式。GC模式的用法将在GC算法部分进行说明。一些快速用户模式陷阱以GC模式而不是用户模式启动陷阱处理程序。TLB还支持1MB的页面，因此1MB的页面成为了无停顿GC算法的基本单元且在下文中会频繁提到。

TLB由操作系统以普通的方式进行管理，当正常加载和存储的地址转换失败时，将调用正常的内核级TLB陷阱处理程序（注：当TLB不存在页面映射缓存时将会根据CPU的不同进行段映射和页映射）。设置GC特权模式位是由JVM通过调用操作系统来完成的。在TLB中访问受GC保护的页面，会导致线程进入快速的用户特权级的陷入操作（注：软中断）而不是操作系统层面的异常（注：如X86的int 指令）。

HotSpot支持GC安全点的概念，即我们对寄存器和堆栈位置上的代码有精确了解（注：参考OOPMAP信息保存了堆栈上的OOP，你想想，OOP叫做普通对象指针，你在线程栈上运行字节码的时候，我咋知道你这个线程上栈帧哪一块是java对象的指针？我是不是得需要一个map来记录一下，这样我GC的时候直接拿这些引用地址就行啦。GC安全点呢，指的就是在哪里执行GC是安全的，不可能在任何一个地方，任何一个时间都能GC吧？至少得Mutator停下来，不去修改内存才可以）。硬件通过只在用户选择的指令上执行的中断支持快速抢占机制，允许我们只在安全点快速停止单个线程。一些常见指令的变体(例如：后退分支、函数入口)被Mark为安全点，并将检查每个CPU的安全点中断位。如果一个safepoint中断位被设置，CPU将会发出一个异常，操作系统将调用一个用户模式的safepoint-trap处理程序。正在运行的线程处于一个已知的安全点，这个线程将会保存它的状态并且调用OS的操作放弃CPU。当操作系统想要抢占一个普通的Java线程时，它会设置这个位，并短暂地等待该线程让步。如果线程没有及时相应，那么它就会像往常一样被抢占。

这样做的结果是几乎所有停止的线程都已经在GC安全点上了。实现全局安全点，即停止世界(STW)暂停，比patch-and-roll-for-ward 要快得多（注：设置polling page 让线程主动跑到安全点上），而且没有通常与软件轮询模式相关的运行时成本。虽然我们提供的算法没有STW暂停，但是我们当前的实现还需要STW。因此，拥有一个快速停止机制仍然是有用的。（注：想法是美好的，现实很骨感）

我们还使用检查点，也就是需要一个点，在所有的Mutator都执行了一些操作之后，我们才能继续执行一些操作。在一个每个Mutator到达一个GC安全点时，会做少量GC相关的工作，然后继续运行。被阻塞的线程已经在GC安全点，GC线程代表它们执行操作。（注：虽然Mutator可以参与少量GC的工作，但是如果极端情况下所有Mutator都由于IO或者其他原因阻塞了呢？谁来执行GC操作？）。在STW暂停期间，所有的Mutator必须到达GC安全点，暂停时间由最慢的线程控制（注：木桶原理，动脑想想？）。在检查点上，正在运行的线程不会空闲（注：因为检查点线程都要去执行其他的一些操作），GC工作也会及时展开。一些硬件和操作系统直接支持STW和Checkpoints。

3.3 硬件读屏障

除了标准的RISC加载/存储指令集之外，CPU有一些自定义指令来帮助分配和收集对象。这一节主要研究了硬件读屏障。值得注意的是，这一屏障与20年前提出的非常相似。

读屏障执行许多检查，并在不同的GC阶段以不同的方式使用。这里简要地描述了它的行为，下一节将在GC算法的上下文中更深入地介绍它。读取屏障在加载指令之后发出，并在1个时钟内执行。有一个标准的使用负载惩罚，编译器会试图对其进行调度。

读屏障“看起来像”一个标准的load指令，因为它有一个基寄存器、一个偏移量寄存器和一个值寄存器。基地址和偏移量不被屏障检查使用，而是给陷阱处理程序使用，并在“自我修复”中使用。值寄存器中的值被假定为一个新加载的引用、一个堆指针，并通过TLB所保存使用，就像基本地址一样。如果指向堆的这个引用，指向了受GC保护的页面，则会调用快速用户空间的陷阱处理程序，以下称为GC-trap（注：GC陷入，想想int 0x80陷入内核一样，只不过这里很强，不跳转到内核，也就是没有线程上下文切换，性能 very good）。

读屏障将会忽略掉空引用（空指针）。与brooks风格的间接屏障不同，它没有null检查、没有内存访问、没有使用负载惩罚、在对象头mark word中没有额外的字段标识和不能使用缓存。此行为在并发Relocate阶段中使用。

我们还从64位地址空间中窃取一个地址位，硬件会忽略这个位(屏蔽掉它)。这个位叫做非Mark通过(NMT)位，在并发Mark阶段使用。硬件为这个位维护一个期望的值，如果引用有错误的格式，则会陷入到NMT -trap。这里也忽略空引用。请注意，可以在标准硬件上以一定的代价模拟读屏障行为。GC保护检查可以用标准页面保护进行模拟，读屏障可以用恒载指令进行模拟。可以通过双映射内存和更改页面保护来模拟NMT检查，以反映预期的NMT位值。但是，使用TLB检查引用权限意味着，检查失败后将触发一个内核级的TLB陷阱，而不是一个快速的用户模式陷阱。将此转换为用户模式陷阱通常会有一些可观的性能提升，并且可能需要修改操作系统源码。我们的读屏障指令不会在空引用上陷入，并且空引用是很常见的。要在标准硬件上模拟这一点，需要在屏障代码或映射页面0地址上进行条件测试。这进而阻止了将常规内存操作的空指针检查，这是现代jvm中常见的优化。

4、无停顿算法

无停顿GC算法分为三个主要阶段:Mark，Relocate，Remap。所有阶段都为并行且并发的（GC操作并行，GC线程与Mutator并发）。Mark位会过期，因为对象会随着时间流逝而消失，而Mark位不能反映变化。Mark负责周期性地刷新Mark位。Relocate阶段使用最近可用的Mark位来查找具有少量活着的对象的页面，Relocate和压缩这些页面，并释放物理内存。Remap阶段更新堆中每个Relocate的指针。

这里没有要求必须很快完成任何一个操作。没有哪个阶段会给需要通过快速结束来缓解的Mutator带来很大的负担。在重新开始收集之前，不存在完成某个阶段的“竞争”——Relocat是连续运行的，并且可以在任何时候立即释放物理内存。由于所有阶段都是并行的，我们只要添加更多的GC线程，GC就可以跟上任何数量的Mutator线程（注：这里指的是Mutator使用内存分配对象的速度小于GC线程回收内存的速度），与其他增量更新算法不同，没有Remark或Final Mark，并发Mark阶段在GC一次收集周期中只执行一次，尽管Mutator正忙于修改堆。GC线程与Mutator线程竞争CPU时间。在Azul的硬件通常有备用的CPU可以做GC工作。但是，在极端情况下一些CPU的一部分将执行GC，并且对Mutator不可用（注：这就会造成Mutator阻塞）。

每个阶段都涉及一个“自修复”方面，在这个方面，Mutator通过读屏障陷入去更新内存中的对象引用。这保证了同一个应用不会触发另一个陷入操作。所涉及的操作因陷入的类型不同而有所不同，详情如下。一旦Mutator的工作集已经被处理，它们就可以全速执行，不再有陷入操作。在某些必然的转移阶段，Mutator遭受“陷入风暴”，陷入风暴相当于暂停，但是很快就会恢复。我们使用最小的Mutator利用率来测量陷入风暴，它们的花费大约是20ms，分散在几百毫秒内。（注：这里指的是肯定存在一个较短的时间，所有Mutator都陷入到了GC Trap去修改自身的内存引用。）

我们提出的算法没有STW暂停，没有设置所有线程必须同时停止的点（线程安全点）。但是，为了简化现有Hotspot JVM的工程，我们的实现不得不包括一些STW。我们认为这些STW可以很容易地设计为暂停时间低于标准OS上下文切换的时间。我们将在实现阶段时，提出实现与理论的不同之处。

4.1 Mark阶段

Mark阶段是一个并行和并发的增量更新(非SATB)Mark算法，增加了读取屏障。Mark阶段负责Mark所有活动对象，以某种方式Mark活动对象以将它们与Death对象区分开来。另外，每个引用都将它的NMT位设置为期望值。Mark阶段以每1M页的方式收集的对象活跃总数。这些对象活跃总数保守估计的给出了页面上实时数据(因此保证了可回收空间的数量)，并在Relocate阶段使用。

基本思想很简单：Mark从一些根集（注：GC Root）(通常是静态全局变量和Mutator堆栈内容)开始Mark可到达的对象。在Mark一个对象(并设置NMT位)之后，该Mark线程将遍历该对象——递归地Mark它在Mark的对象中找到的所有引用。这个算法是之前发布的并行Mark算法的扩展。使Mark完全并发的实现稍微有些困难，下面将进一步描述这些问题。

4.2 Relocate阶段

Relocate阶段是对象Relocate和页面回收的阶段。如果一个页面的大部分对象都是死对象，那么通过将剩余的存活对象Relocate到其他页面，这个页面就会变得完全无用。Relocate阶段首先选择一组位于给定的稀疏阈值之上的页面。这一组中的每个页面在Mutator访问时受到保护，然后将活动对象复制到目标页面上。在页面外部维护转发信息，跟踪Relocate的对象的位置。

如果一个Mutator加载对受保护页面的引用，read-barrier指令将触发GC-trap。不允许mutator以语言可见的方式使用受保护的页面引用。GC-trap处理程序负责将过期的受保护页面引用更改为正确转发的引用。

在Relocate页面内容之后，Relocate阶段释放物理内存。它的内容再也不需要了，物理内存被操作系统回收，可以立即用于新的分配。在堆中还保留着对该页的过时引用的时候，不能释放虚拟内存，这是Remap阶段的工作。（注：前面已经介绍了点虚拟内存和物理内存的区别和映射，如果大家还是不懂可以反馈给我，我通过图形方式再出一期专门讲解OS的内存管理和Intel的奇葩操作以及Linux如何绕过这个操作的）

如图1所示，Relocate阶段不断释放内存，以跟上Mutator的分配。有时它单独运行，有时与下一个Mark阶段同时运行。

图一：完整的GC周期

4.3 Remap阶段

在Remap阶段，GC线程会遍历对象图，对堆中的每个对象引用执行读屏障。如果对象引用引用了一个受保护的页面，那么它就过时了，需要被转发，就像在对象引用上捕获了一个Mutator一样。一旦Remap阶段完成后，没有活动堆引用可以引用受前一个Relocate阶段保护的页面。此时，这些页面的虚拟内存被释放。因为Remap和Mark阶段都需要遍历所有活动对象，所以我们将它们折叠在一起。当前的Remap阶段GC循环与下一个阶段的Mark阶段同时运行，如图1所示。

Remap阶段也与Relocate阶段的第二部分同时进行。Relocate阶段是创建新的过时指针（注：也就是把对象复制到了别的页面，自然得创建一个新的指针指向它，但是原来的指针也保留着，留到Remap阶段去修改为这个新的指针，所以这里说创建了新的过时指针），这些指针只能通过Remap阶段的完整运行来修复，因此在Relocate阶段的第二部分中创建的过时指针只能在下一个Remap阶段结束时清除。接下来的几节将更深入地讨论每个阶段。

5、Mark阶段

Mark阶段首先初始化内部数据结构(例如，Mark工作列表)并清除此阶段的Mark位。每个对象都有两个Mark位，一个表示对象引用在这个GC周期中是否可到达(活着的对象)，另一个表示它在前一个周期中的状态。

然后Mark阶段Mark所有全局引用，扫描每个线程的根集，并flip（注：flip指的是将标志位反转，类似于NIO的flip方法）每个线程期望的NMT值。根集通常包括CPU寄存器和线程堆栈上的所有引用。运行着的线程自己Mark它们自己的根集来共同完成这个工作。阻塞(或停止)的线程被Mark阶段线程并行地Mark。这是一个检查点，每个线程在它的根集被Mark(并且期望值NMTflip)之后可以立即继续，但是Mark阶段在所有线程都通过检查点之前不能继续。（注：所以看得出，这里需要一个短暂的STW，这里也就是通过Mutator去识别出根集，添加到Mark的工作列表，反转NMT位，然后Mutator该干啥干啥去）

在Mark完所有根集之后，我们继续进行一个并行和并发Mark阶段。从工作列表中提取活动引用，它们的目标对象Mark为活动，并且递归地处理它们的内部引用。请注意，Mark忽略了NMT位，它只被Mutator使用。当一个对象被Mark为活动对象时，它的大小被添加到它的1M页面中的活动数据量中(只有大型对象被允许跨越页面边界，并且它们被单独处理，因此活动数据计算是精确的)。此阶段将继续，直到工作列表耗尽并且Mark所有活动对象。

并发Mutator创建的新对象被分配到在这个GC周期中不会Relocate的页面中，因此Relocate阶段不会参考它们的活动位的状态。存储在新对象(或任何对象)中的所有对象引用都已被Mark或在Mark阶段的列表。因此，新对象的活动位的初始状态与Mark阶段无关。

5.1 NMT位

增量更新Mark的难点之一就是Mutator可以从Mark线程中“隐藏”活动对象。Mutator可以将未Mark的对象引用读入寄存器，然后从内存中清除它。该对象保持活动状态(因为它的对象引用在寄存器中)，但对Mark线程不可见(因为它们已经过了Mutator堆栈扫描步骤)。未Mark的对象引用也可以存储在堆中已Mark的区域中。这个问题通常通过需要在Mark结束时另一个STW暂停来解决。在第二个STW期间，Mark线程将重新访问堆的根集和修改部分，并且必须Mark发现的任何新引用。一些GC算法使用SATB不变式来避免额外的STW暂停。SATB的成本使用了一个比较昂贵的写屏障，barrier需要读取和测试覆盖的值。

与STW暂停或写屏障不同，我们使用读屏障，并要求Mutator在加载可能未Mark的对象引用时通过进入NMT-TRAP来执行一些GC工作。我们通过依赖于读取屏障和notmarket - through位来获得陷阱行为：我们从每个对象引用中窃取的位。对象引用在我们系统中占用64位，这是一个巨大的地址空间，而硬件却实现了更小的虚拟地址空间，为了寻址，未使用的位被忽略（注：2^64次方的内存地址空间太大了，基本用不到，所以可以从中窃取一些位来作为标志位）。读屏障保持了NMT位所需值的概念，如果设置为错误，就会陷入NMT陷阱。正确设置NMT位的成本不会超过读取屏障本身的成本。不变条件是，具有正确NMT的对象引用肯定已经与Mark线程通信(即使它们还没有被Mark)。带有不正确的NMT位的对象引用可能已经被Mark出来了，但是mutator没有办法知道。它在任何情况下都通知Mark线程。

如果一个mutator线程加载了设置NMT位错误的对象引用，它就会发现一个潜在的未访问对象引用。mutator会跳转到NMT-trap处理程序。在NMT-trap处理程序中，加载的值正确地设置了它的NMT位。引用在Mark阶段中被记录。随后正确的对象引用被存储回内存中。因为对象引用在内存中改变了，所以这个特定的对象引用在将来不会引起陷阱。

这个“自我修复”的想法是关键，如果没有它，一个阶段的变化将导致所有的Mutator进入连续的NMT陷阱，直到Mark线程可以在Mutator的工作集中flipNMT位。相反，每个Mutator在运行时flip自己的工作集。在短时间的高密度Trap(“Trap风暴”)之后，工作集被转换，并且Mutator以正常的速度继续运行。在Mark阶段的稳定状态期间，Mutator只遭遇很少的陷阱并且工作集缓慢迁移。

更改内存中的引用相当于存储，即使存储的值是java语言的值，也相当于原始值。该存储对正在运行的线程的Java语义是透明的，但对其他线程是可见的：如果不小心，它可能会踩到另一个线程的存储，从而有效地反转它。Trap处理程序不是无条件地存储，而是使用比较-交换(CAS)指令来更新自陷入以来没有更改的内存。如果CAS失败，处理程序将返回当前在内存中的值(而不是最初加载的值)，并且重复读取屏障。

5.2 NMT位和初始栈扫描

在mutators的根集中的对象引用已经错过了运行读取屏障的机会。因此，初始根集堆栈扫描也flip根集中的NMT位。由于flip是通过检查点而不是STW暂停来完成的，所以在一段短暂的时间内，不同的线程会对NMT所需的值有不同的设置。两个线程可以通过在内存中Trap和更新来不断地竞争单个对象引用的期望值NMT值。这种情况只会持续很短的一段时间，直到未flip的线程通过下一个GC安全点，在那里它将捕获、flip它的堆栈并通过检查点。

请注意，单个线程不可能在其根集中用不同的NMT设置保存相同的对象引用两次。因此，我们不受pointer-equality问题的困扰，如果两个引用逐位比较不相等的话，那么他们就是真的不等。

5.3 完成Mark

当Mark线程完成工作时，Mark就几乎完成了。Mark线程需要解决一个问题：一个mutator可能加载了一个未Mark的对象引用(因此有错误的NMT位)，但还没有执行读屏障。读屏障永远不会跨越一个GC安全点，因此它足以要求mutator在没有Trap的情况下跨越一个GC安全点。Mark阶段完成需要一个检查点，但不需要其他的mutator工作。在检查点结束之前发现的任何对象引用将被并发Mark为正常。当所有的mutator都完成检查点而没有一个报告任何新的引用时，Mark阶段就完成了。如果报告了新的引用，Mark线程将解决它们，检查点将重复。由于没有创建具有“错误”NMT位值的对象引用，因此该过程最终将完成。

6、Relocate和Remap阶段

Relocate阶段是Relocate和压缩对象，并释放未使用的页面。回想一下，Mark阶段计算了每1M页的活动对象数量。没有活动对象的页面显然可以回收。只有少量活动数据的页面可以通过将活动对象Relocate到其他页面而完全不使用。

如图1所示，Relocate阶段一直在运行，以一定的速度不断释放内存以保持在mutator之前。Relocate使用当前GC-Cycle的Mark位。一个周期的Relocate阶段将与下一个周期的Mark阶段重叠。当下一个周期的Mark阶段开始时，它使用一组新的Mark位，而不改变当前周期的Mark位。

Relocate阶段首先查找未使用的页面或大部分未使用的页面。从理论上讲，完整的或者大部分完整的页面也可以Relocate，但是这样做的好处很少。图2显示了一系列1M堆页面，活动对象空间被阴影表示。有一个引用从一个完全活动的页面进入一个几乎空的页面。我们想要Relocate“几乎已死”页面中剩下的几个对象，并将它们压缩到一个“新的、空闲的”页面中，然后收回“几乎死掉”的页面。

接下来，Relocate阶段构建一个数组来保存转发指针。转发指针不能保存在对象的旧页中，因为我们将在复制后立即回收物理内存，而且在所有引用Remap之前就回收了。

更新旧引用

保存forwarding指针的数组存储的数据并不大，因为我们Relocate了稀疏的页面。
我们将它实现为一个简单的哈希表。图3显示了side数组。

然后，Relocate阶段GC保护“几乎死亡”的页面(显示为灰色)不受Mutator的影响。这个页面中的对象现在被认为是陈旧的，不允许再修改这些对象。如果一个Mutator加载一个受保护的页面中的对象引用，那么它将会进入读屏障中的GC trap。

接下来，将活动对象复制出来，并修改转发表以反映对象的新位置，如图4所示。复制过程与Mutator并发进行，读屏障使Mutator在陈旧的对象完成移动之前看不到它。活动对象使用最新可用的Mark位并扫描页面。

一旦复制完成，页面映射的物理内存就会被释放。虚拟内存无法回收，直到不再有过时的引用指向释放的页面。陈旧的对象引用留在堆中，由使用读取屏障运行的mutator惰性地发现，并将在下一个Remap阶段完全更新。释放的物理内存立即被操作系统回收，并可能分配给这个或另一个进程。释放内存后，GC线程空闲直到下一个Relocate并且释放内存，或者直到下一个Mark和Remap阶段开始。

6.1 读屏障陷入处理

如果一个Mutator的进入读障碍GC陷阱，那么这个Mutator已经加载了一个过期的对象引用。GC-trap处理程序从side数组查找转发指针，并在寄存器和内存中放置正确的值，如图5所示。类似于NMT trap处理程序的“自修复”行为，更新内存中的对象引用对性能至关重要:它使相同的陈旧对象引用不会再次陷入陷阱。与前面一样，内存更新是通过CAS完成的，以避免从另一个线程竞争而破坏存储。

也有可能需要的对象还没有被复制。在这种情况下，mutator将代表GC线程执行复制——因为mutator将被阻止继续执行。mutator可以读取GC保护的页面，因为trap处理程序以提升的GC保护模式运行。如果该mutator必须复制一个大对象，它可能会停止很长一段时间。这通常不是一个问题：有大量活着对象的页面不需要Relocate并且½页面大小的对象(512 k)可以1毫秒内复制完成。

6.2 其他Relocate阶段动作

在我们保护页面时，运行着的mutator的根集中可能有陈旧的引用。这些已经超过了它们的读取障碍，因此不会被直接捕获。mutator使用检查点从根集中清除所有已经过时的引用，当检查点完成时，可以开始Relocate。

修改TLB保护(一个内核调用和一个系统级的TLB关闭)和清除mutator堆栈的成本对于一个页面和许多页面是一样的。我们对这些操作进行批处理以降低成本，通常每次保护(以及Relocate和释放)几个gb。

注意，不需要很着急的完成Relocate阶段，我们只需要Relocate和释放页面的速度，以保持领先于mutator。还要注意，mutator不可能在未移动的陈旧对象上停止。Relocate的页面只包含一些较老的对象，它们很可能已经从mutator的工作集中移出。虚拟内存不会立即释放，但是我们有很多这样的内存。清除所有陈旧的引用并回收虚拟内存的最后一步是Remap阶段的工作。

6.3 Remap阶段

Remap阶段使用适当的转发指针更新所有陈旧的引用。它必须访问堆中的每个对象引用，以找到所有陈旧的引用。如前所述，它与下一个GC周期的Mark阶段同步运行;一个访问者逻辑同时执行陈旧的对象引用检查和NMT检查。

在Remap阶段结束时，所有在Remap阶段开始之前受保护的页面现在都已被完全清除。不再保留对这些页面的陈旧引用，因此现在可以回收这些虚拟内存页面。此时我们还释放了side数组，完成了一个GC循环。

7 现状

我们的实施的工作正在迅速进行中。在撰写本文时，它遇到了一些在无停顿GC算法中不需要的STW停顿。随着时间流逝，我们希望移出这些STW，或者将它们的暂停的最大时间设计在一个操作系统时间片之下。我们为每一个问题都提出了解决方案，并报告了当前在第8节中描述的8- warehouse 20分钟pseudo-JBB运行中实现的暂停。

7.1 在Mark阶段开始

在Mark阶段开始时，我们停止所有线程以flip所需的NMT状态。我们可以通过一个检查点来flipNMT位;成本将是NMT-bit的一些throbbing(重复NMT陷阱)，直到所有线程flip为止。此外，全局共享资源(例如SystemDictionary、JNI句柄、锁定对象)在这个STW中被Mark。设计这些来使用一个检查点是非常简单的。

最糟糕的停顿是21毫秒，平均是16毫秒。

7.2 在Mark阶段结束

在Mark阶段结束时，我们停止所有线程并执行(并行但不并发)软引用处理、弱引用处理和finalization。Java的软引用和弱引用在使对象引用无效的收集器和增强对象引用的mutator之间产生竞争。我们可以通过让收集器CAS只在对象引用保持未Mark时为空来并发地处理引用。NMT -trap处理程序已经具有适当的CAS'ing行为——收集器和mutator都通过CAS竞争记录一个新值。如果mutator赢了，则增强对象引用(收集器知道这一点)，如果收集器赢了，则无效对象引用(而变异体只看到null)。

在这个STW中处理的许多其他项目可以被设计为并发的，包括类卸载和代码缓存卸载。同样地，设计这些会很简单，但很繁琐。

最严重的停顿为16毫秒，平均为7毫秒。

7.3 在Relocate开始阶段

当GC保护一个页面时，mutator的根集需要清除。这里有两个问题:TLB释放不是原子的，并且在根集中有陈旧的引用。由于TLB释放不是原子的，所以在短时间内可以保护一些mutator而不保护其他mutator。不受保护的mutator将继续直接读写对象，受保护的mutator也需要这样做。但是，读取和写入受保护对象会强制设置GC保护陷阱。我们当前的实现是停止所有线程，并在STW下执行批量TLB切换和mutator根集清除。可以以简单的方式将其设计为并发和增量的。

我们可以使用检查点来更新TLB并清除根集。为了保持并发性，直到所有线程都通过了Relocate检查点，read barrier的TLB trap处理程序被修改为等待检查点完成，然后再继续Relocate或Remap，并在mutator中传播正确的对象引用。在受保护页面中实际访问对象引用的Mutator线程将在检查点与其他线程“汇聚在一起”，继续并发执行检查点。我们优先Relocate稀疏页面，这一事实减轻了这种影响。

最糟糕的停顿是19毫秒，平均为5毫秒。

7.4 在Mark/Remap时不允许执行Relocate

现在，我们还没有实现第二组Mark位，以允许Relocate阶段与下一个阶段同时运行
Mark/Remap阶段。这意味着我们不能在Mark/Remap阶段释放内存。我们有启发式，在Mark开始前预测mutator将需要多少页，在Mark和我们释放那么多(加上一些垫)，如果我们预测低，如果mutator突然“加速”，mutator将阻塞，直到Mark完成。设计重叠的Relocate/Mark阶段将是直截了当的。此外，我们目前还没有动态地添加线程来响应mutator加速。每个阶段结束时都有一些在阶段开始时决定的线程。

结论

Azul Systems抓住了这个难得的机会，生产了用于在产品中运行垃圾收集语言的定制硬件。这种自定义硬件支持非常强大的垃圾收集算法。尽管单个Azul CPU的速度要比X86 P4的CPU慢，但是更糟糕的情况下，事务处理时间要比前者快45倍，平均事务处理时间也差不多。

Azul的无停顿GC算法是为大型多处理器系统设计的一种完全并行和并发的算法。它不需要任何Stop-The-World暂停，也不需要在任何地方同时停止所有的mutator线程。死对象空间可以在GC周期的任何时间回收;没有哪个阶段GC算法必须在mutator耗尽可用空间之前“竞争”完成某个阶段。同样，在运行过程中，也没有突变体支付持续的高成本的阶段。在某些相移阶段会出现短暂的“陷阱风暴”，但这是由于“自我修复”的好处。

Azul的定制硬件包括一个读取屏障，这是一条针对从堆中加载的每个对象引用执行的指令。读屏障允许廉价地维护全局GC不变量。它检查是否加载可能未Mark的对象，防止未Mark的对象扩展到堆中以前Mark的区域。这允许并发增量更新将phaseMark为干净地终止，而不需要最后的STW暂停。读取屏障还会检查是否将陈旧的对象引用加载到Relocate的对象上，而且它比Brooks风格的间接屏障更便宜。

在第七节，现状包括正在进行的和未来的工作。另一个明显且令人满意的特性是不会停顿。如前所述，无停顿算法是一个单代算法。在每个Mark/Remap周期中扫描整个堆。由于该算法是并行和并发的，并且我们有大量的CPU，成本是相当低的。在完全加载的系统上，GC线程将从mutator线程窃取周期，因此我们希望GC尽可能高效。新一代的版本在大多数情况下只需要扫描年轻一代且必要的硬件屏障已经存在。

最后，我们对报告的暂停时间和事务所看到的“用户体验”延迟之间的差异感到非常惊讶。我们强烈建议GC研究人员和生产JVM提供者密切关注完整的GC算法成本，而不仅仅是那些很容易包含计时器启动/计时器停止的成本。

附录一 计算机屏障

可能你会问我，这东西不应该是读屏障、写屏障、全屏障么？学过虚拟机或者有相关概念的同学可能通过不同的渠道了解过这些屏障。那么来看看网上对于这几个屏障的解释：

引入的两个问题

1、CPU高速缓存下有一个问题：

缓存中数据与主内存的数据并不是实时同步的，各CPU(或CPU核心)间缓存的数据也不是实时同步。

在同一个时间点，各CPU所看到同一内存地址的数据的值可能是不一致的。

2、CPU执行指令重排序优化下有一个问题：

虽然遵守了as-if-serial语义，单仅在单CPU自己执行的情况下能保证结果正确。多核多线程中，指令逻辑无法分辨因果关联，可能出现乱序执行，导致程序运行结果错误。

内存屏障

处理器提供了两个内存屏障指令(Memory Barrier)用于解决上述两个问题：

写内存屏障(Store Memory Barrier):在指令后插入Store Barrier,能让写入缓存中的最新数据更新写入主内存，让其他线程可见。强制写入主内存，这种显示调用，CPU就不会因为性能考虑而去对指令重排。

读内存屏障(Load Memory Barrier):在指令前插入Load Barrier,可以让高速缓存中的数据失效，强制从主内存加载数据。强制读取主内存内容，让CPU缓存与主内存保持一致，避免了缓存导致的一致性问题。

全内存屏障(Load Memory Barrier):拥有上面两种功能

看完了上面的解释，不管你看懂与否，你只需要看我下面的一句话，我想不懂得直接醍醐灌顶，懂得直接想入非非：

屏障就是让某个东西到某个时间点上，去干某件事情，根据这个事情来判断下一步的执行动作！！！你想是不是吧。对应到这里来是啥？

CPU在执行指令的时候看到Store Barrier/Load Barrier的时候，去做了一件事，就是强制刷新或加载内存中的值，做完这个事之后呢？继续执行下一条指令。仅此而已

回到开头，为啥我称之为计算机屏障？由于冯诺依曼体系结构规定了咱们的指令放到内存中，然后CPU执行过程中从内存加载指令执行，很自然，我们的内存屏障也在内存中，所有有人叫做内存屏障，那么问题来了，如果我的屏障不在内存中呢？比如根据某个CPU的Mark位干点事呢？这也可以叫做屏障，对吧，看上面我说的概念，所以我称之为计算机屏障。当然聪明的你应该知道，举一反三，这种思想用在生活中也可以称之为生活屏障对吧。

附录二 并行和并发

谈到这个我想，很多人都在懵逼中度过，因为咱们在日常编码中，很少遇见这种东西，甚至在并行与并发的概念中迷失自我，到最后惶惶然，直接弃疗继续CRUD无烦恼的加班去了。但是，这篇论文甚至于所有计算的论文都离不开并行与并发这两个概念，因为这两个东西决定了计算机的性能和你程序的性能，小到CPU逻辑部件，大到各大框架都拥有着这两个概念，所以你不懂是不可以的，这里就用最通俗的语言记录这两个东西的概念，以及他们之间的不同点，搞懂这个很重要！！！搞不懂就别看这篇论文了，浪费时间，因为所有的垃圾回收器都是奔着这两个概念去的。

并行

知道薛定谔的猫吧？平行宇宙？两个你？嗯，对用这种思维去想，就是两个东西同一时间同时运行，就叫做并发。还不懂？

比如：看看你手边的两个电脑，啥？没有电脑？那就两个手机吧，在没有自己脑补。然后你在两个电脑或手机打开不同的软件，同时执行，得，这就叫做并行执行。啥？在不懂，转行吧。

并发

这个东西和上面那个差不多，上面叫做同一时间同时执行，那么这个就是不同时间去执行，啥意思？想想分时，啥意思呢？就是你一天的时间分成了：睡觉，吃饭，工作，陪女朋友啥的，那么称之为这一天之中的不同动作就叫做并发。

对于计算机来着就是，资源有限，不能同时给所有程序用，那么就分着时间用，那么称之为并发。

总结

对于这篇论文来说，并发指的是：应用程序与GC的工作交替执行，而不是GC在工作应用程序就停止了。并行指的是：GC的线程可以分散到不同CPU在同一时刻同时执行，所以称之为并行。

​ 作者：哈士奇-柏羲

这篇关于无停顿的GC算法<翻译>的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！