引用计数垃圾收集方法综述

贺 建 立

(安庆师范学院 计算机与信息学院，安徽 安庆 246133)

贺 建 立

(安庆师范学院 计算机与信息学院，安徽 安庆 246133)

基于两个C语言程序引出引用计数垃圾收集的基本方法、存在的效率和回收环垃圾问题，归纳了引用计数自动回收内存方法在改进效率、回收环垃圾、并发收集方面的研究进展及存在的问题和相应的解决方法，对改进性能和回收环垃圾的方法进行了分类和分析，阐述了并发收集的重要设计策略，并对典型的引用计数垃圾收集器进行了分析和比较。

引用计数；内存管理；垃圾收集；环垃圾 DOI：10.13757/j.cnki.cn34-1150/n.2015.04.011

内存自动管理是快速开发大型可靠软件的重要工具，垃圾收集方法对软件运行时性能会产生重要影响，实现高效的内存管理和垃圾收集是当前系统软件设计的目标之一。J.Mccartihy和G.E.Collins于1960年先后提出了跟踪[1]和引用计数[2]垃圾收集方法。跟踪方法从根集开始传递闭包的遍历对象图，回收没有被跟踪到的对象。引用计数方法记录对象被引用的次数，当对象的引用计数为零时，表明对象是不可达的，可以被回收。简单引用计数方法因频繁地更新对象的引用计数比跟踪方法多损失30%的性能[3]，且不能回收带环的数据对象。五十多年来，由于引用计数方法存在明显缺陷，跟踪垃圾收集器及其变种(标记清扫、半空间拷贝和标记压缩)得到了更为广泛的发展与应用。

引用计数垃圾收集方法相对跟踪方法具备一些明显优势：(1)引用计数为零的垃圾对象及时地被回收；(2)收集过程是增量式的，避免了集中式收集所引发的进程长时间暂停；(3)使用对象局部信息，无需搜索整个堆空间；(4)实现简单，无需运行时系统的支持，避免了从全局数据区、栈和寄存器开始列举在堆空间中的指针[4]。脚本语言AppleScript、Perl和 PHP的设计者选用引用计数方法自动回收内存，在处理带环数据对象方面：AppleScript禁止程序员使用带环的数据结构，Perl忽略环垃圾[5]，PHP以跟踪方法收集环垃圾。

因性能损失和不完全性问题限制了引用计数垃圾收集方法的应用范围。对于引用计数的两大缺陷，人们提出了各种处理带环数据结构的算法[6-12]，及并发的纯引用计数垃圾收集器[14-15]，30%的性能差距已抹平[3,13-20]。随着64位体系结构的盛行，进程的堆地址空间将会变的非常庞大。跟踪收集器需要遍历堆中所有活跃对象，而引用计数收集器不依赖于活跃对象所占的空间。引用计数方法已经被一些系统采用，包括编程语言、应用程序、操作系统文件管理和C++函数库[21]。当前的研究进展与计算环境的变化使得引用计数垃圾收集方法具备更为广阔的应用前景。

1 引用计数收集

简单的引用计数方法因频繁地更新执行程序中对象的引用计数而损失了程序性能。如下代码所示：

1 #include

2 typedef struct objclass{

3 int ref;

4 struct objclass *slot;

5 }objtype;

6 void foo(objtype *pobj){}

7 void main()

8 {

9 objtype *p1 = malloc(sizeof(objtype)); //create O1

10 objtype *p2 = malloc(sizeof(objtype)); //create O2

11 foo(p1);

12 p2->slot = p1;

13 p2 = p1;

14 }

1 baseClass * operator=(baseClass *p)

2 {

3 if(addr != 0)

4 addr->ref--;

5 addr = p;

6 p->ref++;

7 return p;

8 }

