密海英(蘇州工業(yè)職業(yè)技術(shù)學(xué)院　江蘇蘇州　215104)

?

Java虛擬機(jī)垃圾收集算法的研究和改進(jìn)

密海英
(蘇州工業(yè)職業(yè)技術(shù)學(xué)院江蘇蘇州215104)

摘要:Java虛擬機(jī)垃圾算法是Java核心功能。當(dāng)前垃圾回收算法滿足絕大部分的應(yīng)用場合，實(shí)時(shí)性的應(yīng)用場合對算法性能提出更高的要求，為此研究了當(dāng)前的虛擬機(jī)垃圾收集算法并提出了一種適用于實(shí)時(shí)性環(huán)境的Java虛擬機(jī)垃圾收集算法。該算法對收集器中堆空間的劃分方式、對象跟蹤等方面進(jìn)行了改進(jìn)，以減少垃圾收集帶來的不確定性暫停，用戶可以指定一個(gè)時(shí)間段內(nèi)垃圾收集導(dǎo)致應(yīng)用程序暫停的最長時(shí)間，從而使其適用于實(shí)時(shí)性環(huán)境。

關(guān)鍵詞:垃圾收集;實(shí)時(shí)性;增量式收集器;堆空間劃分

0　引言

垃圾收集機(jī)制(GC)是Java語言的優(yōu)勢，也是Java虛擬機(jī)的核心功能，它提高了軟件的可靠性，特別是內(nèi)存管理這方面，實(shí)現(xiàn)了管理的自動化，使開發(fā)者提高了效率，減少了跟蹤內(nèi)存錯誤的時(shí)間。如懸空指針和內(nèi)存泄漏問題在Java程序中再也不會發(fā)生了，這樣開發(fā)人員可以集中精力于算法和程序的邏輯設(shè)計(jì)，提高軟件的功能和質(zhì)量。但由于GC的運(yùn)行，目前的GC通常會導(dǎo)致應(yīng)用程序中的不確定性暫停，大部分情形下這種短暫的不確定暫?？梢越邮?。但實(shí)時(shí)應(yīng)用程序?qū)和r(shí)間要求更高，這種不確定的暫停限制了Java在游戲開發(fā)、工業(yè)控制等新興的實(shí)時(shí)性要求高的領(lǐng)域中的應(yīng)用。

提高GC的實(shí)時(shí)性是提高應(yīng)用程序?qū)崟r(shí)性的一個(gè)主要途徑。本文首先研究并且介紹現(xiàn)有的垃圾收集器的各種算法，使用新的算法將垃圾收集過程導(dǎo)致的整個(gè)程序級別的時(shí)間暫?？刂圃谝粋€(gè)可以設(shè)定的范圍內(nèi)，在此算法基礎(chǔ)上在堆分區(qū)、掃描、垃圾回收時(shí)間估算等方面進(jìn)行優(yōu)化改進(jìn)，使其更好地適用于實(shí)時(shí)性要求高的環(huán)境，并通過在不同情形下進(jìn)行實(shí)驗(yàn)來驗(yàn)證改進(jìn)后的性能。

1　垃圾收集基本算法研究和當(dāng)前的瓶頸

垃圾收集器的核心是識別和回收不可到達(dá)的對象，不同的垃圾收集實(shí)現(xiàn)使用不同的策略來完成，它們與用戶程序和調(diào)度器以不同的方式互動。有幾種垃圾收集的基本策略:引用計(jì)數(shù)、標(biāo)記—清除、標(biāo)記—整理和復(fù)制［1］。此外，還可以按照系統(tǒng)運(yùn)行方式來分類算法，串行收集必須在用戶程序暫停時(shí)進(jìn)行整個(gè)收集，并行或并發(fā)收集是使用多線程進(jìn)行收集來提高效率。

1.1垃圾回收基本算法研究

