常見的垃圾回收演算法及細節實作

分代收集理論

目前主流的虛擬機的垃圾收集器大多都遵循了“分代收集理論”進行設計，實際上是建立在兩個假說的基礎上的：

• 弱分代假說（Weak Generational Hy pothesis）：絕大多數物件都是朝生夕死（用完即可扔~）
• 強分代假說（Strong Generational Hy pothesis）：經過多次垃圾回收都沒有被回收掉的物件就越不容易被回收

基于上邊這兩種假說，收集器應該將Java堆劃分為不同的區域，然后回收物件依據其年齡生活在不同的區域，也就是將朝生夕死，難以熬過前幾次垃圾收集的物件放到一個區域，這個區域只需要關注那些存活的物件，而不需要去管那些大量即將要被回收的物件；將經過多次垃圾回收都沒被回收掉的物件放到一個區域，由于這個區域的物件很難被回收掉，因此可以使用較低的頻率來回收這個區域，這樣就同時兼顧了垃圾收集的時間開銷和記憶體空間的有效利用，
?

后邊講解的“標記-清除”、“標記-復制”、“標記-整理”演算法都是基于這個分代理論來設計的，但是分代收集有一個很明顯的問題，就是“跨代參考”問題，解決“跨代參考”可以通過在收集新生代時遍歷所有的老年代物件來確保物件是可回收的，但無疑會為記憶體回收帶來很大的性能負擔，因此引出了第三條經驗法則：

• 跨代參考假說：跨代參考相對于同代參考來說占極少數

存在相互參考的物件應該是同時生存或者消亡的，例如，某個新生代的物件被老年代的物件參考，在新生代垃圾回收時，由于存在跨代參考，因此新生代的物件不能被回收，當多次回收后新生代的物件也會被提升到老年代中，跨代參考也隨之消失了，

這條假說告訴我們不需要為了解決跨代參考而去掃描整個老年代所有的物件，也不必浪費空間專門記錄新生代有哪些物件存在跨代參考，只需要在新生代中建立一個全域的資料結構（“記憶集”），這個結構把老年代劃分為若干個區域，標識出老年代哪一塊記憶體可能存在跨代參考，此后在發生Minor GC時，只有包含了跨代參考關系的小塊記憶體里的物件才會被假如GC Roots進行掃描，這種辦法需要在物件改變了參考關系的時維護記錄資料的正確性，
?

• Minor GC/Yong GC：新生代收集嗎，只是收集新生代
• Major GC/Old GC：老年代收集，指目標只是老年代的垃圾收集，目前只有CMS垃圾收集器會有單獨收集老年代的行為，
• Mixed GC：收集整個新生代和部分老年代，目前只有G1垃圾收集器會有這種行為
• Full GC：整堆收集，收集整個Java堆和方法區的垃圾收集，
  

常見垃圾收集演算法

標記清除演算法

分為“標記”和“清除”兩個階段：首先標記出所有需要回收的物件，在標記完成后，統一回收掉所有被標記的物件，也可以反過來，
缺點：

1. 執行效率不穩定，如果Java堆中包含大量物件，而且大部分是需要回收的，這時必須進行大量的標記和清除的動作，導致標記和清除兩個程序的執行效率都是隨物件數量增長而下降；
2. 記憶體空間的碎片化問題，標記-清除之后會產生大量不連續的空間碎片，空間碎片太多可能會導致大物件分配記憶體時無法找到足夠連續的記憶體而不得不觸發一次垃圾回收動作，

標記復制演算法

為了解決標記-清除演算法在面對大量可回收物件時執行效率低的問題，69年有人提出了“半區復制”的垃圾收集演算法，它將可用記憶體劃分為兩塊，每次只使用其中的一塊，當這一塊用完了就將存活的物件復制到另一塊上，再把已使用的記憶體空間一次性清理掉，
缺點：

1. 如果記憶體中剩余存活的物件較多，那么這種演算法將產生大量的記憶體復制開銷，因此這種演算法不適合老年代，對于存活的只是很小一部分物件的情況就很合適了，并且每次只使用一半記憶體，復制過去也不用考慮空間碎片的問題，只需要順序分配記憶體即可，
2. 只能使用一半記憶體，空間浪費，
3. 需要停頓用戶執行緒來標記、清理可回收物件，停頓時間相對于下邊講的“標記-整理”演算法停頓時間要短