代码上部分是在Linux操作系统中使用G++编译通过的C语言程序源代码，下部分是执行地址赋值操作时垃圾收集系统执行的代码。其中程序源代码p1和p2是栈变量，9、10行分别在堆中创建了对象O1和O2，11行调用foo函数时传入p1参数，12行为对象O2的地址槽赋值，13行改变栈变量p2的值。程序执行结束后O1的引用计数更新了5次，O2的引用计数更新了2次。另外，多线程环境中还要保证指针操作的原子性，以防止过早的回收对象。代码的下部分在多线程环境中执行是不安全的，需要加锁保护。当前的研究从减少引用计数更新的次数、避免并发程序的锁竞争、改进堆空间中对象布局这3个方面改善效率。

1.1 减少引用计数更新

Deutsch等人[13]提出了推迟引用计数，忽略程序中寄存器和栈内的指针变化，仅在堆中对象的地址槽改变时才更新引用计数。收集器定期地将寄存器和栈内的指针所指对象列入根集，堆引用计数为零的对象存入零引用计数表(ZCT)中，回收在ZCT中且不在根集里的对象。这种策略能将上述执行程序中对象O1和O2的引用计数更新次数分别减少为1次和0次。Levanoni等人[16-17]的并发收集器采用了推迟引用计数策略，而且还合并了大量的堆引用计数。执行程序的堆指针变化时，将对象槽的地址和该槽所指对象的地址存入缓存区，每个对象槽以脏标记保证周期内在缓存区中存入唯一的对象指针。收集线程周期性地读取缓存区，将对象槽上一个周期所指的对象引用计数减1，将对象槽当前周期内所指的对象引用计数加1。假定O1.slot当前值为&O0，程序在收集周期内为对象O1.slot执行了n次地址赋值：O1.slot=&O2，O1.slot =&O3，… O1.slot=&On。合并策略仅需减少对象O0的引用计数一次和增加对象On的引用计数一次，从而将引用计数的更新次数从2n次降低为2次。

分代垃圾收集[22]假设大部分对象是短生命期的，对象按生命期长短划分成新生代和年长代，新生代对象的指针变化快，年长代对象的指针变化慢。文献[18-19]以跟踪收集器回收新生代对象，以引用计数回收年长代对象，跟踪收集器仅跟踪新生代的对象，减少了跟踪范围，年长代对象指针变化较少，引用计数的更新也相应变少。另外，在编译期通过特定的分析算法也能合并掉一些冗余的引用计数更新操作，例如增加了一个对象的引用计数，紧接着减少该对象的引用计数，显然这两次操作可以被合并掉[23]。文献[24]通过分析地址赋值语句间的包含关系，在编译期优化了部分由栈变量赋值引发的对象引用计数更新。

1.2 避免锁竞争

文献[25]在对象槽赋值时将指针的原值和新值存入同一个缓存区，多个线程共享该缓存区，以互斥锁保护缓存区和待更新的地址槽。互斥锁同步会引发死锁、长延迟和优先级反转[26]，非阻塞同步能够避免这些问题。非阻塞同步由比较交换(CAS)机器指令实现，CAS是原子指令[27]。直接的方法至少需要使用3条CAS指令，以更新对象槽和分别更新地址槽所指的新对象与原对象的引用计数。文献[14-15]在减少同步操作方面取得了较大突破，将需要增加与需要减少引用计数的对象地址分别存入不同的缓存区，仅在更新地址槽时使用了一条CAS指令。

文献[16-17]在修改对象槽和更新引用计数时完全避免了原子指令和锁竞争，从3个方面保证了并发程序的正确性：(1)每个线程拥有自己的局部缓存区，以存储线程中变化了的地址槽原值和对象槽的地址；(2)每个地址槽都有一个脏标记，以确保收集周期内缓存区中存入正确的对象槽的原值；(3)写屏障代码依序执行：①地址槽信息存入缓存区，②设置对象槽脏标记，③在对象槽中设置新值。这些措施会导致在收集周期内同一个对象槽信息存入不同线程的局部缓存区中，收集器在调整对象引用计数时要剔除缓存区中多余的副本，以防止错误地减少地址槽原值对象的引用计数。

1.3 改进对象布局

前述方法使得引用计数收集器的性能与全局堆跟踪收集器性能一致，但与性能最好的分代收集器还存在10%的性能差距[20]，文献[20-28]的研究结果表明，通过改进堆空间中对象布局可以弥补这一差距。

