学习垃圾回收理论

Question

学习垃圾回收理论

language-agnosticgarbage-collectiontheory

13

我想学习垃圾回收的理论。我该怎么做？显而易见的答案是 - 一本编译器教材...问题是，在一本文本中通常在垃圾回收之前需要学习词法分析、解析和其他方面的知识是否必要呢？

简而言之，学习垃圾回收理论的先决条件是什么？

P.S - 我知道解析、词法分析等工具的目的，只是不知道它们如何实现。

- Pranav

5

不，解析和词法分析与垃圾回收没有任何关系。 - anon

9

讨论建议删除这个问题的元讨论：https://meta.stackoverflow.com/q/382831/1709587。 - Mark Amery

4个回答

15

我想学习垃圾回收背后的理论。我该如何开始？

我也是一个对垃圾回收很感兴趣的人（甚至编写了自己的垃圾回收虚拟机HLVM）。我通过阅读尽可能多的垃圾回收研究论文并亲手实践这些想法来学习，既可以在我的虚拟机中原始地进行，也可以编写内存安全的高级模拟。

显而易见的答案是- 编译器教材...问题是，在一本文本中通常先于垃圾回收的词法分析、解析和其他内容是否有必要学习？

词法分析、解析和其他内容与垃圾回收无关。您可能会从编译器书籍中获得过时的垃圾回收概述，但需要阅读研究论文才能获得最新的观点，例如关于多核方面的观点。

简而言之，学习垃圾回收理论的先决条件是什么？

您需要了解基本的图论、指针、堆栈、线程和（如果您对多线程感兴趣）低级并发原语，如锁。

垃圾回收完全是关于确定可达性。当程序无法再获取到对值的引用，因为该值已变得不可达时，GC可以回收该值占用的内存。可达性是通过从一组“全局根”（全局变量和线程堆栈中的指针以及核心寄存器中的指针）开始遍历堆来确定的。

垃圾回收设计有许多方面，但您可以从四种主要的垃圾回收算法开始学习：

标记-清除（McCarthy，1960年）
标记-整理（Haddon和Waite，1967年）
停止-复制（Cheney，1970年）
标记区域（McKinley 等人，2007年）

也许这些基本思想中最值得注意的演变是分代垃圾回收，它是多年来的事实标准设计。

我个人认为，一些关于垃圾回收的晦涩工作传达了同样有用的信息，所以我也强烈推荐：

Baker's treadmill（一个美丽的实时GC）。
VCGC（完全不同的三色标记方案）。

然后，您可能还想研究三种写障碍器（Dijkstra、Steele和Yuasa）并查看卡片标记和记忆集技术。

然后，您可能还想检查一些实现者为Java和.NET等语言实现以及Standard ML的SML/NJ编译器、OCaml编译器、Glasgow Haskell编译器等选择的实际设计决策。采用的技术之间的差异与它们之间的相似之处一样大！

还有一些非常相关的论文，比如Henderson的在不合作环境中进行准确的垃圾回收。我使用了那个技术来避免为HLVM编写堆栈行走器。

memorymanagement.org网站是一个非常宝贵的资源，特别是与GC相关术语的词汇表。

- J D

11

有一本完整的垃圾收集书籍，而且相当不错，如果我可以这样说：

Richard Jones 和 Rafael Lins, Garbage Collection, Wiley and Sons (1996), ISBN 0471941484

Richard Jones 还维护了一个很好的垃圾收集资源收集站点。

大多数早期的垃圾收集论文都非常易读。你可以从 Paul Wilson 的《单处理器垃圾回收技术调查》(1992, LNCS vol. 637) 开始，然后深入研究那些听起来有趣的主题的原始文献。

- earl

Jones/Lins这本书和Wilson的调查非常完美。 - Norman Ramsey

1

Richard Jones的新书仍然更好！http://gchandbook.org/ - J D

-2

你可能还想看看Squeak: Open Personal Computing，其中涵盖了Squeak Smalltalk垃圾收集器等ST设计问题。你也应该看看Squeak itself - 它几乎完全是用Smalltalk编写的，包括GC在内的所有源代码都是免费提供的，并且可以使用Smalltalk浏览器轻松学习。

- anon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sam Harwell · Accepted Answer

按顺序阅读这些论文，它们按主题难易程度递进排序（而非按时间顺序）。

此列表直接取自Kathryn McKinley教授的内存管理课程页面，该页面中包含所有文章的链接。

我上学期参加了这门课程，所以我阅读了所有这些论文，并且我必须说我学到了我想要学的知识！

请注意，下面大部分论文的免费可用副本链接已包含在垃圾收集标签维基中：https://stackoverflow.com/tags/garbage-collection/info。

一个在串行计算机上实时进行列表处理的论文, Baker, CACM, 21(4) 280--294, 1978.
一种非递归的列表紧缩算法, Cheney, CACM, 13(11): 677--678, 1970.
基于对象寿命的实时垃圾收集器, Lieberman & Hewitt, CACM, 26(6): 419--429, 1983.
代际式清除: 一种非中断高性能存储回收算法, Ungar, 第一届ACM SIGSOFT/SIGPLAN软件工程对实践环境的研讨会论文集, 1984, 页码157--167.
简单的代际式垃圾收集和快速分配, Appel, Software--Practice and Experience 19(2):171-183, 1989年2月.
基于对象年龄的垃圾收集, D. Stefanovic, K. S. McKinley, J. E. B. Moss, ACM面向对象编程系统、语言和应用程序设计大会(OOPSLA), pp. 370--381. 丹佛科罗拉多州, 1999年11月.
老年优先的垃圾收集在Java虚拟机中的实践评估, D. Stefanovic, M. Hertz, S. M. Blackburn, K. S. McKinley, and J. E. B. Moss, 内存系统性能, 柏林, 德国, 页码175--184, 2002年6月.
Beltway: 解决垃圾收集死锁问题, S. M. Blackburn, R. Jones, K. S. McKinley, and J. E. B. Moss, ACM编程语言设计与实现会议, 柏林, 德国, pp. 153--164, 2002年6月.
一种有效的机器独立垃圾收集程序，适用于各种列表结构, Schorr & Waite, CACM, 10(8): 501--506, 1967.
比较紧缩垃圾收集算法, Cohen & Nicolau, ACM程序设计语言和系统事务处理期刊(TOPLAS), 卷5, 第4期, 页码532--553, 1983年10月.
MC2: 面向内存受限环境的高性能垃圾收集器, Sachindran, Berger & Moss, ACM面向对象编程系统、语言和应用程序设计大会, 页码81-96, 温哥华, BC, 2004年10月.
Immix: 具有空间效率、快速收集和Mutator性能的标记区域垃圾收集器, Blackburn & McKinley, ACM编程语言设计与实现会议, pp.22--32, 图森, AZ, 2008年6月.
一种有效的增量自动垃圾回收算法, Deutsch & Bobrow, CACM, 19(9): 522--526, 1976年9月.
超前引用计数: 快速的垃圾收集，无需等待, S. M. Blackburn and K. S. McKinley , ACM 2003 SIGPLAN面向对象编程系统、语言和应用程序设计大会论文集, 页码344-359,