計算機體系 – 垃圾收集器

（點選上方公眾號，可快速關註）

來源：MRRiddler ，

blog.mrriddler.com/2017/05/01/計算機體系-垃圾收集器/

繼上篇講述了棧和堆以後，程式已經可以“持續”運行了。此篇就來聊聊為了更高效的編寫出“持續”執行的程式，要對記憶體管理進行必要的最佳化(improve)，繼續來看看what’s beyond the scene。

在上篇中已經聊過堆管理器了，堆管理器已經很好的管理起了堆上的內容，但是在編寫程式的時候還是要對堆上內容人為的進行控制。這樣編寫程式即不高效、又容易出錯，最佳化是必須的，而這種最佳化就叫做垃圾收集器(Garbage Collector)，主旨就是將程式員從記憶體管理的勞動中解放出來。

GC有兩種管理方式：取用計數、跟蹤式。而管理方式指的是如何識別是否物件該被回收。而跟蹤式又有多種演演算法實現，下文就逐個聊聊這些內容。

取用計數(Reference-Counting-Collector)

取用計數這種方式比較簡單。對於每個要管理的物件，記錄一個被取用的計數，當被取用，計數就加一，當不被取用，計數就減一。如果計數為零，則可回收。記錄所有管理物件被取用的計數自然需要一個常數級定址的資料結構，一般使用的是雜湊表，以被管理的物件的地址為鍵，其計數為值。

取用計數有很多種最佳化方式，主要就是防止取用計數頻繁被更改，比如一個被管理物件如果在被取用後，馬上不被取用，這一對的取用計數增減操作就可以成對省去。

實際上上文提到了取用計數的一大缺點，需要頻繁更新取用計數。取用計數還有一大缺點，就是取用形成環路造成的迴圈取用，一般透過介入弱取用來解決此問題。

取用計數可以認為手動控制(MRC)，也可以自動管理(ARC)。

取用計數不僅可以用來管理記憶體，作業系統的檔案資源也可以用取用計數方式管理，比如說檔案描述符(fd)。

跟蹤式(Trace-Collector)

跟蹤式就是將所有被管理的物件以取用關係組織成一張有向圖，然後從必定不需回收的節點作為根節點(root)出發，trace其取用關係，遍歷所有可達節點。只要節點可達就不需回收，如果不可達就要回收。

跟蹤式為自動管理，有以下幾種演演算法：

標記-清除(Mark&Sweep;)

這是最經典的演演算法，將整個過程分為兩個階段(phase)：標記和清除，首先先trace出所有被取用的節點，然後標記它們。接著在清除階段，回收所有未被標記節點。這種演演算法有個嚴重的問題就是容易造成外部碎片。而這就影響了記憶體管理的一大指標使用率，所以有下文的演演算法在其基礎上進行最佳化。

標記-壓縮(Mark&Compact;)

類似標記-清除演演算法，標記-壓縮同樣需要標記出所有被取用節點。但是下一步並不是光簡單的清除未被取用的節點，還需要將被取用的節點壓縮到記憶體上的一片連續區域，來最佳化外部碎片問題。

複製(Copying)

這種演演算法將記憶體分為兩大空間，每次只使用一個空間。當觸發回收，將使用空間中所有不需回收的物件複製到另一未使用空間，清除前一使用空間所有物件，然後交換兩空間角色，使用後一空間。很明顯，這種演演算法在不需回收物件較少時更高效，並且需要實現高效的複製。並且由於複製到另一空間，可以最佳化掉外部碎片問題。當然，永遠使用記憶體的一半，也造成了嚴重的資源使用限制。

增量(Incremental Collecting)

由於跟蹤式是集中式的觸發，這種獨佔式處理迫使其他任務停頓，會影響到其他重要任務的實時性，這種獨佔式觸發導致其他任務停頓叫做stop the world。而這種演演算法就是將記憶體分為若干個空間並且使用多執行緒，每次只回收一個或多個空間，回收完切換執行緒去處理其他任務，下次回收在本次回收基礎上繼續。這樣可以使跟蹤式成為併發式，併發處理跟蹤式的回收和其他任務。這種演演算法缺點也很明顯，由於切換執行緒等開銷，會加大跟蹤式的整體開銷。

分代(Generational Collecting)

