JVM——垃圾回收算法保姆式詳解

什麼垃圾？

垃圾就是指在程式運作過程中沒有任何指針指向的對象，這個對象就是需要被回收的垃圾。

在程式的執行過程中，棧幀中的局部變量表中的引用指向具體的對象，當棧幀随着方法的執行結束彈出棧之後，這些對象就處于沒有任何指針指向的狀态（原文是不可達的對象），此時就變成了需要被回收的垃圾。

如果不及時堆記憶體中的垃圾進行清理，那麼這下垃圾對象所占用的記憶體空間會一直儲存到程式的執行結束，被保留的空間無法再次被配置設定，可能導緻記憶體溢出。

是以GC的範圍隻有方法區和堆，堆是GC的重點區域（JVM官方規範中沒有明确說明方法區必須要有GC）。

為什麼要進行GC？

好像是個憨憨問題一樣QaQ

• 對于一門進階語言來說，當然是為了避免過多的垃圾導緻的記憶體被消耗完。
• 垃圾回收可以清除記憶體裡的記錄碎片，碎片整理将非垃圾對象整理到堆的一端，可以整理出一塊較為整體的、連續的記憶體空間用于配置設定給新的對象使用。
• 随着應用程式越來越龐大，使用場景也是越來越複雜，是以就要通過GC不斷的對程式運作環境就行優化。

垃圾回收的相關算法

Garbage Collection，很明顯，垃圾的收集包括了兩個階段：判斷哪些是垃圾（标記垃圾）、清理垃圾。

• 标記階段算法
  • 引用計數算法
  • 可達性分析算法
• 清除階段算法
  • 标記清除算法
  • 複制算法
  • 标記壓縮算法
• 分代收集算法
• 增量收集算法
• 分區算法

垃圾标記階段

在垃圾回收前，需要判斷哪些對象是已經死亡的對象（不再使用的對象，不可達的對象，不再被引用的對象），将這些對象标記為死亡。

引用計數算法（Reference Counting）

簡單的來講，就是為每一個對象儲存一個整形的引用計數屬性，用于記錄對象被引用的情況。對于一個對象O來說，當有任何一個對象引用O的時候，O的引用計數器就+1，當某個引用失效的時候就-1，當對象O的引用計數為0時，就代表該對象不再被使用，可以被回收。

優點：

1. 實作簡單
2. 垃圾對象便于識别，判定效率高
3. 垃圾回收沒有延遲性

缺點：

• 需要單獨的字段儲存計數器，增加了空間上的開銷
• 每次更新計數器，都伴随着+1和-1的操作，增加了時間上的開銷
• 引用計數器無法處理循環引用問題，是以Java的垃圾回收器中沒有使用該類型的算法（python用了該算法，并使用手動接觸和weakref弱引用來解決該問題）。

可達性分析算法

也被稱為 根搜尋算法、追蹤性垃圾收集算法。相對于引用計數算法而言，其同樣具備了實作簡單和執行高效的特點，并且解決了循環引用的問題，防止記憶體洩漏問題的發生。Java和C#都使用了該垃圾标記算法。

基本思路：

• 可達性分析算法是以根對象集合（GC Roots）為起始點，按照從上層到下層的方式搜尋被根對象集合所連接配接的目标對象是否可達。
• 能直接或者間接被連接配接到的對象就是存活的對象，搜尋所經過的路徑為該對象的引用鍊。沒有被GC Roots直接或者間接引用到的就是可回收的對象。

根對象集合（GC Roots）：一組必須活躍的引用。

在Java語言中GC Roots是什麼？

• 虛拟機棧中引用的對象
  • 各個線程中被調用的方法使用的參數、局部變量等（棧幀中的局部變量表）
• 本地方法棧中的JNI（本地方法）引用的對象。
• 方法區中類靜态屬性引用的對象。
  • Java類的引用類型靜态變量
• 方法區中常量引用對象
  • 字元串常量池中的引用
