術語解釋：
1.垃圾
所謂垃圾(Garbage),就是需要回收的對象。作為編寫程序的人，是可以判斷“這個變量已經不需要了”的，但是計算機做不到。因此，如果程序直接或間接的引用一個對象，那么這個對象就被視為“存活”；反之，已經引用不到的對象被視為“死亡”。將這些“死亡”的對象找出來，然后作為垃圾進行回收，這就是GC的本質。
2.根
所謂根（Root），就是判斷對象是否可被引用的起始點，至于哪里才是根，不同的語言和編譯器都有不同的規定，但基本是將變量和運行棧空間作為根。

主要的GC算法包括：標記清除方式、復制收集方式、引用計數方式。

1.標記清除(Mark and Sweep)是最早開發出的GC算法（1960年）。它的原理非常簡單，首先從根開始將可能被引用的對象用遞歸的方式進行標記，然后將沒有標記到的對象作為垃圾進行回收。
初始狀態，一個對象可以對其他的對象進行引用。
標記階段，對象內部有一個Flag標示自己是不是被標記，被標記的對象我們把它涂黑。被標記的對象被視為“存活”對象。標記是從對象樹的根部開始的。
清除階段，在進行垃圾回收時，將從根部開始，將所有對象按順序掃描一遍，將沒有被標記的對象進行回收。
標記清除算法的處理時間，是和存活對象與對象總數的綜合相關的。
作為標記清除的變形，還有一種叫做標記壓縮(Mark and Compact)的算法，他不是將標記的對象清楚，而是將他們不斷壓縮。

標記清除算法有一個缺點，就是在分配了大量的對象，并且其中只有一小部分存活的情況下，所消耗的時間會大大超過必要的值，這是因為在清除階段還需要對大量死亡對象進行掃描。
2.復制收集(Copy and Collection)
復制收集算法試圖克服標記算法的缺陷。在這種算法中，會將從根開始被引用的對象復制到另外的空間中，然后，再將復制的對象所能夠引用的對象用遞歸的方式不斷復制下去。
將所有沒有死亡的對象復制到新的空間中，然后將舊的空間廢棄掉，就可以將死亡對象所占用的空間一口氣全部釋放出來，而沒有必要再次掃描每個對象。下次GC的時候，現在的新空間也就變成了將來的舊空間。
根據我的個人經驗，Java的GC采用了標記清除和復制收集方式。object-c的GC使用另一種GC：

3.引用計數方式
引用計數(Reference Count)方式是GC算法中最簡單也是最容易實現的一種，它和標記清楚方式差不多是在同一時間內發明出來的。
它的基本原理是，在每個對象中保存該對象的引用計數，當引用發生增減時對引用計數進行更新。
引用計數的增減，一般發生在變量賦值、對象內容更新、函數結束(局部變量不再被引用)等時間點。當一個對象的額引用計數變為0時，則說明它將來不會再被引用，因此可以釋放對應的內存空間。
1       1         1
A---->B----->D
   \      |       /|
     \    |     /  | 
       \  2  /    | 1
          C      E
假設上圖中所有對象中都保存著自己被多個其他對象進行引用的數量（引用計數），每個對象右上角的數字就是引用計數。
當對象的引用發生變化時，引用計數也跟著變化。我們讓對象B到對象D的引用失效，于是對象D的引用計數變為0， 于是對象D到C的引用計數為0。由于對象D的引用計數變為0，因此由對象D到對象C和E的引用計數也相應減少。結果，對象E的引用計數也變為0，于是對象E也被釋放掉了。

1       1   失效  0
A---->B_____>D
 \       |         /|
   \     |       /  |
     \   |1   /    |0
         C          E
引用計數變為0 的對象被釋放，“存活”對象則保留了下來。
1        1
A----->B
   \      |
     \    |
       \  1
          C

