logo标签列表

如何实现垃圾收集器？

garbage-collection
71

有人可以指引我如何实现垃圾回收的好资料吗？我正在制作一个类似Lisp的解释型语言。它目前使用引用计数，但当然在释放循环依赖对象方面会失败。

我阅读了标记-清除、三色标记、移动和不移动、增量和停止-全局等内容，但是……我不知道在保持对象被分开成集合的最佳方式和同时将每个对象的内存开销最小的情况下，如何以增量的方式进行操作。

我已经阅读了一些使用引用计数的语言使用循环引用检测的方法，我可以使用这种方法。 我知道我可以使用像Boehm之类的免费收集器，但我想学习如何自己实现。

我将感激任何针对没有此类经验的人的教程或帮助的在线材料。

https://secure.wikimedia.org/wikipedia/en/wiki/Garbage_collection_%28computer_science%29 - Praetorian
23
你不应该从比一个近乎脑死亡的“停-清”标记和清除收集器更复杂的内容开始学习。现在先忘掉集合、增量回收和其他所有这些东西。对于你的第一次尝试，获取根对象、获取所有存活对象的列表等将已经足够具有挑战性了。 - user395760
具体来说，是“实现策略”部分：https://secure.wikimedia.org/wikipedia/en/wiki/Garbage_collection_%28computer_science%29#Implementation_strategies - Ben Zotto
可能是学习垃圾回收理论的重复问题。 - Dour High Arch
2
我不同意这是一个重复的问题。那个问题是关于理论的，而这个问题是关于实现和教程的。 - Zan Lynx
你确实想学习如何进行垃圾回收，对吧？否则，你可以使用Boehm-Demers-Weiser优秀的保守垃圾收集器，至少在语言得到很好的建立并有一些真正的应用程序来展示其价值之前，因为在那之前，有比好的垃圾回收器能够挤出的微小性能更紧迫的问题。 - Jan Hudec
8个回答
35
有没有人能给我指一条好的路线，来实现垃圾回收？
有关垃圾回收的高级资料很多，Garbage Collection Handbook 是很好的一本书。但是我发现缺少基础入门信息，所以我写了一些文章来介绍它。Prototyping a mark-sweep garbage collector 描述了一个最小的用 F# 编写的标记-清除式垃圾收集器。Very Concurrent Garbage Collector 描述了一个更先进的并发收集器。HLVM 是我编写的一个虚拟机，包括一个处理线程的停止-世界收集器。
实现垃圾回收的最简单方法是：

  1. 确保您可以整理全局根。这些是包含指向堆的引用的本地和全局变量。对于本地变量，在其作用域期间将它们推送到影子堆栈中。

  2. 确保您可以遍历堆，例如，堆中的每个值都是实现了一个“访问”方法的对象，该方法返回该对象引用的所有内容。

  3. 保留所有分配值的集合。

  4. 通过调用malloc进行分配，并将指针插入到所有分配值的集合中。

  5. 当所有分配值的总大小超过配额时，启动标记和清除阶段。这会递归遍历堆，累积所有可达值的集合。

  6. 分配值减去可达值的差集是不可达值的集合。迭代它们并调用free，从分配值的集合中删除它们。

  7. 将配额设置为所有分配值的总大小的两倍。

2
嗨Jon，我想阅读你的“原型标记清除垃圾收集器”文章，但它要求订阅。这是唯一的阅读方式吗？ - Hari
10
9
如delnan建议，我从一个非常幼稚的停止世界的三色标记与扫描算法开始。通过将对象作为链接列表节点来保持它们在集合中，但这确实为每个对象添加了大量数据（虚拟指针、两个指向节点的指针、一个枚举变量来保存颜色）。它完美地工作，valgrind上没有内存丢失:) 从这里开始，我可以尝试添加自由列表以进行回收，或者某种检测何时方便停止世界的东西，或者采用增量方法，或者使用特殊分配器以避免碎片化，或者其他任何东西。如果您能指出在哪里找到信息或建议（我不知道是否可以对已回答问题发表评论），告诉我该做什么，我将非常感激。同时，我会检查Lua的GC。
4
我用大约400行C代码实现了一个 Cheney-style copying garbage collector。我为一种静态类型语言编写它，令我惊讶的是，更难的部分实际上是如何传递哪些是指针和哪些不是的信息。在动态类型语言中，这可能更容易，因为您必须已经使用某种标记方案。

还有一本新版本的垃圾收集标准书即将出版： "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Jones, Hosking, Moss。（Amazon UK网站说2011年8月19日。）

4
我还没看到提到使用内存句柄的内容。如果每个对象引用都是一个指向包含该对象真实地址的结构体的指针，那么就可以避免需要双倍的内存（如采用Cheney-style复制算法所需）。对于内存对象使用句柄会使某些例程略微变慢（任何可能移动它的操作都必须重新读取对象的内存地址），但在单线程系统中，垃圾回收只会在可预测的时间发生，这不是太大的问题，并且不需要特殊的编译器支持（多线程GC系统可能需要使用句柄或直接指针，但都需要编译器生成元数据）。
如果使用句柄，并使用一个链表来存储活动句柄（相同的存储可以用于保存死亡需要重新分配的句柄的链表），则可以在标记每个句柄的主记录后，按分配顺序通过句柄列表并将其引用的块复制到堆的开头。由于句柄将按顺序复制，因此不需要使用第二个堆区域。此外，可以通过跟踪一些堆顶指针来支持代。在压缩内存时，从上次GC以来添加的项开始压缩。如果这不能释放足够的空间，则压缩自上次Level1 GC以来添加的项。如果这还不能释放足够的空间，则压缩所有内存。标记阶段可能需要处理所有代的对象，但昂贵的压缩阶段不需要。
实际上，如果采用基于句柄的方法，并且对所有代的事物进行标记，则在每个GC过程中可以计算出每个代中可以释放的空间量，如果Gen2中一半的对象已经死亡，则进行Gen2收集可能是值得的，以减少Gen1收集的频率。
是的，IBM APL解释器使用句柄，效果相当不错。 - Hot Licks
3
1
哇！我想把我写的所有不成体系的代码都扔掉，尝试着去实现我自己的 LISP 类语言，然后从你提供的 Building LISP 教程开始学习。我最喜欢这个教程的主要原因是它实际上是用 C 写的。大多数有关制作 LISP 类语言的教程都是用类似 LISP 的语言编写的，这在学术界很好但实际上毫无意义。 - ArtOfWarfare
《构建自己的Lisp》中有一个类似的推荐文章，即《初学者的垃圾回收器》。该文章链接为：http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/。 - Steven Shaw
2
0

我正在为我的后置解释器做类似的工作。通过我的问题了解更多信息。 我同意Delnan的评论，简单的标记-清除算法是一个很好的起点。您需要函数来设置标记、检查标记、清除标记，并为所有容器提供迭代器。一个简单的优化是在分配新对象时清除标记，并在扫描期间清除标记；否则，您需要在开始设置标记之前进行整个标记清除。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接