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