引用計(jì)數(shù)是最基本的垃圾收集策略，早期的JVM采用此算法，但是缺點(diǎn)也很明顯，如它不能回收不可到達(dá)的循環(huán)結(jié)構(gòu)以及需要監(jiān)控每一次的內(nèi)存操作;標(biāo)志—清除算法主要包括掃描標(biāo)志所有被應(yīng)用對象，然后清除未引用對象兩個(gè)步驟，最大的不足是執(zhí)行時(shí)需要暫停整個(gè)程序，以及容易在堆中產(chǎn)生碎片;復(fù)制算法創(chuàng)新地提出把堆一分為二，其中一個(gè)區(qū)域包含當(dāng)前使用的活躍的數(shù)據(jù)，另一個(gè)區(qū)域未使用，垃圾回收時(shí)，遍歷當(dāng)前已經(jīng)使用的有相關(guān)活躍對象的區(qū)域，把正在使用中的對象從當(dāng)前區(qū)域復(fù)制到另外一個(gè)區(qū)域中，性能好，而且不會有碎片，主要問題就是必須要兩倍的內(nèi)存空間;標(biāo)記—整理算法則是結(jié)合了標(biāo)記—清除和復(fù)制這兩個(gè)算法的優(yōu)點(diǎn)［2］，避免了需要兩倍內(nèi)存空間的問題，但增加了不少復(fù)雜性，該算法也是分兩階段，第一階段從對象根節(jié)點(diǎn)開始標(biāo)記所有被引用對象，第二階段遍歷整個(gè)堆，清除未標(biāo)記對象并且把存活對象“壓縮”到堆的其中一塊，按內(nèi)存順序排放;分代收集利用統(tǒng)計(jì)學(xué)分析的方法來提高效率，分析表明大多數(shù)內(nèi)存塊(90%)的生存周期都比較短，垃圾收集器應(yīng)當(dāng)把更多的精力放在檢查和清理新分配的內(nèi)存塊上，它是基于對象的生存周期統(tǒng)計(jì)分析后得出的算法，把對象分為年青代(年輕的新生對象)、年老代(經(jīng)過幾次回收仍然存活的對象)、持久代(靜態(tài)文件、JAVA類、方法等)，對不同生命周期的對象使用不同的算法(如標(biāo)記整理)進(jìn)行回收。

1.2垃圾回收的瓶頸

經(jīng)過不斷的算法創(chuàng)新和改進(jìn)，垃圾回收方式已經(jīng)在內(nèi)存空間效率和CPU時(shí)間效率兩個(gè)方面有了非常大的提升。但仍然無法解決完全GC帶來的暫停問題。在一些對實(shí)時(shí)性要求很高的應(yīng)用情形下(如期望返回時(shí)間在幾百毫秒以內(nèi))［3］，如果分代垃圾回收方式要達(dá)到這個(gè)指標(biāo)，只能把最大堆的設(shè)置限制在一個(gè)較小范圍內(nèi)，但是這樣又和應(yīng)用本身的處理能力產(chǎn)生很大的矛盾，同樣也是不能接受的。即垃圾收集的周期，以及每次收集的時(shí)間還是不確定。

2　新改進(jìn)的算法

新改進(jìn)的算法主要目標(biāo)是在不犧牲堆空間利用效率和CPU性能的前提下達(dá)到準(zhǔn)實(shí)時(shí)(可以設(shè)定和控制GC最大暫停時(shí)間)，如0.5秒。這個(gè)特性對于準(zhǔn)實(shí)時(shí)響應(yīng)的系統(tǒng)(如電信系統(tǒng))而言非常重要［4］，因?yàn)檫@樣就再也不用擔(dān)心系統(tǒng)會突然暫停兩秒這種情況的發(fā)生了。

為了能夠達(dá)到期望的目標(biāo)，新的算法在原有的各種算法上進(jìn)行了吸收和改進(jìn)，第一方面:新算法吸收了增量GC，將整個(gè)虛擬機(jī)堆劃分為多個(gè)固定大小的區(qū)域［5］，這樣通過先在空間維度上的劃分，然后在小粒度上處理收集的方法，為實(shí)現(xiàn)整個(gè)實(shí)時(shí)性目標(biāo)打下一個(gè)基礎(chǔ)。第二方面，采用了并發(fā)的快照掃描算法，進(jìn)行全局范圍的未到達(dá)對象周期性完整掃描。同時(shí)掃描時(shí)統(tǒng)計(jì)了每個(gè)小區(qū)域中的活躍對象。這個(gè)信息幫助后續(xù)選擇哪一個(gè)區(qū)域進(jìn)行回收。第三方面，采用新的選擇回收機(jī)制估算區(qū)域級垃圾回收時(shí)間，然后根據(jù)限值選擇相應(yīng)的區(qū)域。

2.1新算法堆分區(qū)和區(qū)域結(jié)構(gòu)

