下载本文的PDF版本 PDF

实时垃圾回收

现在可以使用Java开发实时系统了。

DAVID F. BACON，IBM 研究院

传统的计算机科学处理正确结果的计算。实时系统与物理世界交互，因此它们有第二个正确性标准：它们必须在限定的时间内计算出正确的结果。仅仅构建功能正确的软件已经足够困难了。当时间被添加到需求中时，构建软件的成本和复杂性会大幅增加。

过去，实时系统在生产的软件总量中只占相对较小的部分，因此这些问题在很大程度上被主流计算机科学界所忽视。然而，计算机技术的趋势是，具有某种时间要求的软件比例越来越大。

持续的小型化已将计算机带入更广泛的物理系统。今天的汽车有几个网络和多达100个处理器。软件在汽车的消费者价值中占据越来越大的比例，据估计，到2011年，一辆新车将运行1亿行代码——是Windows操作系统中代码量的两倍多。这种趋势将继续向下延伸：在不久的将来，您的笔可能拥有微处理器、无线网络，并运行一个100万行的应用程序。

另一个趋势是，更传统的计算机系统承担越来越多的实时特性。在VoIP的推动下，越来越多的应用程序正在使用音频和视频，丰富了传统的商业应用。金融工具的计算机套利现在对时间非常敏感，以至于几毫秒的优势每年可以转化为数百万美元的利润。

本文介绍了一种IBM开发的新技术，该技术使得使用标准Java开发实时系统成为可能，甚至包括那些具有极其苛刻的时间要求的系统。这项名为Metronome的新技术已被海军新型DDG-1000驱逐舰采用，该驱逐舰目前正在开发中，计划在下一个十年的早期发射。在IBM，我们正在使用Metronome作为米级直升机JAviator的底层技术，我们已经进行了初步的飞行测试。由于音乐是最苛刻的实时应用之一（人耳非常敏感），我们还构建了一个基于Java的音乐合成器，其响应时间为5毫秒——与硬件合成器实现的响应时间一样好。

安全语言和垃圾回收

Java在过去10年中的爆炸性增长表明，安全语言为软件生产力带来了巨大的好处。此处的安全是指程序不可能破坏内存。安全是通过垃圾回收实现的：垃圾回收器不是由程序员手动释放内存，而是定期扫描应用程序的内存空间，查找未使用的对象，并回收它们的空间。

自1960年约翰·麦卡锡为Lisp编程语言发明垃圾回收以来，垃圾回收就一直在使用。1在1970年代后期，随着计算机能力和内存大小的持续增加，垃圾回收和面向对象编程在Smalltalk中结合在一起，一种革命性的新编程风格诞生了，它基于动态分配的对象，其实施和存储布局独立于它们实现的接口。

当然，没有免费的午餐。与许多提高程序员效率的技术一样，垃圾回收需要额外的计算。但真正的致命之处在于，垃圾回收器无法像C或Pascal等语言中使用free()运算符那样，在整个计算过程中零星地进行额外的计算。垃圾回收是一种全局操作，应用于内存的整个状态。它不仅会减慢应用程序的速度，还会给应用程序的执行引入不可预测的、可能很长的暂停。

尽管计算机科学家在垃圾回收的开销和延迟方面都取得了改进，但在1990年代中期万维网出现之前，它仍然是一项边缘技术。每个人都想要动态、令人兴奋的网页，但没有人愿意允许未知的Web服务器在个人计算机上开始运行任意代码。Java的爆炸性增长源于它使用垃圾回收来维护语言级别的安全性。

软实时与硬实时

通常区分软实时和硬实时应用程序。在前一种情况中，错过最后期限是不受欢迎的；在后一种情况中，错过最后期限被认为是灾难性的失败。

这是一种过于简单的说法。实际上，实时应用程序有三个主要特征：响应时间、确定性和容错性。

