一種基于半空間的不完全拷貝垃圾回收機制

吳 昊，季振洲

(哈爾濱工業(yè)大學計算機科學與技術學院，150001哈爾濱，wuhaoster@gmail.com)

在一些面向對象程序設計語言中，如Java，支持自動內(nèi)存管理的機制已經(jīng)被廣泛地接受，其重要原因就是自動內(nèi)存管理可以有效地克服手動內(nèi)存管理的缺陷.傳統(tǒng)的手動內(nèi)存管理的缺陷主要體現(xiàn)在2個方面:1)程序員使用內(nèi)存操作函數(shù)進行分配和回收內(nèi)存，當由于疏忽或錯誤造成程序沒有及時釋放已不再使用的內(nèi)存，就會造成內(nèi)存泄露，降低程序性能;2)如果程序頻繁地申請和釋放不同大小的內(nèi)存，會產(chǎn)生大量細小的無法分配的空閑內(nèi)存，也就是內(nèi)存碎片，內(nèi)存碎片同樣會導致系統(tǒng)性能的下降.隨著程序規(guī)模和復雜程度越來越大，自動內(nèi)存管理顯得越來越重要.

自動內(nèi)存管理是由垃圾回收器來完成，大部分的垃圾回收器都是由一組根指針開始遍歷所有被這些根指針直接或間接引用的對象，最后把沒有被遍歷到的對象作為垃圾回收.經(jīng)典的半空間垃圾回收算法屬于追蹤類垃圾回收算法的一種，其優(yōu)點是回收過程簡單且不產(chǎn)生內(nèi)存碎片，但缺點也很明顯，主要體現(xiàn)在:1)回收過程中對象拷貝的時間開銷大;2)內(nèi)存始終僅有1/2被利用，浪費了1/2的內(nèi)存.目前，在垃圾回收算法中，針對不同特征的對象或者在不同的回收階段使用不同的回收策略來提高垃圾回收性能的改進方式越來越被關注.這其中一個成功的應用就是基于年代的垃圾回收機制，它將對象按生命周期進行分類，通過減少對具有較長生命周期的對象的拷貝提高回收的性能.針對半空間垃圾回收的不足，本文嘗試將對象按大小分類，通過減少對大對象的拷貝的方式提高半空間垃圾回收的性能，減少時間開銷.

1 相關工作

目前的垃圾收集算法中，依據(jù)區(qū)分活動對象和垃圾方式的不同，可以把回收算法分為:引用計數(shù)式、追蹤式和分代式垃圾回收算法.引用計數(shù)方式圾圾回收算法最適合用于實時應用，但由于其不能解決循環(huán)引用而帶來的內(nèi)存泄露問題，因此常常作為輔助的方式配合其他方式的回收;追蹤式垃圾回收算法能有效的克服引用計數(shù)的不足，它是由一組根節(jié)點遍歷整個對象引用圖，遍歷到的對象標記為活動對象，沒有標記的對象被認為是垃圾將被回收;分代式垃圾回收算法將堆內(nèi)存劃分為不同的區(qū)域，用來存放不同“年齡”的對象，根據(jù)不同生命的對象采用不同的回收策略，分代式垃圾回收算法往往能獲得較好的性能.

在實時垃圾回收方面，Bacon[1]通過設計低開銷的讀攔截方式，有效地降低回收過程的內(nèi)存碎片并在回收過程中降低拷貝發(fā)生的次數(shù);Auerbach[2]設計了一個支持實時垃圾回收的 Java虛擬機，作為核心模塊之一的回收器Metronome是一個基于時間調(diào)度的支持異步回收機制的回收器，可以很好地滿足實時性要求;在此基礎上，設計了Tax-and-Spend[3]的調(diào)度機制，融合了多個現(xiàn)有的實時垃圾回收調(diào)度機制，在不同的應用需求下來決策使用不同的調(diào)度策略;Kalibera[4]通過優(yōu)化對象在堆上的讀寫方式，設計了一個低內(nèi)存碎片且滿足實時需求的回收機制.

為了滿足硬實時系統(tǒng)任務對垃圾回收的時限要求，Henriksso等[5－7]提出將垃圾回收作為單獨的實時任務參與調(diào)度來保證實時性，而不是由任務操作觸發(fā).此外，Garner[8]認為在追蹤遍歷階段的消耗，影響了系統(tǒng)的性能，并通過預取的方式進行了改進;Chen等[9]針對嵌入式，內(nèi)存受限條件下提出如何進行回收性能調(diào)優(yōu)，并詳細闡述了在內(nèi)存受限的結構中垃圾回收的重要性;Siebert[10]分析了多核環(huán)境下的標記清除方式的垃圾回收，并給出了最壞的情況下性能提升的上界.

