本文主要是對常用的GC算法（引用計數法、標記-清除法、復制算法、標記-清除算法）作出相關的說明，并對相關知識做簡單的介紹。

一、什么是堆？

堆指用于動態（即執行程序時）存放對象的內存空間。而這個對象，在面向對象的編程中，它指“具有屬性和行為的事物”，然而在GC的世界中，對象表示的是“通過應用程序利用的數據的集合”。具體到Java堆，它是所有線程共享的一塊內存區域，在虛擬機啟動時創建。此內存區域的唯一目的就是存放對象實例，幾乎所有的對象實例都在這里分配內存。（此處的對象實例可以理解為前面所說的對象，因為不僅僅Java有自動的GC，python、JavaScript等語言也有，所以在廣義上說對象是更好的表述，當然，Java的數組也是分配在堆上的）。

二、GC算法的評判標準

GC算法的評判標準主要是以下4點：

1、吞吐量：即單位時間內的處理能力。

2、最大暫停時間：因執行GC而暫停執行程序所需的時間。

3、堆的使用效率：魚與熊掌不可兼得，堆使用效率和吞吐量、最大暫停時間是不可能同時滿足的。即可用的堆越大，GC運行越快；相反，想要利用有限的堆，GC花費的時間就越長。

4、訪問的局部性：在存儲器的層級構造中，我們知道越是高速存取的存儲器容量會越?。ň唧w可以參看我寫的存儲器那篇文章）。由于程序的局部性原理，將經常用到的數據放在堆中較近的位置，可以提高程序的運行效率。

三、可達性

所謂的可達性就是通過一系列稱為“GC Roots”的對象為起點，從這些節點開始向下搜索，搜索走過的路徑稱為引用鏈，當一個對象到GC Roots沒有任何引用鏈相連（用圖論的話來說，就是GC Roots到這個對象不可達）時，則說明此對象是不可用的。如下圖所示，ABC可達，DE不可達。

那么那些對象可以作為GC Roots呢？以Java為例，有以下幾種：

1、棧（棧幀中的本地變量表）中引用的對象。

2、方法區中的靜態成員。

3、方法區中的常量引用的對象（全局變量）。

4、本地方法棧中JNI（一般說的Native方法）引用的對象。

注：第一和第四種都是指的方法的本地變量表，第二種表達的意思比較清晰，第三種主要指的是聲明為final的常量值。

四、引用計數法

1、什么是引用計數法？

所謂的引用計數法就是給每個對象一個引用計數器，每當有一個地方引用它時，計數器就會加1；當引用失效時，計數器的值就會減1；任何時刻計數器的值為0的對象就是不可能再被使用的。

這個引用計數法時沒有被Java所使用的，但是python有使用到它。而且最原始的引用計數法沒有用到GC Roots。

2、優點

<1>可即時回收垃圾：在該方法中，每個對象始終知道自己是否有被引用，當被引用的數值為0時，對象馬上可以把自己當作空閑空間鏈接到空閑鏈表。

<2>最大暫停時間短。

<3>沒有必要沿著指針查找

3、缺點

<1>計數器值的增減處理非常繁重

<2>計算器需要占用很多位。

<3>實現繁瑣。

<4>循環引用無法回收。

五、標記-清除算法

1、什么是標記-清除算法？

該算法分為標記和清除兩個階段。標記就是把所有活動對象都做上標記的階段；清除就是將沒有做上標記的對象進行回收的階段。如下圖所示。

1. 優點

<1>實現簡單

<2>與保守式GC算法兼容（保守式GC在后面介紹）

3、缺點

<1>碎片化：如上圖所示，在回收的過程中會產生被細化的分塊，到后面，即使堆中分塊的總大小夠用，但是卻因為分塊太小而不能執行分配。

<2>分配速度：因為分塊不是連續的，因此每次分塊都要遍歷空閑鏈表，找到足夠大的分塊，從而造成時間的浪費。

<3>與寫時復制技術不兼容：所謂寫時復制就是fork的時候，內存空間只引用而不復制，只有當該進程的數據發生變化時，才會將數據復制到該進程的內存空間。這樣，當兩個進程中的內存數據相同的時候，就能節約大量的內存空間了。而對于標記-清除算法，它的每個對象都有一個標志位來表示它是否被標記，在每一次運行標記-清除算法的時候，被引用的對象都會進行標記操作，這個僅僅標記位的改變，也會變成對象數據的改變，從而引發寫時復制的復制過程，與寫時復制的初衷就背道而馳了。

六、復制算法

1、什么是復制算法？

復制算法就是將內存空間按容量分成兩塊。當這一塊內存用完的時候，就將還存活著的對象復制到另外一塊上面，然后把已經使用過的這一塊一次清理掉。這樣使得每次都是對半塊內存進行內存回收。內存分配時就不用考慮內存碎片等復雜情況，只要移動堆頂的指針，按順序分配內存即可，實現簡單，運行高效。

1. 優點

<1>優秀的吞吐量。

<2>可實現高速分配：復制算法不用使用空閑鏈表。這是因為分塊是連續的內存空間，因此，調用這個分塊的大小，只需要這個分塊大小不小于所申請的大小，移動指針進行分配即可。

<3>不會發生碎片化。

<4>與緩存兼容。

3、缺點

<1>堆的使用效率低下。

<2>不兼容保守式GC算法。

<3>遞歸調用函數。

七、標記-壓縮算法

1、什么是標記-壓縮算法？

標記-壓縮算法與標記-清理算法類似，只是后續步驟是讓所有存活的對象移動到一端，然后直接清除掉端邊界以外的內存。

1. 優缺點

該算法可以有效的利用堆，但是壓縮需要花比較多的時間成本。

八、保守式GC與準確式GC

1、保守式GC

所謂保守式GC就是“不能識別指針和非指針的GC”。

對于寄存器、調用棧、全局變量空間來說，都是不明確的根。例如調用棧中，裝著函數內的局部變量和參數值。而局部變量，如C語言中的int、double這樣就是非指針，但是也會有像void*這樣的指針。

那么保守式GC會怎么檢查不明確的根呢？1、是不是被正確對齊的值？（在32位CPU的情況下，為4的倍數）2、是不是指著堆內？3、是不是指向對象的開頭？當然，這些只是基本的檢查項目。

上面的檢查方法會將一些非指針識別成指針。例如一個數值和一個地址，它們兩個值相等，這個時候，那個值也可以被識別成指針。

保守式GC的優點是語言處理程序不依賴與GC。缺點為識別指針和非指針需要付出成本、錯誤識別指針會壓迫堆、能夠使用的GC算法有限。例如GC復制算法就不能使用，因為其可能會將非指針重寫。

2、準確式GC

準確式GC能夠正確識別指針和非指針的GC。正確的根的創建方法是依賴于語言處理程序的實現的。我們可以通過打標簽、不把寄存器和棧等當作根的方法來實現。

其優點就是完全能夠識別指針，能夠使用復制算法等需要移動對象的算法。但是在創建準確式GC時，語言處理程序必須對GC進行一些支援，而且創建正確的根就必須付出一定的代價。

其實我們垃圾回收機的實現都不是僅僅用哪一種回收算法，都是將幾個結合使用，特別是分代算法，后面我們會詳細的介紹。

參考文獻

《深入理解Java虛擬機》

《垃圾回收的算法與實現》

https://www.zhihu.com/question/60103311