賀 建 立

(安慶師范學(xué)院 計(jì)算機(jī)與信息學(xué)院，安徽 安慶 246133)

賀 建 立

(安慶師范學(xué)院 計(jì)算機(jī)與信息學(xué)院，安徽 安慶 246133)

基于兩個(gè)C語(yǔ)言程序引出引用計(jì)數(shù)垃圾收集的基本方法、存在的效率和回收環(huán)垃圾問(wèn)題，歸納了引用計(jì)數(shù)自動(dòng)回收內(nèi)存方法在改進(jìn)效率、回收環(huán)垃圾、并發(fā)收集方面的研究進(jìn)展及存在的問(wèn)題和相應(yīng)的解決方法，對(duì)改進(jìn)性能和回收環(huán)垃圾的方法進(jìn)行了分類和分析，闡述了并發(fā)收集的重要設(shè)計(jì)策略，并對(duì)典型的引用計(jì)數(shù)垃圾收集器進(jìn)行了分析和比較。

引用計(jì)數(shù)；內(nèi)存管理；垃圾收集；環(huán)垃圾 DOI：10.13757/j.cnki.cn34-1150/n.2015.04.011

內(nèi)存自動(dòng)管理是快速開(kāi)發(fā)大型可靠軟件的重要工具，垃圾收集方法對(duì)軟件運(yùn)行時(shí)性能會(huì)產(chǎn)生重要影響，實(shí)現(xiàn)高效的內(nèi)存管理和垃圾收集是當(dāng)前系統(tǒng)軟件設(shè)計(jì)的目標(biāo)之一。J.Mccartihy和G.E.Collins于1960年先后提出了跟蹤[1]和引用計(jì)數(shù)[2]垃圾收集方法。跟蹤方法從根集開(kāi)始傳遞閉包的遍歷對(duì)象圖，回收沒(méi)有被跟蹤到的對(duì)象。引用計(jì)數(shù)方法記錄對(duì)象被引用的次數(shù)，當(dāng)對(duì)象的引用計(jì)數(shù)為零時(shí)，表明對(duì)象是不可達(dá)的，可以被回收。簡(jiǎn)單引用計(jì)數(shù)方法因頻繁地更新對(duì)象的引用計(jì)數(shù)比跟蹤方法多損失30%的性能[3]，且不能回收帶環(huán)的數(shù)據(jù)對(duì)象。五十多年來(lái)，由于引用計(jì)數(shù)方法存在明顯缺陷，跟蹤垃圾收集器及其變種(標(biāo)記清掃、半空間拷貝和標(biāo)記壓縮)得到了更為廣泛的發(fā)展與應(yīng)用。

引用計(jì)數(shù)垃圾收集方法相對(duì)跟蹤方法具備一些明顯優(yōu)勢(shì)：(1)引用計(jì)數(shù)為零的垃圾對(duì)象及時(shí)地被回收；(2)收集過(guò)程是增量式的，避免了集中式收集所引發(fā)的進(jìn)程長(zhǎng)時(shí)間暫停；(3)使用對(duì)象局部信息，無(wú)需搜索整個(gè)堆空間；(4)實(shí)現(xiàn)簡(jiǎn)單，無(wú)需運(yùn)行時(shí)系統(tǒng)的支持，避免了從全局?jǐn)?shù)據(jù)區(qū)、棧和寄存器開(kāi)始列舉在堆空間中的指針[4]。腳本語(yǔ)言AppleScript、Perl和 PHP的設(shè)計(jì)者選用引用計(jì)數(shù)方法自動(dòng)回收內(nèi)存，在處理帶環(huán)數(shù)據(jù)對(duì)象方面：AppleScript禁止程序員使用帶環(huán)的數(shù)據(jù)結(jié)構(gòu)，Perl忽略環(huán)垃圾[5]，PHP以跟蹤方法收集環(huán)垃圾。