响应时间是应用程序必须响应外部事件的时间量：音乐合成器必须在五毫秒内响应一个人按下钢琴键盘；直升机必须在50毫秒内响应陀螺仪读数的变化；电信服务器必须在20毫秒内响应会话启动消息。

确定性是响应时间的可预测性。当响应时间较低时，可预测性通常需要更严格，但并非总是如此。例如，电信服务器可以容忍50毫秒的方差，而直升机控制只能容忍几毫秒的方差。

容错性是系统在未达到最后期限时的行为。随着系统变得更加安全或对财务至关重要，它们不仅必须被设计为满足其最后期限，而且还必须在错过最后期限的情况下表现良好。错过最后期限可能是由软件故障或（更常见的是）环境中的不可预测性引起的，例如网络电缆被切断或内存奇偶校验错误。

构建一个精心设计的实时系统涉及理解所有这些参数并适当设计系统。对于经典的实时控制，诸如速率单调调度之类的简单但严格的调度规范可能是合适的。

电信系统需要基于排队论的方法。特别是，如果系统可以容忍30毫秒的方差，但这并不意味着可以接受具有30毫秒暂停时间的垃圾回收器：这样的延迟会导致队列积压，并会扰乱后续请求的响应时间。当许多请求非常接近时，系统可能无法保持其整体响应性和确定性要求。

Metronome：走出寒冬

由于垃圾回收造成的中断（长达几秒钟），实时程序员一直处于寒冬之中，无法获得使用Java等安全语言编程的好处。随着实时系统变得越来越大和越来越普及，在实时应用程序中无法使用垃圾回收已成为一个关键问题。

IBM研究院开发的Metronome技术（现已投入生产）通过将中断限制为一毫秒并将它们均匀地分布在应用程序的执行过程中来解决这个问题。2内存消耗也受到严格限制和可预测，因为如果应用程序开始分页或抛出内存不足异常，它就不能是实时的。换句话说，实时行为取决于预测和规范化系统所有资源的利用率。

实时系统通常以倒金字塔形软件结构构建，如图1所示。最注重时间的代码位于底部，但它通常也只占整个应用程序的相对较小部分。构建在其之上的是时间约束稍微不那么严格的代码，这些代码可能会多次使用底层。一个复杂的系统可能有几个这样的层。

实时系统始终受其最薄弱环节的限制。如果金字塔底部出现问题，它将波及整个系统，导致错误，迫使重新设计和变通方法，并通常使系统变得脆弱和不可靠。Metronome允许Java用于时间要求低至一毫秒的系统中，这涵盖了绝大多数实时系统。

其他公司也在提供具有某些实时特性的虚拟机；例如，BEA推出了一种虚拟机，通常可以实现40毫秒左右的最坏情况延迟。这对于某些领域来说已经足够好了，例如某些电信系统。

结果是实时系统构建的生产力革命性提高。

停止世界

垃圾回收器通常会停止应用程序，因为它们需要扫描堆中的指针。在图2中，堆栈上的局部变量指向对象A和B，而对象A和B又指向B、C、D、E和F。如果程序破坏了从B到E的指针，并且在后续分配中没有更多内存，则会触发回收器。它将从堆栈上的指针开始，并跟踪堆中所有可达的指针，将找到的对象标记为live。这意味着它不会找到对象E和F，它们将被回收以供后续分配。

两种基本的回收器是标记-清除和复制。3标记-清除回收器在遇到对象时将其标记，然后进行一次遍历，回收未标记的对象。复制回收器在第一次遇到活动对象时将其复制到新的内存区域，并更新所有指针以使用复制对象的新地址。

复制回收器的优点是只需要与活动数据大小成比例的工作量。它们也具有更好的局部性，因为对象是连续分配并密集保存的。另一方面，标记-清除回收器不会遭受复制的开销，并且不会使用那么多内存，因为它们不需要整个干净的区域来复制对象。

飞行中回收

