C++并发引用计数垃圾收集器实现

贺建立

（安庆师范学院计算机与信息学院，安徽安庆 246133）

C++并发引用计数垃圾收集器实现

贺建立

（安庆师范学院计算机与信息学院，安徽安庆 246133）

引用计数垃圾收集器通常具有增量式和实时性特征，但存在垃圾收集器中断执行程序时间较长的情况。本文实现了一个并发引用计数垃圾收集器，使得垃圾收集器和工作程序并发执行，避免了垃圾收集器中断执行程序。基于C++的语法标准和应用编程接口，无需修改编译器和存储分配器，且收集器和工作程序的同步是锁免除的。Linux操作系统中的实现和实验表明，收集器有极低（低于0.2%）的处理器损失。

引用计数；垃圾收集；工作程序；并发；锁免除

垃圾收集指自动回收堆中垃圾数据对象占用的存储空间。垃圾是在程序中由全局的、寄存器的或栈的指针变量遍历不到的堆内数据对象。内存泄漏是指程序中没有及时回收的垃圾数据。显式地回收内存为软件开发带来了诸多问题，其一，容易导致内存泄漏；其二，容易使用导致运行期错误的悬挂指针（dangling pointer）；其三，增加模块间的耦合，例如两个函数共享同一个堆指针变量，双方要互相通告不再使用该对象的消息，以选择合适的释放对象时机。

现代操作系统在进程退出时回收该进程占用的所有物理内存，内存泄漏对于运行期短的进程存在微观的性能损失，表现在降低了处理器的高速缓存和转换后援缓冲器（TLB）命中率，但对于持续运行几天、甚至几个星期的服务器进程有显著的影响。内存泄漏会导致系统的物理内存紧缺，页面交换技术使得一些内存物理页中的数据会被交换至硬盘交换分区，硬盘的访问速度比内存慢很多［1］，因此，内存泄漏会使得服务进程变慢，严重时会导致用完交换分区后整个系统崩溃。综上所述，垃圾收集器是开发大型、可靠软件系统的重要工具。

垃圾收集不可避免地带来系统性能的损失，早期的实验表明，大型的LISP程序中垃圾收集器占用了系统10%到30%的执行时间［2］。一些垃圾收集器在执行单个垃圾收集线程时要求暂停工作线程（mutators）执行，这显然在多处理器平台中，系统缺乏可伸缩性（scalability），处理器的利用率低。并发收集器与工作程序并发地执行，不会停止工作程序。

垃圾收集器算法分为引用计数［3］、标记-清扫［4］和拷贝［5］三类。引用计数垃圾收集器在每个对象上维持一个引用计数，当有新的变量引用到对象时，引用计数加1，删除一个引用时，计数器减1，当引用计数变为零时，对象被回收。标记-清扫收集器扫描根集，首先标记活动对象，然后回收那些没有被标记的垃圾对象。拷贝收集器将堆空间分成两个区域，垃圾收集时将所有的活动对象从一个区域移动到另一个区域，原来区域中只剩下垃圾对象，变为可用空间。标记-清扫和拷贝收集器必须扫描根集，收集器与工作线程同步会导致工作程序暂停。引用计数收集器不需要扫描根集，收集垃圾与工作程序交错执行，通常具有增量式和实时性特征。

1 设计概览

系统由若干个工作线程和垃圾收集线程构成，线程调度是操作系统的基本功能，多线程在多处理器系统中并发执行。工作线程满足用户的软件需求，其职责还包括创建堆对象和自动维护对象引用计数。垃圾收集线程检测执行程序内堆对象的引用计数，收集那些计数值为零的对象空间。链表将所有对象关联起来，由线程共享，其结构如图1。工作线程创建对象后将对象插入链表中；垃圾收集线程遍历链表，从链表中删除引用计数为零的对象。

链表头由指向链表节点指针、信号量、线程标识和线程属性四部分组成，工作线程结束时向垃圾收集线程发送信号，以回收资源和终止其运行。链表节点两个域分别指向下一个节点和指向某个堆对象。baseClass类定义了一个整型的引用计数变量ref，它是堆对象的父类。若有多个线程操纵对象的ref，baseClass类中需要定义一个自旋锁（spin lock）变量，以防止对ref的并发访问。

将上述设计思想集成到C++开发环境中，需要实现一些软件设施，包括定义由堆对象继承的baseClass类，以提供引用计数变量和一致的数据类型；提供构造新对象并创建垃圾收集线程的应用编程接口以及向垃圾收集线程发送结束信号的编程接口；实现垃圾收集线程；实现帮助自动管理引用计数的对象地址容器类。垃圾收集线程的实现有两个重要目标，即减少处理器的损失和避免多线程操纵对象链表时带来同步锁。

图1 对象链表结构

2 实现

2.1 全局接口

构造堆对象的任务包括创建链表节点；调用new编程接口申请堆空间，将获得的堆空间地址存入链表节点的baseClass*域；将链表节点插入到链表中；创建第一个对象时还要构造垃圾收集线程；另外，工作线程结束时要通知垃圾收集线程。这些任务的实现既分散注意力又涉及深层的系统编程方法，不应该留给应用编程者实现。

