賀建立

（安慶師范學(xué)院計算機與信息學(xué)院，安徽安慶 246133）

C++并發(fā)引用計數(shù)垃圾收集器實現(xiàn)

賀建立

（安慶師范學(xué)院計算機與信息學(xué)院，安徽安慶 246133）

引用計數(shù)垃圾收集器通常具有增量式和實時性特征，但存在垃圾收集器中斷執(zhí)行程序時間較長的情況。本文實現(xiàn)了一個并發(fā)引用計數(shù)垃圾收集器，使得垃圾收集器和工作程序并發(fā)執(zhí)行，避免了垃圾收集器中斷執(zhí)行程序。基于C++的語法標(biāo)準(zhǔn)和應(yīng)用編程接口，無需修改編譯器和存儲分配器，且收集器和工作程序的同步是鎖免除的。Linux操作系統(tǒng)中的實現(xiàn)和實驗表明，收集器有極低（低于0.2%）的處理器損失。

引用計數(shù)；垃圾收集；工作程序；并發(fā)；鎖免除

垃圾收集指自動回收堆中垃圾數(shù)據(jù)對象占用的存儲空間。垃圾是在程序中由全局的、寄存器的或棧的指針變量遍歷不到的堆內(nèi)數(shù)據(jù)對象。內(nèi)存泄漏是指程序中沒有及時回收的垃圾數(shù)據(jù)。顯式地回收內(nèi)存為軟件開發(fā)帶來了諸多問題，其一，容易導(dǎo)致內(nèi)存泄漏；其二，容易使用導(dǎo)致運行期錯誤的懸掛指針（dangling pointer）；其三，增加模塊間的耦合，例如兩個函數(shù)共享同一個堆指針變量，雙方要互相通告不再使用該對象的消息，以選擇合適的釋放對象時機。

現(xiàn)代操作系統(tǒng)在進程退出時回收該進程占用的所有物理內(nèi)存，內(nèi)存泄漏對于運行期短的進程存在微觀的性能損失，表現(xiàn)在降低了處理器的高速緩存和轉(zhuǎn)換后援緩沖器（TLB）命中率，但對于持續(xù)運行幾天、甚至幾個星期的服務(wù)器進程有顯著的影響。內(nèi)存泄漏會導(dǎo)致系統(tǒng)的物理內(nèi)存緊缺，頁面交換技術(shù)使得一些內(nèi)存物理頁中的數(shù)據(jù)會被交換至硬盤交換分區(qū)，硬盤的訪問速度比內(nèi)存慢很多［1］，因此，內(nèi)存泄漏會使得服務(wù)進程變慢，嚴(yán)重時會導(dǎo)致用完交換分區(qū)后整個系統(tǒng)崩潰。綜上所述，垃圾收集器是開發(fā)大型、可靠軟件系統(tǒng)的重要工具。

垃圾收集不可避免地帶來系統(tǒng)性能的損失，早期的實驗表明，大型的LISP程序中垃圾收集器占用了系統(tǒng)10%到30%的執(zhí)行時間［2］。一些垃圾收集器在執(zhí)行單個垃圾收集線程時要求暫停工作線程（mutators）執(zhí)行，這顯然在多處理器平臺中，系統(tǒng)缺乏可伸縮性（scalability），處理器的利用率低。并發(fā)收集器與工作程序并發(fā)地執(zhí)行，不會停止工作程序。

垃圾收集器算法分為引用計數(shù)［3］、標(biāo)記-清掃［4］和拷貝［5］三類。引用計數(shù)垃圾收集器在每個對象上維持一個引用計數(shù)，當(dāng)有新的變量引用到對象時，引用計數(shù)加1，刪除一個引用時，計數(shù)器減1，當(dāng)引用計數(shù)變?yōu)榱銜r，對象被回收。標(biāo)記-清掃收集器掃描根集，首先標(biāo)記活動對象，然后回收那些沒有被標(biāo)記的垃圾對象。拷貝收集器將堆空間分成兩個區(qū)域，垃圾收集時將所有的活動對象從一個區(qū)域移動到另一個區(qū)域，原來區(qū)域中只剩下垃圾對象，變?yōu)榭捎每臻g。標(biāo)記-清掃和拷貝收集器必須掃描根集，收集器與工作線程同步會導(dǎo)致工作程序暫停。引用計數(shù)收集器不需要掃描根集，收集垃圾與工作程序交錯執(zhí)行，通常具有增量式和實時性特征。

1 設(shè)計概覽

