设计垃圾回收系统（第二部分）

原文：Design a Garbage Collection System (Part II)

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

这是设计垃圾回收系统系列的第二篇文章。如果没有阅读我们的第一篇文章，请查看一下，因为我们将继续我们上次的讨论。

在我们之前的文章中，我们一直在谈论垃圾回收的基本概念，垃圾回收是一种在编程语言中自动回收未使用的内存的系统。垃圾回收为什么很酷就很明显。它允许开发人员无需关心内存管理，编写更强大的代码。另一方面，这可能会影响性能，并且使用内存的灵活性较小。

为了继续我们的讨论，我会更多讨论这种朴素的标记和扫描方法，以及我们如何改进它。我还将介绍其他常见的设计垃圾回收系统的方法。

朴素的标记和扫描（续）

朴素的标记和扫描方法的想法是非常简单的。系统执行树的遍历来跟踪对象引用，并标记所有访问的对象。在第二阶段，对于所有无法访问的对象，释放它们的内存。

显然，这个方法很容易理解和实现。那么有什么缺点呢？

最值得注意的问题是整个系统在垃圾回收过程中必须暂停。换句话说，在垃圾回收时偶尔会冻结问题，工作集不允许改动。因此，这将显着影响对时间要求严格的应用的性能。

鉴于标记和扫描的性能问题，现代垃圾回收系统采取了稍微不同的方法 - 三色着色。

让我简单介绍一下这个算法。简而言之，系统将所有对象标记为三种颜色：

最初，从根引用的所有对象都是灰色的，白色的集合包括其他所有东西（黑色是空的）。系统每次挑选一个对象从灰色放到黑色中，并将其所有引用从白色移动到灰色。最后，灰色变成空的，所有的白色对象都被回收。

最显着的优势在于系统可以即时进行垃圾回收，这通过在分配对象和改动期间标记对象来实现。因此，程序不会长时间停止，性能得到改善。

那么有没有设计垃圾回收系统的其他方法，不会冻结程序呢？

一个自然的解决方案是引用计数，这个想法是非常简单的。垃圾回收的核心概念是当一个对象没有引用时，我们应该尽快回收它。那么为什么不跟踪每个对象的引用计数呢？

引用计数系统将为每个对象维护一个计数器，来计算它所拥有的引用数量。计数器在创建引用时递增，并且在销毁引用时递减。当计数器为 0 时，对象应该被回收。显然，系统可以在正确的时间释放内存，因此可以进行垃圾回收。

这种方法有什么缺点？

显然，引用计数器增加了整个系统的空间开销。由于每个对象都需要额外的存储空间来存储引用计数，因此没有任何优化的情况下，所需的总空间显着增加。

另一个问题是速度的开销。由于系统需要不断更新计数器，程序中的每个操作都需要修改一个或多个参考计数器。另一种理解它的方法是，引用计数系统不是将程序冻结来回收对象，而是将开销分成每个小操作。既然你无法免费获得所有的东西，你需要决定是否希望每一个操作都稍微慢一些，或者偶尔停止整个程序。

另外，循环引用也可能是引用计数的问题。如果两个对象相互引用，它们将永远不会被回收。如果你有 obj-c 的经验，你应该已经知道解决方案。一些语言为创建循环的反向指针引入了“弱引用”的概念。它是一个特殊的引用对象，它的存在不会增加引用对象的引用计数。

垃圾回收是一个有趣的话题，因为每个程序员都应该基本了解。更重要的是，它可以帮助你理解为什么有些程序以不同的方式设计。

对于系统设计面试，重要的是要注意，你不一定需要有太多的先验知识。在面对新问题时提供合理的分析更为重要。考虑到这一点，即使你不是编程语言方面的专家，你仍然可以通过垃圾回收的面试。

如果你想更多了解这个话题，我也建议你看看为什么 C++ 没有垃圾回收器的讨论？