因性能損失和不完全性問(wèn)題限制了引用計(jì)數(shù)垃圾收集方法的應(yīng)用范圍。對(duì)于引用計(jì)數(shù)的兩大缺陷，人們提出了各種處理帶環(huán)數(shù)據(jù)結(jié)構(gòu)的算法[6-12]，及并發(fā)的純引用計(jì)數(shù)垃圾收集器[14-15]，30%的性能差距已抹平[3,13-20]。隨著64位體系結(jié)構(gòu)的盛行，進(jìn)程的堆地址空間將會(huì)變的非常龐大。跟蹤收集器需要遍歷堆中所有活躍對(duì)象，而引用計(jì)數(shù)收集器不依賴于活躍對(duì)象所占的空間。引用計(jì)數(shù)方法已經(jīng)被一些系統(tǒng)采用，包括編程語(yǔ)言、應(yīng)用程序、操作系統(tǒng)文件管理和C++函數(shù)庫(kù)[21]。當(dāng)前的研究進(jìn)展與計(jì)算環(huán)境的變化使得引用計(jì)數(shù)垃圾收集方法具備更為廣闊的應(yīng)用前景。

1 引用計(jì)數(shù)收集

簡(jiǎn)單的引用計(jì)數(shù)方法因頻繁地更新執(zhí)行程序中對(duì)象的引用計(jì)數(shù)而損失了程序性能。如下代碼所示：

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操作系統(tǒng)中使用G++編譯通過(guò)的C語(yǔ)言程序源代碼，下部分是執(zhí)行地址賦值操作時(shí)垃圾收集系統(tǒng)執(zhí)行的代碼。其中程序源代碼p1和p2是棧變量，9、10行分別在堆中創(chuàng)建了對(duì)象O1和O2，11行調(diào)用foo函數(shù)時(shí)傳入p1參數(shù)，12行為對(duì)象O2的地址槽賦值，13行改變棧變量p2的值。程序執(zhí)行結(jié)束后O1的引用計(jì)數(shù)更新了5次，O2的引用計(jì)數(shù)更新了2次。另外，多線程環(huán)境中還要保證指針操作的原子性，以防止過(guò)早的回收對(duì)象。代碼的下部分在多線程環(huán)境中執(zhí)行是不安全的，需要加鎖保護(hù)。當(dāng)前的研究從減少引用計(jì)數(shù)更新的次數(shù)、避免并發(fā)程序的鎖競(jìng)爭(zhēng)、改進(jìn)堆空間中對(duì)象布局這3個(gè)方面改善效率。

1.1 減少引用計(jì)數(shù)更新

Deutsch等人[13]提出了推遲引用計(jì)數(shù)，忽略程序中寄存器和棧內(nèi)的指針變化，僅在堆中對(duì)象的地址槽改變時(shí)才更新引用計(jì)數(shù)。收集器定期地將寄存器和棧內(nèi)的指針?biāo)笇?duì)象列入根集，堆引用計(jì)數(shù)為零的對(duì)象存入零引用計(jì)數(shù)表(ZCT)中，回收在ZCT中且不在根集里的對(duì)象。這種策略能將上述執(zhí)行程序中對(duì)象O1和O2的引用計(jì)數(shù)更新次數(shù)分別減少為1次和0次。Levanoni等人[16-17]的并發(fā)收集器采用了推遲引用計(jì)數(shù)策略，而且還合并了大量的堆引用計(jì)數(shù)。執(zhí)行程序的堆指針變化時(shí)，將對(duì)象槽的地址和該槽所指對(duì)象的地址存入緩存區(qū)，每個(gè)對(duì)象槽以臟標(biāo)記保證周期內(nèi)在緩存區(qū)中存入唯一的對(duì)象指針。收集線程周期性地讀取緩存區(qū)，將對(duì)象槽上一個(gè)周期所指的對(duì)象引用計(jì)數(shù)減1，將對(duì)象槽當(dāng)前周期內(nèi)所指的對(duì)象引用計(jì)數(shù)加1。假定O1.slot當(dāng)前值為&O0，程序在收集周期內(nèi)為對(duì)象O1.slot執(zhí)行了n次地址賦值：O1.slot=&O2，O1.slot =&O3，… O1.slot=&On。合并策略僅需減少對(duì)象O0的引用計(jì)數(shù)一次和增加對(duì)象On的引用計(jì)數(shù)一次，從而將引用計(jì)數(shù)的更新次數(shù)從2n次降低為2次。

