垃圾收集 - 标记+清除是否必须 monolithic/atomic
garbage collection - does mark+sweep have to be monolithic/atomic
本次讨论将使用micropython代码，但由于它是如此简单，我希望它对mark+sweep的一般讨论有用
Micropython 使用垃圾回收，特别是 mark-and-sweep；让我们定义它。
马克
在 mark 阶段，gc 遵循内存引用，字面上 marks 使用的内存块以指示它们可以从集合中访问根块。
扫一扫
标记阶段完成后，清扫器遍历整个堆，如果使用了一个内存块但没有 marked 这意味着代码无法访问它，因此它是 "freed"即标记为 免费。在 mark 阶段标记的内存块已删除该标记。
当前的实现需要一个原子调用来执行垃圾收集，也就是 gc，但我一直想知道是否可以将它分成多个调用而不是 monolithic/atomic 调用。
这将有助于减少抖动：而不是一个大的定时命中，你会有一堆较小的调用分散开来。 （这里不讨论如何 "spread out" 调用 gc 的实现细节......除非有人认为它会添加到讨论中。）
如果 gc 是 运行 "in the background" - in-between 字节码或 after pre-defined bytecodes - 那么错误点的分配（或释放）可能会导致race-condition 和堆损坏。在我们可以拆分 gc 执行之前，我们必须确定可能的竞争条件。
可以执行的两个操作是：分配和解除分配。
分配
如果用户在标记或清除阶段的中间执行分配会发生什么情况？
让我们看一个具体的代码示例
>> var1 = SomeAllocation()
标记期间分配
在上面的示例中，在 REPL 中执行了一条语句，因此对字典的任何添加都将添加到作为 GC Roots 中的条目的全局字典中。如果在扫描之前将一个条目添加到全局变量中，则不会发生任何事情 "bad"：新的内存块将被 标记为 ，因为它应该如此。
问题是如果全局变量被扫描之后被修改。在那种情况下，内存块不会被 标记 因此在扫描阶段，它将被视为 "unreachable" 并被释放。 . .尽管不应该。
扫描期间分配
如果在清扫器遍历内存中的那个点之前分配了一个块，它将释放它，因为它没有 mark 中的特殊 mark ] 阶段。如果清扫器遍历该块后分配块，则不会发生任何不良情况。
解决方案
如果 gc 正在执行中，将分配的块标记为 已标记。唯一的缺点是，如果您在阶段扫描中分配并且在扫描器检查了 newly-allocated 块之后，您将使用标记有 标记 的块完成 gc .除非用户明确释放它，否则如果它变得无法访问，您将需要经过一个额外的 gc 周期来释放它。
但是有一个简单的解决方案：如果你在相位扫描期间分配，你检查扫描器的位置：如果 new-block-to-be-allocated 在它后面，不要用 标记标记它 否则，请用 标记 标记它，因为清扫器会删除 标记。这样你就不会退出 gc 标记为 mark.
的块
取消分配
如果用户在标记或清除阶段的中间执行分配会发生什么情况？
标记期间解除分配
如果在扫描引用 (parent) 块之前 释放 块，则不会发生任何事情。
如果一个块被释放并且它有children已经被标记，我们有一个不一致，因为块只有 marked 如果他们有一个 parent 也是 marked （或者 parent 是 GC root).结果是这些无法访问但已标记的块将不会被释放，直到额外的 gc 周期，因为已经 标记 ，这些 parent-less 但 标记 方块不会被相位扫描释放。
但是，我不认为这是一个问题，因为这与单体 gc 的情况没有任何不同。在单体 gc 中，您必须完成当前的 gc 周期，然后用户将调用 free(ptr)，然后该块的 children 将在下一个 [=12] 期间被释放=].堆处于 "correct" 状态之前的时间不会改变。
扫描期间取消分配
如果一个块在扫描程序检查之前被 释放 ，则不会发生任何特殊情况。 free操作改变th目标方块的状态从 marked 到 free 然后当清扫器到达它时。 . .这里没什么可看的，只是一个空闲块。
如果一个块在清扫器检查后被释放，释放操作将目标块的状态从已使用 到 免费 .
问题
我的分析是否正确：是否可以拆分 mark+sweep 垃圾回收？
是的，有可能。
Java 从版本 1.4 (2002) 开始就有一个 Concurrent Mark-Sweep (CMS) 收集器。它的工作原理与您描述的类似。
如果你 运行 Jython，我想你今天可以在本机利用它。
本次讨论将使用micropython代码，但由于它是如此简单，我希望它对mark+sweep的一般讨论有用
Micropython 使用垃圾回收，特别是 mark-and-sweep；让我们定义它。
马克
在 mark 阶段，gc 遵循内存引用，字面上 marks 使用的内存块以指示它们可以从集合中访问根块。
扫一扫
标记阶段完成后，清扫器遍历整个堆，如果使用了一个内存块但没有 marked 这意味着代码无法访问它，因此它是 "freed"即标记为 免费。在 mark 阶段标记的内存块已删除该标记。
当前的实现需要一个原子调用来执行垃圾收集，也就是 gc，但我一直想知道是否可以将它分成多个调用而不是 monolithic/atomic 调用。
这将有助于减少抖动：而不是一个大的定时命中，你会有一堆较小的调用分散开来。 （这里不讨论如何 "spread out" 调用 gc 的实现细节......除非有人认为它会添加到讨论中。）
如果 gc 是 运行 "in the background" - in-between 字节码或 after pre-defined bytecodes - 那么错误点的分配（或释放）可能会导致race-condition 和堆损坏。在我们可以拆分 gc 执行之前，我们必须确定可能的竞争条件。
可以执行的两个操作是：分配和解除分配。
分配
如果用户在标记或清除阶段的中间执行分配会发生什么情况？
让我们看一个具体的代码示例
>> var1 = SomeAllocation()
标记期间分配
在上面的示例中，在 REPL 中执行了一条语句，因此对字典的任何添加都将添加到作为 GC Roots 中的条目的全局字典中。如果在扫描之前将一个条目添加到全局变量中，则不会发生任何事情 "bad"：新的内存块将被 标记为 ，因为它应该如此。
问题是如果全局变量被扫描之后被修改。在那种情况下，内存块不会被 标记 因此在扫描阶段，它将被视为 "unreachable" 并被释放。 . .尽管不应该。
扫描期间分配
如果在清扫器遍历内存中的那个点之前分配了一个块，它将释放它，因为它没有 mark 中的特殊 mark ] 阶段。如果清扫器遍历该块后分配块，则不会发生任何不良情况。
解决方案
如果 gc 正在执行中，将分配的块标记为 已标记。唯一的缺点是，如果您在阶段扫描中分配并且在扫描器检查了 newly-allocated 块之后，您将使用标记有 标记 的块完成 gc .除非用户明确释放它，否则如果它变得无法访问，您将需要经过一个额外的 gc 周期来释放它。
但是有一个简单的解决方案：如果你在相位扫描期间分配，你检查扫描器的位置：如果 new-block-to-be-allocated 在它后面，不要用 标记标记它 否则，请用 标记 标记它，因为清扫器会删除 标记。这样你就不会退出 gc 标记为 mark.
取消分配
如果用户在标记或清除阶段的中间执行分配会发生什么情况？
标记期间解除分配
如果在扫描引用 (parent) 块之前 释放 块，则不会发生任何事情。
如果一个块被释放并且它有children已经被标记，我们有一个不一致，因为块只有 marked 如果他们有一个 parent 也是 marked （或者 parent 是 GC root).结果是这些无法访问但已标记的块将不会被释放，直到额外的 gc 周期，因为已经 标记 ，这些 parent-less 但 标记 方块不会被相位扫描释放。
但是，我不认为这是一个问题，因为这与单体 gc 的情况没有任何不同。在单体 gc 中，您必须完成当前的 gc 周期，然后用户将调用 free(ptr)，然后该块的 children 将在下一个 [=12] 期间被释放=].堆处于 "correct" 状态之前的时间不会改变。
扫描期间取消分配
如果一个块在扫描程序检查之前被 释放 ，则不会发生任何特殊情况。 free操作改变th目标方块的状态从 marked 到 free 然后当清扫器到达它时。 . .这里没什么可看的，只是一个空闲块。
如果一个块在清扫器检查后被释放，释放操作将目标块的状态从已使用 到 免费 .
问题
我的分析是否正确：是否可以拆分 mark+sweep 垃圾回收？
是的，有可能。
Java 从版本 1.4 (2002) 开始就有一个 Concurrent Mark-Sweep (CMS) 收集器。它的工作原理与您描述的类似。
如果你 运行 Jython，我想你今天可以在本机利用它。