3

我应该如何在由多个线程或进程组成的程序中执行垃圾收集？

如何从每个线程和进程中扫描堆栈？

每个进程都需要自己的垃圾收集例程吗？在与实际程序不同的线程/进程中运行垃圾收集器是个好主意吗？

4

5 回答 5

8

您必须为每个地址空间收集一次。多个线程在同一个地址空间中运行，因此需要一个 GC 来处理。对于通过产生不同进程工作的程序，每个进程都在自己的地址空间中运行，每个进程可以有一个 GC。

在多线程的情况下，将 GC 作为另一个线程运行是有意义的。这样，您可以调整该线程的优先级，以确保整个程序的运行最顺利。对于单线程进程，最简单的方法是让 GC 挂钩到“正常”内存管理例程（特别是分配），但您可以有两个线程 - 一个用于原始进程的线程和一个 GC 线程 - ，再次确保半流畅的性能。

stop-the-world-collectors 是最简单的——mark-and-sweep、mark-and-compact、stop-and-copy，应有尽有。挂钩到单线程程序中的内存管理例程的 GC 本质上是 stop-the-world。在多线程的情况下，GC 线程可以被线程调度程序赋予特殊的权限（使它一旦决定运行就不会被中断），这允许你从这样一个特权线程运行一个 stop-the-world GC。

如果 GC 可以被 mutator（即程序的其余部分）中断，特别是因为它只是另一个根本没有得到特殊处理的线程，那么您将需要一个可以处理 mutator 干扰的 GC。在这种情况下，您正在查看增量 GC。IGC 可用于单线程、挂钩到内存管理例程设置中，它可能会被中断，即通过超时来确保整个系统的运行平稳；它也可以在多线程系统中使用，它只是与其他线程竞争运行时间。

我不能告诉你如何找到程序的堆栈或程序的所有线程的堆栈，但是应该为每个操作系统记录这些结构的布局。抓住 Boehm GC 并扫描源代码以获取提示可能是有意义的。

在将 Jones/Lins 运送给您的同时，请花一些时间在http://www.memorymanagement.org/上。更多信息，正如 Charly Martin 上面所说的，Sun 的人们在垃圾收集领域做了一些惊人的研究和开发，就像 IBM Jikes RVM 团队的成员和同事一样。

编辑： 阅读您对查理·马丁的评论后，让我给您一个更简洁的建议：将 Boem GC 连接到您的系统并完成它。编写垃圾收集器很容易。几乎不可能编写一个正确、高效、快速、行为良好、调优和健壮的垃圾收集器。使用现有的 GC 并继续进行项目中有趣的部分。不要被 GC 卡住，或者更糟糕的是，有一个糟糕的 GC 实现会让你烦恼不已。

于 2008-12-28T22:54:07.140 回答
7

大多数 GC 被称为“stop the world” GC - 在某些预定义的点（“Gc 点” - 例如调用点、跳转、返回），每个线程将检查是否存在其他想要执行 GC 循环的线程. 一旦所有线程都停止，GC 循环就会运行。

当然，还有其他可能性——实时的、增量的、并发的（以及更多）GC 也存在——搜索网络（你会找到已发表的论文）或者干脆买一本关于 GC 的书

至于堆栈扫描，有几种方法：

  • 精准扫描：

    • 标记堆栈 - 你基本上保留 2 个堆栈 - 一个带有值，一个带有“标签”。什么标签取决于您的需要，但它主要是“是参考”/“不是参考”标记

    • 没有标签的堆栈 - 基本上，如果您有一种具有严格类型的语言，那么您可以在每个时间点（但更常见的是在每个“GC 点”）都知道堆栈上的类型是什么。我会给你一个使用简单解释器的例子（我只是编造的）：

no-return function XY (int):
 load_param 1 
 ipush 1
 iadd
 call Z (assume: int function Z (int, int))
 new some_object
 call Y

如果我们将 GC 点定义为 call/new，那么可能有 3 个点我们可能需要知道我们的堆栈类型（在 XY 函数入口处，堆栈被认为是“空的”）：

  • 调用 Z - load_param 加载一个 int 参数，ipush 将一个 int - 2 个 int 压入堆栈，我们的 GC 在这里什么也不做
  • new - 调用 Z 使用堆栈中的 2 个整数并放置一个 int
  • 调用 Y - new 放置了一个引用，所以现在我们有一个 int 和一个引用，GC 必须知道那个引用