在垃圾回收进行时完全停止应用程序可能会引入长时间的延迟，对于今天典型的堆大小，通常为数百毫秒。随着64位架构的引入和可用RAM的持续扩展，成本可能会变得更糟。

显然，以小的回收步骤中断应用程序会比要求整个操作在单个停止世界步骤中发生更好。然而，这并不容易，因为回收器正在检查堆的形状，而应用程序同时正在更改它。

人们已经通过两种基本方法避免了长时间的暂停：分代和增量回收。分代回收器将堆划分为两个区域：一个苗圃区，用于放置新分配的对象，以及一个成熟空间。当苗圃区填满时，对象被复制到成熟空间，并且它们的指针被更新。此外，在执行期间，存储到成熟空间中的每个指针都记录了从成熟空间到苗圃区的引用，因此当复制苗圃区对象时，可以快速更新这些引用。

回收苗圃区通常比回收堆花费的时间少得多。然而，分代回收只是推迟了不可避免的事情：迟早，成熟空间会填满，并且必须执行完整的垃圾回收。换句话说，分代回收并没有改善回收的最坏情况行为，而对于实时系统来说，最重要的是最坏情况行为。分代回收现在在商业部署的Java虚拟机中很常见。

对于避免停止世界回收的需求，增量方法是必要的，但这需要解决应用程序并发修改堆的问题。

使用图2中的相同堆在图3中说明了这个问题。假设我们正在将回收器与应用程序交错。回收器启动并标记A和C（对象上的复选标记显示）。然后应用程序运行，从B读取指向E的指针，将其存储在A中，并覆盖B中指向E的指针。现在回收器再次启动，从它停止的地方继续，并标记B和D。但是它没有标记E和F，即使它们仍然可以从A访问。这被称为丢失对象问题。

不是实时的？让我数数方法

自1970年代中期以来，就存在避免丢失对象问题的增量回收器，但它们总是受到一个或多个其他问题的困扰，这使得它们不适合真正的实时应用程序

表达你的意思

Metronome回收器解决了所有这些问题，并提供了基于应用程序简单表征的保证行为。它首次允许使用垃圾回收语言编写硬实时应用程序。

解决这些问题的关键首先是要有一种精确的方法来定义我们想要实现的目标。我们必须精确地描述回收器的执行将如何影响应用程序的执行，以便应用程序开发人员确切地知道它的行为方式。我们还必须描述系统的内存消耗，因为如果它使用过多的内存，它将开始分页，因此，不再是实时的。

以前的增量回收器专注于最坏情况暂停时间，即回收器对应用程序的单次最大中断。良好的研究质量增量回收器通常能够实现50毫秒左右的最坏情况暂停。

然而，由于陷阱风暴和基于工作的调度，暂停时间只说明了部分情况。作为一个极端的例子，假设回收器运行50毫秒，然后应用程序运行1毫秒，然后回收器再次运行50毫秒。最坏情况暂停时间为50毫秒，但从应用程序的角度来看，如果它需要做超过1毫秒的工作，它与100毫秒的暂停一样糟糕。

正确的指标是MMU（最小 mutator 利用率）。4 Mutator 是垃圾回收爱好者称呼应用程序的名称，因为从回收器的角度来看，应用程序唯一相关的方面是它会改变堆。

MMU衡量应用程序在给定时间内运行的最短（最坏情况）时间量。例如，在10毫秒时MMU为70%意味着应用程序保证在每10毫秒中至少运行7毫秒。

图4显示了应用程序的执行，与垃圾回收器交错。在第一次执行中，回收器在应用程序执行每3毫秒后运行1毫秒。它的MMU（4毫秒）为75%。在第二次执行中，回收器执行完全相同的工作量，但它的MMU（4毫秒）仅为25%，因为在从时间3到7的4毫秒内，应用程序仅运行了25%的时间。