分代垃圾收集[22]假設(shè)大部分對(duì)象是短生命期的，對(duì)象按生命期長(zhǎng)短劃分成新生代和年長(zhǎng)代，新生代對(duì)象的指針變化快，年長(zhǎng)代對(duì)象的指針變化慢。文獻(xiàn)[18-19]以跟蹤收集器回收新生代對(duì)象，以引用計(jì)數(shù)回收年長(zhǎng)代對(duì)象，跟蹤收集器僅跟蹤新生代的對(duì)象，減少了跟蹤范圍，年長(zhǎng)代對(duì)象指針變化較少，引用計(jì)數(shù)的更新也相應(yīng)變少。另外，在編譯期通過(guò)特定的分析算法也能合并掉一些冗余的引用計(jì)數(shù)更新操作，例如增加了一個(gè)對(duì)象的引用計(jì)數(shù)，緊接著減少該對(duì)象的引用計(jì)數(shù)，顯然這兩次操作可以被合并掉[23]。文獻(xiàn)[24]通過(guò)分析地址賦值語(yǔ)句間的包含關(guān)系，在編譯期優(yōu)化了部分由棧變量賦值引發(fā)的對(duì)象引用計(jì)數(shù)更新。

1.2 避免鎖競(jìng)爭(zhēng)

文獻(xiàn)[25]在對(duì)象槽賦值時(shí)將指針的原值和新值存入同一個(gè)緩存區(qū)，多個(gè)線程共享該緩存區(qū)，以互斥鎖保護(hù)緩存區(qū)和待更新的地址槽?；コ怄i同步會(huì)引發(fā)死鎖、長(zhǎng)延遲和優(yōu)先級(jí)反轉(zhuǎn)[26]，非阻塞同步能夠避免這些問(wèn)題。非阻塞同步由比較交換(CAS)機(jī)器指令實(shí)現(xiàn)，CAS是原子指令[27]。直接的方法至少需要使用3條CAS指令，以更新對(duì)象槽和分別更新地址槽所指的新對(duì)象與原對(duì)象的引用計(jì)數(shù)。文獻(xiàn)[14-15]在減少同步操作方面取得了較大突破，將需要增加與需要減少引用計(jì)數(shù)的對(duì)象地址分別存入不同的緩存區(qū)，僅在更新地址槽時(shí)使用了一條CAS指令。

文獻(xiàn)[16-17]在修改對(duì)象槽和更新引用計(jì)數(shù)時(shí)完全避免了原子指令和鎖競(jìng)爭(zhēng)，從3個(gè)方面保證了并發(fā)程序的正確性：(1)每個(gè)線程擁有自己的局部緩存區(qū)，以存儲(chǔ)線程中變化了的地址槽原值和對(duì)象槽的地址；(2)每個(gè)地址槽都有一個(gè)臟標(biāo)記，以確保收集周期內(nèi)緩存區(qū)中存入正確的對(duì)象槽的原值；(3)寫(xiě)屏障代碼依序執(zhí)行：①地址槽信息存入緩存區(qū)，②設(shè)置對(duì)象槽臟標(biāo)記，③在對(duì)象槽中設(shè)置新值。這些措施會(huì)導(dǎo)致在收集周期內(nèi)同一個(gè)對(duì)象槽信息存入不同線程的局部緩存區(qū)中，收集器在調(diào)整對(duì)象引用計(jì)數(shù)時(shí)要剔除緩存區(qū)中多余的副本，以防止錯(cuò)誤地減少地址槽原值對(duì)象的引用計(jì)數(shù)。