内存管理系统分为内存分配、活跃对象识别和回收垃圾对象3个方面。空闲块链表的堆空间组织方式导致了高速缓存的局部性差，且增加了分配和回收内存块的执行时间。标记区域(Mark-Region)的内存分配方式通过改变前移(bump)指针将程序需要的内存块分配在连续空间，可批量地进行回收与初始化[29]。Immix[20]是标记区域收集器，区域分为行和块两个等级，块由几行构成，对象可以跨行分配但不能跨块分配，按对象、行和块3种粒度回收空间。

1.4 回收环

McBeth[30]指出了引用计数方法不能回收带环的数据结构。如下所示代码中当执行到11行时对象O1和O2形成了环，这时O1和O2的引用计数都为2；当执行到13行时对象O1和O2的引用计数都为1，此时对象O1和O2都是不可达的，但对象的引用计数都不为零，故对象不可被回收。

1 #include

2 typedef struct objclass{

3 int ref;

4 struct objclass *slot;

5 }objtype;

6 void main()

7 {

8 objtype *p1 = malloc(sizeof(objtype)); //create O1

9 objtype *p2 = malloc(sizeof(objtype)); //create O2

10 p1->slot = &*p2;

11 p2->slot = &*p1;

12 p2 = 0;

13 p1 = 0;

14 }

存在三种解决环问题的方法：(1)特定的编程习俗，例如，文献[31]要求程序员显式地提供信息以发现环。(2)借助很少运行的跟踪收集器全局搜索堆空间以专门回收环垃圾。(3)利用特定的算法局部跟踪堆对象，尝试删除和指针着色是两种不同风格的局部跟踪算法。

1.4.1 尝试删除

尝试删除算法[7]基于两个基本观察：(1)只有引用计数正在减少且其结果值大于零时才可能形成垃圾环；(2)垃圾环中引用计数全部是内部的，当内部引用计数减掉后，环内对象的引用计数全部为零。算法在进行指针删除操作时，当指针所指对象的引用计数大于零时，从该对象(根)开始遍历子图。算法分为3个阶段：阶段1(标记红色)，遍历子图，减少内部引用计数，访问过的对象标记为红色；阶段2(扫描)，再次遍历子图，当某个节点引用计数大于零时，则从该节点遍历子图，恢复上一个阶段减少的引用计数，并将该子图中的对象标记为绿色，其他对象标记为蓝色；阶段3(回收蓝色)，回收被标记为蓝色的对象。

文献[8]将根对象存入队列，随着程序的执行，一些根对象的引用计数可能减为零或增加了，这些根对象可以从队列中删除，从而减少了遍历子图的个数。文献[9]使用特定的数据结构(Jump-stack)消除了扫描操作(阶段2)。文献[15]从3个方面改进了文献[8]的效率：类加载器排除了一些固有无环的对象；为对象加上标记，避免队列中的对象再次进入队列；通过分析根对象的传递闭包关系减少了子图的个数，将算法复杂性限制在子图的边数N与节点数V之和。

1.4.2 指针着色

文献[6]将指针分为强指针和弱指针。强指针不形成环，可以使用标准的算法进行计数；弱指针用于关闭环。对象包含强指针和弱指针引用计数。算法维持两个不变式：强指针不形成环；对象图中每个对象从根集开始至少有一条由强指针形成的路径。对象图的构造由指针拷贝和指针删除操作实现[11]。

指针着色算法仅在指针删除操作中当强指针引用计数为零且弱指针引用计数为正数时才需要遍历子图，减少了访问对象的次数，但需要增加额外的空间描述指针的状态。文献[32]指出了文献[6]的算法在特殊情况下过早地回收对象。当删除对象的最后一个强指针且对象还存在弱指针时，文献[32]从该对象重新开始收集，纠正了文献[6]的问题，但带来了潜在非终结问题。文献[11]的算法引入两种标记以防止无限地查找和保障每次查找终结，算法复杂性是指数阶的。文献[12]在文献[6,11,32]研究基础上引入了第3种类型的指针(Phantom)，使算法复杂性降为线性的。

