JVM：垃圾回收相關算法

文章目錄

• • • 标記階段：引用計數算法
    • • 垃圾标記階段：對象存活判斷
      • 引用計數算法
      • 小結
    • 标記階段：可達性分析算法
    • • 可達性分析（或根搜尋算法、追蹤性垃圾收集）
      • GC Roots
    • 對象的finalization機制
    • MAT與JProfiler的GC Roots溯源
    • • MAT簡介
      • 使用MAT檢視GC Roots
      • 使用JProfiler進行GC Roots溯源
      • 使用JProfiler分析OOM
    • 清除階段：标記-清除算法
    • • 概述
      • 背景
      • 執行過程
      • 示意圖
      • 缺點
      • 特殊說明：何為清除？
    • 清除階段：複制算法
    • • 核心思想
      • 示意圖
      • 優點
      • 缺點
      • 特殊說明
      • 應用場景
    • 清除階段：标記-壓縮算法
    • • 背景
      • 執行過程
      • 優點
      • 缺點
      • 對比三種算法
    • 分代收集算法
    • 增量收集算法、分區算法
    • • 增量收集算法
      • • 背景
        • 基本思想
        • 缺點
      • 分區算法

标記階段：引用計數算法

垃圾标記階段：對象存活判斷

• 在堆裡存放着幾乎所有的Java對象執行個體，在GC執行垃圾回收之前，首先需要區分出記憶體中哪些是存活對象，哪些是已經死亡的對象。隻有被标記為已經死亡的對象，GC才會在執行垃圾回收時，釋放其所占用的記憶體空間，是以這個過程稱為垃圾标記階段
• 在JVM中究竟如何标記一個死亡對象呢？當一個對象已經不再被任何的存活對象繼續引用時，就可以宣判為已經死亡
• 判斷對象存活一般有兩種方式：引用計數算法和可達性分析算法

引用計數算法

• 引用計數算法（Reference Counting）比較簡單，對每個對象儲存一個整型的引用計數器屬性。用于記錄對象被引用的情況

對于一個對象A，隻要有任何一個對象引用了A，則A的引用計數器就加1；當引用失效時，引用計數器就減1，隻要對象A的引用計數器的值為0，即表示對象A不可能在被使用，可進行回收

• 優點：實作簡單，垃圾對象便于辨識；判定效率高，回收沒有延遲性
• 缺點：
  1. 他需要單獨的字段存儲計數器，這樣的做法增加了存儲空間的開銷
  2. 每次指派都需要更新計數器，伴随着加法和減法操作，增加了時間開銷
  3. 引用計數器有一個嚴重的問題，無法處理循環引用的情況，這是一條緻命缺陷，導緻在Java的垃圾回收器中沒有使用這類算法

循環引用示意圖

代碼示範

public class RefCountGC {
    //這個成員屬性唯一的作用就是占用一點記憶體
    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;
        //顯式的執行垃圾回收行為，語句1
        System.gc();
    }
}
           

如上圖，如果不小心直接把

Obj1-reference

和

Obj2-reference

重置為null，則在Java堆當中的兩塊記憶體依然保持着互相引用，無法回收

小結

• 引用計數算法，是很多語言的資源回收選擇，例如Python，他更是同時支援引用計數和垃圾收集機制
• 具體哪種最優是要看場景的，業界有大規模實踐中僅保留引用計數機制，以提高吞吐量的嘗試
• Java并沒有選擇引用計數，是因為其存在一個基本的難題，也就是很難處理循環引用關系
• Python如何解決循環引用問題的呢？
  1. 手動解除：就是在合适的時機，解除引用關系
  2. 使用弱引用weakref，weakref是Python提供的标準庫，旨在解決循環引用

标記階段：可達性分析算法

可達性分析（或根搜尋算法、追蹤性垃圾收集）

• 相對于引用計數算法而言，可達性分析算法不僅同樣具備實作簡單和執行高效等特點，更重要的是該算法可以有效地解決在引用計數算法中循環引用的問題，防止記憶體洩露的發生
• 相較于引用計數算法，這裡的可達性分析就是Java、C#選擇的。這種類型的垃圾收集通常也叫作追蹤性垃圾收集（Tracing Garbage Collection）
• 所謂

  GC Roots

  根集合就是一組必須活躍的引用
