標籤：

垃圾回收機制中，引用計數法是如何維護所有對象引用的？

11-26

以前看JVM的時候總有個問題：講到垃圾回收肯定會提到引用計數法，其優缺點都說了很多，但都沒說要如何去實現它，我想問的是，引用計數法通過如何維護所有對象引用的？

從樓主的問題看來，樓主似乎把GC的幾個術語混為一談了。在回答樓主問題之前先提一點：介紹自動內存管理的科普文章可能會提到引用計數（reference-counting）方式，但現在主流的JVM無一使用引用計數方式來實現Java對象的自動內存管理。

樓主提到的「掃描」與「整理」都與引用計數方式無關。樓主所說的「掃描」可能指的是「trace」，而「整理」指的肯定是「compaction」。這些都是基於可到達性來判斷對象是否存活的tracing GC里會出現的概念，具體來說通常出現在mark-compact GC（「標記-整理GC」）中。

基於引用計數與基於trace這兩大類別的自動內存管理方式最大的不同之處在於：前者只需要局部信息，而後者需要全局信息。

引用計數方式最基本的形態就是讓每個被管理的對象與一個引用計數器關聯在一起，該計數器記錄著該對象當前被引用的次數，每當創建一個新的引用指向該對象時其計數器就加1，每當指向該對象的引用失效時計數器就減1。當該計數器的值降到0就認為對象死亡。每個計數器只記錄了其對應對象的局部信息——被引用的次數，而沒有（也不需要）一份全局的對象圖的生死信息。由於只維護局部信息，所以不需要掃描全局對象圖就可以識別並釋放死對象；但也因為缺乏全局對象圖信息，所以無法處理循環引用的狀況。更高級的引用計數實現會引入「弱引用」的概念來打破某些已知的循環引用，但那是另一個話題了。
在實際實現中，引用計數存在什麼地方是個有趣的話題。可以侵入式的存在對象內，例如CPython就把引用計數存在每個受自動內存管理的Python對象的對象頭裡（PyObject的ob_refcnt欄位），或者COM的IUnknown::AddRef()/Release()；也可以非侵入式的存在對象外面，例如C++11標準庫里的std::shared_ptr。
計數器的管理（自增/自減）可能由人工完成，例如老的Objective-C，或者是從C++里使用COM，等等；也可能是自動管理，例如CPython、使用「自動引用計數」（ARC）的Objective-C、C++/CX的「hat」、前面提到的C++11的std::shared_ptr等等。如果能自動管理，那麼必然有一套明確的規則說明何種情況下一個引用會被認為失效；以std::shared_ptr為例的話，其析構函數被調用（例如離開作用域時）或者其指向別的對象時，原本指向的對象的引用計數就會減1。

Tracing GC與引用計數正好相反，需要全局的對象圖信息，從對象圖的「根」（也就是必然活的引用）出發掃描出去，基於引用的可到達性來判斷對象的生死。這使得對象的生死狀態只能批量的被識別出來，然後批量釋放死對象。Tracing GC不顯式維護對象的引用計數，只在trace的時候才能回答「有」還是「沒有」活引用指向某個對象。

實際上，在內存充裕的前提下，tracing GC的整體開銷比引用計數方式更低一些，所以吞吐量（throughput）高一些。因為引用計數方式通常需要統計冗餘的局部信息，而tracing GC則可以通過全局信息一口氣批量判斷對象的生死；如果是帶整理的tracing GC，則其內存分配通常也會更快。
不過tracing GC通常會比引用計數方式的延遲（latency）大一些，而且內存越緊張的時候tracing GC的效率反而越低，所以在內存不太充裕的地方使用引用計數仍然是個合理的選擇（例如iOS5上的ARC）。
The Garbage Collection Handbook的第6章有對各種基本GC方式的詳細對比，這邊就不贅述了。

GC相關的書我在豆瓣上整理了一份書單，[Garbage Collection][垃圾回收][自動無用內存單元回收]相關讀物
其中ガベージコレクションのアルゴリズムと実裝這本書有對幾種語言實現里的GC做源碼剖析，值得一讀。書是日文的，不過我有在推動國內出版社引進和翻譯它。請期待它的中文版的面世。

前面回答者@RednaxelaFX 從事JVM研發工作，對虛擬機理解很深，但往往超出多數Java工程師的理解與工作範疇。

下面我從一段代碼來分析整個過程，並結合模型圖來簡易講解，希望能讓大家對徹底明白。

在正式回答這個問題之前，先簡單說說 Java運行時內存區，劃分為線程私有區和線程共享區：

  • （1）線程私有區：
    • 程序計數器，記錄正在執行的虛擬機位元組碼的地址；
    • 虛擬機棧：方法執行的內存區，每個方法執行時會在虛擬機棧中創建棧幀；
    • 本地方法棧：虛擬機的Native方法執行的內存區；
  • （2）線程共享區：
    • Java堆：對象分配內存的區域，這是垃圾回收的主戰場；
    • 方法區：存放類信息、常量、靜態變數、編譯器編譯後的代碼等數據，另外還有一個常量池。當然垃圾回收也會在這個區域工作。