1.5 其他问题

对象头中存储引用计数带来了空间消耗和性能损失，一个字大小空间的引用计数损失了程序2.5%的性能[3]。大部分对象的引用计数非常小，文献[3]指出引用计数小于6的对象占99%。对象头中的一个字可以取出几位作为引用计数，其他位可作为别的用途。当引用计数溢出时有两种处理策略：(1)哈希表方法，引用计数溢出时在哈希表内增加一项，每个表项占有两个字大小的空间，分别用于存储对象键值及该对象的引用计数。(2)延迟(stuck)方法，引用计数溢出时停止计数，由跟踪收集器统计和恢复对象的引用计数。

程序中若存在一组对象形成长的单链表，当链表的第一个节点的引用计数为零时，需要回收整个单链表，这会引发程序较长的暂停时间，存在两种解决方案：(1)限制每个收集周期回收对象的个数，超出的对象留给下一个收集周期回收。(2)并发收集，收集线程与工作程序并发执行。

综合本节内容，引用计数垃圾收集方法目前存在的问题和相应的解决办法归纳如表1。

表1 引用计数垃圾收集方法存在问题与解决办法

2 并发收集

并发收集器[15-17,25,33-38]与执行程序并发地工作，以更好地利用多处理器系统。目前大多数并发收集器在发起和停止收集工作时无需同时暂停所有工作线程。在线(On-the-fly)收集器不同时停止所有工作线程，每个工作线程按自身的步调与收集器通过一种软握手[36-37]机制协作。

2.1 滑动视图

在对象槽发生变化时，通过写屏障将对象槽的地址和槽的原值存入线程局部缓存中，每个对象槽有一个相应的脏标记位[16-17]。文献首先描述了快照算法(snapshot algorithm)[39]，由于算法在发起收集工作时需要冻结所有的工作线程，依次读取每个线程的缓存区和线程栈内的地址后才唤醒工作线程，因此，快照算法引发较长的暂停时间且不能较好地利用处理器资源。

为避免长时间的暂停和可伸缩性问题，文献[16-17]提出了滑动视图算法。算法在读取缓存区和线程栈内指针时仅冻结一个工作线程，这种增量方式通过侦听(snoop)机制和增加软握手次数保证了算法的正确性。收集周期开始时设置每个工作线程的侦听标记为真，收集周期结束时侦听标记设为假，工作线程的写屏障代码判断侦听标记是否为真，若为真值则将目标对象并入线程局部集合中，引用计数为零且不在根集和局部集合中的对象被回收。侦听机制产生少量的浮动垃圾，这些对象留给下一个收集周期回收。

对象槽的原值记录在局部缓存中，收集线程减少对象槽原值所指对象的引用计数；当槽的脏标记为假时，收集器直接读取槽的新值，增加对象的引用计数，若槽的脏标记为真，收集器需要再次从工作线程的局部缓存中获得待更新引用计数的对象。滑动视图算法进行4次软握手，第1次握手获取工作线程的局部缓存，收集器异步地清除对象槽的脏标记；第2次握手再次读取局部缓存，以设置缓存区中被异步清除的脏标记；第3次握手确保工作线程发现恢复的脏标记；第4次握手获取根集。

2.2 衍生收集器

滑动视图算法衍生了一些高性能短暂停的并发垃圾收集器[19,40-42]，文献[41]基于滑动视图算法实现了在线的全局跟踪收集器。并发收集器通常以写屏障保护工作线程修改的对象，以防止过早地回收可达对象。文献[41]的写屏障代码从3个方面提高了工作程序的效率：收集器在活跃时修改的对象才存入缓存区；修改的对象只有发生在开始收集之后进入跟踪阶段之前才需要存入缓存区；修改的对象仅需存入缓存区一次。每个对象有一个字大小空间的脏标记，当对象的指针存入缓存区时，脏标记指向缓存区中对象指针存入的位置。

