设计垃圾回收系统(第二部分)

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

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

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

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

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

朴素的标记和扫描(续)

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

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

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

改进

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

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

  • 白色 - 没有引用,应该回收的对象。
  • 黑色 - 不可回收的可达对象。黑色的对象不引用白色的对象。
  • 灰色 - 可从根到达的对象,但没有扫描是否引用了白色对象。

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

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

引用计数

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

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

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

这种方法有什么缺点?

引用计数的缺点

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

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

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

总结

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

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

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