英语原文共 514 页，剩余内容已隐藏，支付完成后下载完整资料
The Garbage Collection Handbook
1
托管语言以及托管运行时系统不仅能够提升程序的安全性，而且可以通过对操作系统和硬件架构的抽象来提升代码的灵活性。因而受到越来越多开发者的青睐。托管代码的优点己经得到广泛认可虚拟机本身提供的多种服务可以减少开发者的工作量如果编程语言是类型安全的。并且运行时系统可以在程序加载时迸行代码检查。在运行时对资源访问冲突、数组以及其他容器迸行边界检查，同时提供自动内存管理能力那么代码的安全性将更有保障。尽管“一次编译，到处运行”的说法有些言过其实，但虚拟机确实使跨平台程序开发变得更加简单，开发成本更低。开发者也可将主要精力专注在应用程序的逻辑上。
几乎所有的现代编程语言都使用动态内存分配。即允许进程在运行时分配或者释放无法在编译期确定大小的对象，且允许对象的存活时间超出创建这些对象的子程序时间。动态分配的对象存在于堆中而非栈或者静态区中所谓栈，即程序的活动记录或者栈帧；静态区则是指在编译期或者链接期就可以确定范围的存储区域。堆分配是十分重要的功能，它允许开发者:
- 在运行时动态地确定新创建对象的太小，从而避免程序在运行时遭遇硬编码数组长度不足产生的失败)。
- 定义和使用具有递归特征的数据结结构，例如链表、树和映射。
- 向父过程返回新创建的对象，例如工厂方法。
- 将一个函数作为另一个函数的返回值，例如函数式语言中的闭包或者悬挂。
堆中分配的对象需要通过引用迸行访问。一般情况下,引用即指向对象的指针也就是对象在内存中的地址)。引用也可以通过间接方式实现，例如它可以是一个间接指向对象的句柄。便用句柄的好处在于当迁移某一对象时，可以仅修改对象的句柄而避免通过程序改变这个对象或句柄的所有引用。
2
标记-清扫、标记-复制、标记-整理、引用计数是4种最基本的垃圾回收策略。太多数回收器可能会以不同的方式对这些基本回收策略迸行组合，例如在堆中某一区域使用一种回收策略，而在另一个区域使用另一种回收策略接下来的4章将专注于这4种基本回收策略的介绍。。第6章将对它们的特点迸行比较。
在对这4种基本回收策略迸行描述时,我们假设赋值器运行在一个或者多个线程之上。且只有一个回收器线程时，当回收器线程运行时，所有的赋值器线程均处干停止状态这种“万物静止'的策略大幅简化了回收器的实现，从赋值器线程角度来看，回收过程的执行是原子性的，即赋值器线程感知不到回收器的任何中间状态，恒收器也不会受到赋值器线程的任何干扰。我们假设当回收过程开始，赋值器线程停止在一个允许回收器。安全扫描其根集合的回收点，具体的运行时接口我们将在第11章详述。通过“万物静止'的方法可以获取堆的快照，因此回收器在迸行对象存活性判定时不用担心赋值器将堆中对象的拓扑结构重新这同时也意味着在回收器释放内存的过程中，我们无需担心在同一时刻存在其他回收器释放内存或者赋值器线程申请内存。进而避免在线程之间引入额外的同步机制。多赋值器线程同时获取内存的情况我们将在第7章讨论。多问收器线程，或者赋值器与回收器井发执行的情况将导致运行时系统更加复杂。我们将在后面的章节中迸行讨论。我们建议读者先熟悉接下来4童中介绍的基本回收算法,然后再进一步了解后面章节中提到的更加高级的回收器。有经验的读者可能会跳过这些基础算法的描述，但是增加对这些基础回收器实现方式的了解也不失为一件有趣的事：认为第2~6章的部分内容过于精简的读者。可以参考J0nes[1996]中的资料,其对经典算法的描述更加详细，并且包含更多的示例。
理想的垃圾回收的目的是回收程序不再使用的对象所占用的空间，任何自动内存管理系统都面临3个任务:
- 为新对象分配空间。
- 确定存活对象。
- 回收死亡对象所占用的空间。
这些任务并非相互独立，特别是回收空间的方法影响着分配新空间的方法。正如第l章所提到的,真正的存活性问题是一个不可确定的问题，因此我们使用指针可达性(参见1。6节)来近似对象的存活性，只有当堆中存在一条从根出发的指针链能最终到达某个对象时,才能认定该对象存活,更进一步,如果不存在这样一条指针链，则认为对象死亡,其空间可以得到回收。尽管存活对象集合中可能包含一些永远不会再被赋值器访问的对象,但是死亡对象集合中的对象却必定是死亡，标记-清扫算法是我们将要介绍的第一种回收算法，它是在指针可达性递归定义指导下最直接的回收方法，它的回收过程分为两个阶段:第一阶段为追踪阶段,即回收器从根集合(寄存器、线程栈、全局变量)开始遍历对象图，并标记所遇到的每个对象;第二阶段为清扫阶段,即回收器检查堆中每一个对象并将所有未标记的对象当作垃圾进行回收。
标记-清扫算法是一种间接回收算法,它并非直接检测垃圾本身而是先确定所有存活对象，然后反过来判定其他对象都是垃圾。需要注意的是，该算法的每次调用都需要重新计算存活对象集合，但并非所有的垃圾回收算法都需要如第5章将介绍一种直接回收策略,即引用计数。与间接回收不同，直接回收可以通过对象本身来判断其存活性，因此其不需要额外的追踪过程。
3
内存碎片化是非移动式回收器无法解决的问题之一，即:尽管堆中仍有可用空间，但是内存管理器却无法找到一块连续内存块来满足较大对象的分配需求,或者需要花费较长时间才能找到合适的空闲内存。上一章我们提到,对于不需要分配很大对象或者对象大小相差不大的程序,分配器可以仅在单个内存块中分配相同大小的对象,从而缓解内存碎片问题，但对于许多长期运行的程序，如果通过非移动式回收器进行内存管理,通常会出现碎片化问题，进而导致程序性能的下降。
在接下来的两章中，我们讨论两种对堆中存活对象进行整理以降低外部碎片的回收策略。堆整理的最大优势在于，它允许极为快速的顺序分配，即简单地进行堆上限判断，然后根据所需空间大小阶跃式地移动空闲指针(我们将在第7章中讨论内存分配机制。本章我们讨论的是原地整理策略，即将对象整理到相同区域的一端。下一张我们将讨论复制式回收策略，即将存活对象从一个区域移动到另一个区域(例如两个半区之间)。
标记-整理算法的执行需要经过数个阶段，首先是标记阶段,其相关内容我们在上一章已经讨论过;然后是整理阶段,即移动存活对象，同时更新存活对象中所有指向被移动对象的指针。在不同算法中,堆的遍历次数、整理过程所遵循的顺序、对象的迁移方式都有所不同。整理顺序会影响到程序的局部性。移动式回收器重排堆中对象时所遵循的顺序包括以下3种:
- 任意顺序 对象的移动方式与它们的原始排列顺序和引用关系无关。
- 线性顺序 将具有关联关系的对象排列在一起，如具有引用关系的对象或者同一数据结构中的相邻对象，
- 滑动顺序将对象滑动到堆的一端“挤出'垃圾,从而保持对象在堆中原有的分配顺序。
我们所了解的整理式回收器太多遵循任意顺序或者滑动顺序。任意顺序整理实现简单且执行速度快,特别是对于所有对象均大小相等的情况。但任意顺序整理很可能会将原本相邻的对象分散到不同的高速缓存行或者虚拟内存页中,从而降低赋值器空间局部，所有现代标记-整理回收器均使用滑动整理顺序，它不改变对象的相对排列顺序，因此不会影响赋值器局部性。复制式回收器甚至可以通过改变对象排布顺序的方式将对象与其父节点或者兄弟节点排列得更近，从而提升赋值器的局部性。近期的一些实验表明，由任意顺序整理导致的对象重排列会大幅降低应用程序的吞吐量。
整理算法可能会存在多种限制，任意顺序算法只能处理单一太小的对象,或者只能对不同大小的对象分别进行整理;整理过程需要两次甚至三次整堆遍历；对象头部可能需要一个额外的槽来保存迁移信息,这对于通用内存管理器来说是一个显著的额外开销。整理算法可能对指针有特定限乱，如指针的引用方向是什么?是否允许使用内部指针?我们将在第11章讨论这些问题。
本章我们将研究几种不同类型的整理算法。首先要介绍的是Edwards的双指针(-)回收算法[Saunders,l974],尽管该算法实现简单且执行速度快，但它打乱了堆中对象的原有布局。第二种整理式回收算法是一种广泛使用的滑动回收算法,即Lisp2算法。与双指针算法不同，该算法需要在每个对象头部增加一个额外的槽来保存转发地址,即对象移动的目标地址。第芒种整理算法是Jonker的引线整理算法,该算法可以在不引人额外空间开销的情况下实现对象的滑动整理，但它需要两次堆遍历过程，且每次遍历的开销都很大。本章所介绍的最后一种整理算法是单次遍历算法,它是一种现代的滑动回收算法，其执行速度快,且不需要在每个对象上引人额外的空间开销。该算法中的转发地址可以实时计算得出，所有整理式回收算法的执行都遵从如下范式。
4
标记-清扫回收的开销较低。但其可能受到内存碎片问题的困扰，在一个设计良好的系统中。垃圾回收通常只会占用整体执行时间的一小部。赋值器的执行开销格决定整个程序的性能，因此应当设法降低赋值器的开销，特别是应当尽量提升它的分配速度。标记-整理回收器可以根除碎片问题，而且支持极为快速的“阶跃指针'分配(见第7章)。但它需要多次堆遍历过程，进而显著增加了回收时间。本章将介绍第三种追踪式回收算法:半区赋值。回收器在复制过程中会迸行堆整理从而可以提升赋值器的分配速度，且回收过程只需对存活对象遍历一次。其最大的缺点在于，堆的可用空间降低了一半。
5
到目前为止，找们所介绍的垃圾回收算法都是间接式的，它们都需要从巳知的根集合出发对存活对象图进行遍历，进而才能确定所有的存活对象。本章将介绍最后一种基本回收算法:引用计效在引用计数算法中，对象的存活性可以通过引用关系的创建或删除直接判定，从而无须像追踪式回收器那徉先通过堆遍历找出所有的存活对象，然后再反向确定出未遍历到的垃圾对象。
引用计数算法所依赖的是一个十分简单的不变式:当且仅当指向某个对象的引用数大于零时,该对象才有可能是存活的，在引用计数算法中，每个对象都需要与一个引用计数相关联,这一计数通常保存在对象头部的某个槽中。算法5。1展示了最简单的引用计数实现,即当创建或者删除某一对象的引用时增加或者减少该对象的引用计数。Write方法用于增加新目标对象的引用计计数，同时减少旧目标对象的引用计数,即使对于局部变的更新也需如此。我们同时假设,在一个方法返回之前,赋值器会将所有局部变量中的引用设置为空。addReference方法实现对象引用计数的增加，相应地,de1eteReference实现引用计数的减少。需要注意的是，对引用计数的修改要遵循先增后减的顺序(算法5.1中的第9~l0行),否则当新对象和老对象相同。也就是src[i]=ref时,可能导致对象被过早回收。一旦某~对象的引用计数降至零(算法5.1中的第20行),便可以将其回收,同时减少其所有子节点的引用计数,这可能引发子节点递归式的回收。
算法5.1中的write方法是写屏障的一个例子，此处编译器在真正的指针写操作之外增加了一些简短的代码序列。我们将在后面章节看到，许多系统中的赋值器都需要执行一些额外的屏障操作。更确切地说，如果不希望回收器关注整个对象图中所有对象的存活性,则赋值器必须承担一定的工作。此类回收器可能会与赋值器并发执行:要么在赋值器的引用计数操作中立即执行,要么在另一个线程中异步地执行。另外,回收器也可能会以不同的频率来处理堆中不同区域的对象，例如分代式回收器。在这些情况下,赋值器必须引人一些额外的屏障操作来确保回收算法的正确性。
6
前面介绍了4种不同类型的垃圾回收器,本章将对它们进行更加详细的比较。我们将从两个不同方面进行考察:首先我们会确立一套标准来评价不同回收算法在不同场景下的优势与不足;然后再介绍追踪式回收算法和引用计数算法的抽象。我们将看到,虽然不同算法在表面上存在差别，但它们在更深层次上却存在着显著的相似性。
读者通常会问:究竟哪种垃圾回收器最好?但这一问题并不存在简单的答案。首先需要明确“最好”的定义是什么:是希望应用程序的吞吐最大还是希望回收的停顿时间最短?是希望空间使用率最，还是希望对这些参数进行综合考虑以达到整体上的平衡?其次,在不同的应用程序中,即使对于同一个评价标准，不同回收器的排名也可能有所不同。例如,通过对20种Java基准测试程序和6种不同的回收器进行研究发现对于任意一种回收器，都存在另一种更加合适的回收器可以将某个特定基准测试程序的执行速度提升至少15%。对于不同大小的可用堆回收器的性能也各不相同，如果可用堆空间更大，则程序通常执行得更优，但如果可用堆空间过大，则相关对象在空间上更加分散,程序的空间局部性更低，进而可能降低程序的性能。这些因素都使得问题的分析更加复杂。
9
垃圾回收器的主要目的是找到已经死亡的对象并回收它们所占用的空间。在对象数量较少的情况下,追踪式垃圾回收器(特别是复制式垃圾回收器)能够最高效地进行回收。但长寿对象的存在却会影响回收效率，因为回收器不是反复地对其进行标证、追踪,就是反复地把它们从一个半区复制到另一个半区。第3章提到,在标记-整理回收器中,长寿对象会积累在堆底,并且回收器通常会避免对这些底部的'沉积物'进行处理。虽然这一策略可以减少移动长寿对象的次数，但是回收器仍然需要对它们进行扫描，也需要对它们所包含的引用迸行更新。
分代垃圾回收是对上述算法的进一步改进与提升。在任何时候,分代垃圾回收算法都尽可能少地去处理长寿对象。弱分代假说告诉我们,大部分对象都在年轻时死亡,因此可以利用这一特性尽量提高回收效益(即回收所得到的空间)，同时减小回收开销。分代垃圾回收算法依照对象的寿命将其划分为不同的分代。同时将不同分代的对象置于堆中不同的区域，回收器会优先回收年轻代对象，并将其中寿命够长的对象提升到更老的一代。
大多数分代垃圾回收算法通过复制的方法来处理年轻代对象。如果被处理的分代中存活对象的数量足够少,则其标记/构造率会降低,即回收器在一次回收过程中所需要处理的数据与分配器在相邻两次回收之间所分配的数据量之间的比例较低。
全文共6224字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[12312]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
