ACM通信
研究突出了
技术角度:最干净的垃圾收集
垃圾回收，这个用于自动存储管理的古怪名字，如果它是今天发明的，很可能被称为内存回收。事实上，它有着悠久的历史，几乎和计算本身一样长，可以追溯到早期的LISP实现，从1960年开始就出现了相关论文。被亲切地称为GC的GC还以速度慢和需要比显式管理的内存多得多的内存而闻名。如果这还不够，大多数GC算法将等待指定的内存填满，然后停止程序、收集并重新启动程序，在主计算中引入暂停。
GC的支持者有很有说服力的软件工程论据:自动存储回收简化了编程并减少了错误，从而提高了程序员的生产力。最终，提高计算机速度和内存容量使GC成为更广泛系统的合理选择。Java把它带入了主流，在那里它已经相当成功了。我们甚至达到了这样的地步:c++最初贴出的标语是“这里没有GC !”，现在提供了对它的可选支持。
但是自动存储管理的圣杯是实现GC的目标实时系统。实时GC之所以具有挑战性，有几个原因。一是实时系统不能容忍大的停顿。这要求收集器要么以细粒度递增，要么与程序并发运行(称为突变用GC的话说，因为它会在GC工作时恶意地改变周围的指针)。我记得当我还是一名研究生的时候，似乎有一个真正的行业围绕着在这个出版物中展示并发GC算法，并证明其正确性。事实上，提供这些证明是因为它们是研究人员能想到的最难的正确性证明之一。不用说，这表明获得正确的并发GC算法非常困难，更不用说将它们转换为正确的实现了。
这是一个相当棒的杰作，以下论文的作者已经建立了可重构硬件的可证明正确的实时收集器。
单靠并发GC还不足以实现实时存储管理。您还需要证明收集时间的界限，以及在这种模式下运行的程序所需的最大内存。首先，收集器不能落后于mutator:它必须能够收集废弃的内存，并至少在mutator分配内存单元的速度上回收这些内存供mutator使用。这意味着，除非您可以对mutator的分配率施加一个人为的限制，否则收集器不仅必须是并发的，而且还必须是快．
虽然人们已经开发了广泛的GC算法，但我们关注的是从程序变量(根)并跟随指针从一个对象到另一个对象，找到所有的可获得的对象。这样的跟踪收集器循环工作:从根开始，跟踪可到达的对象，回收剩下的，然后继续到下一个循环。
虽然这个名称有点不恰当，但GC开发人员也称其为可达对象生活，它们在给定的执行点上的总量为生活的大小．除了一个足够快的并发GC算法之外，对于实时GC，你不仅需要一个程序最大活动大小的硬边界(这可能是实时mutator行为所需要的)，还需要一个垃圾量的边界(遥不可及的对象)，该对象将在收集周期中积累。
因此，这是一个相当棒的杰作，以下论文的作者已经建立了可重构硬件(现场可编程门阵列)的可证明正确的实时收集器。这怎么可能呢?事实证明，FPGA设置在某些方面比在库存处理器上运行软件GC的情况更简单。它们可以合理地使存储器及其布局具有简单的一致性;它们可以利用单时钟的读-修改-写步骤;也许最重要的是，通过双移植内存，它们拥有完全并发的内存访问。所有这些都导致出现了迄今为止最清晰、可能也是最容易理解的并发GC实现之一。实时收集的其他先决条件也很容易实现。当我看到如此复杂的算法理念变成如此简单的硬件实现时，我很难找到合适的词来表达我的感受，“酷!”
这项工作似乎并没有为普通硬件上的软件实现提供简单的实时GC支持的直接途径。与此同时，它有助于通过其对实时GC知识的贡献而不仅仅是对实践的好处来告知工作。特别是，它展示了在运行无暂停收集器所需的总空间上，我们可以实现多么严格的限制。我确信它将激发创造性的方法，帮助垃圾收集在系统实现空间的几乎每个角落得到接受。
数字图书馆是由计算机协会出版的。版权所有©2013 ACM有限公司
没有发现记录