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