垃圾收集算法的比较分析.pdfVIP

维普资讯 2005年第 11期 福 建 电 脑 垃圾收集算法的比较分析 徐剑峰 (上海师范大学上海 200234) 【摘 要】 本文主要比较和分析了垃圾收集器中常用的一些垃圾收集算法，并简要指出在实际应用中如何选择适 - 3的算法。 【关键词】 内存泄露；垃圾收集；垃圾收集算法 1 引言 减少内存块时，与之相关的一系列对象的引用计数值都必须进 1．1 内存泄露 行调整。这类实现不得不支付高昂的处理开销。㈣另一方面，对 目前大多数高级程序设计语言既能在栈(stack)_L也能在堆 于生命期很短的对象，例如过程调用中的参数传递 ，会频繁地进 (heap)分配内存。栈上的内存一般是静态分配，而且已经完全 行计数值的增加和减小的操作。此外，引用计数要 占用相当数量 靠系统 自动释放；而堆上的内存一般是动态分配。在传统的高级 的内存空间也影响了效率。 程序语言中 (像 C和 C++语言)往往需要程序员为 内存 的分配和 (2)更重要的是 ，引用计数算法无法正确释放循环引用的内 释放进行编码。 存块。彼此直接或者间接引用的几个对象(如循环链接的列表或 若程序为某个对象分配了内存．但对象使用完之后却没有 者包含指向父节点的反向指针的树)当变为不可到达时，它们的 执行相应的释放操作 ，就会导致所 占用的内存空间无法释放．直 引用计数值并未减为 0。于是它们成为无法回收的内存垃圾。 到程序终止。我们称这种无法回收的现象为 内存泄露(memory 2．2标记一清除 (Mark-Sweep)算法 leaJ【)。若程序是一个不问断运行的应用系统，产生 内存泄露的 标记一清除算法的执行过程分为 “标记”和 “清除”两大阶段。 代码被反复执行，那么系统内存会被这种程序逐步蚕食殆尽。从 第一个阶段为标记阶段。每个对象使用一个二进制位作为标记 而导致应用系统崩溃。另一方面。对于一个大型的应用系统。代 位，垃圾收集器通过对所有对象进行一次全局遍历来标记所有 码量非常大，难免会出现 内存泄露，而这是一种很难发现和纠正 活动的对象。当遍历完成后那些未被标记的对象就是垃圾对象。 的问题。因此．内存泄露问题成为困扰编程人员的难题。 第二个阶段为清除阶段，回收垃圾对象 占用的内存，同时清除活 1．2 垃圾收集 动对象的标记位。为下一次垃圾收集作好准备。 为解决内存泄露问题，像Java、C撑等现代高级语言大多都 与引用计数算法相 比，标记一清除算法拥有两个优点，第一， 提供了垃圾收集 (GarbageCollection。GC)机制。程序员仍然需要 它可以非常 自然地处理循环引用结构，不需要采取特别的措施： 申请动态分配内存。但他不再需要决定何时释放 内存了：因为它 第二，不需要监测每一次内存分配和指针操作，而只要在标记阶 会被 自动回收。这就是垃圾收集的精确定义 —— 动态分配 内存 段中跟踪即可 。从而减少了开销。 的自动管理机制。[I]自动 内存管理机制以损失性能为代价来限 在另一方面，标记一清除算法也存在缺陷：(1)在垃圾收集器 制复杂性。省去了程序员 自己管理 内存的麻烦和危险，也避免了 运行时用户程序的运行必须暂停。而且暂停可能会很长，在清除 内存管理的错误 。 阶段整个堆都是可访 问的。这对于可能有页面交换的堆 的虚拟 通常。垃圾收集算法一般要做两件事情：(1)垃圾检测：区分 内存系统有非常负面的性能影响。m(2)容易使堆产生碎片，即 垃圾对