garbage-collection - 分两个阶段停止和复制垃圾收集器

Question

当成对实现停止和复制垃圾收集器时，我需要两个存储库（旧的和一个免费的新的）。一个存储库由汽车和CDS组成。因此，基本上，当我创建一个新地址时，它是指向thecars和the-cdrs的指针。

分配新内存时，我发现空间不足，因此启动了GC。这是做什么的：


切换记忆库
移动：从旧银行中读取汽车和cdr，复制到新银行，然后将指针放在旧银行中，指向新银行，以备后用。
scan：循环遍历内存，并将所有内容从旧复制到新。


现在的问题是：为什么我需要先扫描然后再移动。我为什么不能一起做？

Answer 1

听起来好像您正在通过really awesome garbage collection assignment来实现自己的收集器（标记和清除，停止和复制，分代）。

对您问题的一般回答：通过交换空间，两次通过算法通常比一次通过算法使用更少的内存。

更具体的答案：在停止复制收集器中，您可以通过以下两个步骤来完成此操作：（1）首先将实时数据复制到新的半空间中，然后（2）调整实时数据中的内部引用以引用其中的元素新的半空间，将旧内存映射到新内存。

您必须意识到执行映射所必需的信息并不是不可思议的：您需要内存来跟踪如何重定向已移动的内存。请记住：您的收集器本身是一个程序，它必须使用有限的少量内存！例如，将哈希表保留在收集器中以进行簿记将是僵局的：它不是按规则进行的。因此，您需要跟踪的一件事是确保收集器正在使用有限的内存。因此，这解释了为什么停止复制收集器将重用旧的半空间并将那些重定向记录写入那里。

牢记这一约束：重要的是认识到我们需要注意如何遍历实时场景。我们选择哪种方法可能会或可能不会以一些非常微妙和令人惊讶的方式需要额外的内存。特别是在一般情况下递归不是免费的！从技术上讲，在第一遍中，我们不仅应将新的半空间用作复制的目标，而且还应将其用作控制堆栈的时髦表示，用于实现遍历实时数据的递归过程。

具体来说，如果我们正在执行这样的单遍方法来复制活动集：

;; copy-live-set: number -> void
;; copies the live set starting from memory-location.

Pseudocode:

to copy-live-set starting at memory-location:

  copy the block at memory-location over to the new semispace, and

  record a redirection record in the old semispace

  for each internal-reference in the block:

      recursively call copy-live-set at the internal-reference if
      it hasn't been copied already

      remap the internal-reference to that new memory location

那么您可能会惊讶地发现我们搞砸了记忆。上面的内容将打破收集器对运行时环境做出的承诺，因为此处的递归不是迭代的！它将消耗控制堆栈空间。在活动集遍历期间，它将消耗与我们所走过的结构的深度成比例的控制堆栈空间。哎呀

如果您尝试使用另一种方法遍历实时集，则最终应该看到，有一种遍历整个实时集的好方法，同时仍然可以保证有限的小型控制堆栈使用。提示：考虑如何将图遍历算法编写为一个简单的while循环，并使用一个显式容器来保存接下来要访问的内容，直到我们用尽该容器为止。如果斜视得恰到好处，那么新半空间中的中间值看起来就像那个容器。

一旦发现了如何在恒定的控制堆栈空间中遍历活动集，您将看到需要这两次传递才能完成完整的复制和重写内部引用操作。担心这些细节很麻烦，但是对于了解垃圾收集器的实际工作方式却很重要。一个真正的收集器需要做这样的事情，以关心控制堆栈的使用，以确保它在收集过程中使用有限的内存。

简介：两遍算法是一种解决方案，可以帮助我们节省一些时间。但是在性能方面我们付出的代价并不高：尽管我们两次通过了实时设置，但该过程在实时设置的大小上仍然是线性的。



历史记录：请参见Cheney's Algorithm，并注意开创性论文重点的标题：“ A Nonrecursive List Compacting Algorithm”。突出显示的单词“ Nonrecursive”是推动两遍方法的关键：它试图避免消耗控制堆栈。 Cheney的论文是Fenichel和Yochelson“ A LISP Garbage-Collector for Virtual-Memory Computer Systems”的论文的延伸，在那里作者基本提出了递归，堆栈使用的方法。为了改善这种情况，Fenichel和Yochelson随后建议使用非递归（但很复杂！）Schorr-Waite DFS algorithm进行遍历。切尼的方法是一种改进，因为遍历更简单。