学习垃圾收集理论

Question

我想学习垃圾收集背后的理论.我该怎么做呢？显而易见的答案是 - 编译器教科书......问题是,是否有必要学习词法分析,解析和其他通常在文本中垃圾收集之前的东西？

简而言之,了解垃圾收集理论的先决条件是什么？

PS - 我确实知道解析,词法分析等的目的是什么.只是不知道它们是如何实现的.

Answer 1

按顺序阅读这些文章.它们处于渐进主题/难度顺序(不是按时间顺序排列).

列表直接取自Kathryn McKinley教授的记忆管理课程页面,在这里您可以找到所有文章的链接.

我上学期参加了课程,所以我读了所有这些,我不得不说我学到了我要学习的东西!

• 列出在串行计算机上实时处理,Baker,CACM,21(4)280--294,1978.
• 非递归列表压缩算法,Cheney,CACM,13(11):677-678,1970.
• 基于物体寿命的实时垃圾收集器,Lieberman&Hewitt,CACM,26(6):419--429,1983.
• 生成清除:无中断的高性能存储回收算法,Ungar,Proceedings of the first ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments,1984,pages 157-167.
• 简单的世代垃圾收集和快速分配,Appel,软件 - 实践和经验19(2):171 - 183,1989年2月.
• 基于年龄的垃圾收集,D.Stefanovic,KS McKinley,JEB Moss,ACM面向对象编程系统,语言和应用会议.(OOPSLA),第370-381页.丹佛CO,1999年11月.
• 年长一垃圾收集实践:评价一个Java虚拟机,D.斯特凡诺维奇,M.赫兹,SM布莱克本,KS麦金利和杰布·莫斯,存储系统性能,德国柏林,第175--184,2002年6月. .
• 环路:围绕垃圾收集Gridlock,SM Blackburn,R.Jones,KS McKinley和JEB Moss,ACM会议编程语言设计与实现,德国柏林,第153--164页,2002年6月.
• 一种有效的与机器无关的程序,用于各种列表结构中的垃圾收集,Schorr&Waite,CACM,10(8):501--506,1967.
• 用于垃圾收集的压缩算法的比较,Cohen&Nicolau,ACM Programming on Programming Languages and Systems(TOPLAS),Volume 5,Issue 4,pages 532 - 553,1983年10月.
• MC2:针对内存受限环境的高性能垃圾收集,Sachindran,Berger&Moss,面向对象编程系统,语言和应用的ACM会议,第81-96页,温哥华,不列颠哥伦比亚省,2004年10月.
• Immix:具有空间效率,快速收集和Mutator性能的Mark-Region垃圾收集器,Blackburn&McKinley,ACM Conference on Programming Language Design and Implementation,pp.22--32,Tucson,AZ,June 2008.
• 一种高效的增量自动垃圾收集器,Deutsch&Bobrow,CACM,19(9):522--526,1976年9月.
• 别有用心的引用计数:快速的垃圾收集无需等待,SM布莱克本和KS麦金利,面向对象的编程系统,语言和应用程序的ACM 2003 SIGPLAN会议论文集,2003页344-359,Annehiem,CA,十月.
• 循环追踪:高效的并发Mark-Sweep循环收集,Frampton和Blackburn,2009年.(提交给ISMM.)
• Multiprocessing compactifying garbage collection,Guy L. Steele,Jr.,CACM 18(9):495-508,1975.
• 实时垃圾收集:合作练习,EW Dijkstra,L.Lamport,AJ Martin,CS Scholten和EFM Steffens,ACM通讯,21(11):966--975,1978年11月.
• 保持并发垃圾收集算法的正确性,Vechev,Yahav和Bacon,ACM Conference on Programming Language Design and Implementation,Ottawa,Ontario,pp.341-353,2006.
• 一种具有低开销和一致利用率的实时垃圾收集器,Bacon,Cheng和Rajan,ACM Symposium on Programming of Programming Languages,New Orleans,Louisiana,pp.285-298,2003.
• 税收和支出:民主调度实时垃圾收集,奥尔巴赫,培根,郑,林,伯龙,格雷西,麦克洛斯基,Micic和Sciampacone,ACM国际会议的嵌入式软件,佐治亚州亚特兰大,第245-254页,2008.
• 在不合作的环境中收集垃圾,H.Boehm和M.Weiser,Software Practice and Experience,18(9):807-820,1988.
• 囤:一种可扩展的内存分配器为多线程应用程序,ED伯杰,KS麦金利,RD Blumofe和PR威尔逊,对编程语言体系结构支持第九届国际会议和操作系统,剑桥,马萨诸塞州,第117--128,2000年11月. .
• Cork:Garbage-Collected Languages的动态内存泄漏检测,Jump&McKinley,提交给ACM软件实践和经验交易,2009年.(缩写版本出现在ACM Conference on Programming Languagesm,Nice,France,2009年1月.)
• 泄漏修剪,邦德和麦金利,ACM建筑支持编程语言和操作系统会议,华盛顿特区,2009年3月.(出现.)
• Free-me:个人物体回收的静态分析,Guyer&McKinley,ACM会议编程语言设计与实现会议,加拿大渥太华,第364-375页,2006年6月.
• 垃圾收集可以比堆栈分配更快,Appel,Information Processing Letters 25(4):275-279,1987 June 1987.
• 垃圾收集优势:改善程序位置 Huang,Blackburn,McKinley,Moss,Wang和Cheng,面向对象编程系统,语言和应用的ACM会议,温哥华,BC,第69-80页,2004年10月.
• 揭秘魔术:高级低级编程,Daniel Frampton,Stephen M. Blackburn,Perry Cheng,Robin Garner,David P. Grove,J.Eliot B. Moss和Sergey I. Salishev.ACM国际虚拟执行环境会议,华盛顿特区,2009年3月.(出现.)
• 神话与现实:垃圾收集的性能影响,SM Blackburn,P.Cheng和KS McKinley,ACM SIGMETRICS计算机系统测量和建模会议,第25-36页,纽约,纽约,2004年6月.
• 统一的垃圾收集理论,Bacon,Cheng和Rajan,ACM会议,面向对象编程,系统,语言和应用,加拿大温哥华,加拿大,第50-68页,2004年.