文献[42]在滑动视图算法基础上提出引用计数结合跟踪收集的方法，研究了引用计数和分代收集方法组合的3种设计方案，其中引用计数收集年长一代且跟踪方法收集年轻一代的方法获得了最好的性能。分代收集器将堆空间划分为若干部分，通过预留一位指示对象是“新的”或是“老的”，从而在逻辑上将堆分为两代。跟踪方法收集年轻一代避免了在跟踪和清扫阶段访问老一代对象，缩小了问题空间。

文献[15]实现了第一个并发的环收集算法，算法分为两个阶段：第一个阶段记录潜在的环垃圾，由于工作线程与收集线程并发地执行，收集过程中工作线程可能破坏了对象图；第二个阶段在下一个收集周期证实这些潜在的环垃圾能否安全回收，算法存在不完全性[15,42]和低效率[12,42]的缺陷。文献[42]在滑动视图和尝试删除算法的基础上解决了这两个问题，算法结合了分代收集方法[19,42]，进一步减少了需要被跟踪的候选环对象。

3 收集器比较

性能低和不能回收环是引用计数方法面临的两个主要问题，表2和表3从性能改善、回收环、引用计数溢出、是否并发、写屏障是否存在锁竞争和对象是否移动等6个方面对产生重要影响的引用计数收集器进行比较，其中少数文献忽略对引用计数存储位数或溢出处理方法的描述，少量文献没有给出与对象槽更新相应的写屏障代码，未命名的收集器以文献第一作者名表示。对象移动压缩堆空间，减少分配对象操作的开销，但并发收集移动对象会引起较大的代价，大部分收集器在并发收集时不移动对象[43]。

文献[25]描述了Modula-2+编程语言的垃圾收集器，收集器识别线程栈内的指针是保守式的[44]，这消除了收集器对编译器的依赖。保守式的指针识别方法从来不过早地回收对象，保证了程序的正确性，但会引起非常少量的内存泄漏。

表2 收集器处理主要问题比较

从表3可以看出，不同收集器采用不同位数存储引用计数，根据文献[3]的研究结果，最大引用计数为1的对象占68.2%，最大引用计数为3的对象占95.4%，最大引用计数为6的对象占99%。引用计数溢出时延迟计数和哈希表被采用的机会大致相当，延迟计数的性能优于哈希表，延迟计数总体节约了1%的时间，节约了收集器13%的时间[3]。

表3 收集器处理其他问题比较

4 结束语

本文综述了引用计数自动回收内存方法存在的问题与解决的方法，对当前取得的研究进展进行了归纳与分析。将改进效率的方法归纳为减少引用计数更新、避免锁竞争和改进对象布局等3类，将回收环垃圾方法分为尝试删除和指针着色两类；介绍了如何利用一个字大小的引用计数空间和解决偶尔的长暂停问题；阐述了并发收集方法的研究成果。对典型的引用计数垃圾收集器进行了分析比较，在减少引用计数更新方面，推迟的方法被所有收集器采用，结合分代与改进对象布局的方法是最近出现的研究趋势。尝试删除的局部跟踪算法被一些收集器采用；而可靠的指针着色回收环垃圾算法的复杂性是指数阶的，直到2014年的ISMM国际会议上发表了线性复杂性的、并发的算法。但指针着色算法能否被采用仍然面临着挑战，程序中存在着大量的指针，为每个指针增加额外的空间以描述指针的状态，这显然有待商榷。

[1]J. Mccarthy. Recursive functions of symbolic expressions and their computation by machine[J]. Communications of the ACM, 1960, 3(4): 184-195.

[2] G. E. Collins. A method for overlapping and erasure of lists[J]. Communications of the ACM, 1960, 3(12): 655-657.

[3] R. Shahriyar, S. M. Blackburn, D. Frampton. Down for the count? Getting reference counting back in the ring[C].Proceedings of the 2012 International Symposium on Memory Management，New York：ACM, 2012：73-84.

[4] R. Jones, R. Lins. Garbage collection: Algorithms for Automatic Dynamic Memory Management[M].New York: John Wiley & Sons, Inc., 1996: 43-72.