2 不完全拷貝回收

2.1 追蹤類算法比較

在追蹤類的垃圾回收算法中，垃圾回收器從一組根結點開始，依次遍歷所有對象，并識別出哪些是活動的對象，哪些是垃圾對象，非活動的對象所占的內(nèi)存由回收器收回.此類算法中比較成熟的是標記清除算法(mark-sweep)和半空間拷貝算法(semispace).標記清除算法將垃圾回收工作分為2個階段:1)在遍歷過程中定位并標記所有的活動對象;2)清除回收所有未被標記的對象，為了避免因此帶來內(nèi)存碎片，回收過程也會采取對內(nèi)存進行壓縮的策略.半空間拷貝回收與標記清除回收不同的是:半空間算法將內(nèi)存劃分為2個大小相等的空間，分別稱為起始空間(from-space)和到達空間(to-space).回收開始前，所有對象都存放在起始空間，一旦回收工作啟動，在遍歷過程中將發(fā)現(xiàn)的活動對象依次移動到到達空間，當回收工作完成時，所有的活動對象都被移動到到達空間，起始空間的內(nèi)存整體回收，下次回收啟動時再將2個空間的角色互換.半空間回收是一種高效的回收機制，但是需要浪費1/2的內(nèi)存空間，表1比較了2種追蹤類回收算法.

表1 2種追蹤類回收算法比較

2.2 算法思想

相比標記清除回收，半空間算法不需要考慮內(nèi)存碎片的壓縮問題，在執(zhí)行效率上優(yōu)勢明顯.但半空間算法需要進行大量的內(nèi)存拷貝，對象的個數(shù)及大小決定了該回收算法的執(zhí)行速度，因此減少拷貝是算法性能提升的關鍵.半空間的算法的另一優(yōu)勢是在內(nèi)存回收過程中不會產(chǎn)生內(nèi)存碎片，這也是在改進過程中需要考慮的因素.在如何減少拷貝上，本文的出發(fā)點是減少大對象發(fā)生拷貝的次數(shù).大對象、大數(shù)組在回收拷貝過程中耗費較多的時間，被認為是影響系統(tǒng)實時性的主要因素，在文獻[1，3]中對大對象的生命周期及空間分布特點總結為:1)大對象往往是生命周期較長的對象;2)大對象通常在內(nèi)存空間分布上有一定的連續(xù)性.本文認為其合理性主要體現(xiàn)在:1)大對象的加載工作集中在系統(tǒng)的啟動階段，符合實時系統(tǒng)的一般特征;2)頻繁的加載－棄用大對象的行為只存在少數(shù)的應用之中.在此基礎上，本文提出了一種改進的不完全拷貝的半空間回收算法，算法的主要機制為:1)在回收的遍歷階段，只對活動的大對象采取只標記不拷貝的策略，被標記的對象仍留在起始空間;2)增加一個整理階段，僅當起始空間的碎片程度較大時才執(zhí)行整理.按上述2點改進的算法的合理性主要體現(xiàn)在:根據(jù)條件1)算法體現(xiàn)了按對象生命長度進行分代回收的思想;在滿足條件1)、2)的前提下，算法仍可以維護一個較低水平的內(nèi)存碎片程度;相比標記－清除回收，算法增加的整理過程代價要小，與半空間拷貝相比，算法拷貝的代價要小.

2.3 算法描述

圖1給出了不完全拷貝回收的流程.算法使用半空間策略，在初始階段將內(nèi)存劃分為2個等大小的區(qū)域:1)到達空間(to-space);2)起始空間(from-space)，在回收前所有對象都存放在起始空間.當垃圾回收工作時，初始化2個變量Nlive，Ngar分別用來記錄活動的大對象和垃圾的大對象，在LargeObj中判斷該對象是否滿足預先設定的大對象條件.在第1個階段，算法分別遍歷所有的活動對象和垃圾對象，對于活動的大對象需要進行標記并更新計數(shù)Nlive，其他的活動對象則直接拷貝到到達空間;對于被識別為垃圾的大對象，僅需要更新計數(shù)Ngar.在第2個階段利用Nlive，Ngar評估當前起始空間的碎片程度，當碎片度滿足預先給定的上限時則需要在起始空間進行一次內(nèi)存整理.在整理的過程中僅需要移動在第1階段被標記的大對象即可.最后起始空間和到達空間角色互換，下次回收在重復上述過程.

