垃圾回收算法

1.垃圾回收需要做什么

Java垃圾回收器需要做的三件事：

1、哪些內(nèi)存需要回收？即如何判斷對象已經(jīng)死亡；

2、什么時候回收？即GC發(fā)生在什么時候？需要了解GC策略，與垃圾回收器實現(xiàn)有關(guān)；

3、如何回收？即需要了解垃圾回收算法，及算法的實現(xiàn)--垃圾回收器；

2.如何判斷對象可被回收

? 垃圾收集器對堆進行回收前，首先要確定堆中的對象哪些還"存活"，哪些已經(jīng)"死去"。有兩種算法，分別是引用計數(shù)算法(Recference Counting)和可達性分析算法(Reachability Analysis)。

2.1 引用計數(shù)算法

2.1.1 算法思路

給對象添加一個引用計數(shù)器，每當有一個地方引用它，計數(shù)器加1；當引用失效，計數(shù)器值減1；任何時刻計數(shù)器值為0，則認為對象是不再被使用的；

2.1.2 優(yōu)點

• 實現(xiàn)簡單、垃圾便于辨識；
• 判定效率高，回收沒有延遲。

2.1.2 缺點

• 需要單獨的字段存儲計數(shù)器，額外的存儲空間開銷
• 需要更新計數(shù)器，伴隨著加法和減法操作，帶來時間開銷
• 無法處理循環(huán)引用的情況

循環(huán)引用的例子：