• 基本思路
  1. 可達性分析算法是以根對象集合（GC Roots）為起始點，按照從上至下的方式搜尋被根對象集合所連接配接的目标對象是否可達
  2. 使用可達性分析算法後，記憶體中的存活對象都會被根對象集合直接或間接連接配接着，搜尋所走過的路徑成為引用鍊（Reference Chain）
  3. 如果目标對象沒有任何引用鍊相連，則是不可達的，就意味着該對象已經dead，可以标記為垃圾對象
  4. 在可達性分析算法中，隻有能夠被根對象集合直接或間接連接配接的對象才是存活對象

可達性算法示意圖

GC Roots

在Java語言中，GC Roots包括以下幾類元素

1. 虛拟機棧中引用的對象

   例如：各個線程被調用的方法中使用到的參數、局部變量等

2. 本地方法棧内JNI（本地方法）引用的對象

3. 方法區中類靜态屬性引用的對象

   例如：Java類的引用類型靜态變量

4. 方法區中常量引用的對象

   例如：字元串常量池（String Table）裡的引用

5. 所有被同步鎖

   synchronized

   持有的對象

6. Java虛拟機内部的引用

   基本資料類型對應的Class對象，一些常駐的異常對象（如：

   NullPointException

   、

   OutOfMemoryError

   ），系統類加載器
7. 反映Java虛拟機内部情況的JMXBean、JVMTI中注冊的回調、本地代碼緩存等
8. 除了這些固定的GC Roots集合以外，根據使用者所選用的垃圾回收器以及目前回收的記憶體區域不同，還可以有其他對象

   臨時性

   地加入，共同構成完整GC Roots集合。例如，分代收集和局部回收（Partial GC）
   1. 如果隻針對Java堆中的某一塊區域進行垃圾回收，（比如，典型的隻針對新生代），必須考慮到記憶體區域是虛拟機自己的實作細節，更不是孤立封閉的，這個區域的對象完全有可能被其他區域的對象所引用，這時候就需要一個并将關聯的區域對象也加入GC Roots集合中去考慮，才能保證可達性分析的準确性
9. 技巧：由于Root采用棧方式存放變量和指針，是以如果一個指針，它儲存了堆記憶體裡面的對象，但是自己又不存放在堆記憶體 裡面，那它就是一個Root

特殊說明

• 如果要是用可達性分析算法來判斷記憶體是否可回收，那麼分析工作必須在一個能保障一緻性的快照中進行。這點不滿足的話分析結果的準确性就無法保證
• 以上也是導緻GC進行時必須

  Stop The World

  的一個重要原因。即使是号稱（幾乎）不會發生停頓的CMS收集器中，枚舉根節點時也是必須要停頓的

對象的finalization機制

• Java語言提供了對象終止（

  finalization

  ）機制來允許開發人員提供對象被銷毀之前的自定義處理邏輯
• 當垃圾回收器發現沒有引用指向一個對象，即：垃圾回收此對象之前，總會先調用這個對象的

  finalize()

  方法

• finalize()

  方法允許在子類中被重寫，用于在對象被回收時進行資源釋放。通常在這個方法中進行一些資源釋放和清理的工作，比如關閉檔案、套接字和資料庫連接配接等
• 永遠不要主動調用某個對象的

  finalize()

  方法，應該交給垃圾回收機制調用。理由有以下幾點：
  1. 在

     finalize()

     時可能會導緻對象複活

  2. finalize()

     方法的執行時間是沒有保障的，他完全由GC線程決定，極端情況下，若不發生GC，則

     finalize()

     方法将沒有執行的機會
  3. 一個糟糕的

     finalize()

     會嚴重影響GC的性能
• 從功能上來說，

  finalize()

  方法與C++中的析構函數比較相似，但是Java采用的是基于垃圾回收器的自動記憶體管理機制，是以

  finalize()

  方法在本質上不同于C++中的析構函數
• 由于

  finalize()

  方法的存在，虛拟機中的對象一般處于三種可能的狀态
• 如果從所有的根節點都無法通路到某個對象，說明對象已經不再使用了。一般來說，此對象需要被回收。但事實上，也并非是

  非死不可

  的，這時候他們暫時處于

  緩刑

  階段。一個無法觸及的對象有可能在某一個條件下

  複活

  自己，如果這樣，那麼對它的回收就是不合理的，為此，定義虛拟機中的對象可能的三種狀态，如下
  1. 可觸及的：從根節點開始，可以到達這個對象
  2. 可複活的：對象的所有引用都被釋放，但是對象有可能在

     finalize()

     中複活
  3. 不可觸及的：對象的

     finalize()

     被調用，并且沒有複活，那麼就會進入不可觸及狀态。不可觸及的對象不可能被複活，因為==

     finalize()

     隻會被調用一次==