1.3 改進(jìn)對(duì)象布局

前述方法使得引用計(jì)數(shù)收集器的性能與全局堆跟蹤收集器性能一致，但與性能最好的分代收集器還存在10%的性能差距[20]，文獻(xiàn)[20-28]的研究結(jié)果表明，通過(guò)改進(jìn)堆空間中對(duì)象布局可以彌補(bǔ)這一差距。

內(nèi)存管理系統(tǒng)分為內(nèi)存分配、活躍對(duì)象識(shí)別和回收垃圾對(duì)象3個(gè)方面。空閑塊鏈表的堆空間組織方式導(dǎo)致了高速緩存的局部性差，且增加了分配和回收內(nèi)存塊的執(zhí)行時(shí)間。標(biāo)記區(qū)域(Mark-Region)的內(nèi)存分配方式通過(guò)改變前移(bump)指針將程序需要的內(nèi)存塊分配在連續(xù)空間，可批量地進(jìn)行回收與初始化[29]。Immix[20]是標(biāo)記區(qū)域收集器，區(qū)域分為行和塊兩個(gè)等級(jí)，塊由幾行構(gòu)成，對(duì)象可以跨行分配但不能跨塊分配，按對(duì)象、行和塊3種粒度回收空間。

1.4 回收環(huán)

McBeth[30]指出了引用計(jì)數(shù)方法不能回收帶環(huán)的數(shù)據(jù)結(jié)構(gòu)。如下所示代碼中當(dāng)執(zhí)行到11行時(shí)對(duì)象O1和O2形成了環(huán)，這時(shí)O1和O2的引用計(jì)數(shù)都為2；當(dāng)執(zhí)行到13行時(shí)對(duì)象O1和O2的引用計(jì)數(shù)都為1，此時(shí)對(duì)象O1和O2都是不可達(dá)的，但對(duì)象的引用計(jì)數(shù)都不為零，故對(duì)象不可被回收。

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 }

存在三種解決環(huán)問(wèn)題的方法：(1)特定的編程習(xí)俗，例如，文獻(xiàn)[31]要求程序員顯式地提供信息以發(fā)現(xiàn)環(huán)。(2)借助很少運(yùn)行的跟蹤收集器全局搜索堆空間以專門(mén)回收環(huán)垃圾。(3)利用特定的算法局部跟蹤堆對(duì)象，嘗試刪除和指針著色是兩種不同風(fēng)格的局部跟蹤算法。

1.4.1 嘗試刪除

嘗試刪除算法[7]基于兩個(gè)基本觀察：(1)只有引用計(jì)數(shù)正在減少且其結(jié)果值大于零時(shí)才可能形成垃圾環(huán)；(2)垃圾環(huán)中引用計(jì)數(shù)全部是內(nèi)部的，當(dāng)內(nèi)部引用計(jì)數(shù)減掉后，環(huán)內(nèi)對(duì)象的引用計(jì)數(shù)全部為零。算法在進(jìn)行指針刪除操作時(shí)，當(dāng)指針?biāo)笇?duì)象的引用計(jì)數(shù)大于零時(shí)，從該對(duì)象(根)開(kāi)始遍歷子圖。算法分為3個(gè)階段：階段1(標(biāo)記紅色)，遍歷子圖，減少內(nèi)部引用計(jì)數(shù)，訪問(wèn)過(guò)的對(duì)象標(biāo)記為紅色；階段2(掃描)，再次遍歷子圖，當(dāng)某個(gè)節(jié)點(diǎn)引用計(jì)數(shù)大于零時(shí)，則從該節(jié)點(diǎn)遍歷子圖，恢復(fù)上一個(gè)階段減少的引用計(jì)數(shù)，并將該子圖中的對(duì)象標(biāo)記為綠色，其他對(duì)象標(biāo)記為藍(lán)色；階段3(回收藍(lán)色)，回收被標(biāo)記為藍(lán)色的對(duì)象。

