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

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

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

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

　　1. 1 垃圾回收基本算法研究

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

　　1. 2 垃圾回收的瓶頸

　　經(jīng)過(guò)不斷的算法創(chuàng)新和改進(jìn)，垃圾回收方式已經(jīng)在內(nèi)存空間效率和CPU 時(shí)間效率兩個(gè)方面有了非常大的提升。但仍然無(wú)法解決完全GC 帶來(lái)的暫停問(wèn)題。在一些對(duì)實(shí)時(shí)性要求很高的應(yīng)用情形下( 如期望返回時(shí)間在幾百毫秒以內(nèi))，如果分代垃圾回收方式要達(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è)特性對(duì)于準(zhǔn)實(shí)時(shí)響應(yīng)的系統(tǒng)( 如電信系統(tǒng)) 而言非常重要，因?yàn)檫@樣就再也不用擔(dān)心系統(tǒng)會(huì)突然暫停兩秒這種情況的發(fā)生了。

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

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

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

　　下面是具體垃圾回收?qǐng)?zhí)行步驟。

　　2. 2 初始化標(biāo)記

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

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

　　2. 3 遍歷并發(fā)標(biāo)記

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

　　2. 4 標(biāo)記停止

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

　　2. 5 存活計(jì)算活對(duì)象和清除

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

　　C( tc) = Cfix + A* N +Σr∈tc

　　( T* size( r) +

　　S* active( r) ) ( 1)

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

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

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

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

　　通過(guò)在幾種典型的準(zhǔn)實(shí)時(shí)應(yīng)用場(chǎng)景中進(jìn)行實(shí)驗(yàn)，對(duì)新算法和增量式垃圾回收算法在垃圾回收效率、平均暫停時(shí)間、暫停次數(shù)及堆空間使用等方面進(jìn)行比較。運(yùn)用新算法后各方面都有比較大的性能提升。新算法使用C 語(yǔ)言實(shí)現(xiàn)，而增量式垃圾回收算法直接使用Sun JDK 提供的算法。實(shí)驗(yàn)的應(yīng)用場(chǎng)景包括一個(gè)大型的游戲應(yīng)用和一個(gè)企業(yè)級(jí)的產(chǎn)品管理系統(tǒng)。同時(shí)還可以根據(jù)應(yīng)用的情況，調(diào)節(jié)參數(shù)使系統(tǒng)達(dá)到比較好的狀態(tài)。

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

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

【淺談Java虛擬機(jī)垃圾收集算法的研究和改進(jìn)論文】相關(guān)文章：

畢業(yè)論文資料收集和整理的方法03-22

淺談畢業(yè)論文的特色和創(chuàng)新點(diǎn)02-21

淺談個(gè)人、群體和人類的主體性論文04-07

淺談?wù)Z法翻譯法在中國(guó)的沿革及改進(jìn)04-01

淺談檔案的價(jià)值與作用論文03-10

淺談小學(xué)數(shù)學(xué)中學(xué)生數(shù)學(xué)思維能力的培養(yǎng)研究論文01-08

淺談客戶關(guān)系管理理論產(chǎn)生的背景和動(dòng)因論文03-24

淺談巴金后期小說(shuō)創(chuàng)作的思想主題和藝術(shù)風(fēng)格論文03-21

淺析電子機(jī)械制動(dòng)系統(tǒng)的設(shè)計(jì)和研究論文04-01

基于粒子群算法的分布式論文02-10