垃圾內存回收演算法

常見的垃圾回收演算法有引用計數法（Reference Counting）、標註並清理（Mark and Sweep GC）、拷貝（Copying GC）和逐代回收（Generational GC）等演算法，其中Android系統採用的是標註並刪除和拷貝GC，並不是大多數JVM實現里採用的逐代回收演算法。由於幾個演算法各有優缺點，所以在很多垃圾回收實現中，常常可以看到將幾種演算法合併使用的場景，本節將一一講解這幾個演算法。

引用計數回收法（Reference Counting GC）

引用計數法的原理很簡單，即記錄每個對象被引用的次數。每當創建一個新的對象，或者將其它指針指向該對象時，引用計數都會累加一次；而每當將指向對象的指針移除時，引用計數都會遞減一次，當引用次數降為0時，刪除對象並回收內存。採用這種演算法的較出名的框架有微軟的COM框架，如代碼清單14 - 1演示了一個對象引用計數的增減方式。

代碼清單14 - 1 引用計數增減方式演示偽碼

Object *obj1 = new Object(); // obj1的引用計數為1Object *obj2 = obj1; // obj1的引用技術為2Object *obj3 = new Object();obj2 = NULL; // obj1的引用計數遞減1次為1。obj1 = obj3; // obj1的引用計數遞減1次為0，可以回收其內存。

通常對象的引用計數都會跟對象放在一起，系統在分配完對象的內存後，返回的對象指針會跳過引用計數部分，如圖14 - 1所示：

圖 14 - 1 採用引用計數對象的內存布局示例

然而引用計數回收演算法有一個很大的弱點，就是無法有效處理循環引用的問題。

標註並清理回收法（Mark and Sweep GC）

在這個演算法中，程序在運行的過程中不停的創建新的對象並消耗內存，直到內存用光，這時再要創建新對象時，系統暫停其它組件的運行，觸發GC線程啟動垃圾回收過程。內存回收的原理很簡單，就是從所謂的"GC Roots"集合開始，將內存整個遍歷一次，保留所有可以被GC Roots直接或間接引用到的對象，而剩下的對象都當作垃圾對待並回收，如代碼清單14 - 2：

代碼清單14 - 2 標註並清理演算法偽碼

void GC(){ SuspendAllThreads(); List<Object> roots = GetRoots(); foreach ( Object root : roots ) { Mark(root); } Sweep(); ResumeAllThreads();}

演算法通常分為兩個主要的步驟：

