GC的前世與今生

雖然本文是以.NET作為目標來講述GC，但是GC的概念并非才誕生不久。早在1958年，由鼎鼎大名的圖林獎得主John McCarthy所實現的Lisp語言就已經提供了GC的功能，這是GC的第一次出現。Lisp的程序員認為內存管理太重要了，所以不能由程序員自己來管理。但后來的日子里Lisp卻沒有成氣候，采用內存手動管理的語言占據了上風，以C為代表。出于同樣的理由，不同的人卻又不同的看法，C程序員認為內存管理太重要了，所以不能由系統(tǒng)來管理，并且譏笑Lisp程序慢如烏龜的運行速度。的確，在那個對每一個Byte都要精心計算的年代GC的速度和對系統(tǒng)資源的大量占用使很多人的無法接受。而后，1984年由Dave Ungar開發(fā)的Small talk語言第一次采用了Generational garbage collection的技術（這個技術在下文中會談到），但是Small talk也沒有得到十分廣泛的應用。

直到20世紀90年代中期GC才以主角的身份登上了歷史的舞臺，這不得不歸功于Java的進步，今日的GC已非吳下阿蒙。Java采用VM（Virtual Machine）機制，由VM來管理程序的運行當然也包括對GC管理。90年代末期.NET出現了，.NET采用了和Java類似的方法由CLR(Common Language Runtime)來管理。這兩大陣營的出現將人們引入了以虛擬平臺為基礎的開發(fā)時代，GC也在這個時候越來越得到大眾的關注。

為什么要使用GC呢？也可以說是為什么要使用內存自動管理？有下面的幾個原因：

1、提高了軟件開發(fā)的抽象度；

2、程序員可以將精力集中在實際的問題上而不用分心來管理內存的問題；

3、可以使模塊的接口更加的清晰，減小模塊間的偶合；

4、大大減少了內存人為管理不當所帶來的Bug；

5、使內存管理更加高效。

總的說來就是GC可以使程序員可以從復雜的內存問題中擺脫出來，從而提高了軟件開發(fā)的速度、質量和安全性。

什么是GC

GC如其名，就是垃圾收集，當然這里僅就內存而言。Garbage Collector（垃圾收集器，在不至于混淆的情況下也成為GC）以應用程序的root為基礎，遍歷應用程序在Heap上動態(tài)分配的所有對象[2]，通過識別它們是否被引用來確定哪些對象是已經死亡的哪些仍需要被使用。已經不再被應用程序的root或者別的對象所引用的對象就是已經死亡的對象，即所謂的垃圾，需要被回收。這就是GC工作的原理。為了實現這個原理，GC有多種算法。比較常見的算法有Reference Counting，Mark Sweep，Copy Collection等等。目前主流的虛擬系統(tǒng).net CLR，Java VM和Rotor都是采用的Mark Sweep算法。

一、Mark-Compact 標記壓縮算法 簡單把.NET的GC算法看作Mark-Compact算法

階段1: Mark-Sweep 標記清除階段

先假設heap中所有對象都可以回收，然后找出不能回收的對象，給這些對象打上標記，最后heap中沒有打標記的對象都是可以被回收的

階段2: Compact 壓縮階段

對象回收之后heap內存空間變得不連續(xù)，在heap中移動這些對象，使他們重新從heap基地址開始連續(xù)排列，類似于磁盤空間的碎片整理

Heap內存經過回收、壓縮之后，可以繼續(xù)采用前面的heap內存分配方法，即僅用一個指針記錄heap分配的起始地址就可以

主要處理步驟：將線程掛起=>確定roots=>創(chuàng)建reachable objectsgraph=>對象回收=>heap壓縮=>指針修復

可以這樣理解roots：heap中對象的引用關系錯綜復雜（交叉引用、循環(huán)引用），形成復雜的graph，roots是CLR在heap之外可以找到的各種入口點。GC搜索roots的地方包括全局對象、靜態(tài)變量、局部對象、函數調用參數、當前CPU寄存器中的對象指針（還有finalizationqueue）等。主要可以歸為2種類型：已經初始化了的靜態(tài)變量、線程仍在使用的對象（stack+CPU register）

Reachable objects：指根據對象引用關系，從roots出發(fā)可以到達的對象。例如當前執(zhí)行函數的局部變量對象A是一個rootobject，他的成員變量引用了對象B，則B是一個reachable object。從roots出發(fā)可以創(chuàng)建reachable objectsgraph，剩余對象即為unreachable，可以被回收

指針修復是因為compact過程移動了heap對象，對象地址發(fā)生變化，需要修復所有引用指針，包括stack、CPUregister中的指針以及heap中其他對象的引用指針