新算法將堆劃分為多個(gè)固定大小的區(qū)域，每個(gè)區(qū)域都是在內(nèi)存中一塊連續(xù)的區(qū)域。當(dāng)一塊區(qū)域放滿后，會申請新的一塊區(qū)域來存放，空的區(qū)域用鏈表結(jié)構(gòu)組織起來。區(qū)域之間的對象引用通過“關(guān)系集合”來維護(hù)，對于巨大的對象，如超過一個(gè)區(qū)域的一半以上，用專用的一個(gè)堆來處理這類對象。每個(gè)區(qū)域都有一個(gè)關(guān)系集合，關(guān)系集合中包含了從其他區(qū)域中引用當(dāng)前區(qū)域中相關(guān)對象的引用地址，隨著程序的操作，新引用或解除當(dāng)前區(qū)域中的一個(gè)對象都會在關(guān)系集合中做出相應(yīng)的修改。這個(gè)關(guān)系集合主要維護(hù)跨區(qū)域的對象引用聯(lián)系。如圖1所示，區(qū)域1，3中都引用了區(qū)域2的對象b，所以區(qū)域2關(guān)系集合中維護(hù)了相應(yīng)的關(guān)系。這些區(qū)域中對象的引用關(guān)系不斷地發(fā)生改變，新算法采用了卡片表來通知區(qū)域修改“關(guān)系集合”，每個(gè)應(yīng)用的線程都有一個(gè)關(guān)聯(lián)的關(guān)系集合記錄，用于緩存和順序化線程運(yùn)行時(shí)造成的對于卡片的修改。另外，還有一個(gè)全局的緩存區(qū)，當(dāng)應(yīng)用線程執(zhí)行時(shí)修改了卡片后，如果造成的改變僅為同一區(qū)域中的對象之間的關(guān)聯(lián)，則不記錄關(guān)系集合歷史;如造成的改變?yōu)榭鐓^(qū)域中的對象的關(guān)聯(lián)，則記錄到線程的關(guān)系集合歷史;如線程的關(guān)系集合歷史滿了，則放入全局的緩存區(qū)中，線程自身則重新創(chuàng)建一個(gè)新的關(guān)系集合歷史，關(guān)系集合本身也是一個(gè)由一堆卡片構(gòu)成的哈希表。

圖1　堆分區(qū)和關(guān)系集合

下面是具體垃圾回收執(zhí)行步驟。

2.2初始化標(biāo)記

這是第一個(gè)步驟，支持多線程并發(fā)執(zhí)行。主要任務(wù)是掃描并標(biāo)識出虛擬機(jī)每個(gè)區(qū)域中可直接訪問到的對象。虛擬機(jī)每個(gè)區(qū)域都保存了兩個(gè)標(biāo)識作用的位圖，位圖中每個(gè)元素用來標(biāo)識可到達(dá)的對象。一個(gè)名稱為最近引用的位圖，用來保存最近掃描標(biāo)志的結(jié)果。另外一個(gè)為當(dāng)前引用位圖［6］，用來存放當(dāng)前正在計(jì)算的臨時(shí)結(jié)果。當(dāng)計(jì)算完成時(shí)，會把結(jié)果復(fù)制到最近引用位圖中。位圖中包含了一個(gè)地址信息來指向區(qū)域中對象的起始點(diǎn)。

新算法設(shè)定了相關(guān)的條件來觸發(fā)初始化標(biāo)記這一步驟。定義了一個(gè)虛擬機(jī)堆大小的上限，稱為high，另外還有一個(gè)H，H的值為(1-high)*堆大小，根據(jù)虛擬機(jī)的運(yùn)行情況進(jìn)行動態(tài)的調(diào)整，如果引入分代方式，新算法還定義了一個(gè)限值，當(dāng)堆中使用的內(nèi)存超過了限值時(shí)，就會在一次清除執(zhí)行完畢后在應(yīng)用允許的GC暫停時(shí)間范圍內(nèi)盡快地執(zhí)行此步驟。

2.3遍歷并發(fā)標(biāo)記

根據(jù)前面初始化標(biāo)記掃描到的對象進(jìn)行遍歷，以便識別這些對象的下層對象的活躍狀態(tài)，對于在此期間應(yīng)用線程并發(fā)修改的對象則記錄到關(guān)系集合歷史中，采用開始時(shí)刻點(diǎn)快照的方式進(jìn)行對象遍歷。這一過程是并行執(zhí)行的，不會暫停應(yīng)用程序線程。應(yīng)用程序線程新創(chuàng)建的對象則放入比快照頂端值更高的地址區(qū)間中，這些新創(chuàng)建的對象默認(rèn)狀態(tài)即為活躍的，這一過程同時(shí)修改頂端值的信息。這樣的設(shè)計(jì)不僅可以不影響應(yīng)用程序，而且提高了效率。由于是并行的環(huán)境，在做并發(fā)標(biāo)記掃描時(shí)還需要處理一種情況，就是其他程序修改當(dāng)前快照里的對象應(yīng)用。系統(tǒng)允許這樣的修改，但是需要記錄這樣的修改到后續(xù)步驟處理它。