這種演演算法按被管理物件的生命週期長短使用不同的演演算法對其進行管理。如果幾次GC觸發回收仍都不需回收的物件被認為是常駐記憶體的物件，被稱作老生代物件(old generation)，會被放入老生代區域，使用mark&compact;演演算法對其進行管理。而剛被分配的物件，被稱作年輕代物件(young generation)，會被放入年輕代區域，使用copy演演算法對其進行管理。

JVM中的GC

提起GC，我想第二個在腦中的詞彙不是java就是jvm。接下來就聊聊GC在java中的歷史和運用，主要涉及四種GC。這些實際運用的GC會自由搭配上文提到的幾種演演算法。首先是歷史最悠久的Serial GC、Parallel GC，隨後是CMS，最後是最年輕的G1。實際上，generation演演算法提出的比較早，涉及提到的四種GC都是在generation演演算法基礎上設計的。

Serial & Parallel

serial和parallel對old generation回收演演算法就是如上文所說的mark&compact;，這並不是serial或parallel的重點，其真正有意思的是young generation使用的copy演演算法，其copy演演算法並不是簡單的將空間分為兩個區域。而是分為eden、survivor空間，而survivor又分為from、to兩個子空間。新分配的物件會被加入eden空間，eden空間滿後觸發GC，會將eden空間中存活下來的物件copy到survivor中的from或to子空間中。而from或to子空間滿後觸發GC，會被copy到另一子空間中，也就是from和to子空間會符合copy演演算法的要求，其中一個空間為空。當物件多次觸發GC都存活下來就會被放到old generation去。young generation觸發的GC叫做minor GC。

而serial和parallel分別就是單執行緒序列和多執行緒並行。整體的空間佈局如下：

其中除了提到的young generation中的eden、survivor，還有old generation和permanent generation。permanent generation包含類和物件的元資料，也會被回收，觸發的GC叫做major GC。

CMS(Concurrent-Mark-Sweep)

CMS使用的young generation演演算法類似parallel GC，其有意思的地方是對old generation的回收。對young generation的回收必須是stop the world，而對old generation的回收CMS儘力做到能多concurrent就多concurrent。CMS對old generation的回收分為下麵幾個階段：

• initial mark：對root節點標記，這階段會stop the world。

• concurrent mark：對所有存活節點標記，這階段不會stop the world。

• remark：會檢查新增加、新刪除的物件並對它們重新標記，這個階段會stop the world。

• concurrent sweep：回收未被標記的物件，這個階段不會stop the world。

註意，整個回收過程不一定會進行compact，但是如果外部碎片較多，就需要在concurrent sweep後進行compact。

G1(Garbage-First)

G1是個比較複雜的GC，這裡來聊一下整體思想，對具體細節感興趣的同學還請移步官方檔案。

G1結合了上面後三個演演算法。首先，G1使用了incremental演演算法，將空間劃分成若干個大小相等的空間，G1管這些空間叫region。而每次回收並不需要全量回收所有region，可以只回收部分region。根據使用者設定的stop the world時間和已知的region空間大小，G1可以預估出回收多少region，每次stop the world G1只回收這個數量的region，然後切換到其他程式。這樣，G1整體就可以成為一個併發式的GC了。當然，使用者設定的時間，並不是絕對時間，只是參考時間。incremental演演算法給了G1一個可以控制stop the world時間的能力。

而由於incremental演演算法的限制，每次觸發不一定能將所有需要回收的region全部回收完，所以造就了collection context這一概念，觸發collection要繼續上次的collection context繼續回收region，並且這次標記完的記號不需要下次再完全重標一遍，這也包含在collection context之中。實際上，這一概念是本人編造出來幫助理解的，官方檔案沒有說太清楚，但是context這一概念肯定會以某種演演算法、形式實現、存在。這也就是，incremental命名的真正來源，每次接著上次回收的base繼續回收。

如果G1每次回收只回收有限個region，可不可以挑出垃圾最多的region來回收？當然可以，但是這樣需要統計所有region需要清理的垃圾，這太費時間了。不如，將incremental演演算法和generation演演算法結合起來，呈現出這樣的一種效果，這就是G1所做的。將incremental演演算法和generation演演算法結合起來以後，region可以為eden region、survivor region、old region、humongous region(大物件)、available region(可用)(humongous region和available region這裡就不多聊了)。region被分generation後，最常被回收的region自然是young region，然後是old region，雖然old region的垃圾一般會比young region少，但是G1也會挑選old region中垃圾最多的region回收。整體上來看，G1就形成了會挑選垃圾最多的region來回收。相比與以上幾種GC回收整個空間的垃圾，G1做到了在有限的時間內，回收有限空間內最多的垃圾。G1擁有最高的價效比，以高回收垃圾效率為標的，所以被命名為Garbage First！