• 所有被synchronized持有的對象
• Java虛拟機内部的引用
  • 基本資料類型對應的Class對象
  • 一些常駐的異常如：NullPointerException、OutofMemoryError
  • 系統類加載器

除了上述比較固定的作為GC Roots的成員之外，還可以有其他對象臨時性的加入GC Roots，比如：分代收集和局部回收（Partial GC）。

比如隻回收新生代，那麼老年代和永久代就有可能存在對象引用了新生代對象的情況，那麼這時，新生代之外的這些老年代、永久代等區域的對象引用者也可以看作為是GC Roots。

特别注意：

• 可達性分析算法的使用條件必須滿足：分析工作在一個能保障一緻性的快照中進行。正是這個要求導緻了GC過程中需要“stop the world”，将使用者線程都停下來。

垃圾回收與對象的finalization機制

Java提供了finalization機制允許開發者提供對象銷毀之前的自定義處理邏輯：當垃圾收集器發現沒有引用指向某個對象的時候，在回收該對象之前，會主動調用這個對象的finalize()方法。

通常情況下finalize方法在子類中被重寫，用于在對象被垃圾回收之前釋放資源。

不建議主動調用finalize方法：

• finalize方法可能會導緻對象的複活
• finalize方法執行時間是沒有辦法保證的，完全由GC線程決定，極端情況下，如果沒有GC觸發，那麼finalize方法将沒有執行的機會。
• 重寫finalize方法不當将嚴重影響GC的性能

由于finalize()方法，對象的狀态分為三種。當可達性分析之後，某些對象已經沒有被引用的時候，需要對這些死亡對象進行回收，但事實上，這些對象也并非是非死不可，他們這時候處于“死亡暫定階段”。一個無法被觸及的對象在某些情況下可能會“複活”自己，對這樣的對象進行回收其實是不合理的，由于finalize()機制的存在是以虛拟機中的對象可以分為三種：

• 可觸及的
• 可複活的：對象的所有引用都被釋放了，但是對象有可能在finalize()中複活。
• 不可觸及的：對象的finalize()方法被調用，并且沒有複活，那麼就會進入不可達的狀态，不可達的對象不能被複活，是以finalize()隻會被調用一次。

具體過程如下：

判斷一個對象Obj是否可以被回收，至少要經曆兩次标記過程。

1. 如果對象Obj到GC Roots沒有直接或者間接的引用（沒有引用鍊），則進行一次标記
2. 進行篩選，看看次被标記的對象是否需要執行finalize()方法
   1. 如果對象Obj對應的類沒有重寫finalize()方法，或者finalize方法已經被虛拟機調用過，則被虛拟機視為“沒有必要執行”，Obj将被判定為死亡、不可達，将會被回收。
   2. 如果對象Obj對應的類重寫了finalize()方法，并且還沒有執行過，那麼Obj會被插入到F-Queue隊列中，由一個虛拟機自動建立的、低優先級的Finalizer線程觸發其finalize()方法的執行。因為Finalizer線程的優先級很低，是以才說主動調用finalize方法并不能得到及時的執行。
   3. finalize()方法是對象逃離死亡狀态的最後機會，之後GC會對F-Queue隊列中的對象進行第二次标記，如果Obj在finalize()方法中與引用鍊上的任何一個對象建立了聯系，那麼在第二次标記時，Obj将會被移除待回收的集合。之後對象會再次出現沒有引用存在的情況，這個情況下，finalize方法将不會被再次執行，對象會直接變成不可達的狀态，也就是說一個對象的finalize方法隻會被調用一次。

public class Test {

    public static Test obj;//類變量

    //此方法隻會被執行一次
    @Override
    protected void finalize() throws Throwable {

        System.out.println("GC判斷對象死亡之前，Finalizer線程執行F-Queue隊列中對象的finalize()方法");
        obj = this;//此時obj和調用該finalize方法的對象（GC Routs）搭上關系，構成引用鍊
    }