2.4標(biāo)記停止

標(biāo)志停止這個(gè)點(diǎn)除了需要滿足遍歷所有對象和清空當(dāng)前的標(biāo)志堆棧事件這兩個(gè)條件外，還需要處理前面一步由于其它線程的修改保留下來的記錄。前面兩個(gè)條件容易判斷，后一個(gè)條件處理比較困難。因?yàn)檫@些記錄放在相關(guān)的線程中，需要等待相應(yīng)線程操作結(jié)束后處理，有可能會引起一些等待。

2.5存活計(jì)算活對象和清除

前面有提過采用新的機(jī)制為了達(dá)到準(zhǔn)實(shí)時(shí)目標(biāo)。主要的算法根據(jù)前面統(tǒng)計(jì)的活躍對象數(shù)，設(shè)計(jì)算法比較精確地估算出每個(gè)區(qū)域的垃圾回收時(shí)間，如公式(1)所示。同時(shí)根據(jù)系統(tǒng)設(shè)定的目標(biāo)最大暫停時(shí)間，來選擇活躍對象最少、垃圾對象最多、收集最快的區(qū)域進(jìn)行回收，這樣能保證最有效率，而且暫停時(shí)間最短。如果超過設(shè)定的目標(biāo)最大暫停時(shí)間，系統(tǒng)會推遲收集來權(quán)衡目標(biāo)，通過一段時(shí)間，會有更多的非活躍對象。

tc表示收集當(dāng)前區(qū)域估算所需時(shí)間成本，C表示固定的一些步驟開銷。A表示掃描卡片的平均時(shí)間，N表示卡片數(shù)量，T表示從關(guān)系結(jié)合中掃描出卡片的時(shí)間，size(r)表示在關(guān)系集合r中卡片數(shù)。S表示每個(gè)字節(jié)的掃描成本，active(r)表示當(dāng)前區(qū)域r中的存活字節(jié)數(shù)量。

在新算法中，標(biāo)記停止步驟執(zhí)行完，不一定會執(zhí)行清除這一步驟，由于清除步驟需要暫停應(yīng)用對系統(tǒng)有一定的影響，新算法為了能夠達(dá)到準(zhǔn)實(shí)時(shí)的要求，需要根據(jù)用戶指定的最大的GC暫停時(shí)間設(shè)定和公式(1)估算出的時(shí)間成本相結(jié)合來合理地規(guī)劃清除動作。另外還有一些情況也會觸發(fā)清除這個(gè)步驟的執(zhí)行［7］，如新算法在采用復(fù)制方法的特殊步驟情形下，采取的是當(dāng)已經(jīng)使用的內(nèi)存空間達(dá)到了上限時(shí)，就執(zhí)行清除這個(gè)策略以保證有足夠的空間用來做復(fù)制動作。再比如新算法在分代模式的情形下，根據(jù)用戶指定的可接受的暫停時(shí)間和回收年輕代區(qū)域需要消耗的時(shí)間來估算出一個(gè)年輕代區(qū)域存活的數(shù)量的最大值，當(dāng)虛擬機(jī)中分配對象的年輕區(qū)域存活的數(shù)量達(dá)到此值時(shí)，就會執(zhí)行清除。

在這一過程中，在一些特定的情形下，會采用疏散壓縮的計(jì)算來提高效率，主要是針對比較新的計(jì)算。比如說發(fā)現(xiàn)絕大部分當(dāng)前區(qū)域的對象可以被回收掉，會立刻執(zhí)行回收清除動作，然后剩下的對象疏散到其他區(qū)域，這樣的動作非常大地提高了效率，而且支持并發(fā)執(zhí)行。這樣在多處理器的環(huán)境下更能提高效率。

整個(gè)新算法步驟如圖2所示，用雙箭頭的表示可以并發(fā)執(zhí)行。

圖2　新算法執(zhí)行步驟

運(yùn)用新算法是為了盡量做到準(zhǔn)實(shí)時(shí)的響應(yīng)，例如估算暫停時(shí)間的算法、對于經(jīng)常被引用的對象的特殊處理等，運(yùn)用新算法也是為了能夠讓GC既能夠充分地回收內(nèi)存，又能夠盡量少地導(dǎo)致應(yīng)用的暫停。