本文提供两个全局接口函数，函数原型为template＜class objType＞void makeObject（base-Class**a）和void notifyEnd（）。notifyEnd通知垃圾收集线程停止工作，垃圾收集线程分趟扫描对象链表，每趟扫描结束后检测是否收到通知消息。notifyEnd的实现要调用Linux操作系统的C编程接口sem_post（&pHeader-＞end_sem）。make-Object的实现相对复杂些，算法如下

以上算法中objType继承baseClass，其默认构造函数中设置ref为1。first是bool类型的静态变量，初值为true。算法初始化了信号量，设置线程调度策略为SCHED_OTHER的普通分时策略，设置线程为脱离状态［6-7］。图2中往链表中插入节点的代码并未采用任何同步保护原语，下节将论述避免锁同步的理由和方法。

2.2 免除同步锁

代码同步对实时系统性能有非常大的损失，抢占式同步原语允许当前进程在执行临界区的代码时被高优先级进程抢占，在一些情况下这会导致优先级反转［8］，文献［8］很好地论述了优先级反转问题。非抢占式同步原语不允许低优先级任务在执行临界区代码时被高优先级任务抢占，这延迟了高优先级任务调度执行。文献［9］总结了对称多处理器系统中使用同步原语的性能代价，包括指令执行、管线搁置（pipeline-stall）、内存延迟和竞争。

对象链表是工作线程和垃圾收集线程共享的数据结构，工作线程在构造对象时准备好链表节点后将该节点插入到链表中的第一个节点，如2.1节代码。收集线程定期地遍历链表，当链表节点中所指对象的引用计数为零时，回收该节点和节点所指的对象空间。从上述分析可以看出，存在多个写者并发执行的情形。

免除同步锁需要解决两个问题，（1）避免多个写者并发访问同一个链表节点；（2）避免写者破坏读者的链表路径。对象构造算法限定了新的节点只能作为链表的第一个节点，只要保证收集线程始终不破坏链表原有的第一节点就能解决问题（1）。即使第一个链表节点所指对象的引用计数为零，收集线程（见2.4）也不会回收它所占的内存空间。该堆对象空间并不会成为永久垃圾，只是推迟了这部分内存的回收时间。因为随时都有新的节点插入到链表中成为下一个“第一个节点”。只要遵循节点插入链表规范，上述方案也解决了问题（2）。作为写者的工作线程，首先将链表原有的第一个节点的地址存储在新节点的链表节点指针域，然后再将头节点的节点指针域改为新节点的地址。写者只改变了头节点的链表节点指针域。作为读者的收集线程，从链表头读到的指针要么指向新的第一个节点，要么指向“旧的”第一个节点，这都没有破坏链表路径。

2.3 引用计数自动管理

垃圾自动回收的编程环境使得应用程序员无需关心堆对象被多少个指针变量引用，何时调用delete函数释放对象空间，这就要求平台提供引用计数自动管理设施。例如程序中定义了指针变量classBase*p，*q，*r，当程序中出现语句p= new classBase，q=new classBase，r=new class-Base，此时新生成的三个对象的引用计数都为1；之后若出现p=q=r这样的赋值语句，此时p和q原先所指对象引用计数值都自动变为0，而r原先所指对象的引用计数变为3。

解决上述问题要求提供一段对象类的代码，以自动管理每个对象的引用计数。堆指针变量的值在编译时未知，只能在运行时确定，而栈变量空间在编译时静态分配，例如堆指针变量赋值语句p=q，此时p的值可能为零，即p没有指向任何对象，因此，无法调用p所指对象的方法改变引用计数值，这就要求堆变量赋值改为栈变量赋值。

ptrContainer类封装了对象指针变量，帮助自动管理引用计数，ptrContainer类重载了赋值运算符“=”，赋值算符重装的实现如下

以上赋值算符重载中实现了两个“=”算符重载函数，假如程序出现代码ptrContainer a，b，a =new baseClass，b=new baseClass，图中第一个重载函数被调用，两个新对象的引用计数都为1；若出现语句a=b，图中第二个重载函数被调用，b原先所指对象的计数值为2，a原先所指对象的引用计数变为0。变量a和b实际上都为栈变量，为了保持ptrContainter类型变量为指针变量的语义，ptrContainer类重装了运算符“*”和“-＞”，两个算符重载函数都返回封装的指针变量。

2.4 收集线程

垃圾收集线程周期性地遍历对象链表，当某个链表节点所指对象的引用计数为零时，回收堆对象和链表节点的存储空间。垃圾收集的执行频率过高会占用太多的处理器资源，频率过低会推迟垃圾收集的时间。本文的实现选择收集线程与工作线程相同的调度优先级，收集器在每次遍历链表后自动让出处理器，这样垃圾收集线程既能得到公平调度，又节约了处理器资源。算法如下

算法首先判断是否有来自工作线程的信号，使用了非阻塞的信号量函数sem_trywait，如果收到信号，收集链表节点、链表头节点以及其他对象的内存空间，结束线程。然后遍历链表，当链表节点所指对象的引用计数为零时，回收对象空间和节点空间。注意，为免除同步锁，算法没有删除链表的第一个节点。最后，算法调用pthread_yield函数让出处理器。

