algorithm - 为什么标记和清除收集器必须停止世界而不是并行运行？

Question

我正在阅读“垃圾收集手册：第 2 版”。在“Mark-Sweep 垃圾收集”页面中，提到了所有 mutator 线程在收集器线程运行时停止。

是什么原因？在标记阶段，收集器只接触它拥有的字节（标记标志），而突变器甚至不应该使用。在扫描阶段，它只释放最初甚至无法被 mutator 触及的对象，因为它们无法访问（未标记）。

我一定遗漏了一些东西，但是如果它可以完全并行运行（如上所述），为什么要停止所有的 mutator 线程？

Answer 1

在标记阶段，收集器只接触它拥有的字节（标记标志），而突变器甚至不应该使用。

它只改变它拥有的字节。但它会检查 mutator 拥有的字节。当收集器检查它们时，它可能会改变字节。

具体来说，如果标记和突变体同时运行，没有什么能阻止突变体突变已经被标记的单元格。然后该单元格的新内容将保持未标记，结果即使引用的值仍然存在，也会被收集。

在单元格的新内容引用新对象的情况下，您可以通过简单地确保对象被标记来缓解此问题。但是在允许变异的语言中，不能保证它是一个新对象。

具体来说，考虑以下顺序：

Mutator                           Marker
--------------------              -------------
                                  Mark temp
temp := v[i]
v[i] := v[j]
                                  Mark all of v
v[j] := temp

最初的v[i]内容没有被标记（除非有其他引用），因此将被错误地收集。

我只有第一版 Richard Jones 的有用文本；在那个版本中，有一整节是关于如何实现并发标记/清除垃圾收集的。一种可能性是实现一个写入屏障，它可以拦截上面示例中的突变；如果尚未标记新值，则写入屏障会强制对其进行标记。当然，存在同步损失，因为写屏障在 mutator 线程中运行，而不是在标记线程中运行。