Debug和release執(zhí)行模式之間稍有區(qū)別，release模式下后續(xù)代碼沒有引用的對象是unreachable的，而debug模式下需要等到當前函數執(zhí)行完畢，這些對象才會成為unreachable，目的是為了調試時跟蹤局部對象的內容

傳給了COM+的托管對象也會成為root，并且具有一個引用計數器以兼容COM+的內存管理機制，引用計數器為0時這些對象才可能成為被回收對象

Pinnedobjects指分配之后不能移動位置的對象，例如傳遞給非托管代碼的對象（或者使用了fixed關鍵字），GC在指針修復時無法修改非托管代碼中的引用指針，因此將這些對象移動將發(fā)生異常。pinnedobjects會導致heap出現碎片，但大部分情況來說傳給非托管代碼的對象應當在GC時能夠被回收掉

二、 Generational 分代算法 程序可能使用幾百M、幾G的內存，對這樣的內存區(qū)域進行GC操作成本很高，分代算法具備一定統(tǒng)計學基礎，對GC的性能改善效果比較明顯

將對象按照生命周期分成新的、老的，根據統(tǒng)計分布規(guī)律所反映的結果，可以對新、老區(qū)域采用不同的回收策略和算法，加強對新區(qū)域的回收處理力度，爭取在較短時間間隔、較小的內存區(qū)域內，以較低成本將執(zhí)行路徑上大量新近拋棄不再使用的局部對象及時回收掉

分代算法的假設前提條件：

1、大量新創(chuàng)建的對象生命周期都比較短，而較老的對象生命周期會更長

2、對部分內存進行回收比基于全部內存的回收操作要快

3、新創(chuàng)建的對象之間關聯(lián)程度通常較強。heap分配的對象是連續(xù)的，關聯(lián)度較強有利于提高CPU cache的命中率

.NET將heap分成3個代齡區(qū)域: Gen 0、Gen 1、Gen 2

Heap分為3個代齡區(qū)域，相應的GC有3種方式: # Gen 0 collections, # Gen 1 collections, #Gen 2 collections。如果Gen 0 heap內存達到閥值，則觸發(fā)0代GC，0代GC后Gen 0中幸存的對象進入Gen1。如果Gen 1的內存達到閥值，則進行1代GC，1代GC將Gen 0 heap和Gen 1 heap一起進行回收，幸存的對象進入Gen2。2代GC將Gen 0 heap、Gen 1 heap和Gen 2 heap一起回收

Gen 0和Gen 1比較小，這兩個代齡加起來總是保持在16M左右；Gen2的大小由應用程序確定，可能達到幾G，因此0代和1代GC的成本非常低，2代GC稱為fullGC，通常成本很高。粗略的計算0代和1代GC應當能在幾毫秒到幾十毫秒之間完成，Gen 2 heap比較大時fullGC可能需要花費幾秒時間。大致上來講.NET應用運行期間2代、1代和0代GC的頻率應當大致為1:10:100。

三、Finalization Queue和Freachable Queue

這兩個隊列和.net對象所提供的Finalize方法有關。這兩個隊列并不用于存儲真正的對象，而是存儲一組指向對象的指針。當程序中使用了new操作符在Managed Heap上分配空間時，GC會對其進行分析，如果該對象含有Finalize方法則在Finalization Queue中添加一個指向該對象的指針。在GC被啟動以后，經過Mark階段分辨出哪些是垃圾。再在垃圾中搜索，如果發(fā)現垃圾中有被Finalization Queue中的指針所指向的對象，則將這個對象從垃圾中分離出來，并將指向它的指針移動到Freachable Queue中。這個過程被稱為是對象的復生（Resurrection），本來死去的對象就這樣被救活了。為什么要救活它呢？因為這個對象的Finalize方法還沒有被執(zhí)行，所以不能讓它死去。Freachable Queue平時不做什么事，但是一旦里面被添加了指針之后，它就會去觸發(fā)所指對象的Finalize方法執(zhí)行，之后將這個指針從隊列中剔除，這是對象就可以安靜的死去了。.net framework的System.GC類提供了控制Finalize的兩個方法，ReRegisterForFinalize和SuppressFinalize。前者是請求系統(tǒng)完成對象的Finalize方法，后者是請求系統(tǒng)不要完成對象的Finalize方法。

ReRegisterForFinalize方法其實就是將指向對象的指針重新添加到Finalization Queue中。這就出現了一個很有趣的現象，因為在Finalization Queue中的對象可以復生，如果在對象的Finalize方法中調用ReRegisterForFinalize方法，這樣就形成了一個在堆上永遠不會死去的對象，像鳳凰涅