有興趣進一步了解的，可查看我的博文 Jvm內存模型

---------------------------------------------分割線 進入正題----------------------------------------------------

目前虛擬機基本都是採用可達性演算法，為什麼不採用引用計數演算法呢？下面就說說引用計數法是如何統計所有對象的引用計數的，再對比分析可達性演算法是如何解決引用技術演算法的不足。先簡單說說這兩個演算法：

  • 引用計數演算法（reference-counting） ：每個對象有一個引用計數器，當對象被引用一次則計數器加1，當對象引用失效一次則計數器減1，對於計數器為0的對象意味著是垃圾對象，可以被GC回收。
  • 可達性演算法(GC Roots Tracing)：從GC Roots作為起點開始搜索，那麼整個連通圖中的對象便都是活對象，對於GC Roots無法到達的對象便成了垃圾回收的對象，隨時可被GC回收。

採用引用計數演算法的系統只需在每個實例對象創建之初，通過計數器來記錄所有的引用次數即可。而可達性演算法，則需要再次GC時，遍歷整個GC根節點來判斷是否回收。

下面通過一段代碼來對比說明：

public class GcDemo {

public static void main(String[] args) {
//分為6個步驟
GcObject obj1 = new GcObject(); //Step 1
GcObject obj2 = new GcObject(); //Step 2

obj1.instance = obj2; //Step 3
obj2.instance = obj1; //Step 4

obj1 = null; //Step 5
obj2 = null; //Step 6
}
}

class GcObject{
public Object instance = null;
}

很多文章以及Java虛擬機相關的書籍，都會告訴你如果採用引用計數演算法，上述代碼中obj1和obj2指向的對象已經不可能再被訪問，彼此互相引用對方導致引用計數都不為0，最終無法被GC回收，而可達性演算法能解決這個問題。

但這些文章和書籍並沒有真正從內存角度來闡述這個過程是如何統計的，很多時候大家都在相互借鑒、翻譯，卻也都沒有明白。或者乾脆裝作講明白，或者假定讀者依然明白。 其實很多人並不明白為什麼引用計數法不為0，引用計數到底是如何維護所有對象引用的，可達性是如何可達的？ 接下來結合實例，從Java內存模型以及數學的圖論知識角度來說明，希望能讓大家徹底明白該過程。

情況（一）：引用計數演算法
如果採用的是引用計數演算法：

再回到前面代碼GcDemo的main方法共分為6個步驟：

  • Step1：GcObject實例1的引用計數加1，實例1的引用計數=1；
  • Step2：GcObject實例2的引用計數加1，實例2的引用計數=1；
  • Step3：GcObject實例2的引用計數再加1，實例2的引用計數=2；
  • Step4：GcObject實例1的引用計數再加1，實例1的引用計數=2；

執行到Step 4，則GcObject實例1和實例2的引用計數都等於2。

接下來繼續結果圖：

  • Step5：棧幀中obj1不再指向Java堆，GcObject實例1的引用計數減1，結果為1；
  • Step6：棧幀中obj2不再指向Java堆，GcObject實例2的引用計數減1，結果為1。

到此，發現GcObject實例1和實例2的計數引用都不為0，那麼如果採用的引用計數演算法的話，那麼這兩個實例所佔的內存將得不到釋放，這便產生了內存泄露。

情況（二）：可達性演算法
這是目前主流的虛擬機都是採用GC Roots Tracing演算法，比如Sun的Hotspot虛擬機便是採用該演算法。 該演算法的核心演算法是從GC Roots對象作為起始點，利用數學中圖論知識，圖中可達對象便是存活對象，而不可達對象則是需要回收的垃圾內存。這裡涉及兩個概念，一是GC Roots，一是可達性。

那麼可以作為GC Roots的對象（見下圖）：

  • 虛擬機棧的棧幀的局部變數表所引用的對象；
  • 本地方法棧的JNI所引用的對象；
  • 方法區的靜態變數和常量所引用的對象；

關於可達性的對象，便是能與GC Roots構成連通圖的對象，如下圖：

從上圖，reference1、reference2、reference3都是GC Roots，可以看出：

  • reference1-&> 對象實例1；
  • reference2-&> 對象實例2；
  • reference3-&> 對象實例4；
  • reference3-&> 對象實例4 -&> 對象實例6；

可以得出對象實例1、2、4、6都具有GC Roots可達性，也就是存活對象，不能被GC回收的對象。
而對於對象實例3、5直接雖然連通，但並沒有任何一個GC Roots與之相連，這便是GC Roots不可達的對象，這就是GC需要回收的垃圾對象。

到這裡，相信大家應該能徹底明白引用計數演算法和可達性演算法的區別吧。

再回過頭來看看最前面的實例，GcObject實例1和實例2雖然從引用計數雖然都不為0，但從可達性演算法來看，都是GC Roots不可達的對象。

總之，對於對象之間循環引用的情況，引用計數演算法，則GC無法回收這兩個對象，而可達性演算法則可以正確回收。

看完覺得可以，也請點個贊啊，畫圖容易么！O(∩_∩)O~