文獻(xiàn)[8]將根對(duì)象存入隊(duì)列，隨著程序的執(zhí)行，一些根對(duì)象的引用計(jì)數(shù)可能減為零或增加了，這些根對(duì)象可以從隊(duì)列中刪除，從而減少了遍歷子圖的個(gè)數(shù)。文獻(xiàn)[9]使用特定的數(shù)據(jù)結(jié)構(gòu)(Jump-stack)消除了掃描操作(階段2)。文獻(xiàn)[15]從3個(gè)方面改進(jìn)了文獻(xiàn)[8]的效率：類加載器排除了一些固有無(wú)環(huán)的對(duì)象；為對(duì)象加上標(biāo)記，避免隊(duì)列中的對(duì)象再次進(jìn)入隊(duì)列；通過(guò)分析根對(duì)象的傳遞閉包關(guān)系減少了子圖的個(gè)數(shù)，將算法復(fù)雜性限制在子圖的邊數(shù)N與節(jié)點(diǎn)數(shù)V之和。

1.4.2 指針著色

文獻(xiàn)[6]將指針?lè)譃閺?qiáng)指針和弱指針。強(qiáng)指針不形成環(huán)，可以使用標(biāo)準(zhǔn)的算法進(jìn)行計(jì)數(shù)；弱指針用于關(guān)閉環(huán)。對(duì)象包含強(qiáng)指針和弱指針引用計(jì)數(shù)。算法維持兩個(gè)不變式：強(qiáng)指針不形成環(huán)；對(duì)象圖中每個(gè)對(duì)象從根集開(kāi)始至少有一條由強(qiáng)指針形成的路徑。對(duì)象圖的構(gòu)造由指針拷貝和指針刪除操作實(shí)現(xiàn)[11]。

指針著色算法僅在指針刪除操作中當(dāng)強(qiáng)指針引用計(jì)數(shù)為零且弱指針引用計(jì)數(shù)為正數(shù)時(shí)才需要遍歷子圖，減少了訪問(wèn)對(duì)象的次數(shù)，但需要增加額外的空間描述指針的狀態(tài)。文獻(xiàn)[32]指出了文獻(xiàn)[6]的算法在特殊情況下過(guò)早地回收對(duì)象。當(dāng)刪除對(duì)象的最后一個(gè)強(qiáng)指針且對(duì)象還存在弱指針時(shí)，文獻(xiàn)[32]從該對(duì)象重新開(kāi)始收集，糾正了文獻(xiàn)[6]的問(wèn)題，但帶來(lái)了潛在非終結(jié)問(wèn)題。文獻(xiàn)[11]的算法引入兩種標(biāo)記以防止無(wú)限地查找和保障每次查找終結(jié)，算法復(fù)雜性是指數(shù)階的。文獻(xiàn)[12]在文獻(xiàn)[6,11,32]研究基礎(chǔ)上引入了第3種類型的指針(Phantom)，使算法復(fù)雜性降為線性的。

1.5 其他問(wèn)題

對(duì)象頭中存儲(chǔ)引用計(jì)數(shù)帶來(lái)了空間消耗和性能損失，一個(gè)字大小空間的引用計(jì)數(shù)損失了程序2.5%的性能[3]。大部分對(duì)象的引用計(jì)數(shù)非常小，文獻(xiàn)[3]指出引用計(jì)數(shù)小于6的對(duì)象占99%。對(duì)象頭中的一個(gè)字可以取出幾位作為引用計(jì)數(shù)，其他位可作為別的用途。當(dāng)引用計(jì)數(shù)溢出時(shí)有兩種處理策略：(1)哈希表方法，引用計(jì)數(shù)溢出時(shí)在哈希表內(nèi)增加一項(xiàng)，每個(gè)表項(xiàng)占有兩個(gè)字大小的空間，分別用于存儲(chǔ)對(duì)象鍵值及該對(duì)象的引用計(jì)數(shù)。(2)延遲(stuck)方法，引用計(jì)數(shù)溢出時(shí)停止計(jì)數(shù)，由跟蹤收集器統(tǒng)計(jì)和恢復(fù)對(duì)象的引用計(jì)數(shù)。