public class RefCountGC {
    //這個成員屬性唯一的作用就是占用一點內(nèi)存
    private byte[] bigSize = new byte[5 * 1024 * 1024];//5MB
    Object reference = null;
    public static void main(String[] args) {
        RefCountGC obj1 = new RefCountGC();
        RefCountGC obj2 = new RefCountGC();
        obj1.reference = obj2;
        obj2.reference = obj1;
        obj1 = null;
        obj2 = null;
        //顯式的執(zhí)行垃圾回收行為
        //這里發(fā)生GC，obj1和obj2能否被回收？ 能被回收，是因為JVM采用的不是引用計數(shù)算法。所以obj1和obj2能被回收。這里反向證明了JVM沒有采用引用計數(shù)算法。
        System.gc();
        try {
            Thread.sleep(1000000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

2.2 可達性分析算法

2.2.1 算法思路

? 通過一系列的GC Roots的對象作為起始點，從這些根節(jié)點開始向下搜索，搜索所走過的路徑稱為引用鏈（Reference Chain），當一個對象到GC Roots沒有任何引用鏈相連時，則證明此對象是不可用的。

2.2.2 GC Roots對象（兩棧兩方法）

• 虛擬機棧（棧幀中的本地變量表）中引用的對象
• 本地方法棧中 JNI（即一般說的 Native 方法）引用的對象
• 方法區(qū)中類靜態(tài)屬性引用的對象
• 方法區(qū)中常量引用的對象

2.2.3 優(yōu)點

更加精確和嚴謹，可以分析出循環(huán)數(shù)據(jù)結(jié)構(gòu)相互引用的情況；主流的編程語言Java c#的選擇。

2.2.4 缺點

• 消耗大量時間

從前面可達性分析知道，GC Roots主要在全局性的引用（常量或靜態(tài)屬性）和執(zhí)行上下文中（棧幀中的本地變量表）；
要在這些大量的數(shù)據(jù)中，逐個檢查引用，會消耗很多時間；

• GC停頓

可達性分析期間需要保證整個執(zhí)行系統(tǒng)的一致性，對象的引用關(guān)系不能發(fā)生變化；
導(dǎo)致GC進行時必須停頓所有Java執(zhí)行線程（稱為"Stop The World"）；
（幾乎不會發(fā)生停頓的CMS收集器中，枚舉根節(jié)點時也是必須要停頓的） Stop The World： 是JVM在后臺自動發(fā)起和自動完成的； 在用戶不可見的情況下，把用戶正常的工作線程全部停掉；

3.判斷對象生存還是死亡

3.1 兩次標記過程

要真正宣告一個對象死亡，至少要經(jīng)歷兩次標記過程。

1、第一次標記

在可達性分析后發(fā)現(xiàn)到GC Roots沒有任何引用鏈相連時，被第一次標記；并且進行一次篩選：此對象是否必要執(zhí)行finalize()方法；

（A）、沒有必要執(zhí)行

沒有必要執(zhí)行的情況：（1）、對象沒有覆蓋finalize()方法；（2）、finalize()方法已經(jīng)被JVM調(diào)用過；這兩種情況就可以認為對象已死，可以回收；

（B）、有必要執(zhí)行

對有必要執(zhí)行finalize()方法的對象，被放入F-Queue隊列中；稍后在JVM自動建立、低優(yōu)先級的Finalizer線程（可能多個線程）中觸發(fā)這個方法；

2、第二次標記

GC將對F-Queue隊列中的對象進行第二次小規(guī)模標記；finalize()方法是對象逃脫死亡的最后一次機會： （A）、如果對象在其finalize()方法中重新與引用鏈上任何一個對象建立關(guān)聯(lián)，第二次標記時會將其移出"即將回收"的集合；（B）、如果對象沒有，也可以認為對象已死，可以回收了；
一個對象的finalize()方法只會被系統(tǒng)自動調(diào)用一次，經(jīng)過finalize()方法逃脫死亡的對象，第二次不會再調(diào)用；

3.2 finalize()方法

finalize()是Object類的一個方法，是Java剛誕生時為了使C/C++程序員容易接受它所做出的一個妥協(xié)，但不要當作類似C/C++的析構(gòu)函數(shù)；因為它執(zhí)行的時間不確定，甚至是否被執(zhí)行也不確定（Java程序的不正常退出），而且運行代價高昂，無法保證各個對象的調(diào)用順序（甚至有不同線程中調(diào)用）；如果需要"釋放資源"，可以定義顯式的終止方法，并在"try-catch-finally"的finally{}塊中保證及時調(diào)用，如File相關(guān)類的close()方法； 此外，finalize()方法主要有兩種用途：

1、充當"安全網(wǎng)"

當顯式的終止方法沒有調(diào)用時，在finalize()方法中發(fā)現(xiàn)后發(fā)出警告； 但要考慮是否值得付出這樣的代價； 如FileInputStream、FileOutputStream、Timer和Connection類中都有這種應(yīng)用；

2、與對象的本地對等體有關(guān)

本地對等體：普通對象調(diào)用本地方法（JNI）委托的本地對象；
? 本地對等體不會被GC回收；?
? 如果本地對等體不擁有關(guān)鍵資源，finalize()方法里可以回收它（如C/C++中malloc()，需要調(diào)用free()）；?
? 如果有關(guān)鍵資源，必須顯式的終止方法；?
? 一般情況下，應(yīng)盡量避免使用它，甚至可以忘掉它。

4.HotSpot虛擬機中對象可達性分析的實現(xiàn)

4.1 枚舉根節(jié)點

枚舉根節(jié)點也就是查找GC Roots；

目前主流JVM都是準確式GC，可以直接得知哪些地方存放著對象引用，所以執(zhí)行系統(tǒng)停頓下來后，并不需要全部、逐個檢查完全局性的和執(zhí)行上下文中的引用位置；

在HotSpot中，是使用一組稱為OopMap的數(shù)據(jù)結(jié)構(gòu)來達到這個目的的；在類加載時，計算對象內(nèi)什么偏移量上是什么類型的數(shù)據(jù)；在JIT編譯時，也會記錄棧和寄存器中的哪些位置是引用；這樣GC掃描時就可以直接得知這些信息；

4.2 安全點

4.2.1 安全點是什么，為什么需要安全點

HotSpot在OopMap的幫助下可以快速且準確的完成GC Roots枚舉，但是這有一個問題：
運行中，非常多的指令都會導(dǎo)致引用關(guān)系變化；如果為這些指令都生成對應(yīng)的OopMap，需要的空間成本太高；問題解決：

只在特定的位置記錄OopMap引用關(guān)系，這些位置稱為安全點（Safepoint）；即程序執(zhí)行時并非所有地方都能停頓下來開始GC；

4.2.2 安全點的選定

不能太少，否則GC等待時間太長；也不能太多，否則GC過于頻繁，增大運行時負荷；所以，基本上是以程序"是否具有讓程序長時間執(zhí)行的特征"為標準選定；"長時間執(zhí)行"最明顯的特征就是指令序列復(fù)用，如：方法調(diào)用、循環(huán)跳轉(zhuǎn)、循環(huán)的末尾、異常跳轉(zhuǎn)等； 只有具有這些功能的指令才會產(chǎn)生Safepoint；

4.2.3 如何在安全點上停頓

對于Safepoint，如何在GC發(fā)生時讓所有線程（不包括JNI線程）運行到其所在最近的Safepoint上再停頓下來？ 主要有兩種方案可選：

（A）、搶先式中斷（Preemptive Suspension）

不需要線程主動配合，實現(xiàn)如下： （1）、在GC發(fā)生時，首先中斷所有線程； （2）、如果發(fā)現(xiàn)不在Safepoint上的線程，就恢復(fù)讓其運行到Safepoint上； 現(xiàn)在幾乎沒有JVM實現(xiàn)采用這種方式；

（B）、主動式中斷（Voluntary Suspension）

（1）、在GC發(fā)生時，不直接操作線程中斷，而是僅簡單設(shè)置一個標志； （2）、讓各線程執(zhí)行時主動去輪詢這個標志，發(fā)現(xiàn)中斷標志為真時就自己中斷掛起
? 而輪詢標志的地方和Safepoint是重合的；? 在JIT執(zhí)行方式下：test指令是HotSpot生成的輪詢指令；? 一條test匯編指令便完成Safepoint輪詢和觸發(fā)線程中斷；

4.3 安全區(qū)域

4.3.1 為什么需要安全區(qū)域

對于上面的Safepoint還有一個問題： 程序不執(zhí)行時沒有CPU時間（Sleep或Blocked狀態(tài)），無法運行到Safepoint上再中斷掛起；
? 這就需要安全區(qū)域來解決；

4.3.2 什么是安全區(qū)域（Safe Region）

指一段代碼片段中，引用關(guān)系不會發(fā)生變化； 在這個區(qū)域中的任意地方開始GC都是安全的；

4.3.3 如何用安全區(qū)域解決問題

安全區(qū)域解決問題的思路：

（1）、線程執(zhí)行進入Safe Region，首先標識自己已經(jīng)進入Safe Region；

（2）、線程被喚醒離開Safe Region時，其需要檢查系統(tǒng)是否已經(jīng)完成根節(jié)點枚舉（或整個GC）；如果已經(jīng)完成，就繼續(xù)執(zhí)行；否則必須等待，直到收到可以安全離開Safe Region的信號通知；

這樣就不會影響標記結(jié)果；

5.垃圾回收算法

5.1 標記清除

標記-清除算法將垃圾回收分為兩個階段：標記階段和清除階段。

標記: Collector 從引用根節(jié)點開始遍歷，標記所有被引用的對象。一般是在對象的Header中記錄為可達對象。
清除: Collector對堆內(nèi)存從頭到尾進行線性的遍歷，如果發(fā)現(xiàn)某個對象在其Header中沒有標記為可達對象，則將其回收。這里所謂的清除并不是真的置空，而是把需要清除的對象地址保存在空閑的地址列表里。下次有新對象需要加載時，判斷垃圾的位置空間是否夠，如果夠，就存放。

適用場合：

• 存活對象較多的情況下比較高效
• 適用于年老代（即舊生代）

缺點：

• 容易產(chǎn)生內(nèi)存碎片，再來一個比較大的對象時（典型情況：該對象的大小大于空閑表中的每一塊兒大小但是小于其中兩塊兒的和），會提前觸發(fā)垃圾回收而且需要維護一個空閑列表
• 效率不算高（第一次：標記存活對象；第二次：清除沒有標記的對象）
• 在進行GC的時候，需要停止整個應(yīng)用程序，導(dǎo)致用戶體驗差

5.2 復(fù)制算法

將活著的內(nèi)存空間分為兩塊，每次只使用其中一塊，在垃圾回收時將正在使用的內(nèi)存中的存活對象復(fù)制到未被使用的內(nèi)存塊中，之后清除正在使用的內(nèi)存塊中的所有對象，交換兩個內(nèi)存的角色，最后完成垃圾收。

?在新生代，對常規(guī)應(yīng)用的垃圾回收，一 次通?？梢曰厥?0%-99%的內(nèi)存空間。回收性價比很高。所以現(xiàn)在的商業(yè)虛擬機都是用這種收集算法回收新生代。

適用場合：

• 存活對象較少的情況下比較高效
• 掃描了整個空間一次（標記存活對象并復(fù)制移動）
• 適用于年輕代（即新生代）：基本上98%的對象是”朝生夕死”的，存活下來的會很少

優(yōu)點：

• 沒有標記和清除過程，實現(xiàn)簡單，運行高效
• 復(fù)制過去以后保證空間的連續(xù)性，不會出現(xiàn)“碎片”問題。

缺點：

• 需要兩倍的內(nèi)存空間
• 對于G1這種分拆成為大量region的GC，復(fù)制而不是移動，意味著GC需要維護region之間對象引用關(guān)系，不管是內(nèi)存占用或者時間開銷也不小

5.3 標記整理

復(fù)制算法的高效性是建立在存活對象少、垃圾對象多的前提下的。

這種情況在新生代經(jīng)常發(fā)生，但是在老年代更常見的情況是大部分對象都是存活對象。如果依然使用復(fù)制算法，由于存活的對象較多，復(fù)制的成本也將很高。

執(zhí)行過程：

標記-壓縮算法的最終效果等同于標記-清除算法執(zhí)行完成后，再進行一次內(nèi)存碎片整理，因此，也可以把它稱為標記-清除-壓縮(Mark- Sweep-Compact)算法。
二者的本質(zhì)差異在于標記-清除算法是一種非移動式的回收算法，標記-壓縮是移動式的。是否移動回收后的存活對象是一-項優(yōu)缺點并存的風(fēng)險決策。
可以看到，標記的存活對象將會被整理，按照內(nèi)存地址依次排列，而未被標記的內(nèi)存會被清理掉。如此一-來，當我們需要給新對象分配內(nèi)存時，JVM只需要持有一個內(nèi)存的起始地址即可，這比維護一個空閑列表顯然少了許多開銷。

優(yōu)點:

• 消除了標記-清除算法當中，內(nèi)存區(qū)域分散的缺點，我們需要給新對象分配內(nèi)存時，JVM只 需要持有一個內(nèi)存的起始地址即可。消除了復(fù)制算法當中，內(nèi)存減半的高額代價。

缺點:

• 從效率上來說，標記-整理算法要低于復(fù)制算法。移動對象的同時，如果對象被其他對象引用，則還需要調(diào)整引用的地址。移動過程中，需要全程暫停用戶應(yīng)用程序。即: STW

對比三種算法

5.4 分代收集算法

把堆內(nèi)存分為新生代和老年代，新生代又分為 Eden 區(qū)、From Survivor 和 To Survivor。一般新生代中的對象基本上都是朝生夕滅的，每次只有少量對象存活，因此采用復(fù)制算法，只需要復(fù)制那些少量存活的對象就可以完成垃圾收集；老年代中的對象存活率較高，就采用標記-清除和標記-整理算法來進行回收。

在這些區(qū)域的垃圾回收大概有如下幾種情況：

在這些區(qū)域的垃圾回收大概有如下幾種情況：

大多數(shù)情況下，新的對象都分配在Eden區(qū)，當 Eden 區(qū)沒有空間進行分配時，將進行一次 Minor GC，清理 Eden 區(qū)中的無用對象。清理后，Eden 和 From Survivor 中的存活對象如果小于To Survivor 的可用空間則進入To Survivor，否則直接進入老年代）；Eden 和 From Survivor 中還存活且能夠進入 To Survivor 的對象年齡增加 1 歲（虛擬機為每個對象定義了一個年齡計數(shù)器，每執(zhí)行一次 Minor GC 年齡加 1），當存活對象的年齡到達一定程度（默認 15 歲）后進入老年代，可以通過 -XX:MaxTenuringThreshold 來設(shè)置年齡的值。

當進行了 Minor GC 后，Eden 還不足以為新對象分配空間（那這個新對象肯定很大），新對象直接進入老年代。

占 To Survivor 空間一半以上且年齡相等的對象，大于等于該年齡的對象直接進入老年代，比如 Survivor 空間是 10M，有幾個年齡為 4 的對象占用總空間已經(jīng)超過 5M，則年齡大于等于 4 的對象都直接進入老年代，不需要等到 MaxTenuringThreshold 指定的歲數(shù)。

在進行 Minor GC 之前，會判斷老年代最大連續(xù)可用空間是否大于新生代所有對象總空間，如果大于，說明 Minor GC 是安全的，否則會判斷是否允許擔保失敗，如果允許，判斷老年代最大連續(xù)可用空間是否大于歷次晉升到老年代的對象的平均大小，如果大于，則執(zhí)行 Minor GC，否則執(zhí)行 Full GC。

當在 java 代碼里直接調(diào)用 System.gc() 時，會建議 JVM 進行 Full GC，但一般情況下都會觸發(fā) Full GC，一般不建議使用，盡量讓虛擬機自己管理 GC 的策略。

永久代（方法區(qū)）中用于存放類信息，jdk1.6 及之前的版本永久代中還存儲常量、靜態(tài)變量等，當永久代的空間不足時，也會觸發(fā) Full GC，如果經(jīng)過 Full GC 還無法滿足永久代存放新數(shù)據(jù)的需求，就會拋出永久代的內(nèi)存溢出異常。

大對象（需要大量連續(xù)內(nèi)存的對象）例如很長的數(shù)組，會直接進入老年代，如果老年代沒有足夠的連續(xù)大空間來存放，則會進行 Full GC。

6.參考

1.JVM：引用計數(shù)算法和可達性分析算法(https://www.zhifou.net/blogdetail/183)

2.4種JVM垃圾回收算法詳解（https://mikechen.cc/7102.html）

3.深入理解Java虛擬機（四）之垃圾回收算法(https://www.codenong.com/cs106639755/)

到此這篇關(guān)于最新JVM垃圾回收算法詳解的文章就介紹到這了,更多相關(guān)JVM垃圾回收算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！