圖1 不完全拷貝回收過程

在回收過程中內(nèi)存被劃分為2個等半?yún)^(qū)，每次回收并不對所有的活動對象都進行拷貝，隨著回收工作的進行，活動的大對象在2個半?yún)^(qū)都有分布，但是在每一個回收周期中，垃圾對象只產(chǎn)生于FROM-SPACE角色的半?yún)^(qū)中.

圖2 內(nèi)存回收及整理的過程

由上述算法可知，垃圾回收的工作分為2個階段來完成:1)對象拷貝的過程;2)當內(nèi)存碎片達到一定程度時執(zhí)行半?yún)^(qū)內(nèi)的內(nèi)存整理過程.圖2演示了執(zhí)行2個階段內(nèi)存回收工作的過程.假設以圖2(a)為起始的內(nèi)存狀態(tài)，在FROMSPACE 半?yún)^(qū)遍歷的過程中發(fā)現(xiàn) S1、S2、S3、S4這4個活動對象需要移動，然后回收器把它們拷貝到TO-SPACE半?yún)^(qū)中，如圖2(b)所示.在遍歷過程的同時記錄下被識別為垃圾的大對象，以確定是否有必要進行內(nèi)存整理.在第2階段，對如圖2(b)所示的FROM-SPACE進行內(nèi)存整理，由左到右依次將活動的大對象進行移動，整理完成時狀態(tài)如圖2(c)所示，F(xiàn)ROM-SPACE垃圾全部回收.在下一次執(zhí)行回收前將FROM-SPACE和TO-SPACE的角色互換，然后再重復上述回收過程.在內(nèi)存碎片程度不高的情況下，算法僅需要對一部分活動的對象進行拷貝，且拷貝的對象都不是大對象;在最壞的情況下，算法需要對FROM-SPACE半?yún)^(qū)進行整理，但并不需要對全部的大對象進行拷貝，由于是不完全的半空間回收，隨著程序的執(zhí)行大對象在內(nèi)存的2個半空間都有分布，而回收和整理只在FROM-SPACE半?yún)^(qū)進行.

3 實驗結果

3.1 實驗平臺

為了對不完全拷貝垃圾回收的性能進行評估，本文采用2種基準測試來檢驗算法的有效性.本文使用虛擬機平臺為 Apache-Harmony 5.0[11]提供的Java虛擬機DRLVM，在該平臺上設計了本文提出的不完全拷貝垃圾回收回收算法.在實驗中，使用的是比較公認的Java虛擬機性能基準測試程序 SPECjvm2008[12]和 Dacapo[13].具體的實驗環(huán)境及測試項目如表2所示.

表2 實驗平臺及測試環(huán)境

3.2 實驗1:SPECjvm2008基準測試

SPECjvm2008是一個觀測JRE運行性能的基準測試套件.它的測試用例涵蓋了大部分Java基礎應用場景，是架構選型和VM性能評測的重要依據(jù).本實驗中選中的6項測試涵蓋了多線程圖片渲染、矩陣運算、音頻解碼、不對稱加密、壓縮算法和普通 Java編譯這些應用.在實驗中，使用SPECjvm2008分別對使用不完全拷貝回收的虛擬機和使用半空間回收的虛擬機進行基準評測，并給出比較的結果.圖3是 2種回收算法在SPECjvm2008下的基準評測得分結果，包括6個項目的評測得分和最后的平均得分(composite).測試得分反映了虛擬機執(zhí)行基準測試的吞吐性能，得分越高表示在單位時間內(nèi)執(zhí)行的操作數(shù)越多.可以看出相比半空間回收，使用不完全拷貝回收的虛擬機的基準評測得分要高一些.

圖3 SPECjvm2008基準測試實驗結果

3.3 實驗2:垃圾回收性能測試

