An Investigation into Automatic Dynamic Memory Management Strategies using Compacting Collection
关于使用整理收集法的自动动态内存管理策略调研
本文自一篇关于GC的论文-Daniel John
Frampton Department of Computer Science Australian National University
摘要
本论文描述了在Java内存管理工具集（JMTk）中几个整理收集器的设计，实现和性能特征。
整理收集器是一类用于多个生产运行时环境的收集器，包括微软CLR(通用语言运行时环境)和IBM JRE。整理策略相关开发对JMTk工具集有不小的贡献，提供了一个与其他收集器的对比基础。
这些工作不仅仅作为对这类收集器的初步调查，还有我们期望通过增加JMTk和类似RVM支持的操作集，能够促使新的收集器实现并与之对比。即使执行整理算法的成本比较高，但是它能够减少内存碎片。（这是标记-清理收集器不具备的）
引言
现在的面向对象语言比如C# 【11】和Java 【15】变得在业界越来越重要，还有很多主要角色随之跟进，包括Sun和IBM的Java和微软的.Net,很明显它们还要持续重要很长一段时间。
这些语言要求运行时环境，比如微软CLR【12】和Sun的Hotspot JVM 【17】，这些运行时环境负责承担以往程序员需要承担的动态内存的管理任务。
即使有很多因素影响整体性能，但是GC成本还是相当重要的【5】。
整理式收集技术被用于多个生产环境虚拟机-微软CLR和IBM的Java垃圾收集器。即使是业界较为青睐的技术，整理收集在流性的内存管理研究平台JMTk缺席了很长一段时间。
Blackburn,Chen和McKinley【5】引入一种多种全堆收集器包括标记-整理和复制算法收集器间的详细的对比方法。在所有条件都相同的情况下，对比单虚拟机下的性能，包括了许多可重用的组件，这为各种技术的性能对比提供了坚实的基础。理解整理收集方法的成本和优点是本文的重点。
添加整理收集支持到研究平台上允许对于这些GC技术进行详细的对比分析，另外在JMTk和Jikes RVM中允许此类算法使得全新种类收集器引入成为可能。
要哭了，为啥一直在扯皮
本文探讨了几个整理算法，包括使用bump pointer和空闲列表分配技术的整理式收集器。
分析中包括了整理式收集器和其他全堆收集器的对比。对于标记-整理式/标记-清除式混合收集器的最佳整理频率也做了一些研究。
自动动态内存管理
所有程序都需要内存，内存能够静态分配，比如编译期已知大小的全局数据结构，
栈式分配，数据的生命周期取决于其在方法调用栈的位置。内存当然也能够被程序动态分配，在这种情况下，对象的声明周期就不确定了。
动态内存分配的区域称为堆。通常在堆内分配或回收内存都是在程序中显示声明的。一个很平常的例子就是C的malloc和free。
在很多情况下，比如程序处理很复杂的数据结构，要求程序员手动管理内存是不合理的【14】。因为这个问题非常普遍，因此开发一个程序自动执行这些任务是很自然的想法。这个自动化过程首先识别出无用的垃圾然后回收这些空间，这些自动化过程称为垃圾收集。
内存碎片
当堆中的数据分配情况使得即使内存可用大小足够，依然无法为对象分配空间。这表示有内存碎片现象。图1帮你理解内部碎片和外部碎片。
内部碎片是当为对象分配内存时，需要为它分配额外的内存空间（图中格子A）。
外部碎片出现是因为没有一块足够大的连续空间来分配（比如分配数组），即使可用内存空间大小满足条件。
整理式算法就是减少内存碎片的一种算法。
局部性原理
对象的内存布局对于程序的整体性能有很大的影响【23】。局部性在多个方面影响程序性能，智能的分配机制将局部性原理考虑到设计之中。如果应用活跃地处理一堆对象，而且它们在内存中离地很近，那么这种应用会比那些在内存中较远分布于堆中的程序性能要好。局部性原理表现出较高的缓存命中率和较低的缺页率。
很多因素影响这局部性，包括程序行为和内存分配策略，因此很多情况下良好局部性现象靠运气。但是，有几个规律可以帮助程序在大多数情况下提高局部性。包括将相同大小或者年龄相同的对象分配到一块，将巨型对象分配到一块，还有一些相互引用的对象。
分配技术
本部分介绍两个基本的分配技术：
- 冲突检测指针
最简单的分配方式就是bump pointer(冲突检测指针)。本质上就是一个内存游标，划过可用内存区域来满足内存分配需求。即使这种操作非常快，但是它依赖于特定的垃圾器。
- 空闲列表
空闲列表本质上是一个空闲单元格组成的链式结构，这些单元格记录那些内存区域是可用的。回到图1你可以看到C，E就是空闲列表中的单元格。当单元格代表的内存被分配出去，这个单元格就会从空闲列表中移除。即使直觉上很简单的概念，这个基础想法衍生出很多变种，很多长篇累牍地对它进行讨论，最有名就是Wilson 等人【22】.好的分配策略甚至能够在实际地程序中做到零碎片【13】。
可以管理多种空闲列表，依据是类或者对象大小。这样地收集器叫分离式空闲列表。
分离式空闲列表如果按对象大小的话，总是使用最先匹配比较好一点。
当使用分离式空闲列表，内存碎片会变得更严重【14，22】。如果一个程序分配大量对象，然后全部回收，之后不再分配任何的那种对象，那种对象的空闲列表会成为浪费的内存。如果分离式空闲列表是基于基础块的二级分配，那么这种分配器叫做二级分配器【14，7】。JMTk包含这样一个分配器。
内存回收技术
所有垃圾回收机制要求满足两个基本原则，和两种在本章开始探讨的基本内存分配错误紧密相关，它们是：
-
安全
没有任何对象的内存被回收，除非执行程序不再持有其任何引用。 -
完备性
所有执行程序不再引用的对象其内存空间最终会被回收。
- 跟踪收集
运行时环境中有一些对象是明显永久存活，这些对象包括被栈和硬件寄存器引用的对象，存储在静态字段的对象，还有运行时直接引用的对象，这些对象组成的集合称为根集合。
跟踪垃圾收集以遍历从根到对象的引用组成的图的方式工作。任何可以被引用到的对象被认为是存活的，不可以被遍历到的认为是垃圾。
跟踪收集器的例子是标记-清除和标记-扫描收集器【14，16】。标记-清除收集器首先遍历对象图，每当遍历到一个对象，就将此对象标记为存活------这是标记阶段。然后它回收所有垃圾----这是清除阶段。
当标记独享的时候，存储对象标记信息是必然的。最简单的方式是包括一个标记位在对象头中。
- 复制收集器
复制收集【14】是一种跟踪收集办法，只是当遍历的时候会将才能活的对象复制到一个不同的区域中。通常，这些内存的这些不同区域会标记出从哪到哪。前向指针存储在每个对象中，因此任何引用此对象的对象会更新引用。简单的复制收集器被称为半区收集器【10】。
复制收集方法的一个重要特点是GC成本和存活对象的数量密切相关。而不是堆的尺寸，因为只有存活的对象才会被处理。
复制算法也允许使用简单的冲突检测指针分配机制，这样可以提高内存分配操作的性能。但是，复制收集器需要保留复制区空间，复制区空间能够容忍所有对象100%存活的可能性。
整理收集
整理收集器目的在于将整个堆划分两块连续的区域：一个区域保存存活的对象数据，另一个区域是空闲可分配的空间。
滑动整理算法【18，19，14】实际上将全部垃圾移除然后在内存空间中滑动存活对象。
一个这样的算法例子比如Lisp 2写的算法【14】需要几次扫描堆：
标记：对象通过像标记-整理收集算法那样通过使用传递闭包方式被标记
计算：计算每个对象的前向指针通过从内存中由低位向高位移动。
更新引用：再一次迭代寻找所有指针字段并更新引用，使得存储在对象的前向指针中引用更新到最新位置。
移动对象：最后一次迭代将所有对象复制到目标区域。
滑动整理收集方法的效果在图2，对象C和F被识别位垃圾，所有D和E滑动到内存低位形成连续的块：A,B,D.
.
权衡
很明显没有任何一个最好的内存管理策略【5】。吞吐率和响应性的权衡是很重要的。吞吐率和有效率的收集垃圾有关，响应性和应用在收集发生时的停顿时长有关。一些应用比如实时性程序需要保证响应性，愿意为这个保证承担所有成本。据说，有一项新研究试图开发一个兼具吞吐率和响应性的收集算法【6】。
另外一个经典权衡是时间空间权衡。最极端的例子是不回收任何内存，这种收集器给定足够大的堆，只能在程序显示出很差的局部性时才会显得性能低下。
=------待续-----困--------