系統(tǒng)由若干個工作線程和垃圾收集線程構(gòu)成，線程調(diào)度是操作系統(tǒng)的基本功能，多線程在多處理器系統(tǒng)中并發(fā)執(zhí)行。工作線程滿足用戶的軟件需求，其職責(zé)還包括創(chuàng)建堆對象和自動維護對象引用計數(shù)。垃圾收集線程檢測執(zhí)行程序內(nèi)堆對象的引用計數(shù)，收集那些計數(shù)值為零的對象空間。鏈表將所有對象關(guān)聯(lián)起來，由線程共享，其結(jié)構(gòu)如圖1。工作線程創(chuàng)建對象后將對象插入鏈表中；垃圾收集線程遍歷鏈表，從鏈表中刪除引用計數(shù)為零的對象。

鏈表頭由指向鏈表節(jié)點指針、信號量、線程標(biāo)識和線程屬性四部分組成，工作線程結(jié)束時向垃圾收集線程發(fā)送信號，以回收資源和終止其運行。鏈表節(jié)點兩個域分別指向下一個節(jié)點和指向某個堆對象。baseClass類定義了一個整型的引用計數(shù)變量ref，它是堆對象的父類。若有多個線程操縱對象的ref，baseClass類中需要定義一個自旋鎖（spin lock）變量，以防止對ref的并發(fā)訪問。

將上述設(shè)計思想集成到C++開發(fā)環(huán)境中，需要實現(xiàn)一些軟件設(shè)施，包括定義由堆對象繼承的baseClass類，以提供引用計數(shù)變量和一致的數(shù)據(jù)類型；提供構(gòu)造新對象并創(chuàng)建垃圾收集線程的應(yīng)用編程接口以及向垃圾收集線程發(fā)送結(jié)束信號的編程接口；實現(xiàn)垃圾收集線程；實現(xiàn)幫助自動管理引用計數(shù)的對象地址容器類。垃圾收集線程的實現(xiàn)有兩個重要目標(biāo)，即減少處理器的損失和避免多線程操縱對象鏈表時帶來同步鎖。

圖1 對象鏈表結(jié)構(gòu)

2 實現(xiàn)

2.1 全局接口

構(gòu)造堆對象的任務(wù)包括創(chuàng)建鏈表節(jié)點；調(diào)用new編程接口申請堆空間，將獲得的堆空間地址存入鏈表節(jié)點的baseClass*域；將鏈表節(jié)點插入到鏈表中；創(chuàng)建第一個對象時還要構(gòu)造垃圾收集線程；另外，工作線程結(jié)束時要通知垃圾收集線程。這些任務(wù)的實現(xiàn)既分散注意力又涉及深層的系統(tǒng)編程方法，不應(yīng)該留給應(yīng)用編程者實現(xiàn)。

本文提供兩個全局接口函數(shù)，函數(shù)原型為template＜class objType＞void makeObject（base-Class**a）和void notifyEnd（）。notifyEnd通知垃圾收集線程停止工作，垃圾收集線程分趟掃描對象鏈表，每趟掃描結(jié)束后檢測是否收到通知消息。notifyEnd的實現(xiàn)要調(diào)用Linux操作系統(tǒng)的C編程接口sem_post（&pHeader-＞end_sem）。make-Object的實現(xiàn)相對復(fù)雜些，算法如下

以上算法中objType繼承baseClass，其默認構(gòu)造函數(shù)中設(shè)置ref為1。first是bool類型的靜態(tài)變量，初值為true。算法初始化了信號量，設(shè)置線程調(diào)度策略為SCHED_OTHER的普通分時策略，設(shè)置線程為脫離狀態(tài)［6-7］。圖2中往鏈表中插入節(jié)點的代碼并未采用任何同步保護原語，下節(jié)將論述避免鎖同步的理由和方法。

2.2 免除同步鎖

代碼同步對實時系統(tǒng)性能有非常大的損失，搶占式同步原語允許當(dāng)前進程在執(zhí)行臨界區(qū)的代碼時被高優(yōu)先級進程搶占，在一些情況下這會導(dǎo)致優(yōu)先級反轉(zhuǎn)［8］，文獻［8］很好地論述了優(yōu)先級反轉(zhuǎn)問題。非搶占式同步原語不允許低優(yōu)先級任務(wù)在執(zhí)行臨界區(qū)代碼時被高優(yōu)先級任務(wù)搶占，這延遲了高優(yōu)先級任務(wù)調(diào)度執(zhí)行。文獻［9］總結(jié)了對稱多處理器系統(tǒng)中使用同步原語的性能代價，包括指令執(zhí)行、管線擱置（pipeline-stall）、內(nèi)存延遲和競爭。

