術(shù)語解釋：
1.垃圾
所謂垃圾(Garbage),就是需要回收的對象。作為編寫程序的人，是可以判斷“這個(gè)變量已經(jīng)不需要了”的，但是計(jì)算機(jī)做不到。因此，如果程序直接或間接的引用一個(gè)對象，那么這個(gè)對象就被視為“存活”；反之，已經(jīng)引用不到的對象被視為“死亡”。將這些“死亡”的對象找出來，然后作為垃圾進(jìn)行回收，這就是GC的本質(zhì)。
2.根
所謂根（Root），就是判斷對象是否可被引用的起始點(diǎn)，至于哪里才是根，不同的語言和編譯器都有不同的規(guī)定，但基本是將變量和運(yùn)行?？臻g作為根。
主要的GC算法包括：標(biāo)記清除方式、復(fù)制收集方式、引用計(jì)數(shù)方式。1.標(biāo)記清除(Mark and Sweep)是最早開發(fā)出的GC算法（1960年）。它的原理非常簡單，首先從根開始將可能被引用的對象用遞歸的方式進(jìn)行標(biāo)記，然后將沒有標(biāo)記到的對象作為垃圾進(jìn)行回收。
初始狀態(tài)，一個(gè)對象可以對其他的對象進(jìn)行引用。
標(biāo)記階段，對象內(nèi)部有一個(gè)Flag標(biāo)示自己是不是被標(biāo)記，被標(biāo)記的對象我們把它涂黑。被標(biāo)記的對象被視為“存活”對象。標(biāo)記是從對象樹的根部開始的。
清除階段，在進(jìn)行垃圾回收時(shí)，將從根部開始，將所有對象按順序掃描一遍，將沒有被標(biāo)記的對象進(jìn)行回收。
標(biāo)記清除算法的處理時(shí)間，是和存活對象與對象總數(shù)的綜合相關(guān)的。
作為標(biāo)記清除的變形，還有一種叫做標(biāo)記壓縮(Mark and Compact)的算法，他不是將標(biāo)記的對象清楚，而是將他們不斷壓縮。
標(biāo)記清除算法有一個(gè)缺點(diǎn)，就是在分配了大量的對象，并且其中只有一小部分存活的情況下，所消耗的時(shí)間會(huì)大大超過必要的值，這是因?yàn)樵谇宄A段還需要對大量死亡對象進(jìn)行掃描。2.復(fù)制收集(Copy and Collection)
復(fù)制收集算法試圖克服標(biāo)記算法的缺陷。在這種算法中，會(huì)將從根開始被引用的對象復(fù)制到另外的空間中，然后，再將復(fù)制的對象所能夠引用的對象用遞歸的方式不斷復(fù)制下去。
將所有沒有死亡的對象復(fù)制到新的空間中，然后將舊的空間廢棄掉，就可以將死亡對象所占用的空間一口氣全部釋放出來，而沒有必要再次掃描每個(gè)對象。下次GC的時(shí)候，現(xiàn)在的新空間也就變成了將來的舊空間。
根據(jù)我的個(gè)人經(jīng)驗(yàn)，Java的GC采用了標(biāo)記清除和復(fù)制收集方式。object-c的GC使用另一種GC：
3.引用計(jì)數(shù)方式
引用計(jì)數(shù)(Reference Count)方式是GC算法中最簡單也是最容易實(shí)現(xiàn)的一種，它和標(biāo)記清楚方式差不多是在同一時(shí)間內(nèi)發(fā)明出來的。
它的基本原理是，在每個(gè)對象中保存該對象的引用計(jì)數(shù)，當(dāng)引用發(fā)生增減時(shí)對引用計(jì)數(shù)進(jìn)行更新。
引用計(jì)數(shù)的增減，一般發(fā)生在變量賦值、對象內(nèi)容更新、函數(shù)結(jié)束(局部變量不再被引用)等時(shí)間點(diǎn)。當(dāng)一個(gè)對象的額引用計(jì)數(shù)變?yōu)?時(shí)，則說明它將來不會(huì)再被引用，因此可以釋放對應(yīng)的內(nèi)存空間。
1 1 1
A---->B----->D
\ | /|
\ | / |
\ 2 / | 1
C E
假設(shè)上圖中所有對象中都保存著自己被多個(gè)其他對象進(jìn)行引用的數(shù)量（引用計(jì)數(shù)），每個(gè)對象右上角的數(shù)字就是引用計(jì)數(shù)。
當(dāng)對象的引用發(fā)生變化時(shí)，引用計(jì)數(shù)也跟著變化。我們讓對象B到對象D的引用失效，于是對象D的引用計(jì)數(shù)變?yōu)?， 于是對象D到C的引用計(jì)數(shù)為0。由于對象D的引用計(jì)數(shù)變?yōu)?，因此由對象D到對象C和E的引用計(jì)數(shù)也相應(yīng)減少。結(jié)果，對象E的引用計(jì)數(shù)也變?yōu)?，于是對象E也被釋放掉了。
1 1 失效 0
A---->B_____>D
\ | /|
\ | / |
\ |1 / |0
C E
引用計(jì)數(shù)變?yōu)? 的對象被釋放，“存活”對象則保留了下來。
1 1
A----->B
\ |
\ |
\ 1
C
實(shí)現(xiàn)容易是引用計(jì)數(shù)算法最大的優(yōu)點(diǎn)。標(biāo)記清楚和復(fù)制收集這些GC機(jī)制在實(shí)現(xiàn)上都有一定難度；而引用計(jì)數(shù)方式的話，凡是有些年頭的C++程序員（包括我在內(nèi)），應(yīng)該都曾經(jīng)實(shí)現(xiàn)過類似的機(jī)制，可以說這種算法是相當(dāng)具有普遍性的。
除此之外，當(dāng)對象不在被引用的瞬間就會(huì)被釋放，這也是一個(gè)優(yōu)點(diǎn)。其他的GC機(jī)制中，要預(yù)測一個(gè)對象合適會(huì)唄釋放是很困難的，而在引用計(jì)數(shù)方式中則是立即被釋放的。而且，由于釋放操作是針對每個(gè)對象級別執(zhí)行的，因此和其他算法相比，由于GC而產(chǎn)生的中斷時(shí)間（Pause time）就比較短，這也是一個(gè)優(yōu)點(diǎn)。
引用計(jì)數(shù)方式的缺點(diǎn)： 引用計(jì)數(shù)最大的缺點(diǎn)，就是無法釋放循環(huán)引用的對象。
1
A
^ \
/ \
1/ ‘/1
B-------->C
上圖中，A、B、C三個(gè)對象沒有被其他對象引用，而是相互循環(huán)引用，因此他們的引用計(jì)數(shù)永遠(yuǎn)不會(huì)為0，結(jié)果這些對象就永遠(yuǎn)不會(huì)被釋放。
引用計(jì)數(shù)的第二個(gè)缺點(diǎn)，就是必須在引用發(fā)生增減時(shí)對引用計(jì)數(shù)做出正確的增減，而如果漏掉了某個(gè)增減的話，就會(huì)引發(fā)很難找到原因的內(nèi)存錯(cuò)誤。引用計(jì)數(shù)忘記了增加的話，會(huì)對不恰當(dāng)?shù)膶ο筮M(jìn)行釋放；而引用計(jì)數(shù)忘記了減少的話，對象會(huì)一直殘留在內(nèi)存中，從而導(dǎo)致內(nèi)存泄露。如果語言編譯器本身對引用計(jì)數(shù)進(jìn)行管理的話還好，否則，如果是手動(dòng)管理引用計(jì)數(shù)的話，那將成為孕育BUG的溫床。
最后一個(gè)缺點(diǎn)就是，引用計(jì)數(shù)并不適合并行處理。為了在多線程環(huán)境下避免多個(gè)線程同時(shí)操作引用計(jì)數(shù)，引用計(jì)數(shù)的操作必須采用獨(dú)占的方式來進(jìn)行，如果引用計(jì)數(shù)操作頻繁發(fā)生，每次都要使用加鎖等并發(fā)控制機(jī)制的話，其開銷也是不可小覷的。
GC的基本算法，大體上都逃不出上述三種方式以及他們的衍生品?，F(xiàn)在，通過對這三種方式進(jìn)行融合，出現(xiàn)了一些更高級的方式。最有代表的是：分代回收、增量回收和并行回收。
1.分代回收(Generational GC)由于GC和程序處理的本質(zhì)是無關(guān)的，因此它消耗的時(shí)間越短越好。分代回收的目的，正是為了在程序運(yùn)行期間，將GC所消耗的時(shí)間盡量縮短。
分代回收的基本思路，是利用了一般性程序所具備的性質(zhì)，即大部分對象都會(huì)在短時(shí)間內(nèi)成為垃圾，而經(jīng)過了一定時(shí)間依然存活的對象往往用于偶較長的壽命。如果壽命長的對象跟容易存活下來，壽命短的對象則會(huì)被很快的廢棄，那么到底怎樣做才能讓GC變得更加高效呢？如果對分配不久，誕生時(shí)間較短的“年輕”對象進(jìn)行重點(diǎn)掃描，應(yīng)該就可以更有效的回收大部分垃圾。
在分代回收中，對象按照生成的時(shí)間進(jìn)行分代，剛剛生成不久的年輕對象劃為新生代(Young generation)，而存活了較長時(shí)間的對象則劃為老生代(Old generation).根據(jù)具體實(shí)現(xiàn)方式的不同，可能會(huì)劃分更多的代。那么根據(jù)程序的一般性質(zhì)（即大部分對象都會(huì)在短時(shí)間內(nèi)成為垃圾，而經(jīng)過了一定時(shí)間依然存活的對象往往擁有較長的壽命）,那么只要僅僅掃描新生代對象，就可以回收大部分廢棄對象中的一部分。
這種方式稱為小回收(Minor GC),參考Java的垃圾回收機(jī)制：
http://www.blogjava.net/ldwblog/archive/2013/07/24/401919.html
小回收：首先從根開始一次常規(guī)掃描，找到“存活”對象。這個(gè)步驟常采用標(biāo)記清楚或者是復(fù)制收集算法都可以，不過大多數(shù)分代回收都采用了復(fù)制收集算法。在掃描過程中，如果遇到屬于老生代的對象，則不對該對象繼續(xù)進(jìn)行遞歸掃描。這樣一來，需要掃描的對象就大幅減少。
然后，將第一次掃描完后殘余下來的對象劃分到老生代。具體來說，如果是用復(fù)制收集算法，只要將復(fù)制目標(biāo)空間設(shè)置為老生代就可以了；而標(biāo)記清除算法，則大多采用在對象上設(shè)置某種標(biāo)志的方式。
對來自老生代的引用進(jìn)行記錄：按照前面的方式，從老生代對象對新生代的引用怎么辦呢？如果指掃描新生代區(qū)域的話，那么從老生代對新生代的引用就不會(huì)被檢測到。如果一個(gè)年輕的對象只有來自老生代的引用，就會(huì)被誤認(rèn)為已經(jīng)“死亡”了。因此，在分代回收中，會(huì)對對象的更新進(jìn)行監(jiān)視，將從老生代對新生代的引用，記錄在一個(gè)叫做記錄集（remembered set）的表中。在執(zhí)行小回收的過程中，這個(gè)記錄集也作為一個(gè)根來對象。
未來讓分代回收正確工作，必須使記錄集的內(nèi)容報(bào)紙更新。為此，在老生代到新生代的引用產(chǎn)生的瞬間，就必須對該引用進(jìn)行記錄，而負(fù)責(zé)執(zhí)行這個(gè)操作的子程序，需要被嵌入到所有設(shè)計(jì)對象更新操作的地方。
這個(gè)負(fù)責(zé)記錄引用的子程序是這樣工作的：設(shè)有兩個(gè)對象A和B，當(dāng)對A的內(nèi)容進(jìn)行改寫并加入對B的引用，如果A屬于老生代對象，并且B屬于新生代對象，則將該引用添加到記錄集中。
這種檢查程序需要對所有涉及修改對象內(nèi)容的地方進(jìn)行保護(hù)，因此被成為寫屏障（Writes barrier）.寫屏障不僅用于分代回收，同時(shí)也用在很多其他的GC算法中。
在運(yùn)行過程中，老生代對象也會(huì)死亡。為了避免老生代區(qū)域中的“死亡”對象拜拜占用內(nèi)存空間，偶爾需要對包括老生代區(qū)域在內(nèi)的全部區(qū)域進(jìn)行一次少秒回收。想這樣以全部區(qū)域?yàn)閷ο蟮腉C操作被成為完全回收（Full GC）或者大回收(Major GC)。
分代回收的性能會(huì)被程序行為、分代數(shù)量、大回收觸發(fā)條件等因素大幅左右。
2.增量回收在對實(shí)時(shí)性要求很高的程序中，比起縮短GC的平均中斷時(shí)間，往往更重視縮短GC的最大中斷時(shí)間。例如，在機(jī)器人的姿勢控制程序中，如果因?yàn)镚C而讓控制程序中斷了0.1秒，機(jī)器人可能就摔倒了?；蛘哕囕v控制程序因?yàn)镚C而延遲相應(yīng)的花，后果也是不堪設(shè)想的。
在這些對實(shí)時(shí)性要求很高的程序中，必須能夠?qū)C所產(chǎn)生的中斷做出預(yù)測。例如可以將最多中斷10毫秒作為附加條件。
在一般的GC算法中，GC產(chǎn)生的中斷時(shí)間與對象的數(shù)量和狀態(tài)有關(guān)。因此，為了維持程序的實(shí)時(shí)性，不等到GC全部完成，而是將GC操作細(xì)分成多個(gè)部分逐一執(zhí)行。這種方式被成為增量回收(Incremental GC)。
在增量回收中GC過程是漸進(jìn)的，再回首過程中程序本身會(huì)繼續(xù)運(yùn)行，對象之間的引用關(guān)旭也可能發(fā)生變化。如果已經(jīng)完成掃描和標(biāo)記的對象被修改，對新的對象產(chǎn)生了引用，這個(gè)新的對象就不會(huì)被標(biāo)記，明明是存“存活”的對象卻被回收掉了。
為了避免這樣的問題，和分代回收一樣也采用了寫屏障。當(dāng)已經(jīng)被標(biāo)記的對象的引用關(guān)系發(fā)生變化時(shí)，通過寫屏障會(huì)將新被引用的對象作為掃描的起始點(diǎn)記錄下來。
由于增量回收的過程是分布漸進(jìn)式的，可以將中斷時(shí)間控制在一定長隊(duì)之內(nèi)。另一方面由于終端操作需要消耗一定的時(shí)間，GC所消耗的總時(shí)間就會(huì)相應(yīng)的增加。
3.并行回收最近的計(jì)算機(jī)中，一塊芯片上搭載多個(gè)CPU核心的多核處理器已經(jīng)逐漸普及。例如core i7就擁有6核12線程。
在這樣的環(huán)境中，就需要通過利用多線程來充分發(fā)揮CPU的性能。并行回收正是通過最大限度利用CPU的處理能力來進(jìn)行GC操作的一種方式。
并行回收的基本原理是，在原有的程序運(yùn)行的同事進(jìn)行GC操作，這一點(diǎn)和增量回收是相似的。不過，相對于在一個(gè)CPU上進(jìn)行GC任務(wù)分割的增量回收來說，并行回收可以利用多CPU的性能，盡可能讓這些GC任務(wù)并行進(jìn)行。
由于軟件運(yùn)行和GC操作是同事進(jìn)行的，因此就會(huì)遇到和增量回收同樣的問題。為了解決這個(gè)問題，并行回收也需要用寫屏障來對當(dāng)前狀態(tài)信息保持更新。不過，讓GC操作完全并行，而一點(diǎn)不影響原有程序運(yùn)行，是做不到的。因此在GC操作的某些特定階段，還是需要中斷原有程序的運(yùn)行。
GC大一統(tǒng)理論：美國IBM公司沃森研究中心的David F.Bacon等人認(rèn)為，任何一種GC算法，都是跟中回收和引用計(jì)數(shù)回收兩種思路的組合。例如，用于改善分代回收和增量回收等跟蹤回收算法的新屏障機(jī)制，從對引用狀態(tài)變化進(jìn)行記錄這個(gè)角度來看，就是吸收了引用計(jì)數(shù)回收的思路。