Chapter 3-5. GC - GC Algorithms
Last updated
Last updated
在JVM裡, 有很多種的Garbage Collector, 其使用的演算法以及適合的場景也大不相同, 這篇會簡單記錄一下目前常見的Garbage Collection演算法, 但不會深入談細部的演算法實作(我功力還不到) .
這應該可以說是最陽春的演算法了, 正如其名, 演算法分成以下兩階段:
Mark: 標記出所有需要回收的物件(標記過程在前一個chapter已經提過了)
Sweep: 在標記完成後統一回收所有被標記的物件
之所以說這個是最陽春的演算法, 是因為後續的演算法都是基於這裡的概念去改進其不足的部分而出現的. 其不足的部分大概有以下兩點:
效率問題: Mark/Sweep的效率其實並不高
空間問題: 在Mark/Sweep之後, 可能會產生大量不連續的記憶體碎片, 記憶體碎片太多會導致之後在程式運作的過程中需要分配較大的物件時, 無法找到足夠的連續記憶體而不得不提前觸發另一次的GC動作.
下圖就是Mark-Sweep的簡單示意圖:
為了解決效率問題, 這個演算法出現了, 其將可用記憶體按照容量劃分為大小相等的兩塊, 每次只使用其中的一塊. 若當前使用的這塊記憶體用光了, 就把還存活的物件複製到另一塊上面, 然後再把當前已使用的記憶體空間清乾淨. 這就是說, 每次都是對整個半塊的記憶體進行回收, 所以分配時也不用管碎片問題了, 只要移動Heap指標, 按順序分配記憶體即可, 實作簡單且高效. 可是代價其實也不小, 因為記憶體縮小成原來的一半了. 下圖是Copying的簡單示意圖:
其實, 現在大多數的商用解決方案幾乎都是採用這個方式來回收新生代的, 以HotSpot為例, 大致上會把記憶體分為以下三個部分:
Eden Area: 物件一開始生出來大概都會進到這裡, 是三塊裡面空間最大的
From Survivor: 在某些情況下, Eden Area的物件可以晉升到這裡
To Survivor: 這裡就是前面提到的兩塊記憶體(這邊的兩塊就是指From Survivor/To Survivor)的另一塊
具體的運作方式大概是這樣: 每次使用Eden和其中一塊Survivor, 當回收時, 將Eden和當前的Survivor中還活著的物件都一次性複製到另外一個Survivor區塊中, 最後清掉Eden和剛才用過的Survivor. HotSpot默認Eden和Survivor的空間大小比例為8:1, 也就是新生代中可用記憶體空間為整個新生代容量的90%(80% + 10%), 剩下的10%就是預備的那個Survivor. 當Survivor不夠用時, 就必須依靠其它記憶體(通常指老年代, 即Tenured Generation)來進行擔保(Handle Promotion).
前面提到的Copying演算法在物件存活率高的時候就要進行比較多次的複製動作, 那效率就不高了. 更重要的, 如果你想要省那50%的空間, 就要有額外的空間進行分配擔保, 以應對被使用的記憶體中所有物件都活著的極端情況, 所以在老年代基本上是不會選擇Copying演算法的. 所以根據老年代的特性, 有人提出了Mark-Compact演算法, 其步驟概述如下:
Mark: 跟Mark-Sweep一樣
Compact: 讓所有存活的物件都向記憶體的一邊靠攏, 然後清掉靠攏後的邊界之外的記憶體
此演算法的簡單示意圖如下:
在當前商用的JVM中, 很多也會採用此作法, 這個並沒有什麼創新的地方, 只是說其會根據物件生命週期的不同將其記憶體劃分成幾塊. 一般來說是把Java Heap分成新生代/老年代, 然後就可以根據不同年代的特點採用最適合的演算法:
新生代(Young Generation): 這區的物件陣亡率基本上都頗高的, 只會有少量物件存活, 所以就可以用copying演算法, 只要花費少量存活物件的複製成本就可以完成收集作業.
老年代(Tenured Generation): 能進來這區的物件通常都是存活率高, 且可能沒有額外空間對其進行分配擔保的, 那就可以考慮用Mark-Sweep/Mark-Compact來做回收.
Mark-Sweep: 通常用於 tenured generation
Copying: 通常用於 young generation
Mark-Compact:通常用於 tenured generation