對象鏈表是工作線程和垃圾收集線程共享的數(shù)據(jù)結(jié)構(gòu)，工作線程在構(gòu)造對象時準(zhǔn)備好鏈表節(jié)點后將該節(jié)點插入到鏈表中的第一個節(jié)點，如2.1節(jié)代碼。收集線程定期地遍歷鏈表，當(dāng)鏈表節(jié)點中所指對象的引用計數(shù)為零時，回收該節(jié)點和節(jié)點所指的對象空間。從上述分析可以看出，存在多個寫者并發(fā)執(zhí)行的情形。

免除同步鎖需要解決兩個問題，（1）避免多個寫者并發(fā)訪問同一個鏈表節(jié)點；（2）避免寫者破壞讀者的鏈表路徑。對象構(gòu)造算法限定了新的節(jié)點只能作為鏈表的第一個節(jié)點，只要保證收集線程始終不破壞鏈表原有的第一節(jié)點就能解決問題（1）。即使第一個鏈表節(jié)點所指對象的引用計數(shù)為零，收集線程（見2.4）也不會回收它所占的內(nèi)存空間。該堆對象空間并不會成為永久垃圾，只是推遲了這部分內(nèi)存的回收時間。因為隨時都有新的節(jié)點插入到鏈表中成為下一個“第一個節(jié)點”。只要遵循節(jié)點插入鏈表規(guī)范，上述方案也解決了問題（2）。作為寫者的工作線程，首先將鏈表原有的第一個節(jié)點的地址存儲在新節(jié)點的鏈表節(jié)點指針域，然后再將頭節(jié)點的節(jié)點指針域改為新節(jié)點的地址。寫者只改變了頭節(jié)點的鏈表節(jié)點指針域。作為讀者的收集線程，從鏈表頭讀到的指針要么指向新的第一個節(jié)點，要么指向“舊的”第一個節(jié)點，這都沒有破壞鏈表路徑。

2.3 引用計數(shù)自動管理

垃圾自動回收的編程環(huán)境使得應(yīng)用程序員無需關(guān)心堆對象被多少個指針變量引用，何時調(diào)用delete函數(shù)釋放對象空間，這就要求平臺提供引用計數(shù)自動管理設(shè)施。例如程序中定義了指針變量classBase*p，*q，*r，當(dāng)程序中出現(xiàn)語句p= new classBase，q=new classBase，r=new class-Base，此時新生成的三個對象的引用計數(shù)都為1；之后若出現(xiàn)p=q=r這樣的賦值語句，此時p和q原先所指對象引用計數(shù)值都自動變?yōu)?，而r原先所指對象的引用計數(shù)變?yōu)?。

解決上述問題要求提供一段對象類的代碼，以自動管理每個對象的引用計數(shù)。堆指針變量的值在編譯時未知，只能在運行時確定，而棧變量空間在編譯時靜態(tài)分配，例如堆指針變量賦值語句p=q，此時p的值可能為零，即p沒有指向任何對象，因此，無法調(diào)用p所指對象的方法改變引用計數(shù)值，這就要求堆變量賦值改為棧變量賦值。

ptrContainer類封裝了對象指針變量，幫助自動管理引用計數(shù)，ptrContainer類重載了賦值運算符“=”，賦值算符重裝的實現(xiàn)如下

以上賦值算符重載中實現(xiàn)了兩個“=”算符重載函數(shù)，假如程序出現(xiàn)代碼ptrContainer a，b，a =new baseClass，b=new baseClass，圖中第一個重載函數(shù)被調(diào)用，兩個新對象的引用計數(shù)都為1；若出現(xiàn)語句a=b，圖中第二個重載函數(shù)被調(diào)用，b原先所指對象的計數(shù)值為2，a原先所指對象的引用計數(shù)變?yōu)?。變量a和b實際上都為棧變量，為了保持ptrContainter類型變量為指針變量的語義，ptrContainer類重裝了運算符“*”和“-＞”，兩個算符重載函數(shù)都返回封裝的指針變量。

2.4 收集線程

垃圾收集線程周期性地遍歷對象鏈表，當(dāng)某個鏈表節(jié)點所指對象的引用計數(shù)為零時，回收堆對象和鏈表節(jié)點的存儲空間。垃圾收集的執(zhí)行頻率過高會占用太多的處理器資源，頻率過低會推遲垃圾收集的時間。本文的實現(xiàn)選擇收集線程與工作線程相同的調(diào)度優(yōu)先級，收集器在每次遍歷鏈表后自動讓出處理器，這樣垃圾收集線程既能得到公平調(diào)度，又節(jié)約了處理器資源。算法如下