    public static void main(String[] args) {

        try {
            obj = new Test();
            //對象通過finalize方法第一次成功拯救自己
            obj = null;//在此之後對象将失去引用，會被GC标記
            System.out.println("第一次GC");
            System.gc();
            //因為Finalizer線程的優先級很低，暫停一會，等等它
            Thread.sleep(3 * 1000);
            if (obj == null) {
                System.out.println("obj is dead");
            } else {
                System.out.println("obj is alive");
            }

            //第二次gc

            obj = null;//在此之後對象将失去引用
            System.out.println("第二次GC");
            System.gc();
            //因為Finalizer線程的優先級很低，暫停一會，等等它
            Thread.sleep(3 * 1000);
            if (obj == null) {
                System.out.println("obj is dead");
            } else {
                System.out.println("obj is alive");
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

    }
}


執行結果：
第一次GC
GC判斷對象死亡之前，Finalizer線程執行F-Queue隊列中對象的finalize()方法
obj is alive
第二次GC
obj is dead
           

清除階段算法

在成功标記垃圾對象之後，接下來GC需要做的就是清除這些垃圾，釋放記憶體供之後的對象使用

标記-清除算法（Mark Sweep）

當堆中的記憶體空間被耗盡的時候，就會停止整個程式（stop the world），然後進行标記、清除工作

• 标記：Collector從引用根節點開始周遊，标記所有被引用的對象，一般是在對象的header中标記為可達對象。
• 清除：Collector對堆記憶體從頭到尾進行線性的的周遊，如果發現某個對象在其Header中沒有可達對象的資訊，将其回收。
  • 這裡所謂的清除并不是真的進行了内産釋放，而是把需要清楚的對象位址儲存在空閑的位址清單中，下次由新的對象需要配置設定記憶體空間的時候，判斷垃圾所在的記憶體空間是否夠用，如果夠就存放。

算法缺點：

• 效率不高，存在兩次周遊操作
• 進行GC的時候需要停掉所有使用者線程（stop the world）
• 清理出來的空閑記憶體是不連續的，需要維護一個空閑記憶體的清單

複制算法

為了解決标記-清除算法在垃圾收集效率上的問題被M.LMinsky在1963年提出，最後應用到了Lisp語言的一個版本中。

核心思想是将活着的記憶體分為兩部分，每次隻是用其中的一塊記憶體空間，在垃圾回收時将正在使用的記憶體中的活對象複制到未被使用的記憶體塊中，之後清除正在使用的那一塊記憶體中剩下的所有對象（剩下的就是不可達的死亡對象），在此之後交換兩個記憶體塊的角色，完成垃圾收集，之後每次收集重複上述過程。

每一次的可達的對象複制到另一個未被使用的記憶體塊中的時候，這些對象被連續存放，解決記憶體碎片化問題。

優點：

• 沒有标記和清除過程，實作簡單，運作高效
• 複制到另一塊記憶體空間的過程，解決了記憶體碎片化的問題

缺點：

• 需要兩倍的記憶體空間，或者說是少了一半實際可用的記憶體空間
• 對于G1這種拆分成大量region的GC來說，進行對象的複制，需要維護region之間對象的引用關系，不管是記憶體占用還時間開銷也不小。
  • Java中站内通過直接引用（非句柄引用）指向堆内對象，對象的複制導緻棧中的引用也要改變，也是不小的開銷

但是：

• 如果可達的對象數量很多，垃圾很少的情況下，複制算法就不是那麼的“劃算”。反之，複制算法較為适用于垃圾對象較多、存活對象較少的情況。

應用場景：

由于複制算法鮮明的優缺點，以及新生代中70%-80%的對象都是“照生夕死”的，是以很多虛拟機都是使用複制算法來收回新生代。也就是Survivor0和Survivor1（也叫from和to區）。

标記-壓縮算法（Mark-Compact）

由于複制算法不适用于老年代，标記-清除算法效率較低并且會造成記憶體碎片化的問題，在标記-清除算法基礎之上産生了标記-壓縮算法。

原理：

• 标記：從引用根節點開始周遊，标記所有被引用的對象，一般是在對象的header中标記為可達對象。
• 壓縮：将所有标記為存活的對象壓縮到記憶體的一段，按順序存放。這些對象占用的記憶體空間是連續的
• 清除：清理所有存活對象所占用記憶體空間之外的記憶體區域

由于該算法在清理的過程中已經整理了可用的對象記憶體存放順序，不存在記憶體碎片，也就不需要維護記憶體空閑清單。

優點：

• 不存在記憶體碎片化的問題，隻需要JVM持有一個記憶體的起始位址即可（指針碰撞）
• 沒有記憶體減半的浪費問題

缺點：

• 效率上低于複制算法和标記-清除算法
• 移動對象的同時，還需要改變對象的引用位址
• 在移動過程中需要停止使用者線程（stop the world）

分代收集算法

上面闡述的三種算法都是各有各的優缺點，是以沒有說是存在一種完美的算法能解決所有問題，具體使用哪種算法應該具體問題具體分析。

分代收集算法基于的事實基礎如下：

不同的對象的生命周期是不一樣的，是以可以根據不同生命周期的對象使用不同的垃圾收集算法，提高垃圾回收的執行效率。JVM中的劃分的新生代、老年代，就可以根據各自的特點使用合适的回收算法，提高垃圾回收效率。目前幾乎所有的GC都是采用分代收集算法。

在Hotspot VM中，GC所使用的記憶體回收算法也是結合新生代和老年代的特點

新生代（Young Gen）：區域較小，對象生命周期短、存活率低、回收頻繁，是以使用複制算法是最合适的。複制算法的效率由于新生代中對象存活率低顯得更為優異，在新生代回收次數多的情況下，複制算法滿足了效率上的要求，記憶體浪費的缺點由于兩個Survivor區較小的原因顯得也不嚴重。預設情況下年輕代和老年代比例為1：2， Eden：Survivor0：Survivor1 = 8：1：1，是以浪費的也就隻有新生代大小的1/30。

老年代（Tenured Gen）：區域較大，對象生命周期長，存活率高，回收頻率低于新生代，是以标記清除算法和标記壓縮算法在老年代使用較多。

• 标記（Mark）階段的開銷和存活對象的數量成正比
• 清除（Sweep）階段的開銷和所管理的記憶體區域的大小成正比（對堆記憶體從頭到尾進行線性的的周遊）
• 壓縮（Compact）階段的開銷和存活對象的數量成正比

增量收集算法

上述算法都會存在STW問題，使用者線程會被暫停，實時垃圾收集算法——增量收集算法就是為了解決這個問題而誕生的。

基本思路：

如果想要一次性的處理所有現存的垃圾，那必将造成使用者線程的停頓，基于這樣的原因，那就讓垃圾收集線程和使用者線程交替執行，每次垃圾收集線程都用較短的時間處理一小塊記憶體空間的垃圾，之後就交給使用者線程執行，如此反複，知道垃圾收集全部收集完成。

總體來講，增量收集算法的基礎仍然是标記清除算法和複制算法，隻不過着重處理的是垃圾收集線程和使用者線程之間的沖突問題，階段性的使用标記-清除算法或者複制算法完成所有的垃圾收集工作。

缺點：

由于垃圾回收線程和使用者線程交替執行的原因，會造成大量線上程間切換和上下文切換的消耗，是的垃圾回收的總成本變高，造成系統的吞吐量下降。

分區算法

一般來講，堆空間越大，完成一次GC的時間就越長，GC的操作就越長。為了更好的控制GC産生的停頓時間，将一塊大的記憶體分割為若幹個小快記憶體區域（連續的小記憶體區間region），根據目标的停頓時間（STW的限制時間），每次合理的回收若幹個小區域，而不是整個堆空間，進而減少一次GC所産生的時間。每個小區間region都獨立使用，獨立回收，給的目标停頓時間長一次垃圾收集就多處理若幹個region，給的時間短就少處理若幹個region。

總結

以上都是一些基礎的垃圾回收算法或者思路，實際GC的實作要複雜的多，基本都是使用符合算法，力求兼顧效率和減小副作用。