[5] I. Jibaja, S. M. Blackburn, M.R.Haghighat, et al.. Deferred Gratification:Engineering for high performance garbage collection from the get go[C]. ACM SIGPLAN workshop on memory systems performance and correctness,New York：ACM, 2011：58-65.

[6] D. R. Brownbridge. Cyclic reference counting for combinator machines[C].Conference on functional programming languages and computer architecture，Berlin：Springer, 1985：273-288.

[7] A. D. Martinez ,R. Wachenchauzer, R. D. Lins. Cyclic reference counting with local mark-scan[J].Information Processing Letters, 1990,34(1):31-35.

[8] R. D. Lins. Cyclic reference counting with lazy mark-scan[J].Information Processing Letters, 1992,44(4):215-220.

[9] R. D. Lins. An efficient algorithm for cyclic reference counting[J].Information Processing Letters, 2002,83(3):145-150.

[10] R. D. Lins. Cyclic reference counting[J]. Information Processing Letters, 2008,109(1):71-78.

[11] E.J.H. Pepels, M.C.J.D.V. Eekelen,M.J.Plasmeijer.A cyclic reference counting algorithm and Its proof [R].Nijmegen: Department of Informatics, Faculty of Science, University of Nijmegen, 1988.

[12] S. R. Brandt, H. Krishnan, G. Sharma, et al.. Concurrent parallel garbage collection in linear time[C].Proceedings of the 2014 international symposium on memory management，New York：ACM, 2014：47-58.

[13] L. P. Deutsch, D. G. Bobrow.An efficient,incremental,automatic garbage collector[J].Communications of the ACM, 1976, 19(9): 522-526.

[14] D. F. Bacon, C. R. Attanasio, H. B. Lee, et al..Java without the coffee breaks: a nonintrusive multiprocessor garbage collector[C].ACM conference on programming language design and implementation，New York：ACM, 2001：92-103.

[15] D. F. Bacon, V. T. Rajan. Concurrent cycle collection in reference counted systems[C].European conference on object-oriented programming, Berlin: Springer Berlin Heidelberg, 2001：207-235.

[16] Y. Levanoni, E. Petrank.An on-the-fly reference counting garbage collector for java[C].ACM conference on object-oriented programming systems,languages, and applications,New York：ACM, 2001：367-380.

[17] Y. Levanoni, E. Petrank. An on-the-fly reference-counting garbage collector for java[J]. ACM transactions on programming languages and systems, 2006, 28(1):1-69.

[18] S. M. Blackburn, K. S. Mckinley. Ulterior reference counting: Fast garbage collection without a long wait[C].ACM conference on object-oriented programming systems, languages, and applications, New York：ACM, 2003：344-358.

[19] H. Paz, E. Petrank, S. M. Blackburn.Age-oriented concurrent garbage collection[C].International conference on compiler construction，Berlin：Springer, 2005: 121-136.

[20] R. Shahriyar, S. M. Blackburn, Yang Xi, et al.. Taking off the gloves with reference counting immix[C].ACM conference on object-oriented programming systems, languages, and spplications, New York：ACM, 2013：93-110.

[21] R. Jones, A. Hosking, J. E. B. Moss. The Harbage Vollection Handbook: the Art of Automatic Memory Management[M].Boca Raton: CRC Press, 2011：57-74.

[22] H. Lieberman, C. Hewitt. A real-time garbage collector based on the lifetimes of objects[J].Communications of the ACM, 1983,26(6):419-429.

[23] D. Frampton. Garbage Collection and the Case for High-level Low-level Programming [D].Canberra：Australian National University, 2010.

[24] P. G. Joisha. Compiler optimizations for nondeferred reference:Counting garbage collection[C].Proceedings of the 5th international symposium on memory management, New York：ACM, 2006：150-161.

[25] J. Detreville. Experience with concurrent garbage collectors for modula-2+[R]. Palo Alto, CA: DEC Systems Research Center, 1990.

[26] B. W. Lampson, D. R.David. Experiences with processes and monitors in mesa[J]. Communications of the ACM, 1980, 23(2):105-117.

[27] M. Greenwald.Non-blocking Synchronization and System Design [D]. California：Stanford University, 1999.