MMU允许以对应用程序有意义的术语指定需求。一个以每秒25帧（每40毫秒一帧）生成视频，并且需要20毫秒来生成单个视频帧的应用程序，需要MMU（40毫秒）为50%。

时间就是金钱，但空间就是时间

一旦您知道应用程序在MMU方面的要求，您就需要知道它是否可以实现。我们配置Metronome默认以MMU（10毫秒）为70%运行，最坏情况暂停为1毫秒。这适用于大多数应用程序，但对于关键系统，必须正确理解应用程序，以便可以保证其行为。了解如何提供保证的行为对于应用程序开发过程至关重要。

使用Metronome，实现MMU目标取决于两个应用程序参数：它使用的最大活动内存和最大长期分配率。

如果这看起来需要提供大量信息，请记住，即使对于非实时应用程序，您也不能确定它是否会运行，而不知道其最大活动内存消耗：如果您使用的内存超过系统拥有的内存，则无法运行。为了保证应用程序的实时行为，您需要了解其资源消耗速率，这并不奇怪。如果您以极快的速度分配内存，那么很明显回收器将不得不频繁运行，这意味着最终您可以给回收器足够的时间的唯一方法是降低您的MMU要求。

执行垃圾回收所需的时间取决于程序消耗的活动内存量，因为它必须跟踪所有这些对象（这在某种程度上是过于简化的，但将有助于理解所有关键概念）。该回收时间必须分布在应用程序的执行过程中，而MMU指定了回收器允许执行此操作的方式。

例如，如果我们的视频应用程序最多使用100 MB的内存，那么在特定的硬件上，它可能会在两秒钟内被回收。由于要求是MMU（40毫秒）为50%，因此这两秒钟必须分布在四秒钟的实际时间内。

这就是内存分配率发挥作用的地方：当回收器开始运行时，系统具有一定的可用内存量。然而，在回收在四秒钟后完成之前，该内存不能耗尽，否则整个系统将阻塞。因此，如果应用程序每秒执行分配30 MB，那么它将在回收进行期间分配60 MB。这意味着系统至少需要160 MB才能实现其MMU目标并保持实时行为。

此属性允许用增加的空间来换取更好的实时行为：通过提供更多内存，您可以提供更大的“缓冲区”，从而允许回收器花费更长的时间来完成，这意味着它可以以更高的MMU运行。如果您没有更多内存，您可以降低MMU要求或更改您的应用程序以更慢地分配内存。

图5显示了这一切是如何结合在一起的。顶部的图表显示了正在使用的内存量（红色）、垃圾回收处于活动状态的区域（黄色）、MMU（绿色）和MMU要求（蓝色）。当回收器不活动时，MMU为100%。当回收器运行时，MMU下降，但仍保持在70%的目标之上。当回收完成时（黄色区域结束），内存利用率会下降。第一次回收没有释放太多内存；第二次回收释放了更多内存。释放的内存量取决于回收开始时堆中的活动内存。

图5底部的图表显示了回收器在单个回收量子级别的详细行为。在此图中，时间像书一样读取：从左到右，从上到下。图中白色部分表示应用程序正在运行；彩色部分表示回收器正在运行。每个矩形都是一个大约500微秒的单个回收量子。量子以五到六个为一组出现，每10毫秒有一组。这是因为系统已在MMU（10毫秒）= 70%的情况下运行，目标暂停时间为500微秒。

如果您有兴趣更详细地了解行为，这些图表是使用名为TuningFork的交互式实时可视化工具生成的，该工具可从IBM alphaWorks获得（http://www.alphaworks.ibm.com/tech/tuningfork），以及一些Metronome示例跟踪。

与其他方法的比较

许多其他不太自动的方法可以保证或改善垃圾回收语言的实时行为。它们可以大致分为对象池或基于区域的内存管理。

对象池基本上是手动内存管理的一种形式，在语言级别实现。对象池在应用程序启动时分配，对象从池中显式分配，并显式放回池中。池本质上是更高级别的malloc/free形式。