请注意，我说函数入口时堆栈是“空的” - 确实不是，但您可以单独分析每个函数，然后向上移动“调用堆栈”（您在某处有一个返回指针，因此您知道您在哪里必须返回 - return-1 是一些调用，您还可以获得堆栈的图像。重复直到到达顶部）。

有两种方法可以记住此信息（对于未标记的堆栈）：

  • 为每个 GC 点生成一个表
  • 为每个 GC 点生成一个代码片段（代码片段本身会标记引用的对象）

至于你什么时候收集这些信息，它可以是预编译的，也可以是及时的。

这也可以应用于机器堆栈，但事情会变得有点复杂，因为您可能还必须跟踪寄存器。

您也应该能够在网上找到一些关于无标签堆栈的好论文。

在添加例如的位置还有进一步的修改。数据的“活跃度”信息（好的，堆栈上有一个引用，但是如果在使用它的指令流中没有代码，我现在可以将其视为无法访问）

  • 保守的收集（与精确扫描相反） - 你问自己“这个值在堆栈上，解释为指针，引用”，如果是，那么它是“活着的”。如果有例如，这当然会泄漏。一个看起来像指针的整数（如果整数发生变化，内存将被释放，但也可能永远泄漏）。大多数 c/c++ 收集器都是以这种方式实现的，因此如果您好奇，请朝那个方向搜索。

每个进程都需要自己的垃圾收集例程吗？

没有什么需要这样做，但我想说这很常见——为简单起见，我的每个进程都有一个不同的 GC 实例（但所有线程只有一个）。我想进程之间可能存在共享内存分配器 - 我看到的唯一好处可能是更好地管理内存碎片（因为你控制更多内存）但复杂性（进程间通信/同步 - 糟糕），共享数据量缺乏独立性成为问题。我在这里猜测，我对这种类型的 GC（或者即使它们存在）没有真正的经验——这对我来说似乎是常识。

在与实际程序不同的线程/进程中运行垃圾收集器是个好主意吗？

这要看情况。将它保存在另一个线程中应该是一个好主意，但是你得到什么取决于 - 你想让你的 GC 简单（“停止世界” - 所有其他线程都被暂停，所以它在我们在哪个线程执行我们的 GC，但如果它有自己的线程更好），或者您有特殊要求（例如，您的线程是实时的，不应该长时间停止，那么您将有不同的 GC线程并使用实时/增量 GC 算法）。

这一切都取决于您需要什么，但无论您做什么，请记住 - 使其尽可能简单。

而且我几乎忘记了，有一些很好的替代方法可以从头开始编写自己的 GC - 例如。请参阅LLVM，他们声称“利用这些工具，只需大约 100 行 C++ 代码，就可以直接为您的运行时发出类型准确的堆栈映射。” （仅预编译代码，从 jet 开始不支持代码 JIT 生成）。此外，您可能会查看一些 java VM 的代码（例如，phoneME Advanced VM (CVM)，据我所知，kaffe 的可读性很好）。

免责声明：我曾经（作为一个学生项目）实现了一个精确的、停止世界、无标记、标记和扫描 GC - 这里写的所有内容都是我从经验中记忆的结果，应该是正确的，但它可能不是“最佳实践”。欢迎指正。

于 2008-12-28T21:21:55.797 回答
2

为什么要自己做GC？还是您只是想了解一般的 GC？Hrvoje 推荐的 Jones and Lin 书相当不错，维基百科的文章看起来也不错。

1.4.2 之后的 Java 提供了增量混合 GC，不会强制“stop the world”停止；我们需要这样做来处理面向设备的 Java，例如 Java ME 世界。Sun java 网站上有一篇很好的扩展论文。

于 2008-12-28T22:00:25.703 回答
1

大多数 GC 环境，例如 Java 和 .NET，都会在垃圾收集期间停止所有线程。

于 2008-12-28T21:12:07.657 回答
1

这是Maoni Stephens 的博客。她是 .Net GC 的当前主要开发人员。

这是一篇关于并发 GC的帖子，其中讨论了 .Net GC 在这种情况下是如何工作的。

于 2008-12-28T22:12:31.700 回答