• 以上3種狀态中，是由于

  finalize()

  方法的存在，進行的區分。隻有在對象不可觸及時才可以被回收

具體過程

判定一個對象A是否可回收，至少要經曆

兩次标記

過程

1. 如果對象A到GC Roots沒有引用鍊，則進行第一次标記
2. 進行篩選，判斷此對象是否有必要執行

   finalize()

   方法

   ①如果對象A沒有重寫

   finalize()

   方法，或者

   finalize()

   方法已經被虛拟機調用過，則虛拟機視為沒有必要執行，對象A被判定為不可觸及的

   ②如果對象A重寫了

   finalize()

   方法，且還未執行過，那麼對象A會被插入到F-Queue隊列中，由一個虛拟機自動建立的、低優先級的Finalizer線程觸發其

   finalize()

   方法執行

   finalize()

   方法是對象逃脫死亡的最後機會，稍後GC會對F-Queue隊列中的對象進行第二次标記，如果A在

   finalize()

   方法中與引用鍊上的任何一個對象建立聯系，那麼在第二次标記時，A會被移出

   即将回收

   集合，之後，對象會再次出現沒有引用存在的情況，在這種情況下，

   finalize()

   方法不會被再次調用，對象會直接程式設計不可觸及的狀态，也就是說，一個對象的

   finalize()

   方法隻會被調用一次

MAT與JProfiler的GC Roots溯源

MAT簡介

• MAT是Memory Analyzer的簡稱，它是一款功能強大的Java堆記憶體分析器。用于查找記憶體洩漏以及檢視記憶體消耗情況
• MAT是基于Eclipse開發的，是一款免費的性能分析工具

擷取dump檔案

**方式1：通過指令行的形式擷取，指令行使用

jmap**

方式2：使用JVisualVM導出

• 捕獲的heap dump檔案是一個臨時檔案，關閉JVisual VM後自動删除，若要保留，需要将其另存為檔案
• 可以通過以下方法捕獲heap dump：
  1. 在左側的"Application"子視窗中右擊相應的應用程式，選擇Heap Dump
  2. 在Monitor子标簽頁中點選Heap Dump按鈕
• 本地應用程式的Heap dumps作為應用程式标簽頁的一個子标簽頁打開。同時，heap dump在左側的Application欄中對應一個含有時間戳的節點。右擊這個節點選擇save as即可将heap dump儲存到本地

使用MAT檢視GC Roots

示範代碼