Answer 2

我想学习垃圾收集背后的理论。我该怎么办？

我也是对垃圾收集感兴趣的涉猎者（到目前为止，我编写了自己的称为HLVM的垃圾收集VM ）。我通过阅读尽可能多的有关垃圾回收的研究论文以及自己玩弄的想法中学到了东西，这些想法既存在于虚拟机中，也存在于编写内存安全的高级模拟中。

明显的答案是-编译器教科书...问题是，有必要学习通常在文本中进行垃圾收集之前的词法分析，解析和其他内容吗？

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

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

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

垃圾收集就是确定可达性。当程序由于无法访问该值而无法再获取对该值的引用时，GC可以回收该值所占用的内存。通过从一组“全局根”（线程栈和内核寄存器中的全局变量和指针）开始遍历堆来确定可到达性

GC设计有很多方面，但是您可能会从四种主要的垃圾收集算法开始：

• 扫一扫（McCarthy，1960）
• 紧凑型（Haddon和Waite，1967年）
• 停止复制（Cheney，1970）
• 标记区域（McKinley et al。，2007）

这些基本思想的最显着发展也许就是分代垃圾收集，这是多年来的实际标准设计。

我个人的感觉是，有关垃圾收集的一些晦涩的工作传达了同样多的有用信息，因此我强烈建议：

• 贝克的跑步机（漂亮的实时GC）。
• VCGC（完全不同的三色标记方案）。

您可能还想研究三种写障碍（Dijkstra，Steele和Yuasa的写障碍），并研究卡片标记和记忆设置技术。

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

还有一些与切线相关的重要论文，例如在不合作的环境中亨德森的《准确的垃圾收集》。我使用该技术来避免必须为HLVM编写堆栈行程序。

该memorymanagement.org网站是一个非常宝贵的资源，气相色谱-相关方面尤其是词汇。

Answer 3

有一本关于垃圾收集的书,如果我可以添加一个相当不错的书:

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

理查德琼斯还有一个很好的网站收集垃圾收集资源.

大多数早期的垃圾收集文件都非常易读.你可以从保罗威尔逊对"单处理器垃圾收集技术"(1992,LNCS vol.637)的调查开始,然后深入探讨有关主题的原始文献.