淺談Java虛擬機垃圾收集算法的研究和改進論文
1 垃圾收集基本算法研究和當前的瓶頸
垃圾收集器的核心是識別和回收不可到達的對象，不同的垃圾收集實現(xiàn)使用不同的策略來完成，它們與用戶程序和調(diào)度器以不同的方式互動。有幾種垃圾收集的基本策略: 引用計數(shù)、標記—清除、標記—整理和復(fù)制。此外，還可以按照系統(tǒng)運行方式來分類算法，串行收集必須在用戶程序暫停時進行整個收集，并行或并發(fā)收集是使用多線程進行收集來提高效率。
1. 1 垃圾回收基本算法研究
引用計數(shù)是最基本的垃圾收集策略，早期的JVM 采用此算法，但是缺點也很明顯，如它不能回收不可到達的循環(huán)結(jié)構(gòu)以及需要監(jiān)控每一次的內(nèi)存操作; 標志—清除算法主要包括掃描標志所有被應(yīng)用對象，然后清除未引用對象兩個步驟，最大的不足是執(zhí)行時需要暫停整個程序，以及容易在堆中產(chǎn)生碎片; 復(fù)制算法創(chuàng)新地提出把堆一分為二，其中一個區(qū)域包含當前使用的活躍的數(shù)據(jù)，另一個區(qū)域未使用，垃圾回收時，遍歷當前已經(jīng)使用的有相關(guān)活躍對象的區(qū)域，把正在使用中的對象從當前區(qū)域復(fù)制到另外一個區(qū)域中，性能好，而且不會有碎片，主要問題就是必須要兩倍的內(nèi)存空間; 標記—整理算法則是結(jié)合了標記—清除和復(fù)制這兩個算法的優(yōu)點，避免了需要兩倍內(nèi)存空間的問題，但增加了不少復(fù)雜性，該算法也是分兩階段，第一階段從對象根節(jié)點開始標記所有被引用對象，第二階段遍歷整個堆，清除未標記對象并且把存活對象“壓縮”到堆的其中一塊，按內(nèi)存順序排放; 分代收集利用統(tǒng)計學(xué)分析的方法來提高效率，分析表明大多數(shù)內(nèi)存塊( 90%) 的生存周期都比較短，垃圾收集器應(yīng)當把更多的精力放在檢查和清理新分配的內(nèi)存塊上，它是基于對象的生存周期統(tǒng)計分析后得出的算法，把對象分為年青代( 年輕的新生對象) 、年老代( 經(jīng)過幾次回收仍然存活的對象) 、持久代( 靜態(tài)文件、JAVA 類、方法等) ，對不同生命周期的對象使用不同的算法( 如標記整理) 進行回收。
1. 2 垃圾回收的瓶頸
經(jīng)過不斷的算法創(chuàng)新和改進，垃圾回收方式已經(jīng)在內(nèi)存空間效率和CPU 時間效率兩個方面有了非常大的提升。但仍然無法解決完全GC 帶來的暫停問題。在一些對實時性要求很高的應(yīng)用情形下( 如期望返回時間在幾百毫秒以內(nèi))，如果分代垃圾回收方式要達到這個指標，只能把最大堆的設(shè)置限制在一個較小范圍內(nèi)，但是這樣又和應(yīng)用本身的處理能力產(chǎn)生很大的矛盾，同樣也是不能接受的。即垃圾收集的周期，以及每次收集的時間還是不確定。
2 新改進的算法
新改進的算法主要目標是在不犧牲堆空間利用效率和CPU 性能的前提下達到準實時( 可以設(shè)定和控制GC 最大暫停時間) ，如0. 5 秒。這個特性對于準實時響應(yīng)的系統(tǒng)( 如電信系統(tǒng)) 而言非常重要，因為這樣就再也不用擔心系統(tǒng)會突然暫停兩秒這種情況的發(fā)生了。
為了能夠達到期望的目標，新的算法在原有的各種算法上進行了吸收和改進，第一方面: 新算法吸收了增量GC，將整個虛擬機堆劃分為多個固定大小的區(qū)域[5]，這樣通過先在空間維度上的劃分，然后在小粒度上處理收集的方法，為實現(xiàn)整個實時性目標打下一個基礎(chǔ)。第二方面，采用了并發(fā)的快照掃描算法，進行全局范圍的未到達對象周期性完整掃描。同時掃描時統(tǒng)計了每個小區(qū)域中的活躍對象。這個信息幫助后續(xù)選擇哪一個區(qū)域進行回收。第三方面，采用新的選擇回收機制估算區(qū)域級垃圾回收時間，然后根據(jù)限值選擇相應(yīng)的區(qū)域。
2. 1 新算法堆分區(qū)和區(qū)域結(jié)構(gòu)
新算法將堆劃分為多個固定大小的區(qū)域，每個區(qū)域都是在內(nèi)存中一塊連續(xù)的區(qū)域。當一塊區(qū)域放滿后，會申請新的一塊區(qū)域來存放，空的區(qū)域用鏈表結(jié)構(gòu)組織起來。區(qū)域之間的對象引用通過“關(guān)系集合”來維護，對于巨大的對象，如超過一個區(qū)域的一半以上，用專用的一個堆來處理這類對象。每個區(qū)域都有一個關(guān)系集合，關(guān)系集合中包含了從其他區(qū)域中引用當前區(qū)域中相關(guān)對象的引用地址，隨著程序的操作，新引用或解除當前區(qū)域中的一個對象都會在關(guān)系集合中做出相應(yīng)的修改。這個關(guān)系集合主要維護跨區(qū)域的對象引用聯(lián)系。區(qū)域1，3中都引用了區(qū)域2 的對象b，所以區(qū)域2 關(guān)系集合中維護了相應(yīng)的關(guān)系。這些區(qū)域中對象的引用關(guān)系不斷地發(fā)生改變，新算法采用了卡片表來通知區(qū)域修改“關(guān)系集合”，每個應(yīng)用的線程都有一個關(guān)聯(lián)的關(guān)系集合記錄，用于緩存和順序化線程運行時造成的對于卡片的修改。另外，還有一個全局的緩存區(qū)，當應(yīng)用線程執(zhí)行時修改了卡片后，如果造成的改變僅為同一區(qū)域中的對象之間的關(guān)聯(lián)，則不記錄關(guān)系集合歷史; 如造成的改變?yōu)榭鐓^(qū)域中的對象的關(guān)聯(lián)，則記錄到線程的關(guān)系集合歷史; 如線程的關(guān)系集合歷史滿了，則放入全局的緩存區(qū)中，線程自身則重新創(chuàng)建一個新的關(guān)系集合歷史，關(guān)系集合本身也是一個由一堆卡片構(gòu)成的哈希表。
下面是具體垃圾回收執(zhí)行步驟。
2. 2 初始化標記
這是第一個步驟，支持多線程并發(fā)執(zhí)行。主要任務(wù)是掃描并標識出虛擬機每個區(qū)域中可直接訪問到的對象。虛擬機每個區(qū)域都保存了兩個標識作用的位圖，位圖中每個元素用來標識可到達的對象。一個名稱為最近引用的位圖，用來保存最近掃描標志的結(jié)果。另外一個為當前引用位圖，用來存放當前正在計算的臨時結(jié)果。當計算完成時，會把結(jié)果復(fù)制到最近引用位圖中。位圖中包含了一個地址信息來指向區(qū)域中對象的起始點。
新算法設(shè)定了相關(guān)的條件來觸發(fā)初始化標記這一步驟。定義了一個虛擬機堆大小的上限，稱為high，另外還有一個H，H 的值為( 1-high) * 堆大小，根據(jù)虛擬機的運行情況進行動態(tài)的調(diào)整，如果引入分代方式，新算法還定義了一個限值，當堆中使用的內(nèi)存超過了限值時，就會在一次清除執(zhí)行完畢后在應(yīng)用允許的GC 暫停時間范圍內(nèi)盡快地執(zhí)行此步驟。
2. 3 遍歷并發(fā)標記
根據(jù)前面初始化標記掃描到的對象進行遍歷，以便識別這些對象的下層對象的活躍狀態(tài)，對于在此期間應(yīng)用線程并發(fā)修改的對象則記錄到關(guān)系集合歷史中，采用開始時刻點快照的方式進行對象遍歷。這一過程是并行執(zhí)行的，不會暫停應(yīng)用程序線程。應(yīng)用程序線程新創(chuàng)建的對象則放入比快照頂端值更高的地址區(qū)間中，這些新創(chuàng)建的對象默認狀態(tài)即為活躍的，這一過程同時修改頂端值的信息。這樣的設(shè)計不僅可以不影響應(yīng)用程序，而且提高了效率。由于是并行的環(huán)境，在做并發(fā)標記掃描時還需要處理一種情況，就是其他程序修改當前快照里的對象應(yīng)用。系統(tǒng)允許這樣的修改，但是需要記錄這樣的修改到后續(xù)步驟處理它。
2. 4 標記停止
標志停止這個點除了需要滿足遍歷所有對象和清空當前的標志堆棧事件這兩個條件外，還需要處理前面一步由于其它線程的修改保留下來的記錄。前面兩個條件容易判斷，后一個條件處理比較困難。因為這些記錄放在相關(guān)的線程中，需要等待相應(yīng)線程操作結(jié)束后處理，有可能會引起一些等待。
2. 5 存活計算活對象和清除
前面有提過采用新的機制為了達到準實時目標。主要的算法根據(jù)前面統(tǒng)計的活躍對象數(shù)，設(shè)計算法比較精確地估算出每個區(qū)域的垃圾回收時間，如公式( 1) 所示。同時根據(jù)系統(tǒng)設(shè)定的目標最大暫停時間，來選擇活躍對象最少、垃圾對象最多、收集最快的區(qū)域進行回收，這樣能保證最有效率，而且暫停時間最短。如果超過設(shè)定的目標最大暫停時間，系統(tǒng)會推遲收集來權(quán)衡目標，通過一段時間，會有更多的非活躍對象。
C( tc) = Cfix + A* N +Σr∈tc
( T* size( r) +
S* active( r) ) ( 1)
tc 表示收集當前區(qū)域估算所需時間成本，C 表示固定的一些步驟開銷。A 表示掃描卡片的平均時間，N 表示卡片數(shù)量，T 表示從關(guān)系結(jié)合中掃描出卡片的時間， size( r) 表示在關(guān)系集合r 中卡片數(shù)。S表示每個字節(jié)的掃描成本，active( r) 表示當前區(qū)域r中的存活字節(jié)數(shù)量。
在新算法中，標記停止步驟執(zhí)行完，不一定會執(zhí)行清除這一步驟，由于清除步驟需要暫停應(yīng)用對系統(tǒng)有一定的影響，新算法為了能夠達到準實時的要求，需要根據(jù)用戶指定的最大的GC 暫停時間設(shè)定和公式( 1) 估算出的時間成本相結(jié)合來合理地規(guī)劃清除動作。另外還有一些情況也會觸發(fā)清除這個步驟的執(zhí)行，如新算法在采用復(fù)制方法的特殊步驟情形下，采取的是當已經(jīng)使用的內(nèi)存空間達到了上__限時，就執(zhí)行清除這個策略以保證有足夠的空間用來做復(fù)制動作。再比如新算法在分代模式的情形下，根據(jù)用戶指定的可接受的暫停時間和回收年輕代區(qū)域需要消耗的時間來估算出一個年輕代區(qū)域存活的數(shù)量的最大值，當虛擬機中分配對象的年輕區(qū)域存活的數(shù)量達到此值時，就會執(zhí)行清除。
在這一過程中，在一些特定的情形下，會采用疏散壓縮的計算來提高效率，主要是針對比較新的計算。比如說發(fā)現(xiàn)絕大部分當前區(qū)域的對象可以被回收掉，會立刻執(zhí)行回收清除動作，然后剩下的對象疏散到其他區(qū)域，這樣的動作非常大地提高了效率，而且支持并發(fā)執(zhí)行。這樣在多處理器的環(huán)境下更能提高效率。
運用新算法是為了盡量做到準實時的響應(yīng)，例如估算暫停時間的算法、對于經(jīng)常被引用的對象的特殊處理等，運用新算法也是為了能夠讓GC 既能夠充分地回收內(nèi)存，又能夠盡量少地導(dǎo)致應(yīng)用的暫停。
3 實驗結(jié)果與分析
通過在幾種典型的準實時應(yīng)用場景中進行實驗，對新算法和增量式垃圾回收算法在垃圾回收效率、平均暫停時間、暫停次數(shù)及堆空間使用等方面進行比較。運用新算法后各方面都有比較大的性能提升。新算法使用C 語言實現(xiàn)，而增量式垃圾回收算法直接使用Sun JDK 提供的算法。實驗的應(yīng)用場景包括一個大型的游戲應(yīng)用和一個企業(yè)級的產(chǎn)品管理系統(tǒng)。同時還可以根據(jù)應(yīng)用的情況，調(diào)節(jié)參數(shù)使系統(tǒng)達到比較好的狀態(tài)。
4 結(jié)束語
為了實現(xiàn)準實時的目標，本文提出了一種新的垃圾回收算法，在堆空間劃分、并發(fā)掃描及區(qū)域垃圾回收成本等方面做了很大的改進，將因垃圾收集而導(dǎo)致的程序暫停時間和次數(shù)限制在一個可以設(shè)定的范圍內(nèi)，并可以通過相關(guān)的配置參數(shù)的調(diào)節(jié)，達到一個在時間和空間成本比較高效率的狀態(tài)，滿足了實時性應(yīng)用所要求的短暫停，并且在應(yīng)用環(huán)境下取得了令人比較滿意的效果，這對于有巨大緩存的各種應(yīng)用而言，會有很大的幫助。
【淺談Java虛擬機垃圾收集算法的研究和改進論文】相關(guān)文章：
詳談改進的遺傳算法求解柔性作業(yè)車間調(diào)度問題論文12-16
淺談轉(zhuǎn)爐除塵濁環(huán)系統(tǒng)水泵的優(yōu)化改進論文02-18
淺談全電流不停電啟和停槽技術(shù)的研究與應(yīng)用的論文01-03
淺談小學(xué)作文的閱讀和寫作論文03-09
淺談高校教育教學(xué)改革的研究論文03-25
淺談鑄造橫梁結(jié)構(gòu)改進有限元分析論文02-19
淺談水利工程設(shè)計中存在的問題及改進措施論文03-02
淺談中職化工專業(yè)英語教學(xué)改進探析論文03-16
- 相關(guān)推薦