程序中若存在一組對(duì)象形成長(zhǎng)的單鏈表，當(dāng)鏈表的第一個(gè)節(jié)點(diǎn)的引用計(jì)數(shù)為零時(shí)，需要回收整個(gè)單鏈表，這會(huì)引發(fā)程序較長(zhǎng)的暫停時(shí)間，存在兩種解決方案：(1)限制每個(gè)收集周期回收對(duì)象的個(gè)數(shù)，超出的對(duì)象留給下一個(gè)收集周期回收。(2)并發(fā)收集，收集線程與工作程序并發(fā)執(zhí)行。

綜合本節(jié)內(nèi)容，引用計(jì)數(shù)垃圾收集方法目前存在的問(wèn)題和相應(yīng)的解決辦法歸納如表1。

表1 引用計(jì)數(shù)垃圾收集方法存在問(wèn)題與解決辦法

2 并發(fā)收集

并發(fā)收集器[15-17,25,33-38]與執(zhí)行程序并發(fā)地工作，以更好地利用多處理器系統(tǒng)。目前大多數(shù)并發(fā)收集器在發(fā)起和停止收集工作時(shí)無(wú)需同時(shí)暫停所有工作線程。在線(On-the-fly)收集器不同時(shí)停止所有工作線程，每個(gè)工作線程按自身的步調(diào)與收集器通過(guò)一種軟握手[36-37]機(jī)制協(xié)作。

2.1 滑動(dòng)視圖

在對(duì)象槽發(fā)生變化時(shí)，通過(guò)寫(xiě)屏障將對(duì)象槽的地址和槽的原值存入線程局部緩存中，每個(gè)對(duì)象槽有一個(gè)相應(yīng)的臟標(biāo)記位[16-17]。文獻(xiàn)首先描述了快照算法(snapshot algorithm)[39]，由于算法在發(fā)起收集工作時(shí)需要凍結(jié)所有的工作線程，依次讀取每個(gè)線程的緩存區(qū)和線程棧內(nèi)的地址后才喚醒工作線程，因此，快照算法引發(fā)較長(zhǎng)的暫停時(shí)間且不能較好地利用處理器資源。

為避免長(zhǎng)時(shí)間的暫停和可伸縮性問(wèn)題，文獻(xiàn)[16-17]提出了滑動(dòng)視圖算法。算法在讀取緩存區(qū)和線程棧內(nèi)指針時(shí)僅凍結(jié)一個(gè)工作線程，這種增量方式通過(guò)偵聽(tīng)(snoop)機(jī)制和增加軟握手次數(shù)保證了算法的正確性。收集周期開(kāi)始時(shí)設(shè)置每個(gè)工作線程的偵聽(tīng)標(biāo)記為真，收集周期結(jié)束時(shí)偵聽(tīng)標(biāo)記設(shè)為假，工作線程的寫(xiě)屏障代碼判斷偵聽(tīng)標(biāo)記是否為真，若為真值則將目標(biāo)對(duì)象并入線程局部集合中，引用計(jì)數(shù)為零且不在根集和局部集合中的對(duì)象被回收。偵聽(tīng)機(jī)制產(chǎn)生少量的浮動(dòng)垃圾，這些對(duì)象留給下一個(gè)收集周期回收。