整體的空間佈局如下：

G1會觸發兩種collection，一種是young collection，一種是mixed collection。望文生義，young collection是針對young generation發起的回收，而mixed collection是針對young和old generation發起的回收。

Young-Collection

當JVM從young generation中的eden region分配空間，如果分配失敗，也就是eden region已滿就會觸發young collection。為了繼續上次young collection進行回收，要從young collection context中挑選出需要回收的eden region和survivor region。其中，eden region會被copy到survivor region，而survivor region根據其生命週期長短，可能會被copy到old region(promoted)，也可能會留在下次young collection，也可能會被放到mixed collection中去回收。

Marking-Cycle

當已使用空間達到threshold，會啟動marking cycle，結束後會觸發mixed collection，而marking cycle就是幫mixed collection對old generation進行標記。

marking cycle類似CMS，分為以下幾個階段：initial mark、root region scanning、concurrent marking、remark、cleanup。initial mark會對root節點標記，這個階段會stop the world，此階段還會捎帶(piggybacked，吐槽一下，Oracle原檔案這個詞用出了境界)上一次young collection。root region scanning會對root節點取用的old generation物件進行標記，這個階段不會stop the world。concurrent marking會標記出heap上所有存活的物件，這個階段不會stop the world。remark會檢查新增加、新刪除的物件並對它們重新標記，這個階段會stop the world。cleanup會將挑選出一些需要被回收的old region作為候選交給接下來的mixed collection，這個階段會stop the world。類似CMS，marking cycle會儘量concurrent起來。

Mixed-Collection

mixed collection會從marking cycle獲得的候選，根據被設定的引數，挑出一些合理的、垃圾最多(lowest “liveness”)的old region，和一些young region一起進行回收。不過這裡要註意，雖然上文說過，young generation適合用copy演演算法、old generation適合用mark&compact;演演算法，但是G1在這個階段要回收的old generation已經是被精挑細選出的有大量垃圾region，直接使用copy演演算法就好。也就是說G1對old generation是相當於進行了mark&compact;。不過，這個mark&compact;是透過mark和copy hybrid出來的。

實際上，不光是old generation，所有region被copy的時候，都相當於是copy演演算法，所以G1不需要額外處理外部碎片問題。

比較(comparison)

相比於取用計數管理方式和跟蹤式管理方式，取用計數不儲存取用關係，而跟蹤式會儲存明確的取用關係，自然就不會出現迴圈取用。跟蹤式是集中式的觸發，會引起stop the world，雖然跟蹤式儘力做到concurrent，但是無法避免stop the world，而取用計數是單點式的觸發。相比較而言，集中式的stop the world容易造成明顯的卡頓，相信大家的看過微博上一張各個語言參加運動會的圖片，java本來遙遙領先，觸發full GC以後，名落孫山。取用計數和跟蹤式都可以自動管理，這一點上這兩種方式半斤八兩。如果整體比較效能的話，很難得出孰勝孰劣，在不同情況下，面對不同系統各有利弊。對於實時互動系統來說，個人認為取用計數單點式觸發更勝一籌。對於記憶體充裕的情況下，跟蹤式更勝一籌。對於記憶體緊張的情況下，取用計數更勝一籌。

取用

• GC概述

  https://www.ibm.com/developerworks/cn/java/j-lo-JVMGarbageCollection/

• Serial & Parallel & CMS

  http://www.alexleo.click/java-喝杯咖啡，聊點-gc（一）-基礎概念/

• G1官方檔案-1

  http://www.oracle.com/technetwork/tutorials/tutorials-1876574.html

• G1官方檔案-2

  http://www.oracle.com/technetwork/articles/java/g1gc-1984535.html

• G1深入瞭解

  http://blog.jobbole.com/109170/

看完本文有收穫？請轉發分享給更多人

關註「ImportNew」，提升Java技能