Ruby垃圾收集深潜：三色标记和扫描

在Ruby Garbage Collection Deep Dive系列的第一篇文章中，我们经历了一些定义，以使我们了解Ruby如何在内存中存储值。如果您尚未阅读，请先阅读！在本文中，我们将基于这些定义。特别是，我们将更多地讨论Ruby Heap，Pages，Slot和RVALUES。

好的，既然我们已经有了这些基线定义，那么这篇文章将解释Ruby的垃圾收集器用来确定它可以收集哪些对象的算法：三色标记和清除算法。该算法分为两个阶段。您猜对了：标记和清除。在标记阶段，垃圾收集器标记所有包含可访问RVALUES的插槽。在清除阶段，垃圾收集器从所有未标记的插槽中清除RVALUES。让我们深入探讨！

我们将从讨论标记阶段开始。如果我们将Ruby ObjectSpace想象成是带有根节点的有向图，这是最容易理解的。图中的所有节点均为RVALUES。图中的所有边都是从一个RVALUE到另一个RVALUE的引用。

Ruby的垃圾收集器从根节点开始，并跟踪它可以从这些根节点访问的每个边缘，并标记在此过程中看到的每个RVALUE。最后，所有未被跟踪的RVALUE都将被垃圾回收，因此无法从根RVALUE访问。

好的，但是Ruby用于垃圾收集的算法称为“三色标记和扫描”算法，那么“三色”部分是什么呢？我们可以使用Tri-Color算法模型来了解Ruby的垃圾收集器在做什么，以及如何跟踪其进度。三色算法中的三种颜色（实际上是三种阴影）是白色，黑色和灰色。

在垃圾回收开始时，Ruby Heap中的每个插槽都是白色的。然后，作为初始设置的一部分，所有包含根RVALUE的插槽都标记为灰色。

根RVALUES是Ruby程序知道将需要运行的所有RVALUES。这些示例包括存在于程序所遵循的指令堆栈中的RVALUES或受保护的全局变量。

在所有根插槽为灰色而所有其他插槽为白色的情况下，我们进入了算法的关键：

我们遍历所有灰色插槽，将其RVALUES引用的插槽着色为灰色，并将其自身着色为黑色。该算法继续进行，直到没有剩余的灰色插槽为止。此时，任何黑色插槽都包含根插槽中的RVALUE可以到达的RVALUES，任何白色插槽都不包含可以到达的RVALUES，因此可以将其扫除！

对于视觉学习者来说，这是该算法的效果的图像：

这里有一个细节需要进一步解释：RVALUE如何知道它引用的其他RVALUE？

这取决于对象的类型。对于Ruby内置函数，跟踪引用只是烘焙到垃圾收集器代码本身中。例如，要从数组RVALUE中查找所有引用，收集器将迭代数组中的每个元素并找到其引用。对于哈希，它将对键和值都执行此操作。这一切都发生在垃圾收集器的mark_children方法中。

但是，当对象由C扩展定义时，C扩展必须自己标记所有子对象。我们将在以后的C扩展文章（我将在此处反向链接）中进一步介绍这一点。

好的，现在我们了解了如何找到所有可访问对象，我们需要学习如何处理所有不可访问对象。

此时，我们有两组：黑色插槽和白色插槽。在内部，这些表示为标记的位图。 Ruby Heap上的每个页面都有其自己的标记位图，每个插槽一位。 1位表示该插槽可访问，或者在我们的三色方案中为黑色。 0位表示该插槽不再可用，或者在我们的三色方案中为白色。

除了保存该标记的位图之外，每个页面还具有一个空闲列表，该列表表示该页面上没有活动对象的插槽。垃圾收集器遍历所有页面，找到所有未标记的插槽。然后，垃圾收集器将未标记的位置添加到每个页面的空闲列表中（如果适用）。如果占用这些插槽的RVALUES也占用了操作系统堆中的空间，则它还将释放此内存。

扫描完页面后，可能会有一些页面现在完全未分配。它们没有包含RVALUES的插槽。这些页面称为“ Tomb页面”。坟墓页面的内存已完全返回到操作系统的堆。这对于内存管理确实很有帮助。这意味着清除可能会导致释放内存或减小Ruby Heap的整体大小。

任何具有至少一个占用插槽的页面都称为“ Eden页面”。扫描阶段可能会减少Eden Page中占用的插槽数。垃圾收集器将使用Eden Pages的空闲列表进行将来的对象分配。也就是说，如果实例化一个对象，则垃圾收集器将在Eden页面中查找这些空闲插槽之一，并将代表您的对象的RVALUE放置在其中。

这里还有一个细微差别。从Ruby 3.0开始，如果启用了自动压缩，则压缩实际上将作为清除阶段的一部分进行。关于此情况发生的方式和原因的更深入说明，将在此垃圾收集深潜系列中有关压缩的后续文章中进行。

Ruby的垃圾收集器使用三色标记和清除算法来确定哪些插槽中保存了不再具有可访问引用的对象。它遵循三色算法（它遵循根RVALUES的所有引用）来标记它引用的所有插槽。垃圾收集器知道从根目录可以访问哪些对象后，便可以开始清除阶段，在此阶段将未占用的插槽添加到每个页面的空闲列表中，并释放所有保留了RVALUES的操作系统内存。这使插槽可以重新用于新的对象分配。

就是这个帖子！我将继续在本系列文章中撰写博客文章，并且还将撰写一本有关托管垃圾收集的书，重点是Ruby。如果您对此感兴趣，请加入下面的新闻通讯或在Twitter上关注我以获取更新！