實現容易是引用計數算法最大的優點。標記清楚和復制收集這些GC機制在實現上都有一定難度；而引用計數方式的話，凡是有些年頭的C++程序員（包括我在內），應該都曾經實現過類似的機制，可以說這種算法是相當具有普遍性的。
除此之外，當對象不在被引用的瞬間就會被釋放，這也是一個優點。其他的GC機制中，要預測一個對象合適會唄釋放是很困難的，而在引用計數方式中則是立即被釋放的。而且，由于釋放操作是針對每個對象級別執行的，因此和其他算法相比，由于GC而產生的中斷時間（Pause time）就比較短，這也是一個優點。
引用計數方式的缺點：
 引用計數最大的缺點，就是無法釋放循環引用的對象。
                1
                A
              ^  \
             /      \
         1/          ‘/1
          B-------->C
上圖中，A、B、C三個對象沒有被其他對象引用，而是相互循環引用，因此他們的引用計數永遠不會為0，結果這些對象就永遠不會被釋放。
引用計數的第二個缺點，就是必須在引用發生增減時對引用計數做出正確的增減，而如果漏掉了某個增減的話，就會引發很難找到原因的內存錯誤。引用計數忘記了增加的話，會對不恰當的對象進行釋放；而引用計數忘記了減少的話，對象會一直殘留在內存中，從而導致內存泄露。如果語言編譯器本身對引用計數進行管理的話還好，否則，如果是手動管理引用計數的話，那將成為孕育BUG的溫床。
最后一個缺點就是，引用計數并不適合并行處理。為了在多線程環境下避免多個線程同時操作引用計數，引用計數的操作必須采用獨占的方式來進行，如果引用計數操作頻繁發生，每次都要使用加鎖等并發控制機制的話，其開銷也是不可小覷的。


GC的基本算法，大體上都逃不出上述三種方式以及他們的衍生品。現在，通過對這三種方式進行融合，出現了一些更高級的方式。最有代表的是：分代回收、增量回收和并行回收。

1.分代回收(Generational GC)
由于GC和程序處理的本質是無關的，因此它消耗的時間越短越好。分代回收的目的，正是為了在程序運行期間，將GC所消耗的時間盡量縮短。
分代回收的基本思路，是利用了一般性程序所具備的性質，即大部分對象都會在短時間內成為垃圾，而經過了一定時間依然存活的對象往往用于偶較長的壽命。如果壽命長的對象跟容易存活下來，壽命短的對象則會被很快的廢棄，那么到底怎樣做才能讓GC變得更加高效呢？如果對分配不久，誕生時間較短的“年輕”對象進行重點掃描，應該就可以更有效的回收大部分垃圾。
在分代回收中，對象按照生成的時間進行分代，剛剛生成不久的年輕對象劃為新生代(Young generation)，而存活了較長時間的對象則劃為老生代(Old generation).根據具體實現方式的不同，可能會劃分更多的代。那么根據程序的一般性質（即大部分對象都會在短時間內成為垃圾，而經過了一定時間依然存活的對象往往擁有較長的壽命）,那么只要僅僅掃描新生代對象，就可以回收大部分廢棄對象中的一部分。
這種方式稱為小回收(Minor GC),參考Java的垃圾回收機制：http://www.blogjava.net/ldwblog/archive/2013/07/24/401919.html
小回收：首先從根開始一次常規掃描，找到“存活”對象。這個步驟常采用標記清楚或者是復制收集算法都可以，不過大多數分代回收都采用了復制收集算法。在掃描過程中，如果遇到屬于老生代的對象，則不對該對象繼續進行遞歸掃描。這樣一來，需要掃描的對象就大幅減少。
然后，將第一次掃描完后殘余下來的對象劃分到老生代。具體來說，如果是用復制收集算法，只要將復制目標空間設置為老生代就可以了；而標記清除算法，則大多采用在對象上設置某種標志的方式。