• 標註（Mark）階段：這個過程的偽碼如代碼清單14 - 2所示，針對GC Roots中的每一個對象，採用遞歸調用的方式（第8行）處理其直接和間接引用到的所有對象：

  void Mark(Object* pObj) { if ( !pObj->IsMarked() ) { // 修改對象頭的Marked標誌 pObj->Mark(); // 深度優先遍歷對象引用到的所有對象 List<Object *> fields = pObj->GetFields(); foreach ( Object* field : fields ) { Make(field); // 遞歸處理引用到的對象 } }}

  如果對象引用的層次過深，遞歸調用消耗完虛擬機內GC線程的棧空間，從而導致棧空間溢出（StackOverflow）異常，為了避免這種情況的發生，在具體實現時，通常是用一個叫做標註棧（Mark Stack）的數據結構來分解遞歸調用。一開始，標註棧（Mark Stack）的大小是固定的，但在一些極端情況下，如果標註棧的空間也不夠的話，則會分配一個新的標註棧（Mark Stack），並將新老棧用鏈表連接起來。

  與引用計數法中對象的內存布局類似，對象是否被標註的標誌也是保存在對象頭裡的，如圖 14 - 2所示。

  

  圖 14 - 2 標註和清理演算法中的對象布局
  如圖 14 - 2是垃圾回收前的對象之間的引用關係；GC線程遍歷完整個內存堆之後，標識出所以可以被"GC Roots"引用到的對象－即代碼清單14 - 2中的第4行，結果如圖 14 - 3中高亮的部分，對於所有未被引用到（即未被標註）的對象，都將其作為垃圾收集。

  

  圖 14 - 3 回收內存垃圾之前的對象引用關係

  

  圖 14 - 4 GC線程標識出所有不能被回收的對象實例

• 清理（SWEEP）階段：即執行垃圾回收過程，留下有用的對象，如圖 14 - 4所示，代碼清單14 - 3是這個過程的偽碼，在這個階段，GC線程遍歷整個內存，將所有沒有標註的對象（即垃圾）全部回收，並將保留下來的對象的標誌清除掉，以便下次GC過程中使用。
  代碼清單14 - 4 標註和清理法中的清理過程偽碼

  void Sweep() {Object *pIter = GetHeapBegin(); while ( pIter < GetHeapEnd() ) { if ( !pIter->IsMarked() ) Free(pIter); else pIter->UnMark(); pIter = MoveNext(pIter); }}

  

  圖 14 - 5 GC線程執行完垃圾回收過程後的對象圖
  這個方法的優點是很好地處理了引用計數中的循環引用問題，而且在內存足夠的前提下，對程序幾乎沒有任何額外的性能開支（如不需要維護引用計數的代碼等），然而它的一個很大的缺點就是在執行垃圾回收過程中，需要中斷進程內其它組件的執行。

標註並整理回收法（Mark and COMPACT GC）

這個是前面標註並清理法的一個變種，系統在長時間運行的過程中，反覆分配和釋放內存很有可能會導致內存堆里的碎片過多，從而影響分配效率，因此有些採用此演算法的實現（Android系統中並沒有採用這個做法），在清理（SWEEP）過程中，還會執行內存中移動存活的對象，使其排列的更緊湊。在這種演算法中，，虛擬機在內存中依次排列和保存對象，可以想像GC組件在內部保存了一個虛擬的指針 – 下個對象分配的起始位置 ，如圖 14 - 6中演示的示例應用，其GC內存堆中已經分配有3個對象，因此"下個對象分配的起始位置"指向已分配對象的末尾，新的對象"object 4"（虛線部分）的起始位置將從這裡開始。

這個內存分配機制和C/C++的malloc分配機制有很大的區別，在C/C++中分配一塊內存時，通常malloc函數需要遍歷一個"可用內存空間"鏈表，採取"first-first"（即返回第一塊大於內存分配請求大小的內存塊）或"best-fit"（ 即返回大於內存分配請求大小的最小內存塊），無論是哪種機制，這個遍歷過程相對來說都是一個較為耗時的時間。然而在Java語言中，理論上，為一個對象分配內存的速度甚至可能比C/C++更快一些，這是因為其只需要調整指針"下個對象分配的起始位置"的位置即可，據Sun的工程師估計，這個過程大概只需要執行10個左右的機器指令。

圖 14 - 6 在GC中為對象分配內存

由於虛擬機在給對象分配內存時，一直不停地向後遞增指針"下個對象分配的起始位置"，潛台詞就是將GC堆當做一個無限大的內存對待的，為了滿足這個要求，GC線程在收集完垃圾內存之後，還需要壓縮內存 – 即移動存活的對象，將它們緊湊的排列在GC內存堆中，如圖 14 - 7是Java進程內GC前的內存布局，執行回收過程時，GC線程從進程中所有的Java線程對象、各線程堆棧里的局部變數、所有的靜態變數和JNI引用等GC Root開始遍歷。

圖 14 - 7中，可以被GC Root訪問到的對象有A、C、D、E、F、H六個對象，為了避免內存碎片問題，和滿足快速分配對象的要求，GC線程移動這六個對象，使內存使用更為緊湊，如圖 14 - 7所示。由於GC線程移動了存活下來對象的內存位置，其必須更新其他線程中對這些對象的引用，如圖 14 - 7中，由於A引用了E，移動之後，就必須更新這個引用，在更新過程中，必須中斷正在使用A的線程，防止其訪問到錯誤的內存位置而導致無法預料的錯誤。

圖 14 - 7 垃圾回收前的GC堆上的對象布局及引用關係

圖 14 - 8 GC線程移動存活的對象使內存布局更為緊湊

注意現代操作系統中，針對C/C++的內存分配演算法已經做了大量的改進，例如在Windows中，堆管理器提供了一個叫做"Look Aside List"的緩存針對大部分程序都是頻繁分配小塊內存的情形做的優化。

拷貝回收法（Copying GC）

這也是標註法的一個變種， GC內存堆實際上分成乒（ping）和乓（pong）兩部分。一開始，所有的內存分配請求都有乒（ping）部分滿足，其維護"下個對象分配的起始位置"指針，分配內存僅僅就是操作下這個指針而已，當乒（ping）的內存快用完時，採用標註（Mark）演算法識別出存活的對象，如圖 14 - 9所示，並將它們拷貝到乓（pong）部分，後續的內存分配請求都在乓（pong）部分完成，如圖 14 - 10。而乓（pong）里的內存用完後，再切換回乒（ping）部分，使用內存就跟打乒乓球一樣。

圖 14 - 9 拷貝回收法中的乒乓內存塊

圖 14 - 10 拷貝回收法中的切換乒乓內存塊以滿足內存分配請求

回收演算法的優點在於內存分配速度快，而且還有可能實現低中斷，因為在垃圾回收過程中，從一塊內存拷貝存活對象到另一塊內存的同時，還可以滿足新的內存分配請求，但其缺點是需要有額外的一個內存空間。不過對於回收演算法的缺點，也可以通過操作系統地虛擬內存提供的地址空間申請和提交分布操作的方式實現優化，因此在一些JVM實現中，其Eden區域內的垃圾回收採用此演算法。

逐代回收法（Generational GC）

也是標註法的一個變種，標註法最大的問題就是中斷的時間過長，此演算法是對標註法的優化基於下面幾個發現：

• 大部分對象創建完很快就沒用了 – 即變成垃圾；

• 每次GC收集的90%的對象都是上次GC後創建的；

• 如果對象可以活過一個GC周期，那麼它在後續幾次GC中變成垃圾的幾率很小，因此每次在GC過程中反覆標註和處理它是浪費時間。

可以將逐代回收法看成拷貝GC演算法的一個擴展，一開始所有的對象都是分配在"年輕一代對象池" 中 – 在JVM中其被稱為Young，如圖 14 - 11：

圖 14 - 11 逐代（generational） GC中開始對象都是分配在年輕一代對象池（Young generation）中

第一次垃圾回收過後，垃圾回收演算法一般採用標註並清理演算法，存活的對象會移動到"老一代對象池"中– 在JVM中其被稱為Tenured，如圖 14 - 12，而後面新創建的對象仍然在"年輕一代對象池"中創建，這樣進程不停地重複前面兩個步驟。等到"老一代對象池"也快要被填滿時，虛擬機此時再在"老一代對象池"中執行垃圾回收過程釋放內存。在逐代GC演算法中，由於"年輕一代對象池"中的回收過程很快 – 只有很少的對象會存活，而執行時間較長的"老一代對象池"中的垃圾回收過程執行不頻繁，實現了很好的平衡，因此大部分虛擬機，如JVM、.NET的CLR都採用這種演算法。

圖 14 - 12 逐代GC中將存活的對象挪到老一代對象池

在逐代GC中，有一個較棘手的問題需要處理 – 即如何處理老一代對象引用新一代對象的問題，如圖 14 - 13中。由於每次GC都是在單獨的對象池中執行的，當GC Root之一R3被釋放後，在"年輕一代對象池"中執行GC過程時，R3所引用的對象f、g、h、i和j都會被當做垃圾回收掉，這樣就導致"老一代對象池"中的對象c有一個無效引用。

圖 14 - 13 逐代GC中老一代對象引用新對象的問題

為了避免這種情況，在"年輕一代對象池"中執行GC過程時，也需要將對象C當做GC Root之一。一個名為"Card Table"的數據結構就是專門設計用來處理這種情況的，"Card Table"是一個位數組，每一個位都表示"老一代對象池"內存中一塊4KB的區域 – 之所以取4KB，是因為大部分計算機系統中，內存頁大小就是4KB。當用戶代碼執行一個引用賦值（reference assignment）時，虛擬機（通常是JIT組件）不會直接修改內存，而是先將被賦值的內存地址與"老一代對象池"的地址空間做一次比較，如果要修改的內存地址是"老一代對象池"中的地址，虛擬機會修改"Card Table"對應的位為 1，表示其對應的內存頁已經修改過 - 不幹凈（dirty）了，如圖 14 - 14。

圖 14 - 14 逐代GC中Card Table數據結構示意圖

當需要在 "年輕一代對象池"中執行GC時， GC線程先查看"Card Table"中的位，找到不幹凈的內存頁，將該內存頁中的所有對象都加入GC Root。雖然初看起來，有點浪費， 但是據統計，通常從老一代的對象引用新一代對象的幾率不超過1%，因此"Card Table"的演算法是一小部分的時間損失換取空間。

推薦閱讀：