標記整理演算法

由于“標記-復制”演算法在物件存活較多情況下，復制開銷較大，因此不適合在物件不易被回收的老年代使用，更關鍵的是，由于復制演算法會浪費一半的空間使用，對于老年代這種大部分物件都是不會被回收的區域，一般不會選復制演算法，
針對老年代物件的特征，74年提出了另外一種有針對性的“標記-整理（Mark Compact）”演算法，其中的標記程序與“標記-清除”演算法的標記程序是相同的，但后續步驟不是直接將可回收物件回收，而是將存活物件都向記憶體空間另一端移動，然后直接清理掉邊界以外的記憶體，


兩種演算法的本質差異在于，前一種是非移動式的回收演算法，后一種是移動式的回收演算法，
是否移動回收后存活的物件是一項優缺點并存的風險決策：

• 如果移動物件，在老年代這種每次收集都有大量存活物件的區域，移動存活物件并更新所有參考這些物件的地方將會是一種極為負重的操作，而且這種物件移動操作必須STW才可以（最新的ZGC和Shenandoah收集器使用讀屏障技術實作了整理程序與用戶執行緒的并發執行）
• 如果不移動物件，那么面對這種大量不連續的記憶體空間就只能依賴更為復雜的記憶體分配器和記憶體訪問器來解決，但是針對記憶體訪問的操作，增加額外的負擔，勢必會影響程式的吞吐量，

基于以上兩點，是否移動物件都存在弊端，移動則回收更為復雜，不移動則分配記憶體更為復雜，從垃圾回收的停頓時間看，不移動物件的停頓時間更短，甚至可以不需要停頓，但是從整個程式的吞吐量來講，移動物件更劃算，即時不移動物件會使得收集器的效率更高些，但因記憶體分配比垃圾收集的頻率要高的多，這部分的耗時增加，整體的吞吐量還是降低的，HotSpot虛擬機里關注吞吐量的Parall Scavenge收集器是基于標記-整理演算法的，而關注延遲的CMS收集器則是基于標記-清除的，
還有一種辦法就是可以不在記憶體分配和訪問上增太大額外負擔，做法是讓虛擬機平時多數時間都采用“標記-清除”演算法，暫時容忍記憶體碎片的存在，直到影響到物件分配記憶體時，再使用“標記-整理”演算法收集一次，以獲得規整的記憶體空間，CMS垃圾收集器面臨空間碎片過多時就是使用這種辦法，

演算法實作細節

GC Roots根節點列舉

問題

列舉所有的GC Roots耗時問題，根節點列舉時為了保證物件參考關系的一致性，需要STW，

解決方案，如何做才能不需要遍歷所有的GC Roots

由于虛擬機垃圾收集都是準確式收集，虛擬機知道哪些地方存著物件參考，HotSpot中采用了OOP Map的資料結構，也就是在掃描的時候就可以直接從OOP Map中獲取到哪些位置有參考，就不需要遍歷所有的GC Roots了，

安全點

問題

物件之間的參考關系變化非常多，導致OOP Map內容變化的指令非常多，也不可能為每一條指令生成一個OOP Map，

解決方案，如果做到避免物件之間的參考關系頻繁變化影響GC呢？

HotSpot沒有為每條指令都生成OOP Map，只是在“特定位置”記錄這些資訊，這些位置被稱為“安全點（Safe Point）”，

作用

“安全點”的目的就是告訴用戶的程式不是在任意位置都能暫停下來進行垃圾收集，

選取

• 安全點的選取不能太少，因為會導致垃圾收集程式等待時間太長
• 安全點的選取位置在《深入理解Java虛擬機》里是這么說的，“是否具有讓程式長時間執行的特征 ”為標準進行選定，由于程式每條指令的執行時間都很短暫，程式不可能指令流太長就長時間執行，“長時間執行”最明顯的特征就是指令序列的復用，如“方法呼叫”、“回圈跳轉”、“例外跳轉”等，
  

如何在垃圾收集時讓所有的執行緒都跑到最近的安全點停頓下來