題主的問題是如何實現引用計數，大多數回答是在講Java中的Trace GC，可能是因為標籤上打了JVM的原因吧。其實，標上Python可能會更好一些。因為目前就我所知的，主流的編程語言虛擬機的實現中，Python還在使用引用計數，而JVM是沒有使用的。

我看題主的描述，應該是對引用計數的原理和優缺點有一個大概的了解了，只是想知道在虛擬機中如何實現。我這裡有兩篇文章，可以先看一下：

GC演算法之引用計數

以及一個實際的例子：

Python的引用計數

簡短地說，實現分這樣幾個步驟：

第一步，源代碼編譯成位元組碼。這樣我們就有機會在位元組碼的執行過程中做手腳，去維護這個引用計數。

例如：

A a = new A();
B b = new B();
a.refB = b;

第三行語句就會被翻譯成putfield指令。

第二步，解釋位元組碼，我們可以在putfiled指令的時候，通過使用do_oop_store來實現，我把偽代碼拿出來，是這樣的：

void do_oop_store(Value * obj, Value value) {
inc_ref(value);
dec_ref(obj);
obj = value;
}

如果a.refB原來引用是b1,後來引用的是b2，那麼在賦值的時候，就要把b1的引用計數減一，把b2的引用計數加一。如果引用計數為0，就可以把這部分空間釋放了：

void inc_ref(Value * ptr) {
ptr-&>ref_cnt++;
}

void dec_ref(Value * ptr) {
ptr-&>ref_cnt--;
if (ptr-&>ref_cnt == 0) {
collect(ptr);
for (Value * ref = ptr-&>first_ref; ref != null; ref=ref-&>next)
dec_ref(ref);
}
}

至於如何釋放。根據分配方法和內存組織的不同的，也許是使用free_list來維護，也許是使用點陣圖來維護。這就不一定了，要根據具體的情況來看。

通常GC就不是基於引用計數的。有循環引用，引用計數就會出問題。這個問題在Java那裡是找不到答案的。只有Python奇葩的GC是基於引用計數的。你可以看老版本的Python對於GC的介紹，Garbage Collection for Python。

就是這樣

R大已經回答完備了。
如果想了解細節，R大的博客里有Cheney演算法的實現。
大多數垃圾回收器使用根遍歷來收集引用關係，而不再是引用計數法。
貼個自己做的圖，HotSpot里minorGC回收時用的Cheney演算法：

根遍歷。
從BFS演算法-&>Cheney演算法。

自動引用計數配合trace，引用計數立刻釋放死對象，trace在內存高水位時觸發循環引用檢查和回收，加上程序員手工weak引用破除一些循環引用，不就可以實現近似完美的GC？

可以看一下java編程思想第四版，裡面的對象的清理有較為詳細的解釋。
與此同時，計數法已經不是首選了。
掃描和整理，我的理解是：
在系統相對空閑的時候，啟動對所有存在的引用進行掃描，然後標記可達的對象，然後複製這些對象到準備好的內存塊，隨後清理所有對象，再把備份的對象移動回來。
但是這個方法比較損耗內存，因為需要一次性複製所有的可達對象。
所以引用計數和掃描整理都會使用，在內存不足的時候，或者可達對象較多的時候進行逐個清理。
入門菜鳥，如有不準確的地方，望指正。

《深入理解Java虛擬機》第3章第2節有相關解釋。

在主流的商用程序語言（Java、C#，甚至包括前面提到的古老的Lisp）的主流實現中，都是稱通過可達性分析（Reachability Analysis）來判定對象是否存活的。

Java的回收機制已經不用引用計數法了吧，缺點太明顯：循環引用無法解決。

簡單的說就是：

在堆中存儲對象時，會額外為每個對象維護一個計數器，增加引用計數器值+1，一個引用失效則-1，為0時代表對象已死。

另外，Java、C#都是用可達性分析來判斷對象是否存活，好好研究這個演算法吧。

好像Redis還在用引用計數法

簡單答，jvm不用引用計數法，因為解決不了循環引用問題。都是ROOT trace

好文章

mark

RednaxelaFX 已經完整回答了。

引用計數法 是一種 i++ 和 i-- 的計數方式，較為簡單，適用範圍比較小，掃描的方式，其實就像DOM樹，如果要刪除，則上面添加一個mark，其實Tree的掃描效率很快的，掃描到mark為刪除就回收，循環引用麻煩些，但每個Node都記錄了信息，還是掃一下就可以知道那個Node要刪除回收，next.next也不慢。主要還是要存儲的信息較多而已。內存充足情況下，可以延遲來gc。 所以其吞吐會很快。 如果內存不足，則麻煩，因為需要不斷申請內存。

推薦閱讀：

※碼農們最常說的「謊言」有哪些？
※IT行業都有哪些職位，初學者（0基礎，新人）該如何選擇，才能夠快速進入這個行業？
※如何教會非計算機專業的女友寫代碼並且找到工作？
※學習 JAVA，有什麼書籍推薦？學習的方法和過程是怎樣的？

TAG:Java | Java 虛擬機（JVM） | Java 編程 | GC垃圾回收（計算機科學） |