3　實(shí)驗(yàn)結(jié)果與分析

通過在幾種典型的準(zhǔn)實(shí)時(shí)應(yīng)用場景中進(jìn)行實(shí)驗(yàn)，對新算法和增量式垃圾回收算法在垃圾回收效率、平均暫停時(shí)間、暫停次數(shù)及堆空間使用等方面進(jìn)行比較［8］，如表1所示。運(yùn)用新算法后各方面都有比較大的性能提升。新算法使用C語言實(shí)現(xiàn)，而增量式垃圾回收算法直接使用Sun JDK提供的算法。實(shí)驗(yàn)的應(yīng)用場景包括一個(gè)大型的游戲應(yīng)用和一個(gè)企業(yè)級的產(chǎn)品管理系統(tǒng)。

同時(shí)還可以根據(jù)應(yīng)用的情況，調(diào)節(jié)參數(shù)使系統(tǒng)達(dá)到比較好的狀態(tài)。

表1　垃圾回收性能比較表

4　結(jié)束語

為了實(shí)現(xiàn)準(zhǔn)實(shí)時(shí)的目標(biāo)，本文提出了一種新的垃圾回收算法，在堆空間劃分、并發(fā)掃描及區(qū)域垃圾回收成本等方面做了很大的改進(jìn)，將因垃圾收集而導(dǎo)致的程序暫停時(shí)間和次數(shù)限制在一個(gè)可以設(shè)定的范圍內(nèi)，并可以通過相關(guān)的配置參數(shù)的調(diào)節(jié)，達(dá)到一個(gè)在時(shí)間和空間成本比較高效率的狀態(tài)，滿足了實(shí)時(shí)性應(yīng)用所要求的短暫停，并且在應(yīng)用環(huán)境下取得了令人比較滿意的效果，這對于有巨大緩存的各種應(yīng)用而言，會有很大的幫助。

參考文獻(xiàn):

［1］Bill Venners.深入Java虛擬機(jī)［M］.曹曉鋼，蔣勁，譯.北京:機(jī)械工業(yè)出版社，2003:241-242.

［2］SACHINDRANN，ELIOT J，MOSS B.Mark-copy:fast copying GC with less space overhead［C］//Proc of the 18th ACM SIGPLAN OO-PSLA.NewYork:ACM，2003:326-343.

［3］張寧，熊光澤.基于關(guān)鍵引用驗(yàn)證的分布式實(shí)時(shí)垃圾搜集器［J］.計(jì)算機(jī)應(yīng)用研究，2009(11):4036-4038.

［4］BAKERHG.List processing inreal-time on a serial computer［J］.Communications of the ACM，1978(4):280-294.

［5］郭慶琳，李艷梅，唐琦.基于VSM的文本相似度計(jì)算的研究［J］.計(jì)算機(jī)應(yīng)用研究，2008(11):3256-3258.

［6］趙苑苑，王萬誠，黃廣君，等.無用內(nèi)存單元自動回收過程的實(shí)時(shí)性問題研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2006(2):137-139.

［7］CHEN G，KANDEMIR M，VIJAYKRISHNAN N，et al.Heap Compression for Memory Constrained Java Environments［A］.OOPSLA‘03［C］.Anaheim，CaIifornia，USA.2003(10):282-301.

［8］CHEN G，KANDEMIR M，VIJAYKRISHNAN N，et al.Penn-Bench:A Benchmark Suite for Embedded Java［A］.DATE‘03［C］.Munich，Germany.2002(11):71-80.

Research and Improvement of Java Virtual Machine Garbage Collection Algorithm

MI Haiying
(Suzhou Institute of Industrial Technology，Suzhou 215104，China)

Abstract:GC(garbage collection)algorithm is the key function of Java.The current algorithm can satisfy most application situation.The real-time environment requires high performance of GC algorithm.So this paper studies current GC algorithm and describes a new garbage collection algorithm for real-time environment.The algorithm improves the division of heap and reference tracking of the incremental garbage collection algorithm for reducing the uncertain pauses caused by garbage collection;furthermore，it provides users to give a biggest time value that the application paused in a certain period.All of these make it suitable for real-time environment.

Key words:garbage collection(GC);real-time;incremental garbage collection;division of heap

作者簡介:密海英(1980-)，女，講師、工程師，主要研究方向:軟件工程、web系統(tǒng)開發(fā)

收稿日期:2016-01-11

中圖分類號:TP 311.1

文獻(xiàn)標(biāo)志碼:A

文章編號:1672-2434(2016)01-0036-04