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

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

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

我们的系统设计面试系列在过去几个月得到了很多反馈。我很高兴知道,我们的读者觉得有帮助。

我经常给的一个建议是不要把这些文章作为标准答案。系统设计面试问题通常是开放式的,全部是关于分析和交流。讨论中的任何一点都可以根据面试官的偏好进行更深入的研究。

本周,这个问题略有不同,因为它有点低级,但同时也相当有用 - 垃圾回收系统。垃圾回收系统不仅在很多现代编程语言中广泛使用,同样的思想也可以适应其他领域。

你对垃圾回收了解多少?

许多面试官喜欢与候选人讨论语言偏好。有时就像热身讨论,但有时候他们想要更深入。垃圾回收必然会包含在讨论当中,因为它是几乎所有编程语言中最重要的概念之一。

作为一个面试官,我想这样开始讨论,询问“告诉我你对垃圾回收的了解”。这个问题可以让我了解,候选人对这个话题有多熟悉。

请记住,要在面试中表现出色,你不一定需要了解很多垃圾回收的知识,因为面试官关心分析而不是知识。另一方面,了解很多垃圾回收并不意味着你可以轻松通过面试。

回到问题,垃圾回收是一种系统,可以自动回收编程语言中未使用的内存。 Java 是一个最流行的例子。编写 Java 时,你不需要控制如何分配和回收内存。一切都发生在背后。

优缺点

那么为什么我们需要垃圾回收?很多人可以轻易说出垃圾回收的优点,但是当被问及垃圾回收的缺点时会感到困惑。同样,如果你能很好把握程序的工作,你可以通过分析问题轻松得出好的答案,这不是你需要记住的事实。

垃圾回收的最明显的好处是它使编程更容易。请记住,当我们编写 C ++ 时,我们需要非常小心指针和内存分配(译者注:也可以使用智能指针来避免它)。通过让程序自己处理所有这些,开发人员可以更多关注核心逻辑。

更具体地说,首先垃圾回收有助于开发人员避免几个内存问题,它防止访问悬挂指针,它指向不再存在的对象。其次,它防止释放已经释放的内存区域(双重释放)。最后,它避免了内存泄漏,这意味着无法释放不可访问的内存区域。当开发人员尝试手动管理内存时,所有这些都是常见的缺陷。

那么有什么缺点呢?显然,有许多语言没有像 C++ 那样的内置垃圾回收。

最大的缺点是垃圾回收会消耗计算资源。想一想,垃圾回收不仅需要实现逻辑来回收内存,还要消耗内存来存储对象的状态。在一些朴素的垃圾回收实现中,回收过程甚至可能会阻塞程序。

另一种思考的方式是,如果没有垃圾回收,开发人员可以完全控制内存的使用方式,从而使程序具有更大的灵活性,更容易优化。这就是为什么 C++ 更高效的原因之一。当然,它也容易出错。

设计一个简单的垃圾回收系统

那么如何设计垃圾回收系统?试着自己想想这个问题。如果你没有先前的知识,这会更好。我不想跳到解决方案,而是想告诉你如何逐步分析这个问题。

由于垃圾回收系统的本质是回收程序中未使用的内存,所以关键是要确定哪一块内存是未使用的。更具体地说,我们应该搜索不再被引用的变量。

如果考虑程序中的所有对象(变量),就像一个有向图,每个对象引用其他对象,同时也被一些对象引用。因此,那些没有任何引用的,不可到达的对象应该被回收。正如你所看到的,这个大问题已经简化为一个图问题 - 在一个图中找到不可达的节点。

朴素的标记和扫描

事实上,上述解决方案只是最朴素的方法,被称为标记和扫描。首先,垃圾回收系统执行树的遍历来对象引用,并标记所有访问的对象。在第二阶段,对于所有无法访问的对象,释放它们的内存。

但是系统如何跟踪那些不可达的对象呢?一个简单的方法是保存程序中的所有对象。每当一个新的对象被初始化时,将它添加到池中。

总结

你已经看到了,标记和扫描方法的本质与简单的图的遍历问题没有什么不同。这就是我总是强调基础数据结构/算法的原因,这是所有技术面试问题的基础。

在垃圾回收系统的第二篇文章中,我们将讨论标记和扫描的问题,并与其他实现进行比较。我们还将讨论现代语言中的垃圾回收。