算法首先判斷是否有來自工作線程的信號，使用了非阻塞的信號量函數(shù)sem_trywait，如果收到信號，收集鏈表節(jié)點、鏈表頭節(jié)點以及其他對象的內(nèi)存空間，結(jié)束線程。然后遍歷鏈表，當(dāng)鏈表節(jié)點所指對象的引用計數(shù)為零時，回收對象空間和節(jié)點空間。注意，為免除同步鎖，算法沒有刪除鏈表的第一個節(jié)點。最后，算法調(diào)用pthread_yield函數(shù)讓出處理器。

3 驗證和評估

本文測試平臺的操作系統(tǒng)為Linux2.6.24內(nèi)核，處理器為Intel Core2 Duo CPU，其主頻為1.80 GHz。為了統(tǒng)計垃圾收集線程占用的處理器時間和比率，在工作線程中通過兩重for循環(huán)來延長執(zhí)行時間，代碼為for（int i=0；i＜FIRSTLEVEL；i+ +）｛for（int j=0；j＜SECONDLEVEL；j+ +）｝。通過改變循環(huán)次數(shù)和構(gòu)造對象個數(shù)，以g++為編譯工具，以gprof作為性能分析工具，獲得了表1和表2兩組數(shù)據(jù)。

gprof取樣時間為0.01秒。表2相對表1而言，程序執(zhí)行內(nèi)循環(huán)的次數(shù)擴大了一個數(shù)量級，程序執(zhí)行時間顯著增加了。從表中可以看出，垃圾收集線程處理器的最大占有率僅為0.13%。

表1 FIRSTLEVEL=10 000，SECONDLEVEL=10 000

表2 FIRSTLEVEL=10 000，SECONDLEVEL=100 000

內(nèi)存方面的損失包括每個對象增加了一個整型的引用計數(shù)變量，占4個字節(jié)；增加了與每個對象相關(guān)的一個鏈表節(jié)點，占8個字節(jié)。容器類封裝了對象的地址變量，占4個字節(jié)，不應(yīng)算作額外的損失。假設(shè)程序中堆對象的平均大小為N個字節(jié)，忽略一些不變量（如鏈表頭節(jié)點）內(nèi)存損失的比率為12/N。堆對象的平均大小是不能確定的，假定為1 K，則內(nèi)存損失率約為1.17%。

4 結(jié)束語

本文實現(xiàn)一個C++并發(fā)引用計數(shù)垃圾收集器，使得垃圾收集器和工作線程并發(fā)執(zhí)行，避免了垃圾收集器中斷執(zhí)行程序的情況。實現(xiàn)不依賴于編譯器產(chǎn)生的目標(biāo)代碼和操作系統(tǒng)的存儲管理機制；且收集器和工作程序間的同步是鎖免除的。Linux操作系統(tǒng)中的實現(xiàn)和驗證表明，在忽略線程切換損失的情況下，收集器有非常?。ǖ陀?.2%）的處理器占有率。盡管實現(xiàn)調(diào)用了一些Linux操作系統(tǒng)C語言編程接口，筆者認為較容易移植到Windows或其他操作系統(tǒng)平臺上。

［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程序設(shè)計［M］.北京：機械工業(yè)出版社，2002：1-757.

［7］Dp Bovet，MCesati.深入理解Linux內(nèi)核［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

計數(shù)垃圾收集器也存在明顯的缺陷：（1）若一組對象組成一個環(huán)狀結(jié)構(gòu)，即使從根集不存在到該對象的路徑，對象的引用計數(shù)也不會減為零。在處理有環(huán)的數(shù)據(jù)結(jié)構(gòu)時，需要消除環(huán)或者結(jié)合其他垃圾收集算法。（2）若一組對象形成一個鏈表，當(dāng)收集鏈表中的某個對象時，其他對象的引用計數(shù)可能都會變?yōu)榱?，這會導(dǎo)致垃圾收集中斷執(zhí)行程序時間較長。本文實現(xiàn)并發(fā)引用計數(shù)垃圾收集器，旨在解決問題（2）。

時間：2014-9-15 16：07 網(wǎng)絡(luò)出版地址：http：//www.cnki.net/kcms/doi/10.13757/j.cnki.cn34-1150/n.2014.03.014.html

2014-04-09

賀建立，男，安徽宿松人，博士，安慶師范學(xué)院計算機與信息學(xué)院講師，主要研究方向為Linux操作系統(tǒng)、動態(tài)存儲管理。