對(duì)象槽的原值記錄在局部緩存中，收集線程減少對(duì)象槽原值所指對(duì)象的引用計(jì)數(shù)；當(dāng)槽的臟標(biāo)記為假時(shí)，收集器直接讀取槽的新值，增加對(duì)象的引用計(jì)數(shù)，若槽的臟標(biāo)記為真，收集器需要再次從工作線程的局部緩存中獲得待更新引用計(jì)數(shù)的對(duì)象?；瑒?dòng)視圖算法進(jìn)行4次軟握手，第1次握手獲取工作線程的局部緩存，收集器異步地清除對(duì)象槽的臟標(biāo)記；第2次握手再次讀取局部緩存，以設(shè)置緩存區(qū)中被異步清除的臟標(biāo)記；第3次握手確保工作線程發(fā)現(xiàn)恢復(fù)的臟標(biāo)記；第4次握手獲取根集。

2.2 衍生收集器

滑動(dòng)視圖算法衍生了一些高性能短暫停的并發(fā)垃圾收集器[19,40-42]，文獻(xiàn)[41]基于滑動(dòng)視圖算法實(shí)現(xiàn)了在線的全局跟蹤收集器。并發(fā)收集器通常以寫(xiě)屏障保護(hù)工作線程修改的對(duì)象，以防止過(guò)早地回收可達(dá)對(duì)象。文獻(xiàn)[41]的寫(xiě)屏障代碼從3個(gè)方面提高了工作程序的效率：收集器在活躍時(shí)修改的對(duì)象才存入緩存區(qū)；修改的對(duì)象只有發(fā)生在開(kāi)始收集之后進(jìn)入跟蹤階段之前才需要存入緩存區(qū)；修改的對(duì)象僅需存入緩存區(qū)一次。每個(gè)對(duì)象有一個(gè)字大小空間的臟標(biāo)記，當(dāng)對(duì)象的指針存入緩存區(qū)時(shí)，臟標(biāo)記指向緩存區(qū)中對(duì)象指針存入的位置。

文獻(xiàn)[42]在滑動(dòng)視圖算法基礎(chǔ)上提出引用計(jì)數(shù)結(jié)合跟蹤收集的方法，研究了引用計(jì)數(shù)和分代收集方法組合的3種設(shè)計(jì)方案，其中引用計(jì)數(shù)收集年長(zhǎng)一代且跟蹤方法收集年輕一代的方法獲得了最好的性能。分代收集器將堆空間劃分為若干部分，通過(guò)預(yù)留一位指示對(duì)象是“新的”或是“老的”，從而在邏輯上將堆分為兩代。跟蹤方法收集年輕一代避免了在跟蹤和清掃階段訪問(wèn)老一代對(duì)象，縮小了問(wèn)題空間。

文獻(xiàn)[15]實(shí)現(xiàn)了第一個(gè)并發(fā)的環(huán)收集算法，算法分為兩個(gè)階段：第一個(gè)階段記錄潛在的環(huán)垃圾，由于工作線程與收集線程并發(fā)地執(zhí)行，收集過(guò)程中工作線程可能破壞了對(duì)象圖；第二個(gè)階段在下一個(gè)收集周期證實(shí)這些潛在的環(huán)垃圾能否安全回收，算法存在不完全性[15,42]和低效率[12,42]的缺陷。文獻(xiàn)[42]在滑動(dòng)視圖和嘗試刪除算法的基礎(chǔ)上解決了這兩個(gè)問(wèn)題，算法結(jié)合了分代收集方法[19,42]，進(jìn)一步減少了需要被跟蹤的候選環(huán)對(duì)象。

3 收集器比較