[28] S. M. Blackburn, K. S. Mckinley. Immix: A mark-region garbage collector with space efficiency, fast collection, and mutator locality[C].ACM conference on programming language design and implementation，New York：ACM, 2008：22-32.

[29] Yang Xi, S. M. Blackburn, D. Frampton.Why nothing matters: The impact of zeroing[C].ACM conference on object-oriented programming systems, languages, and applications，New York：ACM, 2011：307-324.

[30] J. H. Mcbeth. Letters to the editor: on the reference counter method[J]. Communications of the ACM, 1963, 6(9):575-575.

[31] D. G. Bobrow. Managing re-entrant structures using reference counts[J]. ACM Transactions on Programming Languages and Systems, 1980,2(3):269-273.

[32] J. Salkild. Implementation and Analysis of Two Reference Counting Algorithm [D].London：University College,1987.

[33] H. G. Baker. List processing in real time on a serial computer[J]. Communications of the ACM, 1978,21(4):280-294.

[34] A. W. Appel, J. R. Ellis, Li Kai. Real-time concurrent collection on stock multiprocessors[J]. ACM SIGPLAN Notices, 1988, 23(7):11-20.

[35] H. J. Boehm, A. J. Demers, S. Shenker. Mostly parallel garbage collection[J]. ACM SIGPLAN Notices, 1991, 26(6):157-164.

[36] D. Doligez, G. Gonthier. Portable unobtrusive garbage collection for multiprocessor systems[C].Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on principles of programming languages，New York：ACM, 1994：70-83.

[37] D. Doligez, G. Gonthier.A concurrent generational garbage collector for a multi-threaded implementation of ML[C].Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on principles of programming languages，New York：ACM, 1993：113-123.

[38] T. Printezis, D. Detlefs. A generational mostly-concurrent garbage collector[C].Proceedings of the 2nd international symposium on memory management，New York：ACM, 2000：143-154.

[39] T. Yuasa. Real-time garbage collection on general-purpose machines[J]. Journal of Systems and Software, 1990,11(3):181-198.

[40] H. Azatchi, Y. Levanoni, H. Paz, et al.. An on-the-fly mark and sweep garbage collector based on sliding views[C].Proceedings of the 18th annual ACM SIGPLAN conference on object-oriented programming, systems, languages, and applications，New York：ACM, 2003：269-281.

[41] H. Paz, E. Petrank, D. F. Bacon, et al.. An efficient on-the-fly cycle collection[C].Proceedings of the 14th international conference on compiler construction，Berlin：Springer, 2005：156-171.

[42] H. Azatchi, E. Petrank. Integrating generations with advanced reference counting garbage collectors[C].Proceedings of the 12th international conference on compiler construction，Berlin：Springer, 2003：185-199.

[43] H. Kermany, E. Petrank. The compressor: Concurrent, incremental and parallel compaction[C].Proceedings of SIGPLAN conference on programming languages design and implementation, New York：ACM, 2006：354-363.

[44] H. Boehm, M. Weiser. Garbage collection in an uncooperative environment[J]. Software-Practice and Experience, 1998, 18(9): 807-820.

Survey of Reference Counting Approach to Garbage Collection

HE Jian-li

(School of Computer and Information Science, Anqing Teachers College, Anqing 246133, China)

This paper draws the fundamental methods and problems about high overhead and collecting cycle for reference counting approach to garbage collection from two C language programs. The research progresses about reference counting approach to automatic memory management in improvement performance and collecting cyclic garbage and concurrent collection are surveyed. The existing problems and the corresponding solutions are induced. The solutions to improvement performance and collecting cycle are classified and analyzed. The important design strategies about concurrent collection are expounded. Finally, the typical reference counting garbage collectors are analyzed and compared.

reference counting, memory management, garbage collection, cycle garbage

2015-04-18

贺建立，男，安徽宿松人，博士，安庆师范学院计算机与信息学院讲师，主要研究方向为动态内存管理。

时间：2016-1-5 13:01 网络出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160105.1301.011.html

计数垃圾收集方法综述

TP311.52

A

1007-4260(2015)04-0041-07