GC的分類
通常情況下GC分為兩種，分別是：掃描GC(Tracing GC)和引用計數GC(Reference counting GC)。其中掃描GC是比較常用的GC實現方法，其原理是：把正在使用的對象找出來，然后把未被使用的對象釋放。而引用計數GC則是對每個對象都添加一個計數器，引用增加一個計數器就加一，引用減少一個計數器就減一，當計數器減至零時，把對象回收釋放。引用計數GC跟C++中的shared_ptr類似，自然也會存在循環引用問題。
掃描GC(Tracing GC)是廣泛使用的GC方法，最簡單的實現方式是mark-sweep，即掃描所有存活的對象并mark，然后遍歷整個GC對象列表，把所有標記過的對象清除標記，把未標記過的對象釋放。如果GC使用的是mark-sweep方法，程序運行一段時間后觸發了GC，每次GC的時候會把當前程序中的所有對象都掃描一次，然后釋放未使用的對象。這對于分配GC對象少的程序來說沒有什么問題，當程序中存在大量分配GC對象時，每次啟動GC掃描所有對象的代價是很高的，又因為GC的過程通常是stop-the-world，所以高代價的GC會導致整個程序卡頓一段時間。對于這個問題，解決方法有增量GC(Incremental GC)和分代GC(Generational GC)。
增量GC(Incremental GC)會把整個GC過程分成很多步(phase)，每步的執行可以存在一定間隔運行程序本身，這就盡量把stop-the-world的時間變短，使得程序不會因為GC而導致延遲太大。Lua默認采用的是這種實現方法，Lua 5.2中也引入了分代GC作為備選GC方法。
分代GC(Generational GC)把對象分成幾代(Generation)，通常把GC分為兩種：Minor GC和Major GC。剛剛分配出來的對象屬于最年輕的一代，在一次GC過后把年輕代中存活的對象上升到年老的一代中。把只掃描年輕一代的對象以減少掃描對象數量的GC過程稱為Minor GC，只有在特定情況下才會啟動完整的Major GC。分代GC是基于在大多數程序中新創建的對象同時也是最快變成無效的對象的經驗設計的，對年輕代對象GC時，可以釋放大多數無效對象，存活下來的對象一般存活時間也會更長，因此把它們上升到下一代中以減少最這些對象的掃描。
對于GC內存的管理，有移動和非移動之分。移動的就是把一次GC過后存活的對象compact到一起，使GC管理的內存保持連續，這里增加了一個移動對象的開銷，不過它也同樣帶來不少好處：分配釋放對象快和更快的序列遍歷(在CPU cache中及在同一個Virtual memory page中)。正因為它會把對象compact到一起，對象的地址就會發生變化，這也就導致一個明顯的缺點，不能使用指針引用GC對象。
其它高級GC方法，比如.NET的background GC，幾乎不需要stop-the-world就可以在GC線程中完成GC，這種高科技的GC對于我這種初級人士基本屬于不可想象。
初級分代GC設計
了解了基本的GC方法之后，我為
luna第二版實現了一個初級的分代GC，把對象分成三代：GCGen0,GCGen1,GCGen2:
GCGen0是最年輕的一代，默認所有對象都是分配在這代中。
GCGen1是年老的一代，在一次GC過后GCGen0代存活的對象會移動到這一代中。
GCGen2是最老的一代，一般情況下用于存放編譯時分配的會長期存在的對象，比如函數及字符串常量。
由于我在很多地方直接引用了GC對象的指針，為了簡單起見，我沒有在GC之后移動對象，而是對每個對象單獨分配釋放內存。每個對象都有Generation標記和GC標記以及一個用于指向跟自己屬于同代的GC對象的指針。
Minor GC對GCGen0代對象mark-sweep，并把存活的對象移動到GCGen1代中。既然需要mark，自然需要對所有GCGen0代存活的對象標記，這通過對root對象的遍歷完成，root是指所有對象的引用入口，比如程序的棧和全局表。對于Minor GC的root對象遍歷最簡單的方法是跟Major GC的root遍歷完全一致，不過這樣的遍歷對于本來就是為了減少遍歷對象的Minor GC來說似乎不合，所以通常只對某一小塊root遍歷，比如只對棧上的對象遍歷，然后再把存活的對象保留不存活的對象釋放。
Minor GC的root遍歷存在一個問題：假設只把棧上的對象作為root遍歷，會存在一些從GCGen0代分配出來的對象沒有被棧上的對象引用，而被全局表中的某個對象引用，或者其它某個非GCGen0對象引用了，這樣對GCGen0代sweep的時候可能會把這個存活的對象當做無效對象而釋放掉，這種操作自然也就會導致整個程序crash。于是為了控制root遍歷的范圍，又要解決這個問題，對非GCGen0對象引用GCGen0對象的時候，需要把這個非GCGen0的對象也加入到root遍歷列表中去。這時引入了barrier，對于非GCGen0對象引用GCGen0對象時，把這個非GCGen0的對象放到barrier列表中。
Major GC是一個完整的GC，它遍歷所有的root并mark，并把所有的無效的對象都sweep釋放。
GC啟動的時機
GC什么時候啟動是一個需要仔細考慮的問題，由于我實現的GC并沒有自己管理內存(Lua也沒有自己管理內存，所有內存分配都通過realloc)，所以我把GCGen0代和GCGen1代的對象數量作為啟動時機的衡量指標，當GCGen0和GCGen1的對象數量大于它們的閾值時，分別啟動Minor GC和Major GC。我覺得對象的數量比起內存占用大小(各種復雜的GC對象導致內存占用很難精確的統計，Lua的內存統計也不夠精確)更能反映GC時間的長短，如果兩者結合也許會更好。
通過判斷GC對象個數超過閾值時啟動GC，同時需要在GC之后自動調整閾值大小。比如某些程序很快的達到GCGen0的閾值并在Minor GC之后有超過一半的對象還是存活的，這時需要把閾值調大，以減少GC啟動的次數，這個閾值也不能無限擴大，這不僅會導致一段時間內內存占用一直上升，也會導致一旦觸發GC所需掃描的對象數量太多，GC耗時太長，程序運行的延時增加。
結語
為了減少stop-the-world的時間，引入的各種方法都會讓GC實現難度加大。GC是一個復雜的東西，網上所能找到的資料文章似乎不太多，而有關GC的書，目前只發現
《The Garbage Collection Handbook》(我還沒有看過)，而這本書既沒有pdf也沒有kindle版，只能在美國Amazon上買紙質書。另外一個參考資料就是各個語言的實現源碼了。
posted on 2013-11-17 22:20
airtrack 閱讀(2660)
評論(1) 編輯 收藏 引用