在SPECjvm2008的6項基準測試中，主要是對使用不同的垃圾回收算法的虛擬機的綜合性能進行比較.而Dacapo的測試程序集更側重于對Java虛擬機的內(nèi)存管理方面的評估.在測試中，本文對Dacapo的7項測試的每一項重復執(zhí)行10次，然后統(tǒng)計運行每一項測試的平均耗時并統(tǒng)計垃圾回收的情況，對于垃圾回收分別記錄下了平均的回收次數(shù)和平均耗時以及最大耗時，測試結果如表3所示.

表3 Dacapo基準測試結果

回收耗時反應了在執(zhí)行垃圾回收過程造成的應用程序停頓時間，平均的回收耗時是衡量一個回收算法性能的重要指標，實驗2比較了2種垃圾回收算法的平均回收時間的情況.由圖4可以看出相比半空間垃圾回收不完全拷貝回收的平均時間開銷較小，在平均的垃圾回收耗時上本文的算法相比經(jīng)典的半空間回收降低了1/4左右.

圖4 Dacapo測試下的平均回收耗時

4 結論

1)深入研究了追蹤類垃圾回收的原理，針對傳統(tǒng)的半空間垃圾回收的不足，提出了將對象分類并進行不完全拷貝回收的改進方法.

2)基于半空間的不完全拷貝回收機制，考慮了大對象的生命周期及空間分布特點，通過減少對大對象的拷貝次數(shù)、降低內(nèi)存碎片以及內(nèi)存壓縮開銷等方式來提高半空間垃圾回收的性能.

3)基準測試及對比實驗驗證了算法的有效性，表明該方法可以有效地降低回收的平均時間開銷，提高了半空間垃圾回收的實時性.

[1]BACON D F，CHENG P，RAJAN V T.A real-time garbage collector with low overhead and consistent utilization[C]//Proceedings of the 30thAnnual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.New York，NY:ACM，2003:285－298.

[2]AUERBACH J，BACON D F，BLAINEY B，et al.Design and implementation of a comprehensive real-time Java virtual machine[C]//Proceedings of The 7thACM/IEEE International Conference on Embedded Software.New York，NY:ACM，2007:249－258.

[3]AUERBACH J，BACON D F，CHENG P，et al.Taxand-spend:Democratic scheduling for real-time garbage collection[C]//Proceedings of the 7thACM International Conference on Embedded software.New York，NY:ACM，2008:245－254.

[4]KALIBERA T.Replicating real-time garbage collector for Java[C]//Proceedings of the 7th International Workshop on Java Technologies for Real-time and Embedded Systems.New York，NY:ACM，2009:100－109.

[5]HENRIKSSON R.Scheduling Garbage Collection in Embedded Systems[D].Sweden:PhD thesis，Lund U-niversity，1998.

[6]ROBERTZ S G，HENRIKSSON R.Time-triggered garbage collection:Robust and adaptive real-time GC scheduling for embedded systems[C]//ACM SIGPLAN 2003 Conference on Languages，Compilers，and Tools for Embedded Systems.New York，NY:ACM，2003:93 －102.

[7]BACON D F，CHENG P，RAJAN V T.Controlling fragmentation and space consumption in the Metronome，a real-time garbage collector for Java[C]//Proceedings of the Conference on Languages，Compilers，and Tools for Embedded Systems.New York，NY:ACM，2003:81－92.

[8]GARNER R，BLACKBURN S M，F(xiàn)RAMPTON D.Effective prefetch for mark-sweep garbage collection[C]//Proceedings of the 6thInternational Symposium on Memory Management.New York，NY:ACM，2007:43－54.

[9]CHEN G，SHETTY R，KANDEMIR M，et al.Tuning garbage collection for reducing memory system energy in an embedded java environment[J].ACM Transactions on Embedded Computing Systems，2002，1(1):27 －55.

[10]SIEBERT F.Limits of parallel marking garbage collection[C]//Proceedings of the 7th International Symposium on Memory Management.New York，NY:ACM，2008:21－29.

[11]The Apache Software Foundation.Dynamic Runtime Layer Virtual Machine Developer's Guide[EB/OL].[2009-11-18].http://harmony.apache.org./subcomponents/drlvm/developers_guide.html.

[12]Standard Performance Evaluation Corporation.SPECjvm2008 Run and Reporting Rules[EB/OL].[2008-04-14].http://www.spec.org/jvm 2008/docs/Runrules.html.

[13]BLACKBURN S M，GARNER R.The DaCapo Benchmarks:Java benchmarking development and analysis[C]//Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-oriented Programing， Systems，Languages，and Applications.New York，NY:ACM，2006:169－190.