垃圾回收是否标记+清除必须是单片/atomi

Question

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

Micropython使用垃圾回收，特别是标记和清除；让我们来定义它。在

标记
在标记阶段，gc遵循内存引用，并按字面上的标记已使用的内存块，以指示它们可从根块集访问。在

<_strong_> _扫描_ <_br_/>_ 标记阶段完成后，清理程序将在整个堆上循环，如果使用了内存块，但没有标记该内存块，则表示代码无法访问该内存块，因此它被“释放”，即标记为空闲。在标记阶段标记的内存块已删除该标记。在

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

这将有助于减少抖动：不是一个大的定时命中，而是一堆小的呼叫分散开来。（这里不讨论如何“分散”调用的实现细节。除非有人认为这会增加讨论。）

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

可以执行的两个操作是：分配和取消分配。在

分配

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

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

>> var1 = SomeAllocation()

标记期间的分配
在上面的示例中，在REPL中执行一个语句，因此对字典的任何添加都将添加到全局字典中，而全局字典是GC Roots中的一个条目。如果一个条目在扫描前被添加到全局变量中，则不会发生任何“坏”的情况：新的内存块将被标记为原来的样子。在

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

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

解决方案

如果gc正在执行中，请将分配的块标记为标记为。唯一的缺点是，如果您分配同相扫描，并且在sweeper检查了新分配的块之后，您将使用一个标记为标记的块来完成gc。除非用户显式地释放它，否则当它无法访问时，您将需要经历一个额外的gc周期来释放它。在

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

解除分配

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

标记期间取消分配

如果一个块在referec之前被释放ing（父）块被扫描，什么也没有发生。在

如果一个块被释放并且它的子块已经被标记，那么我们就有一个不一致性，因为只有当一个父块也被标记时（或者父块是一个GC root）才应该被标记。结果是，这些不可到达但已标记的块在另一个gc循环之前不会被释放，因为这些已被标记的父级较少但标记的块将不会通过相位扫描释放。在

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

在扫描期间取消分配

如果一个块在sweeper检查之前被释放了，则不会发生任何特殊情况。自由操作将目标块的状态从标记的更改为空闲，然后当清扫器到达它时。这里没什么可看的只是一个免费的街区。在

如果一个块在sweeper检查后被释放，则空闲操作会将目标块的状态从已使用更改为空闲。在

问题

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

Answer 1

是的，有可能。在

Java从1.4版（2002年）开始就有了一个Concurrent Mark-Sweep (CMS)收集器。它的工作原理与你描述的相似。在

如果您运行Jython，我想您今天可以在本机上利用它。在