无停顿GC算法，ZGC原理
1. 简介
文章翻译的是，Azul Systems很多年前提出的Pauseless GC
当中实现的算法正是ZGC所采用的
2. ZGC介绍
基于Region内存布局的，（暂时）不设分代的，使用了读屏障、染色指针和内存多重映射等技术来 实现可并发的标记-整理算法的，以低延迟为首要目标的一款垃圾收集器。
3. 正文翻译
摘要
现代事务响应时间敏感的mutator。在垃圾收集堆的大小上遇到了实际的限制。堆只能在GC暂停超过responsetime限制之前增长。可持续的、可伸缩的并发收集已经成为值得付费的特性。
Azul Systems已经构建了一个定制系统（CPU、芯片、板和操作系统）专门用来运行垃圾收集的虚拟机。这个自定义CPU包括一个 read barrier（读屏障）指令。read barrier实现高度并发（没有 STW 阶段），并行压缩GC算法。无停顿算法设计用于在每个GC阶段不间断地执行mutator和一致的mutator吞吐量。
mutator mutator它的实体就是“应用程序”。 GC 就是在这个 mutator 内部精神饱满地工作着。 mutator 实际进行的操作有以下 2 种： • 生成对象 • 更新指针 mutator 在进行这些操作时，会同时为应用程序的用户进行一些处理（数值计算等）。随着这些处理的逐步推进，对象间的引用关系也会“改变”。伴随这些变化会产生垃圾，而负责回收这些垃圾的机制就是 GC。
除了收集速度超过分配速度的基本要求之外，Pauseless收集器从不“匆忙”地完成任何GC阶段。没有哪个阶段会给应用程序带来不适当的负担，也没有哪个阶段会在应用程序产生更多的工作之前争先完成。Pauseless算法的一部分还具有“自我修复”行为，它限制了mutator的开销并降低了mutator对当前GC状态的敏感性。
Pauseless算法 也就是无停顿算法
我们将介绍Pauseless GC算法、支持它的硬件特性，以及运行持续工作负载时的开销、效率和暂停时间方面的数据。
分类和主题描述
D.3.4 [Processors] – Memory management, D.3.3 [Language Constructs and Features] – Dynamic storage management,
一般词汇
语言，性能，设计，算法。
关键词
读屏障，内存管理，垃圾回收，并发GC，Java，定制硬件
1. 简介
今天的许多企业应用程序都是基于垃圾收集的虚拟机环境，如Java和.NET。
大多数都有响应时间敏感的组件——例如，一个人可能正在等待网页加载，或者需要完成信用卡刷卡。由于不适当的GC暂停而停止会导致无法接受的响应时间。对于这些应用程序，收集器以偶尔的低响应时间为代价来驱动高平均吞吐量是不可接受的。
这些企业应用程序需要一个低暂停时间收集器(暂停时间按照人的反应顺序，10-100ms)，可以处理非常大的Java程序(堆大小从100MB到100GB)和高并发工作负载(100个并发mutator线程)。这样的收集器需要在很长一段时间内保持一致和可预测的性能，而不是简单地在工作负载的短时间爆发中表现出色。
许多现代垃圾收集器依赖于在mutator堆写上施加的write barriers（写屏障），以跟踪不同堆区域之间的引用。这实现了高效的分代或基于区域的GC，并在许多垃圾收集语言中广泛使用，包括大多数生产Java实现。另一方面， Read barriers（读屏障）很少在生产系统中使用，尽管有大量的学术研究，因为它们通常招致高mutator 成本。
Azul Systems构建了一个定制的系统(CPU、芯片、主板和操作系统)，专门用于运行垃圾收集虚拟机。自定义CPU包括一个读屏障指令。读屏障支持高并发、并行和压缩的GC算法。Pauseless GC算法简单、高效(低mutator开销)，并且没有停顿。
2. 相关工作
垃圾收集的概念已经存在很长时间了。我们不打算总结所有相关的GC工作，而是向读者推荐几个GC调查，并突出显示一些论文。
GC暂停及其对mutator不可预测的影响是并发收集器早期工作背后的驱动力。当时的预期是，特殊的GC硬件不久将成为可行的和普遍的。这种早期工作需要广泛的细粒度同步，因此只有在专用硬件上才可行。直到今天，仍然有人提出使用GC硬件。
使用公共页面保护硬件来支持GC的想法也已经有一段时间了。Appel和Ossia都保护那些可能包含带有非转发指针的对象的页面(最初是所有页面)。访问受保护的页会导致操作系统陷阱，GC通过转发该页上的所有指针来处理该陷阱，然后清除页保护。Appel以内核模式进行转发，Ossia用第二个不受保护的虚拟地址映射物理内存供GC使用。Pauseless收集器保护包含被移动对象的页面，而不是保护包含指向移动对象的指针的页面。这是一个小得多的页面集，并且可以对页面进行增量保护。我们的读取屏障允许我们拦截和纠正个别过时的引用，并避免阻塞mutator来修复整个页面。我们还支持一种特殊的GC保护模式，以允许快速的、非内核模式的陷阱处理程序访问受保护的页面。
增量收集器(通过引用计数)也不是新概念。增量收集通过在时间上分散收集工作，精细地交错GC工作和mutator工作来减少暂停时间。因为引用计数很昂贵，而且实际上所有的屏障(引用计数通常涉及 write barrier（写屏障）)都会增加一些mutator的成本，因此在降低屏障成本方面有很多研究。在硬件中实现read-barrier大大降低了成本。在我们的例子中，典型的成本大约是一条单周期ALU指令的成本。
增量式和低暂停时间收集器再次变得非常流行——部分原因是嵌入式设备的计算能力已经增长到可以在其上运行垃圾收集语言的程度。Metronome是用于单处理器嵌入式系统的现代低暂停时间收集器的一个示例，Metronome报告的暂停时间实际上比这里报告的要小。但是，目前描述的Metronome是单线程的，大型业务类应用程序有足够的修改器来覆盖任何单线程收集器。Pauseless是完全并行的，可以在任何时候添加GC工作线程。Metronome要求oracle预测正在运行的应用程序的未来GC需求;这个oracle很容易在嵌入式系统中使用固定的应用程序集提供(工程师运行有限的应用程序集并度量GC消耗)。服务器通常没有固定的应用程序集，并且GC需求高度不可预测。Metronome mutator的使用率约为50%。相比之下，我们的mutator利用率接近98%，我们使用额外的cpu来完成收集工作。作为交换，Metronome提供硬实时保证，而我们只提供软实时保证。
我们的 read-barrier（读障碍）用于 Baker-style 的重新定位，即在允许mutator使用它之前更正加载的值。我们把收集工作集中在那些已知大多死亡的regions，类似于Garbage-First(G1收集器)。我们的标记阶段使用增量更新风格，而不是开始快照(SATB)风格。SATB需要一个稍微昂贵的写屏障，它首先执行读取(通常是一系列依赖测试)。Pauseless收集器不需要 write barrier（写屏障）
G1收集器 G1收集器就是Garbage-First，为什么叫这个名字，是因为G1收集器在后台维护了一个优先列表，每次根据允许的收集时间，优先选择回收价值最大的Regin.
并发GCs在大多数现代生产JVM中都是可用的;BEA的JRockit、SUN的HotSpot和IBM的生产JVM都有并发收集器，我们用每个供应商提供的Java 1.4的最新可用版本进行了测试。然而，在所有情况下，这些收集器都不是默认的。它们看起来不像并行收集器那样稳定，而且它们有时会给mutator线程带来很高的开销。对于其中一些收集器，最差情况下的事务时间并不比默认收集器好。
3. 硬件支持
3.1 背景
Azul Systems构建了一个定制系统(CPU、芯片、主板和OS)，专门用于运行垃圾收集虚拟机(如Java);JVM基于SUN的HotSpot。我们描述了实际生产的硬件，这些硬件在设计、开发和调试方面有实际的成本。因此，我们有强烈的动机设计简单和成本效益高的硬件。最后，我们构建的自定义GC硬件非常小。
基本的CPU核心是一个64位的RISC，经过优化可以运行Java等现代托管语言。它是一个优秀的JIT目标，但不直接执行Java字节码。每个芯片包含24个cpu，多达16个这样的芯片可以使缓存相干;最大规模的系统有384个CPU核和256G内存在一个平坦的、对称的内存空间。该机器运行自定义操作系统，并可以在内存允许的情况下运行尽可能多的jvm。单个JVM可以动态伸缩以使用所有cpu和所有可用内存。
硬件支持许多快速的用户模式陷阱处理程序。这些陷阱处理程序可以在几个时钟周期(4-10个，具体取决于)内输入和保留，并且经常被GC算法使用;快速陷阱是关键。硬件还通过中断支持一种快速的协作抢占机制，中断只能在用户选择的指令上进行。
3.2 操作系统支持
硬件TLB在通常的用户模式和内核模式之间支持额外的特权级别——gc模式。GC算法部分解释了这种GC模式的使用。有几个快速的用户模式陷阱以gc模式而不是用户模式启动陷阱处理程序。TLB还支持1兆字节的页面;1M页面因此成为Pauseless GC算法的标准工作单元，经常出现在下面。
操作系统按照通常的方式管理TLB，当正常的加载和存储无法进行地址转换时，将调用普通的内核级TLB陷阱处理程序。JVM通过调用操作系统来设置GC特权模式位。gc保护页面上的TLB违规将生成快速的用户级陷阱，而不是操作系统级异常。
HotSpot支持GC安全点的概念，也就是我们对寄存器和堆栈位置有精确了解的代码位置。硬件通过中断支持一种快速协作抢占机制，中断只能在用户选择的指令上进行，允许我们仅在安全点快速停止单个线程。一些常见指令的变体(例如，向后分支，函数条目)被标记为安全点，并检查是否有一个等待的每个cpu安全点中断。如果安全点中断处于挂起状态，CPU会出现异常，操作系统会调用用户模式的安全点陷阱处理程序。运行中的线程处于已知的安全点，然后将其状态以某种方便的格式保存，并调用操作系统生成。当操作系统想要抢占一个普通Java线程时，它会设置这个位并简短地等待线程让步。如果线程没有及时返回报告，它就会像往常一样被抢占。
安全点
安全点就是指代码中一些特定的位置，当线程运行到这些位置的时候它的状态是确定的，这样JVM就可以安全的进行一些操作，比如GC等，所以GC不是想什么时候触发就立即触发的，是需要等待所有线程运行到安全点后才能触发，这些安全点位置主要有以下几种：
1.方法返回之前
2.调用某个方法之后
3.抛出异常的位置
4.循环的末尾
Safe point时对正在执行的线程设定的。如果一个线程处于Sleep或终端状态，它就不能响应JVM的中断请求，再运行到Safe point上。因此JVM引入了Safe Region。
safe regions安全区域
安全区域是指在一段代码片段中，引用的关系不会发生变化。在这个区域内的任意地方开始GC都是安全的。线程在进入Safe Region的时候线标记自己已进入了Safe Region，等被唤醒时准备离开Safe Region时，先检查能否离开，如果GC完成了，那么线程可以离开，否则等待知道收到安全离开的信号为止。
这种行为的结果是几乎所有停止的线程都已经在GC安全点上了。实现一个全局安全点，即停止世界(STW)暂停，比补丁和前滚方案要快得多，而且没有通常与软件轮询方案相关联的运行时成本。虽然我们提供的算法没有STW暂停，但我们的当前实现有。因此，有一个快速停止机制仍然是有用的。
我们还使用了检查点，在所有mutator线程都执行了某些操作之前，我们无法继续执行这些检查点。在检查点中，每个突变器到达一个GC安全点，执行少量GC相关的工作，然后继续执行。阻塞的线程已经处于GC安全点;GC线程代表它们执行操作。在STW暂停中，所有修改器必须达到GC安全点，才能继续执行;暂停时间由最慢的线程控制。在检查点中，运行的线程永远不会空闲，GC工作将及时展开。STW暂停和检查点使用相同的硬件和操作系统支持。
3.3 硬件Read Barrier
除了标准的RISC加载/存储指令集，cpu还有一些自定义指令来帮助对象分配和收集。在本文中，我们主要研究硬件read barrier。值得注意的是，这一壁垒与20年前的壁垒极为相似
读屏障执行许多检查，并在不同的GC阶段以不同的方式使用。这里将简要描述它的行为，然后在下一节中更深入地介绍GC算法。读取屏障在加载指令后发出，并在1个时钟内执行。有一个标准的加载-使用惩罚，编译器试图对其进行调度
读屏障“看起来像”一个标准的加载指令，因为它有一个基寄存器、一个偏移量寄存器和一个值寄存器。基值和偏移量不用于屏障检查，而是提供给陷阱处理程序并用于“自愈”。值寄存器中的值被假设为一个新加载的ref(堆指针)，并像基址一样在TLB中循环。如果ref引用gc保护的页面，将调用一个快速usermode trap处理程序(以下称为GC-trap)。读屏障会忽略null refs。与布鲁克斯风格的间接屏障不同，它没有空检查、没有内存访问、没有loaduse惩罚、对象头中没有额外的字以及没有缓存占用。此行为在并发重新定位阶段使用。
我们还从64位地址空间中偷 取1位地址位;硬件忽略了这个位(掩盖了它)。这个位称为非标记通过(NMT)位，在并发标记阶段使用。硬件为这个位保持一个期望的值，如果ref有错误的风格，就会陷入NMT-trap。这里也忽略Null ref。
请注意，可以在标准硬件上模拟读障碍行为，但要付出一定的代价。GC保护检查可以用标准页保护来模拟，读屏障可以用死负载指令来模拟。NMT检查可以通过对内存进行双映射和修改页面保护来模拟预期的NMT位值。但是，使用TLB检查ref特权意味着失败将触发一个kernellevel TLB陷阱，而不是一个快速的用户模式陷阱。将其转变为用户模式陷阱通常会有相当大的成本，并且可能需要修改操作系统。我们的read barrier指令不会在null ref上陷入陷阱，而null ref是非常常见的。要在标准硬件上模拟这一点，需要在barrier代码或映射页0中进行条件测试。这又阻止了使用普通内存操作同时进行空指针检查，这是现代jvm中的常见优化。
4. 无停顿GC算法(Pauseless GC)
Pauseless GC算法分为三个主要阶段:标记、重新定位和重新映射。每个阶段都是完全并行和并发的。标记位不新鲜;对象会随着时间的推移而消亡，标记位不反映这些变化。标记阶段负责定期刷新标记位。重新定位阶段使用最新可用的标记位查找活动数据很少的页面，重新定位和压缩这些页面，并释放后备物理内存。重新映射阶段更新堆中每个重新定位的指针。
完成任何阶段都不需要“rush”。没有哪个阶段会给突变体带来实质性的负担，需要通过快速结束该阶 段来减轻这种负担。在重新开始收集之前，不存在完成某个阶段的“竞争”——重新定位会连续运行，并且可以在任何时候立即释放内存。因为所有阶段都是并行的，所以GC可以通过添加更多的GC线程来跟上任意数量的mutator线程。不像其他增量更新算法，没有重新标记或最终标记阶段;尽管mutators正忙着修改堆，但并发标记阶段将一次性完成。GC线程确实与mutator线程竞争CPU时间。在Azul的硬件上，通常有一些可用的空闲cpu来执行GC工作。但是，“在一定限度”，一些cpu将执行GC，并且对mutators不可用。
每个阶段都涉及一个“自愈”方面，其中mutators通过更新内存中的ref立即纠正每个读障碍陷阱的原因。这保证了同一个裁判不会触发另一个陷阱。所涉及的工作因陷阱类型不同而有所不同，下文将对此进行详细说明。一旦处理了mutators的工作集，它们就可以全速执行，不再有trap。在某些相位变化期间，突变体遭受“陷阱风暴”，大量的陷阱相当于在时间上抹去停顿。我们使用最小Mutator利用率来测量陷阱风暴，它们花费了大约20ms，分散在几百毫秒之间。
我们提出的算法没有停止世界(STW)暂停，没有所有线程必须同时停止的地方。但是，为了便于工程到现有的热点JVM中，我们的实现包括一些STWs。我们认为这些STWs可以很容易地将暂停时间设计为低于标准的OS上下文切换时间，在这种情况下，GC暂停与操作系统上下文切换之间的区别是难以区分的。在描述阶段时，我们将提到实现与理论的不同之处
4.1 标记阶段
标记阶段是一个并行和并发的增量更新(不是SATB)标记算法[17]，增加了读屏障。标记阶段负责标记所有活动对象，以某种方式标记活动对象，以区别于死对象。此外，每个ref将其NMT位设置为期望值。标记阶段还收集每100万页的活跃度总和。这些总数给出了页面上实时数据的保守估计(因此保证了可回收空间的数量)，并用于重新定位阶段
基本思想很简单:标记从某个ROOT(通常是静态全局变量和mutator堆栈内容)开始标记可访问对象。在标记了一个对象(并设置了NMT位)之后，标记器然后标记该对象——递归地标记它在标记的对象中找到的所有refs。先前发布的[17]扩展使该算法并行化。使标记完全并发有点困难，下面将进一步描述这些问题。
4.2 迁移阶段
重新定位阶段是重新定位对象和回收页面的阶段。通过将剩余的活动对象重新定位到其他页面，具有大部分死对象的页面就完全不用了。重新定位阶段从选择一组超过给定稀疏阈值的页面开始。此集合中的每个页面都受到保护，不受mutator访问，然后复制活动对象。跟踪重新定位对象位置的转发信息在页面外部维护。
如果mutator加载对受保护页面的引用，那么读屏障指令将触发GC-trap。不允许mutator以语言可见的方式使用受保护页引用。GC-trap处理程序负责将过时的受保护页引用更改为正确转发的引用。
重新定位页面内容后，重新定位阶段释放物理内存;它的内容再也不需要了。物理内存被操作系统回收，可以立即用于新的分配。在对该页的旧引用不再保留在堆中之前，不能释放虚拟内存，而这是重新映射阶段的任务。
如图1所示，重新定位阶段会不断释放内存，以跟上变化器的分配。有时它单独运行，有时与下一个标记阶段并发。
4.3重新映射阶段
在重新映射阶段，GC线程遍历对象图，对堆中的每个ref执行读屏障。如果ref引用了一个受保护的页面，那么它就过时了，需要被转发，就像一个mutator被困在ref上一样。一旦重新映射阶段完成，活动堆ref就不能引用上一个重新定位阶段保护的页面。此时，这些页面的虚拟内存将被释放
因为重新映射和标记阶段都需要接触所有活动对象，所以我们将它们折叠在一起。当前GC周期的重新映射阶段与下一个GC周期的标记阶段并发运行，如图1所示。
重新映射阶段也与重新定位阶段的第二部分同时运行。重新定位阶段创建的旧指针只能通过重新映射阶段的完整运行来修复，因此在这个重新定位阶段的后半部分中创建的旧指针只能在下一个重新映射阶段结束时清除。接下来的几节将更深入地讨论每个阶段。