性能低和不能回收環(huán)是引用計(jì)數(shù)方法面臨的兩個(gè)主要問(wèn)題，表2和表3從性能改善、回收環(huán)、引用計(jì)數(shù)溢出、是否并發(fā)、寫(xiě)屏障是否存在鎖競(jìng)爭(zhēng)和對(duì)象是否移動(dòng)等6個(gè)方面對(duì)產(chǎn)生重要影響的引用計(jì)數(shù)收集器進(jìn)行比較，其中少數(shù)文獻(xiàn)忽略對(duì)引用計(jì)數(shù)存儲(chǔ)位數(shù)或溢出處理方法的描述，少量文獻(xiàn)沒(méi)有給出與對(duì)象槽更新相應(yīng)的寫(xiě)屏障代碼，未命名的收集器以文獻(xiàn)第一作者名表示。對(duì)象移動(dòng)壓縮堆空間，減少分配對(duì)象操作的開(kāi)銷，但并發(fā)收集移動(dòng)對(duì)象會(huì)引起較大的代價(jià)，大部分收集器在并發(fā)收集時(shí)不移動(dòng)對(duì)象[43]。

文獻(xiàn)[25]描述了Modula-2+編程語(yǔ)言的垃圾收集器，收集器識(shí)別線程棧內(nèi)的指針是保守式的[44]，這消除了收集器對(duì)編譯器的依賴。保守式的指針識(shí)別方法從來(lái)不過(guò)早地回收對(duì)象，保證了程序的正確性，但會(huì)引起非常少量的內(nèi)存泄漏。

表2 收集器處理主要問(wèn)題比較

從表3可以看出，不同收集器采用不同位數(shù)存儲(chǔ)引用計(jì)數(shù)，根據(jù)文獻(xiàn)[3]的研究結(jié)果，最大引用計(jì)數(shù)為1的對(duì)象占68.2%，最大引用計(jì)數(shù)為3的對(duì)象占95.4%，最大引用計(jì)數(shù)為6的對(duì)象占99%。引用計(jì)數(shù)溢出時(shí)延遲計(jì)數(shù)和哈希表被采用的機(jī)會(huì)大致相當(dāng)，延遲計(jì)數(shù)的性能優(yōu)于哈希表，延遲計(jì)數(shù)總體節(jié)約了1%的時(shí)間，節(jié)約了收集器13%的時(shí)間[3]。

表3 收集器處理其他問(wèn)題比較

4 結(jié)束語(yǔ)

本文綜述了引用計(jì)數(shù)自動(dòng)回收內(nèi)存方法存在的問(wèn)題與解決的方法，對(duì)當(dāng)前取得的研究進(jìn)展進(jìn)行了歸納與分析。將改進(jìn)效率的方法歸納為減少引用計(jì)數(shù)更新、避免鎖競(jìng)爭(zhēng)和改進(jìn)對(duì)象布局等3類，將回收環(huán)垃圾方法分為嘗試刪除和指針著色兩類；介紹了如何利用一個(gè)字大小的引用計(jì)數(shù)空間和解決偶爾的長(zhǎng)暫停問(wèn)題；闡述了并發(fā)收集方法的研究成果。對(duì)典型的引用計(jì)數(shù)垃圾收集器進(jìn)行了分析比較，在減少引用計(jì)數(shù)更新方面，推遲的方法被所有收集器采用，結(jié)合分代與改進(jìn)對(duì)象布局的方法是最近出現(xiàn)的研究趨勢(shì)。嘗試刪除的局部跟蹤算法被一些收集器采用；而可靠的指針著色回收環(huán)垃圾算法的復(fù)雜性是指數(shù)階的，直到2014年的ISMM國(guó)際會(huì)議上發(fā)表了線性復(fù)雜性的、并發(fā)的算法。但指針著色算法能否被采用仍然面臨著挑戰(zhàn)，程序中存在著大量的指針，為每個(gè)指針增加額外的空間以描述指針的狀態(tài)，這顯然有待商榷。

[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

賀建立，男，安徽宿松人，博士，安慶師范學(xué)院計(jì)算機(jī)與信息學(xué)院講師，主要研究方向?yàn)閯?dòng)態(tài)內(nèi)存管理。

時(shí)間：2016-1-5 13:01 網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160105.1301.011.html

計(jì)數(shù)垃圾收集方法綜述

TP311.52

A

1007-4260(2015)04-0041-07