垃圾回收算法手册:自动内存管理的艺术
基本信息
- 原书名:The Garbage Collection Handbook: the Art of Automatic Memory Management
- 作者: (英)理查德·琼斯(Richard Jones)(美)安东尼·霍思金(Antony Hosking)(美)艾略特·莫斯(Eliot Moss)
- 译者: 王雅光 薛迪
- 丛书名: 计算机科学丛书
- 出版社:机械工业出版社
- ISBN:9787111528821
- 上架时间:2016-3-3
- 出版日期:2016 年3月
- 开本:16开
- 页码:437
- 版次:1-1
- 所属分类:计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
教材

编辑推荐
为1996年《Garbage Collection:Algorithms for Automatic Dynamic Memory Management》一书提供了完整的、最新的、权威的续作。
全面讲解并行垃圾回收算法、并发垃圾回收算法以及实时垃圾回收算法。
深入剖析某些垃圾回收领域的棘手问题,包括与运行时系统的接口。
提供在线数据库支持,包含超过2500条垃圾回收相关文献。
内容简介
计算机书籍
几乎所有的现代编程语言都采用了垃圾回收机制
,因此深入了解此方面内容对于所有开发者而言都大
有裨益。对于不同垃圾回收器的工作方式,以及当前
垃圾回收器所面临的各种问题。这本**手册都提供
了专业的解答。掌握这方面的知识之后,在面对多种
不同的垃圾回收器以及各种调节选项时。相信开发者
能够*有把握。
理查德·琼斯、安东尼·霍思金、艾略特·莫斯
所*的这本《垃圾回收算法手册(自动内存管理的艺
术)》共19章,**章探讨为什么需要自动内存管理,
并简要介绍对不同垃圾回收策略进行比较的方法:第
2~5章详细描述4种经典的垃圾回收算法,包括标记
一清扫算法、标记-整理算法、复制式回收算法和引
用计数算法;第6章深入比较第2~5章所介绍的回收
策略与算法;第7章介绍多种不同的内存分配技术,
并进一步探究自动垃圾回收与显示内存管理这两种场
景下分配策略的不同之处;第8章讨论为何需要将堆
划分为多个不同的空间。以及如何管理这些空间;第
9章介绍分代垃圾回收;**0章介绍大对象的管理策
略以及其他分区策略;**1章介绍运行时接口。包括
作译者
Antony Hosking,普渡大学西拉法叶分校计算机学院副教授。1985年在澳大利亚阿德莱德大学获得数学学士学位,1987年在新西兰怀卡托大学获得计算机科学硕士学位,1995年获得马萨诸塞大学阿默斯特分校计算机科学博士学位。他的主要研究方向是编程语言的设计与实现,特别是数据库与持久化编程语言、面向对象数据库系统、动态内存管理、编译器优化以及编程语言和应用的架构支持。美国计算机协会高级会员、电气与电子工程师协会会员,且经常担任编程语言设计与实现方面主要会议的组织和指导委员会成员。已婚,育有三个孩子,最大的业余爱好是坐在阿德莱德大学Oval体育场内观看板球锦标赛。
Eliot Moss,马萨诸塞大学阿默斯特分校计算机科学学院教授。1975年获得电气工程学士学位,1978年获得电气工程硕士学位,1981年获得计算机科学博士学位,上述学位均是在麻省理工学院获得。在服完4年兵役后,他任职于马萨诸塞大学阿默斯特分校计算机科学系,主要研究方向为编程语言及其实现,而且早在1978年就构建出垃圾回收器。除了自动内存管理领域的研究之外,他在持久编程语言、虚拟机实现、事务性编程与事务内存方面也拥有较高的知名度。还与IBM研究员一起推动Jikes RVM Java虚拟机的学术研究许可,并最终促使其成为开源项目。2007年成为美国计算机协会研究员,2009年成为电气与电子工程师协会研究员。他曾在美国计算机协会的编程语言特别兴趣小组担任4年的秘书长职务,也曾多次担任其研究领域重大会议的组织与指导委员会成员。2005年被授予圣公会牧师,在学术研究工作之余还主持一些教会事务。已婚,育有两子。闲暇之余喜欢听录音书、看电影,竖琴演奏技艺也有小成就。
目录
译者序
前言
作者简介
第1章 引言 1
1.1 显式内存释放 1
1.2?自动动态内存管理 3
1.3 垃圾回收算法之间的比较 5
1.3.1 安全性 5
1.3.2 吞吐量 5
1.3.3 完整性与及时性 5
1.3.4 停顿时间 6
1.3.5 空间开销 7
1.3.6 针对特定语言的优化 7
1.3.7 可扩展性与可移植性 8
1.4 性能上的劣势 8
1.5 实验方法 8
1.6 术语和符号 10
1.6.1 堆 10
1.6.2 赋值器与回收器 11
译者序
本书可以说是垃圾回收领域排名第二的经典著作之一,排名第一的也出自同一作者之手。1996年,Jones等的Garbage Collection: Algorithms for Automatic Dynamic Memory Management一书出版,并于2004年译成中文。回顾1996年,垃圾回收技术的大范围应用才刚刚起步——C++正称霸着软件开发领域,Java语言才推出一年之久,Anders Hejlsberg(C#之父,.NET的创立者)刚刚加入微软公司。近20年过去了,垃圾回收技术早已在各种编程语言中遍地开花,而且几乎成为每种新诞生语言的标配。与1996年的Garbage Collection: Algorithms for Automatic Dynamic Memory Management一书相比,本书不仅在内容上更加丰富,而且更加注重充分利用近20年来硬件发展所带来的机遇与挑战。
本书从最基础的垃圾回收算法出发,进一步介绍了到目前为止已经十分成熟的工业级垃圾回收技术实现(例如分代回收机制),这些内容基本上算是垃圾回收领域的“经典”内容。与此同时,面对多核技术的发展以及并行程序的普及,本书使用接近一半的篇幅介绍了如何充分利用多处理器的能力来实现垃圾回收(例如并行回收、并发回收等),相关技术大都是近些年才研发出来的新成果,代表着垃圾回收领域最先进的发展方向。本书最后进一步介绍了垃圾回收技术在实时系统领域的最新研究成果。
对于开发人员而言,在享受垃圾回收机制所带来便利的同时,是否曾想过隐藏在它背后的秘密?在进行技术选型时,如何评估垃圾回收对性能可能造成的影响?面对编程语言所提供的种类繁多的垃圾回收相关参数,应当如何进行配置与调优?通过本书,开发人员能够更加深入地了解垃圾回收方面的相关问题、不同回收器的工作模式。对于研究生以及大学生而言,如果他们对编程语言的垃圾回收机制的技术实现感兴趣,本书将是不二之选。
最后,我要感谢那些在翻译过程中给予我帮助与支持的人。首先要感谢《Java虚拟机规范(Java SE 7版)》的译者薛迪将我引入技术书籍翻译这个领域,并在翻译过程中指出我的许多不足。同时还要感谢机械工业出版社的吴怡和张梦玲编辑对我的帮助,以及对我延迟交稿的包容。最后要特别感谢的是我的妻子,在这一年多的时间里,翻译工作让我没有太多的时间陪她,在此致以深深的歉意。
王雅光
2015年12月
前言
THE GARBAGE COLLECTOR HAS BEEN CALLED. SOME INTERESTING STATISTICS ARE AS FOLLOWS:
以及其他一些更加冗长的错误信息,这一问题几乎占据了当时的整个演示时间,于是McCarthy的项目小组不得不省略刷新Lisp核心映像的相关内容,并在观众的笑声中无奈地结束演示。50多年后的今天,垃圾回收早已不再是一个笑话,反而已经成为现代编程语言实现的关键组成部分之一。对于所有诞生于1990年之后且得到广泛应用的编程语言,Visual Basic(出现于1991年)是其中唯一一个没有采用自动内存管理的语言,但是其现代版本VB.NET(出现于2002年)却依赖于具备垃圾回收能力的微软公共语言运行时(Microsoft common language runtime)。
垃圾回收给软件开发带来的收益不胜枚举。它可以消除开发过程中的几大类错误,例如尝试对悬挂指针(即指向已经回收或错误甚至被重新分配出去的内存)进行解引用,或者对已经释放的内存进行二次释放。尽管其不能保证完全消除内存泄漏问题,但也能大幅减少该问题的出现几率,还能够大幅简化并发数据结构的构建和使用[Herlihy and Shavit, 2008]。综上所述,开发者能够基于垃圾回收所提供的抽象能力进行更好的软件工程实践。它简化了用户接口,使得代码更加容易理解和维护,进而更加可靠。由于用户接口不再需要关注内存管理,所以提升了代码的可复用性。
在过去的数年中,内存管理技术在软件和硬件方面都取得了长足进步。1996年,典型的Intel 奔腾处理器的时钟速度只有120MHz,就连基于Digital的Alpha芯片的高端工作站主频也只有266MHz。而在今天,主频达到3GHz以上的高端处理器以及多核芯片已经非常普遍,主存空间也几乎取得了1000倍的增长,普通台式计算机的内存大小已经从最初的几兆字节扩展到了4GB。尽管如此,DRAM内存的性能提升速度依然赶不上处理器的主频增长速度。我们曾在Garbage Collection: Algorithms for Automatic Dynamic Memory Management中指出,“垃圾回收是能够解决所有内存管理问题的灵丹妙药”,并特别指出“垃圾回收机制尚无法应用于硬实时系统(即系统必须在给定时限内对事件做出响应)”。但时至今日,硬实时垃圾回收器已经走出实验室并进入到商业应用领域。尽管现代垃圾回收器已经解决了大多数内存管理问题,但新硬件、新环境以及新应用的出现仍会在内存管理领域不断抛出新的问题与挑战。
致读者
本书试图将过去50多年间学者和开发者们在自动内存管理领域所积累的丰富经验加以总结。所涉文献数量庞大,在写作期间我们的在线资源库收集了多达2500条记录。在描述最重要的实现策略以及代表最先进水平的实现技术时,我们尽量在一个统一的、易于接受的框架内进行讨论与比较。我们特别注意使用统一的风格和术语来介绍相关的算法与概念,同时辅以伪代码和插图来描述具体细节。对于关乎性能的部分,我们特别注意对底层细节的描述,例如同步操作原语的选择、硬件组件(如高速缓存)对算法设计的影响。
在过去的10年间,硬件和软件设施的发展给垃圾回收领域带来了许多新的挑战。处理器和内存之间的性能差距总体在不断扩大。处理器时钟速度得到大幅增长,单个芯片上集成的处理器核心数量越来越多,使用多处理器的模块也越来越普遍。本书重点关注了这些变化对高性能垃圾回收器的设计与实现所造成的影响。由于高速缓存对性能的影响至关重要,所以垃圾回收算法必须考虑到局部性问题。越来越多的应用程序已经多线程化,且运行在多核处理器之上,因而我们应当避免内存管理器成为性能瓶颈。另外,垃圾回收器的设计应当充分利用硬件的并行能力。在Jones[1996]中,我们完全没有考虑如何使用多线程进行并行回收,只用一章的篇幅来介绍增量回收与并发回收,这在当时的书中显得格外引人注目。
本书自始至终都密切关注现代硬件所带来的机遇与限制,对局部性问题的考量将贯穿全书。我们默认应用程序可能是多线程的。尽管本书涵盖了很多更加简单、更加传统的算法,但我们还是花了全书近一半的篇幅来介绍并行回收、增量回收、并发回收以及实时回收。
我们希望本书能够帮助到对编程语言实现感兴趣的研究生、研究人员和开发人员。对于选修了编程语言、编译器构建、软件工程或操作系统方面高级课程的本科生而言,本书也会有所帮助。此外,我们希望专业开发人员能够通过本书更加深入地了解垃圾回收面临的相关问题、不同回收器的工作模式,我们相信,与具体的专业知识相结合,开发人员在面对多种垃圾回收方法时,能够更好地进行回收器的选型与配置。由于几乎所有的现代编程语言都提供了垃圾回收机制,所以全面了解这一课题对所有开发者来说都是不可或缺的。
本书结构
本书第1章以探讨为什么需要自动内存管理作为开篇,简要介绍了对不同垃圾回收策略进行比较的方法。该章结尾介绍了贯穿全书的抽象记法与伪代码描述方式。
接下来的4章详细描述了4种经典的垃圾回收算法,分别是标记–清扫算法、标记–整理算法、复制式回收算法以及引用计数算法。本书对这些回收算法进行了深入的研究,并特别关注了其在现代硬件设施上的实现。如果读者需要一些更加基础的介绍,可以参阅我们先前的一本书Garbage Collection: Algorithms for Automatic Dynamic Memory Management(Richard Jones and Rafael Lins, Wiley, 1996)。第6章深入比较了第2~5章所介绍的回收策略与算法,评估了它们各自的优缺点以及在不同情况下的适用性。
内存回收策略同样依赖于内存分配策略。第7章介绍了多种不同的内存分配技术,并进一步探究了自动垃圾回收与显式内存管理这两种场景下分配策略的不同之处。
前7章假定所有堆中的对象均采用相同的管理策略,但根据许多因素可知这并非一种良好的设计策略。第8章讨论了为何需要将堆划分为多个不同的空间,以及如何管理这些空间;第9章介绍了最成功的对象管理策略之一:分代垃圾回收;第10章介绍了大对象的管理策略以及其他分区策略。
在构建垃圾回收器的过程中,与运行时系统其他部分的对接是最复杂的内容之一。因此第11章用了一整章的篇幅来介绍运行时接口,包括指针查找、能够安全发起垃圾回收的代码位置、读写屏障等。第12章讨论了特定语言相关内容,包括终结机制和弱引用。
在接下来的章节中,我们将注意力集中在并发环境下。第13章探讨了现代硬件系统给垃圾回收器的实现者所带来的新机遇与挑战,同时介绍了同步、前进、结束、一致等问题的相关算法。第14章介绍如何在挂起所有应用程序线程的前提下使用多个线程进行垃圾回收。接下来的4章介绍了多种不同种类的并发回收器,它们均放宽了“万物静止”这一要求,其回收过程只需要给用户程序引入十分短暂的停顿。最后,第19章探讨了最富挑战性的课题,即垃圾回收在硬实时系统中的应用。
每一章结尾都总结了一些需要考虑的问题,其目的在于引导读者去思考自己的系统有什么样的需求,以及如何满足这些需求,这些问题不仅关乎用户程序的行为,也关乎操作系统,甚至底层硬件的形为。但这些问题并不能替代对具体章节的阅读,它们并不是描述现有解决方案,而是提供进一步研究的焦点。
本书缺少了哪些内容?我们仅仅讨论了内嵌于运行时系统的自动内存管理技术,即使编程语言指定了垃圾回收相关的规范,我们也没有深入探讨其所支持的其他内存管理机制。最明显的例子是区域(region)的应用[Tofte and Talpin, 1994],其在Java实时规范中占据着显著的地位。我们仅花费了少量的篇幅来介绍区域推断以及栈上分配技术,并且几乎没有涉及其他通过编译期分析来替代,甚至辅助垃圾回收的技术。尽管引用计数策略在C++等语言中得到了广泛应用,但我们依然认为它不是在用户程序中进行自动内存管理的最佳选择。最后,我们认为,下一代计算机将采用高度非一致内存架构,并配备异构垃圾回收器(heterogeneous collector)。这方面的技术与分布式垃圾回收(distributed garbage collection)的相关性较大,但在过去的数十年间,分布式垃圾回收领域鲜有新的研究成果发表,这不得不说是一件憾事。本书没有介绍分布式垃圾回收的相关内容。
在线资源