public class GCRootsTest {
    public static void main(String[] args) {
        List<Object> numList = new ArrayList<>();
        Date birth = new Date();

        for (int i = 0; i < 100; i++) {
            numList.add(String.valueOf(i));
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        System.out.println("資料添加完畢，請操作：");// 在此處，使用JvisualVM導出dump檔案
        new Scanner(System.in).next();
        // 釋放引用
        numList = null;
        birth = null;

        System.out.println("numList、birth已置空，請操作：");// 在此處，再次使用JvisualVM導出dump檔案
        new Scanner(System.in).next();
        System.out.println("結束");
    }
}
           

使用MAT來分析兩次導出的dump檔案

從上圖可知，隻有30多行的代碼就存在這1700個GC Root。

在實際情況下，很少擷取全部的GC Root，一來是GC Root節點太多，擷取時間太長；二來擷取全部後分析與定位不友善

使用JProfiler進行GC Roots溯源

使用JProfiler分析OOM

清除階段：标記-清除算法

概述

• 當成功區分出記憶體中存活對象和死亡對象後，GC接下來的任務就是執行垃圾回收，釋放無用對象所占用的記憶體空間，以便有足夠的可用記憶體空間為新對象配置設定記憶體
• 目前在JVM中比較常用的三種垃圾收集算法是标記-清除算法（Mark-Sweep）、複制算法（Copying）、标記-壓縮算法（Mark-Compact）

背景

标記-清除算法（Mark-Sweep）是一種非常基礎和常見得垃圾收集算法，該算法被J.McCarthy等人在1960年提出并應用于Lisp語言

執行過程

當堆中的有效記憶體空間（

available memory

）被耗盡的時候，就會停止整個程式（也就是Stop The World），然後進行兩項工作：第一項是标記，第二項則是清除

• 标記：Collector從引用根節點開始周遊，标記所有被引用的對象。一般是在對象的Header中記錄為可達對象
• 清除：Collector對堆記憶體從頭到尾進行線性的周遊，如果發現某個對象在其Header中沒有标記為可達對象，則将其回收

示意圖

缺點

• 效率不算高
• 在進行GC的時候，需要停止整個應用程式，導緻使用者體驗差
• 這種方式清理出來的空閑記憶體是不連續的，産生記憶體碎片。需要維護一個空閑清單

特殊說明：何為清除？

這裡所謂的清除并不是真的置空，而是把需要清除的對象位址儲存在空閑的位址清單裡，下次有新對象需要加載時，判斷垃圾的位置空間是否夠，如果夠，就存放

清除階段：複制算法

核心思想

将活着的記憶體空間分為兩塊，每次隻使用其中一塊，在垃圾回收時将正在使用的記憶體中的活對象複制到未被使用的記憶體塊中，之後清除正在使用的記憶體塊中所有對象，交換兩個記憶體的角色，最後完成垃圾回收

示意圖

優點

• 沒有标記和清除的過程，實作簡單，運作高效
• 複制過去以後保證空間的連續性，不會出現“碎片”問題

缺點

• 該算法的缺點也是很明顯的，需要兩倍的記憶體空間
• 對于G1這種分拆成為大量的region的GC，複制而不是移動，意味着GC需要維護region之間的對象引用關系，不管是記憶體占用或者時間開銷也不小

特殊說明

如果系統中的垃圾對象很多，複制算法需要複制的存活對象數量并不會太大，或者說非常低才行

應用場景

在新生代，對正常應用的垃圾回收，一次通常可以回收70%~99%的記憶體空間。回收成本效益很高。是以現在的商業虛拟機都是用這種收集算法回收新生代

清除階段：标記-壓縮算法

背景

• 複制算法的高效性是建立在存活對象少，垃圾對象多的前提下的。這種情況在新生代經常發生，但是在老年代，更常見的情況是大部分對象都是存活對象。如果依然使用複制算法，由于存活對象較多，複制的成本也将很高。是以，基于老年代垃圾回收的特性，需要使用其他的算法
• 标記-清除算法的确可以應用在老年代中，但是該算法不僅執行效率低下，而且在執行完記憶體回收後還會産生記憶體碎片，是以JVM的設計者需要在此基礎上進行改進。标記-壓縮算法由此誕生

執行過程

• 第一階段和标記清除算法一樣，從根節點開始标記所有被引用的對象
• 第二階段将所有的存活對象壓縮到記憶體的一端，按順序排放，之後清理邊界外所有的空間

标記-壓縮算法的最終效果等同于标記-清除算法執行完成後，再進行一次記憶體碎片整理，是以，也可以把它稱為标記-清除-壓縮（Mark-Sweep-Compact）算法

兩者的本質差異在于标記-清除算法是一種非移動式的回收算法，标記-壓縮是移動式的。是否移動回收後的存活對象是一項優缺點并存的風險決策

可以看到，标記的存活對象将會被整理，按照記憶體位址依次排列，而未被标記的記憶體會被清理掉。如此一來，當我們需要給新對象配置設定記憶體時，JVM隻需要持有一個記憶體的起始位址即可，這比維護一個空閑清單顯然少了許多開銷

優點

• 消除了标記-清除算法當中，記憶體區域分散的缺點，需要給新對象配置設定記憶體時，JVM隻需要持有一個記憶體的起始位址即可
• 消除了複制算法當中，記憶體減半的高額代價

缺點

• 從效率上來看，标記-整理算法要低于複制算法
• 移動對象的同時，如果對象被其他對象引用，則還需要調整引用的位址
• 移動過程中，需要全程暫停使用者應用程式，即：STW

對比三種算法

Mark-Sweep算法	Mark-Compact算法	Copying算法
速度	中等	最慢	最快
空間開銷	少（但會堆積碎片）	少（不堆積碎片）	通常需要活對象的2倍大小（不堆積碎片）
移動對象	否	是	是

效率上來說，複制算法是當之無愧的老大，但是卻浪費了太多記憶體

而為了盡量兼顧上面提到的三個名額，标記-整理算法相對來說更平滑一些，但是效率上不盡如人意，他比複制算法多了一個标記階段，比标記-清除多了一個整理記憶體的階段。

分代收集算法

• 有沒有一種最優算法呢？——沒有最好的算法，隻有最合适的算法
• 前面的算法中，并沒有一種算法可以完全替代其他算法，他們都具有自己獨特的優勢和特點。分代收集算法應運而生
• 分代收集算法，是基于不同的對象的生命周期是不一樣的。是以，不同生命周期的對象可以采取不同的收集方式，以便提高回收效率。一般是把Java堆分為新生代和老年代，這樣就可以根據各個年代的特點使用不同的回收算法，以提高垃圾回收的效率
• 在Java程式運作的過程中，會産生大量的對象，其中有些對象是與業務資訊相關，比如Http請求中的Session對象、線程、Socket連接配接，這類對象跟業務直接挂鈎，是以生命周期比較長，但是還有一些對象，主要是程式運作過程中生成的臨時變量，這些對象生命周期會比較短，比如String對象，由于其不變類的特性，系統會産生大量的這些對象，有些對象甚至隻用一次即可回收

目前幾乎所有的GC都是采用分代收集（Generational Collecting）算法執行垃圾回收的。

在HotSpot中，基于分代的概念，GC所使用的的記憶體回收算法必須結合年輕代和老年代各自的特點

• 年輕代（Young Gen）
  1. 年輕代的特點：區域相對老年代較小，對象生命周期短、存活率低、回收頻繁
  2. 這種情況複制算法的回收整理，速度是最快的。複制算法的效率隻和存活對象的大小有關，是以很适用于年輕代的回收。而複制算法記憶體使用率不高的問題，通過hotspot中的兩個survivor的設計得到緩解
• 老年代（Tenured Gen）
  1. 老年代的特點：區域較大，對象生命周期長、存活率高，回收不及年輕代頻繁
  2. 這種情況存在大量存活率高的對象，複制算法明顯變得不合适。一般是由标記-清除或者是标記-清除與标記-整理的混合實作
     • Mark階段的開銷與存活對象的數量成正比
     • Sweep階段的開銷與所管理區域的大小成正比
     • Compact階段的開銷與存活對象的資料成正比

以HotSpot中的CMS回收器為例，CMS是基于Mark-Sweep實作的，對于對象的回收效率很高。而對于碎片問題，CMS采用基于Mark-Compact算法的Serial Old回收器作為補償措施；當記憶體回收不佳（碎片導緻的Concurrent Mode Failure時）将采用Serial Old執行Full GC以達到對老年代記憶體的整理

增量收集算法、分區算法

增量收集算法

背景

上述現有的算法，在垃圾回收過程中，應用軟體将處于一種STW的狀态，在STW狀态下，應用程式所有的線程都會挂起，暫停一切正常的工作，等待垃圾回收的完成。如果垃圾回收時間過長，應用程式會被挂起很久，将嚴重影響使用者體驗或者系統的穩定性。為了解決這個問題，即對實時垃圾收集算法的研究直接導緻了增量收集（Incremental Collecting）算法的誕生

基本思想

• 如果一次性将所有的垃圾進行處理，需要造成系統長時間的停頓，那麼就可以讓垃圾收集和應用程式線程交替執行。每次，垃圾收集線程隻收集一小片區域的記憶體空間，接着切換到應用程式線程。依次反複，知道垃圾收集完成
• 增量收集算法的基礎仍是傳統的标記-清除和複制算法。增量收集算法那通過對線程間沖突的妥善處理，允許垃圾收集線程以分階段的方式完成标記、清理或複制工作

缺點

使用這種方式，由于垃圾回收過程中，間斷性地還執行了應用程式代碼，是以能減少系統的停頓時間。但是，由于線程切換和上下文轉換的消耗，會使得垃圾回收的總體成本上升，造成系統吞吐量的下降

分區算法

• 一般來說，在相同條件下，堆空間越大，一次GC時所需的時間就越長，有關GC産生的停頓也越長。為了更好地控制GC産生的停頓時間，将一塊大的記憶體區域分割成多個小塊，根據目标的停頓時間，每次合理地回收若幹個小區間，而不是整個堆空間，進而減少一次GC所産生的停頓。
• 分代算法将按照對象的生命周期長短劃分兩個部分，分區算法将整個堆空間劃分成連續的不同小區間。每一個小區間都獨立使用、獨立回收。這種算法的好處就是可以控制一次回收多少個小區間。