3 验证和评估

本文测试平台的操作系统为Linux2.6.24内核，处理器为Intel Core2 Duo CPU，其主频为1.80 GHz。为了统计垃圾收集线程占用的处理器时间和比率，在工作线程中通过两重for循环来延长执行时间，代码为for（int i=0；i＜FIRSTLEVEL；i+ +）｛for（int j=0；j＜SECONDLEVEL；j+ +）｝。通过改变循环次数和构造对象个数，以g++为编译工具，以gprof作为性能分析工具，获得了表1和表2两组数据。

gprof取样时间为0.01秒。表2相对表1而言，程序执行内循环的次数扩大了一个数量级，程序执行时间显著增加了。从表中可以看出，垃圾收集线程处理器的最大占有率仅为0.13%。

表1 FIRSTLEVEL=10 000，SECONDLEVEL=10 000

表2 FIRSTLEVEL=10 000，SECONDLEVEL=100 000

内存方面的损失包括每个对象增加了一个整型的引用计数变量，占4个字节；增加了与每个对象相关的一个链表节点，占8个字节。容器类封装了对象的地址变量，占4个字节，不应算作额外的损失。假设程序中堆对象的平均大小为N个字节，忽略一些不变量（如链表头节点）内存损失的比率为12/N。堆对象的平均大小是不能确定的，假定为1 K，则内存损失率约为1.17%。

4 结束语

本文实现一个C++并发引用计数垃圾收集器，使得垃圾收集器和工作线程并发执行，避免了垃圾收集器中断执行程序的情况。实现不依赖于编译器产生的目标代码和操作系统的存储管理机制；且收集器和工作程序间的同步是锁免除的。Linux操作系统中的实现和验证表明，在忽略线程切换损失的情况下，收集器有非常小（低于0.2%）的处理器占有率。尽管实现调用了一些Linux操作系统C语言编程接口，笔者认为较容易移植到Windows或其他操作系统平台上。

［1］M.Hertz，Y.Feng，E.D.Berger.Garbage collection without paging［C］//Proceedings of the 2005 ACMSIGPLAN conference on programming language design and implementation，2005，40（7）：143-153.

［2］Jacques Conhen.Garbage collection of linked data structures［J］. ACMcomputing surveys，1981，13（3）：341-367.

［3］Yossi，Levanoni，Erez Petrank.An on-the-fly reference-counting garbage collector for java［J］.Transactions on programming languages and systems，2006，28（1）：1-69.

［4］Hezi Azatchi，Yossi Levanoni，Harel Paz，Erez Petrank.An onthe-flymark and sweep garbage collector based on sliding views［C］//Proceedings of the18th annual ACMSIGPLAN conference on Object-oriented programing，systems，languages，and applications.November 2003.

［5］Martin Kero，Johan Nordlander，Per Lindgren.A correct and useful incremental copying garbage collector［C］//Proceedings of the 6th international symposium on memory management.October 2007.

［6］N Matthew，R Stones.Linux程序设计［M］.北京：机械工业出版社，2002：1-757.

［7］Dp Bovet，MCesati.深入理解Linux内核［M］.北京：中国电力出版社，2012：1-823.

［8］Sha，L.，Rajkumar，R.，and Lehoczky，J.P..Priority inheritance protocols：an approach to real-time synchronization［J］. IEEE transactions on computers，1990，39（9）：1175-1185.

［9］Mckenney，P.E.Exploiting deferred destruction：an analysis of read-copy-update techniques in operating system kernels［D］. OGISchool of Science and Engineering atOregon Health and Sciences University，2004.

The Implementation of Concurrent Reference-counting Garbage Collector for C++

HE Jian-li
（School of Computer and Information Science，Anqing Teachers College，Anqing 246133，China）

Reference-counting garbage collector has incremental nature ofmost of its operation and can easily satisfy real-time requirements.However，there are cases in which garbage collection interruptions can be long.This paper implements a concurrent reference-counting garbage collector for C++，which can avoid the cases where collector interruptsmutators.The implementation is based on C++grammar standards and application programming interfaces，so it is no need tomodify compiler andmemory allocator.The cooperation between collector andmutator is lock-free.The implementation and experiments in Linux OSshow that the CPU cost is extreme low（less than 0.2%）.

reference-counting，garbage collector，mutator，concurrent，lock-free

TP311.52

A

1007-4260（2014）03-0054-05

计数垃圾收集器也存在明显的缺陷：（1）若一组对象组成一个环状结构，即使从根集不存在到该对象的路径，对象的引用计数也不会减为零。在处理有环的数据结构时，需要消除环或者结合其他垃圾收集算法。（2）若一组对象形成一个链表，当收集链表中的某个对象时，其他对象的引用计数可能都会变为零，这会导致垃圾收集中断执行程序时间较长。本文实现并发引用计数垃圾收集器，旨在解决问题（2）。

时间：2014-9-15 16：07 网络出版地址：http：//www.cnki.net/kcms/doi/10.13757/j.cnki.cn34-1150/n.2014.03.014.html

2014-04-09

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