• 搶斷式（不需要用戶執行緒配合）
  • 在垃圾收集發生時，系統首先把所有用戶執行緒全部中斷，如果發現有用戶執行緒中斷的地方不在安全點上，則讓這條執行緒繼續執行，直到跑到安全點上（幾乎沒有虛擬機實作使用這種方式）
• 主動式（需要用戶執行緒配合）
  • 不主動去中斷用戶執行緒，設定一個標志位，用戶執行緒不斷的去輪詢這個標志位，一旦發現標志位為真時自己就在最近的安全點掛起，標志位與安全點是重合的，另外HotSpot還考慮到在創建物件或者為物件分配記憶體的位置加上標志位，為了檢查是否即將要發生垃圾收集，避免沒有足夠的記憶體進行記憶體分配新物件，

安全區域

只有安全點似乎很完美的解決了在進行垃圾回收之前停頓用戶執行緒，安全點機制保證了程式執行時，在不長的時間內就會安全點，但是假如程式不執行呢，例如用戶執行緒處于Sleep或者Blocked狀態， 這時候執行緒就沒辦法回應虛擬機的中斷請求，但是虛擬機也不能一直干等著用戶執行緒執行，因此就引入了安全區域，安全區域能確保在某一段代碼片段中，參考關系不會發生變化，因此在這個區域任何位置開始垃圾收集都是安全的，

并發的可達性分析

GC Roots物件遍歷一致性快照

可達性分析目前是主流的垃圾收集器使用的判斷物件是否存活的演算法，但是這個演算法理論上要求全程序都基于一個能保障一致性的快照中才能夠進行分析，意味著必須要STW才可以，上邊已經講過了根節點列舉通過Oop Map的優化，停頓時間已經減小很多了，但是從GC Roos往下遍歷物件的時間是隨著堆記憶體的大小正比例增長的（堆記憶體越大，物件越多，物件之間的關系越復雜，那這個程序所花的時間就越長），這里為何必須在一個能保障一致性的快照上的才能進行遍歷，大家自行查詢三色標記相關資料即可，

三色標記

這里做簡單描述：假設黑色為已經遍歷過并且可達的物件，灰色為已經被遍歷過，白色為待遍歷或者遍歷過但仍不可達物件，但是這個物件上至少存在一個參考還沒有被掃描過，下圖中參考C物件的有E和D，在遍歷程序中，D和C的參考被斷開了，因此E和D仍為白色，但是遍歷完C所有的參考物件后，D物件的參考關系發生了變化，被用戶執行緒修改為被B參考，但是標記執行緒又不會再標記一次，因此D物件就會被回收掉，這樣就出現大問題了，被使用的物件突然被回收了，是不是很可怕，因此GC Roots遍歷程序需要在一個能保障一致性快照上才可以，
?

解決辦法

目前大多數垃圾收集器都是用可達性分析演算法，如果在GC Roots物件遍歷程序中必須STW，這種情況就會影響大部分垃圾收集器，如果能減少這部分的停頓時間，帶來的收益將是巨大的，
在上邊的三色標記中我們發現導致并發標記的原因有：

• 用戶執行緒將黑色物件參考指向白色物件
• 用戶執行緒將灰色物件與白色物件的參考斷開

因此分別產生了兩種解決方案：

增量更新

增量更新要解決的是第一種情況，當黑色物件插入新的指向白色物件的參考關系時，就將這個新插入的參考記錄下來，等并發掃描結束后，再講這些記錄過的參考關系中的黑色物件為根，重新掃描一遍，也就是說黑色物件只要指向白色物件，那黑色物件就變為灰色物件，

原始快照

原始快照要解決的是第二種情況，當灰色物件要洗掉指向白色物件的參考關系時，就將這個要洗掉的參考記錄下來，在并發掃描結束后，再將這些記錄過得參考關系中的灰色物件為根，重新掃描一遍，這里可以理解為，無論參考關系是否洗掉，都會按照剛剛開始掃描那一刻的物件快照來進行搜索，
?

以上兩種版方案虛擬機都是通過寫屏障來實作的，兩種方案都有應用，比如CMS是基于增量更新來做并發標記，G1、Shenandoah這是使用原始快照，

本文由博客一文多發平臺 OpenWrite 發布！

標籤：Java

上一篇：終于有人把分庫分表寫清楚了！！

下一篇：mac無坑安裝nginx