当在Java中实现时，池是强类型的，因此释放仍在使用的对象不会导致内存损坏。但是，它仍然会导致应用程序故障，缺点是由于池对象是强类型的，因此内存不能从一个池重新分配到另一个池，因此内存消耗可能会因需要许多不同的池而增加。

对于某些应用程序，对象池可能非常有效，如果数据结构很简单，则过早释放的危险可能很低。

基于区域的内存管理将内存划分为成批回收的区域。这通常与堆栈规范相结合：内存区域与特定的函数调用相关联，并且该区域可以由该函数及其被调用者访问。当函数退出时，区域及其所有对象都会被释放。

基于区域的内存管理的优点是释放内存速度很快。然而，它有一个严重的缺点，即限制了应用程序的结构。特别是，从堆栈中较低区域到堆栈中较高区域的指针可能会在释放较高区域时导致悬空指针。

对此有几种方法。“向上指针”可以使用运行时检查动态阻止，或者程序分析可以将对象分配给保证在堆栈中足够低的区域，以避免任何向上指针。

自动程序分析是安全且非侵入性的。实际上，此类分析无法很好地完成工作，尤其是在存在多线程的情况下，因此这种方法对于大多数环境而言还不够成熟。

动态检查是RTSJ（Java实时规范）中采用的方法，RTSJ是为实时编程设计的Java变体。5由于RTSJ是在没有实时垃圾回收的情况下设计的，并且由于自动区域分析是不可行的，因此它依赖于区域（它称为Scope）和运行时检查。每次存储指针时，系统都会检查它是否是从一个Scope到另一个Scope的向上指针。如果是，则抛出运行时异常。

这有一些严重的缺点：最明显的是，检查每个指针访问的Scope包含性会产生显著的性能成本。然而，真正的成本在于程序复杂性：由于Scope行为未在方法的接口中记录，因此API用户无法可靠地预测其在使用Scope时的行为，尤其是在程序的Scope结构涉及多个Scope时。对于在没有RTSJ的情况下开发的库（绝大多数Java库），问题尤其严重。因此，虽然Scope在内存释放方面购买了确定性，但它们降低了整体灵活性，并可能导致不可预测的运行时故障。

超越垃圾回收器

尽管垃圾回收是Java中不确定性的最大来源，但也存在其他问题：类加载和JIT（即时）编译。

Java的动态语义规定，在首次运行时引用类之前，不会加载和初始化类。由于类加载涉及文件输入和可能很长的初始化序列，因此大量的类加载可能会损害实时行为。我们的生产实时虚拟机包括预加载提供的类集并避免此问题的能力。

JIT编译也广泛用于Java运行时系统：应用程序最初以解释模式运行，系统进行自我监控，查找“热”方法。当找到热方法时，它会被编译，通常会导致性能显着提升。

然而，在实时系统中使用JIT有三个问题。首先，JIT编译可能很昂贵，因此可能会中断应用程序相当长的时间。其次，JIT编译会改变代码的性能，从而降低可预测性；性能通常会提高，但是，尤其是在使用多级优化的系统中，某些JIT编译实际上可能会降低系统速度。第三，由于JIT编译是根据程序执行自适应执行的，因此它发生在程序执行的不可预测的点。

在不可预测的时间发生、持续时间不可预测且对后续执行速度具有不可预测影响的中断组合使得JIT在实时系统中非常成问题。

一种解决方案是使用AOT（提前）编译器。AOT编译器采用代码单元（在我们的例子中是JAR文件）并将其编译为机器代码。这可以在应用程序构建时完成。然后执行非常确定。性能有时低于使用最佳JIT编译实现的性能，但对于对时间非常敏感或关键的应用程序，这通常是正确的权衡。

例如，对于我们构建的合成器应用程序，如果没有AOT编译，我们无法实现具有五毫秒响应时间的无故障音乐合成。对于以50毫秒周期运行的JAviator直升机，JIT编译速度足够快。然而，由于代码的关键性，我们在生产飞行中使用AOT编译。

