python - 垃圾收集-mark + sweep是否必须为整体/原子

Question

本讨论将使用micropython代码，但由于它非常简单，我希望它对mark + sweep的一般讨论有用。

Micropython使用垃圾收集，特别是标记和清除；让我们定义一下。



标记
在标记阶段，gc跟随内存引用，并逐字标记已使用的内存块，以指示它们可以从根块集中到达。

扫
标记阶段完成后，清除程序将循环遍历整个堆，如果使用了内存块但未标记，则表示代码无法访问该内存块，因此将其“释放”，即标记为空闲。在标记阶段标记的存储块已删除该标记。

当前的实现需要原子调用来执行垃圾回收（又称为gc），但我一直在想，是否有可能将其拆分为多个调用，而不是单片/原子调用。

这将有助于减少抖动：您会分散一堆较小的电话，而不是大的时间限制。 （这里没有讨论如何“分散” gc调用的实现细节，除非有人认为这样做会增加讨论的范围。）

如果gc在“后台”（在字节码或after pre-defined bytecodes之间）运行，则在错误的位置进行分配（或释放）可能会导致争用条件和堆损坏。在拆分gc执行之前，我们必须确定可能的竞争条件。

可以执行的两个操作是：分配和释放。

分配

如果用户在标记或扫描阶段的中间执行分配，会发生什么？

让我们看一个具体的代码示例

>> var1 = SomeAllocation()

标记期间的分配
在上面的示例中，在REPL中执行了一条语句，因此对字典的任何添加都将添加到作为 GC Roots中条目的全局字典中。如果在扫描之前将条目添加到全局变量，则不会发生“不良”情况：新的内存块将被标记为应有的状态。

问题是在扫描全局变量后是否对其进行了修改。在这种情况下，不会标记内存块，因此在扫描阶段，它将被视为“无法访问”并释放。 。 。即使不应该这样。

扫描期间的分配
如果在清除程序遍历内存中的该点之前分配了一个块，则它将释放它，因为它在标记阶段没有特殊标记。如果在清扫程序遍历该块之后分配了一个块，则不会发生任何不良情况。

解

如果 gc在执行过程中，则将已分配的块标记为已标记。唯一的缺点是，如果您在阶段扫描中分配，并且在扫描器检查了新分配的块之后，您将使用标记为mark的块结束 gc。除非用户明确释放它，否则您将需要经历一个额外的 gc周期以释放它，如果它变得不可访问。

但这有一个简单的解决方案：如果在阶段扫描期间进行分配，则检查扫描器的位置：如果要分配的新块在其后面，请不要在其上标记，否则请对其进行标记带有标记，因为清除程序会删除标记。这样，您将不会退出带有标记标记的块的 gc。

解除分配

如果用户在标记或扫描阶段的中间执行分配，会发生什么？

标记期间的重新分配

如果在扫描参考（父）块之前释放了块，则不会发生任何事情。

如果一个块被释放并且它的子对象已经被标记，那么我们将有一个不一致的地方，因为只有当它们的父元素也被标记（或者父元素是 GC root）时，才应该标记它们。结果是，这些无法访问但已标记的块将不会释放，直到另外的 gc周期为止，因为经过标记后，这些无父但已标记的块将不会被相位扫描释放。

但是，我认为这不是问题，因为这与单片 gc的情况没有什么不同。在整体式 gc中，您必须完成当前的 gc循环，然后用户将调用 free(ptr)，然后在下一个 gc中释放该块的子级。直到堆处于“正确”状态的时间不会更改。

清扫期间的重新分配

如果在清除程序检查之前释放了块，则不会发生任何特殊情况。释放操作将目标块的状态从标记更改为释放，然后在清除程序到达时将其更改。 。 。什么也没看到，这里只是一个免费的街区。

如果在清除程序检查后释放了块，则释放操作会将目标块的状态从“已使用”更改为“释放”。

题

我的分析正确吗：是否可以拆分标记+清除垃圾回收？

Answer 1

对的，这是可能的。

自版本1.4（2002）起，Java有了Concurrent Mark-Sweep (CMS)收集器。它的工作方式与您的描述类似。

如果您运行Jython，我想您今天就可以利用它了。