對來自老生代的引用進行記錄：
按照前面的方式，從老生代對象對新生代的引用怎么辦呢？如果指掃描新生代區域的話，那么從老生代對新生代的引用就不會被檢測到。如果一個年輕的對象只有來自老生代的引用，就會被誤認為已經“死亡”了。因此，在分代回收中，會對對象的更新進行監視，將從老生代對新生代的引用，記錄在一個叫做記錄集（remembered set）的表中。在執行小回收的過程中，這個記錄集也作為一個根來對象。
未來讓分代回收正確工作，必須使記錄集的內容報紙更新。為此，在老生代到新生代的引用產生的瞬間，就必須對該引用進行記錄，而負責執行這個操作的子程序，需要被嵌入到所有設計對象更新操作的地方。
這個負責記錄引用的子程序是這樣工作的：設有兩個對象A和B，當對A的內容進行改寫并加入對B的引用，如果A屬于老生代對象，并且B屬于新生代對象，則將該引用添加到記錄集中。
這種檢查程序需要對所有涉及修改對象內容的地方進行保護，因此被成為寫屏障（Writes barrier）.寫屏障不僅用于分代回收，同時也用在很多其他的GC算法中。
在運行過程中，老生代對象也會死亡。為了避免老生代區域中的“死亡”對象拜拜占用內存空間，偶爾需要對包括老生代區域在內的全部區域進行一次少秒回收。想這樣以全部區域為對象的GC操作被成為完全回收（Full GC）或者大回收(Major GC)。
分代回收的性能會被程序行為、分代數量、大回收觸發條件等因素大幅左右。

2.增量回收
在對實時性要求很高的程序中，比起縮短GC的平均中斷時間，往往更重視縮短GC的最大中斷時間。例如，在機器人的姿勢控制程序中，如果因為GC而讓控制程序中斷了0.1秒，機器人可能就摔倒了。或者車輛控制程序因為GC而延遲相應的花，后果也是不堪設想的。
在這些對實時性要求很高的程序中，必須能夠對GC所產生的中斷做出預測。例如可以將最多中斷10毫秒作為附加條件。

在一般的GC算法中，GC產生的中斷時間與對象的數量和狀態有關。因此，為了維持程序的實時性，不等到GC全部完成，而是將GC操作細分成多個部分逐一執行。這種方式被成為增量回收(Incremental GC)。
在增量回收中GC過程是漸進的，再回首過程中程序本身會繼續運行，對象之間的引用關旭也可能發生變化。如果已經完成掃描和標記的對象被修改，對新的對象產生了引用，這個新的對象就不會被標記，明明是存“存活”的對象卻被回收掉了。
為了避免這樣的問題，和分代回收一樣也采用了寫屏障。當已經被標記的對象的引用關系發生變化時，通過寫屏障會將新被引用的對象作為掃描的起始點記錄下來。
由于增量回收的過程是分布漸進式的，可以將中斷時間控制在一定長隊之內。另一方面由于終端操作需要消耗一定的時間，GC所消耗的總時間就會相應的增加。

3.并行回收
最近的計算機中，一塊芯片上搭載多個CPU核心的多核處理器已經逐漸普及。例如core i7就擁有6核12線程。
在這樣的環境中，就需要通過利用多線程來充分發揮CPU的性能。并行回收正是通過最大限度利用CPU的處理能力來進行GC操作的一種方式。
并行回收的基本原理是，在原有的程序運行的同事進行GC操作，這一點和增量回收是相似的。不過，相對于在一個CPU上進行GC任務分割的增量回收來說，并行回收可以利用多CPU的性能，盡可能讓這些GC任務并行進行。
由于軟件運行和GC操作是同事進行的，因此就會遇到和增量回收同樣的問題。為了解決這個問題，并行回收也需要用寫屏障來對當前狀態信息保持更新。不過，讓GC操作完全并行，而一點不影響原有程序運行，是做不到的。因此在GC操作的某些特定階段，還是需要中斷原有程序的運行。

GC大一統理論：美國IBM公司沃森研究中心的David F.Bacon等人認為，任何一種GC算法，都是跟中回收和引用計數回收兩種思路的組合。例如，用于改善分代回收和增量回收等跟蹤回收算法的新屏障機制，從對引用狀態變化進行記錄這個角度來看，就是吸收了引用計數回收的思路。