另一种方法是使JIT编译更像Metronome——也就是说，使其以小的量子执行其工作，这些量子与回收器一起调度，以满足应用程序的MMU要求。这提供了更可预测的JIT行为，而不会给AOT编译带来不便，也不会因缺乏运行时信息而导致性能下降。然而，对于不能容忍执行早期速度变化的应用程序，AOT编译仍然是最佳方法。

结论

垃圾回收显着简化了编程并提高了软件可靠性。随着实时垃圾回收技术的出现，这些优势也可以应用于实时编程领域。随着越来越多具有某种实时要求的应用程序被构建，这些软件工程和生产力优势变得越来越重要。

Metronome技术现在作为产品上市，随着时间的推移，您可以期望看到更多Java和其他高级面向对象语言的实现，包括垃圾回收技术，这些技术可以显着提高确定性并减少延迟。

参考文献

  1. McCarthy, J. 1960. Recursive functions of symbolic expressions and their computation by machine. Communications of the 3(4): 184–195.
  2. Bacon, D. F., Cheng, P., Rajan, V. T. 2003. A real-time garbage collector with low overhead and consistent utilization. Conference Record of the Thirtieth Symposium on Principles of Programming Languages (New Orleans, Louisiana, January): 285-298.
  3. Jones, R. E. 1996. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. New York: Wiley and Sons.
  4. Cheng, P., Blelloch, G. 2001. A parallel, real-time garbage collector. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (Snowbird, Utah, June). SIGPLAN Notices 36(5): 125–136.
  5. Bollella, G., Gosling, J., Brosgol, B. M., Dibble, P., Furr, S., Hardin, D., Turnbull, M. 2000. The Real-Time Specification for Java. Reading, MA: Addison-Wesley.

DAVID F. BACON是IBM T.J. Watson研究中心的Research Staff Member，他在那里领导Metronome项目。他最近的工作重点是高级实时编程、嵌入式系统、编程语言设计和计算机体系结构。他获得了加州大学伯克利分校计算机科学博士学位，以及哥伦比亚大学的A.B.学位。

acmqueue

最初发表于Queue vol. 5, no. 1—
在数字图书馆中评论本文




更多相关文章

Matt Godbolt - C++ 编译器中的优化
在向编译器提供更多信息方面需要权衡：这可能会使编译速度变慢。诸如链接时优化之类的技术可以为您带来两全其美的效果。编译器中的优化仍在不断改进，即将到来的间接调用和虚拟函数分派方面的改进可能很快会带来更快的多态性。


Ulan Degenbaev, Michael Lippautz, Hannes Payer - 作为合资企业的垃圾回收
跨组件跟踪是解决跨组件边界的引用循环问题的一种方法。只要组件可以形成跨API边界具有非平凡所有权的任意对象图，就会出现此问题。CCT的增量版本在V8和Blink中实现，从而能够以安全的方式有效且高效地回收内存。


David Chisnall - C 不是一种低级语言
在最近的Meltdown和Spectre漏洞之后，值得花一些时间来研究根本原因。这两个漏洞都涉及处理器推测性地执行超出某种访问检查的指令，并允许攻击者通过侧信道观察结果。导致这些漏洞以及其他几个漏洞的功能被添加进来，是为了让C程序员继续相信他们正在使用低级语言编程，而这种情况已经过去几十年了。


Tobias Lauinger, Abdelberi Chaabane, Christo Wilson - 你不应该依赖我
大多数网站都使用JavaScript库，其中许多库已知存在漏洞。了解问题的范围，以及包含库的许多意外方式，仅仅是朝着改善情况迈出的第一步。此处的目的是，本文中包含的信息将有助于为社区提供更好的工具、开发实践和教育工作。



© 保留所有权利。

© . All rights reserved.