各種垃圾回收算法的通俗解

http://bbs.ss.pku.edu.cn/ss/index.php/5770/action_viewspace_itemid_5084.html

引用計數（ Reference Counting ）算法 北京大學軟體與微電子學院超級部落格?)F`j;G o,?

)S!RM8A#Y g"^)W| I0 1960 年以前，人們為胚胎中的 Lisp 語言設計垃圾 收集機制時，第一個想到的算法是引用計數算法。拿餐巾紙的例子來說，這種算法的原理大緻可以描述為：

%/@dnvjd v'VP0

5lQ%z:hMGq7Y0 午 餐時，為了把腦子裡突然跳出來的設計靈感記下來，我從餐巾紙袋中抽出一張餐巾紙，打算在上面畫出系統架構的藍圖。按照“餐巾紙使用規約之引用計數版”的要 求，畫圖之前，我必須先在餐巾紙的一角寫上計數值 1 ，以表示我在使用這張餐巾紙。這時，如果你也想看看我畫的藍圖，那你就要把餐巾紙上的計數值加 1 ，将它改為 2 ，這表明目前有 2 個人在同時使用這張餐巾紙（當然，我是不會允許你用這張餐巾紙來擦鼻涕的）。你看完後，必須把計數值減 1 ，表明你對該餐巾紙的使用已經結束。同樣，當我将餐巾紙上的内容全部謄寫到筆記本上之後，我也會自覺地把餐巾紙上的計數值減 1 。此時，不出意外的話，這張餐巾紙上的計數值應當是 0 ，它會被垃圾收集器——假設那是一個專門負責打掃衛生的機器人——撿起來扔到垃圾箱裡，因為垃圾收集器的惟一使命就是找到所有計數值為 0 的餐巾紙并清理它們。 北京大學軟體與微電子學院超級部落格9C`&ajp/Ry8w

北京大學軟體與微電子學院超級部落格"T[ C3p;Xd? R_q

引 用計數算法的優點和缺陷同樣明顯。這一算法在執行垃圾收集任務時速度較快，但算法對程式中每一次記憶體配置設定和指針操作提出了額外的要求（增加或減少記憶體塊的 引用計數）。更重要的是，引用計數算法無法正确釋放循環引用的記憶體塊，對此， D. Hillis 有一段風趣而精辟的論述：

{Ymz8Hf?/qG2z0

5|_ z1b1A0 一天，一個學生走到 Moon 面前說：“我知道如何設計一個更好的垃圾收集器了。我們必須記錄指向每個結點的指針數目。” Moon 耐心地給這位學生講了下面這個故事：“一天，一個學生走到 Moon 面前說：‘我知道如何設計一個更好的垃圾收集器了……’” 北京大學軟體與微電子學院超級部落格0Nu["F6R*ovq6a

北京大學軟體與微電子學院超級部落格Qs+YkB2CZ

D. Hillis 的故事和我們小時候常說的“從前有座山，山上有個廟，廟裡有個老和尚”的故事有異曲同工之妙。這說明，單是使用引用計數算法還不足以解決垃圾收集中的所有 問題。正因為如此，引用計數算法也常常被研究者們排除在狹義的垃圾收集算法之外。當然，作為一種最簡單、最直覺的解決方案，引用計數算法本身具有其不可替 代的優越性。 1980 年代前後， D. P. Friedman ， D. S. Wise ， H. G. Baker 等人對引用計數算法進行了數次改進，這些改進使得引用計數算法及其變種（如延遲計數算法等）在簡單的環境下，或是在一些綜合了多種算法的現代垃圾收集系統 中仍然可以一展身手。

)aa"P?!]D0E)o[0 北京大學軟體與微電子學院超級部落格9N8Xq"d5X"nK

标記－清除（ Mark-Sweep ）算法

;~Y4by,x{0

%kC`C$TdE0g0 第一種實用和完善的垃圾收集算法是 J. McCarthy 等人在 1960 年提出并成功地應用于 Lisp 語言的标記－清除算法。仍以餐巾紙為例，标記－清除算法的執行過程是這樣的： 北京大學軟體與微電子學院超級部落格-m K8y9w ~ey

;@8J$IJm1tk;Z%N}0 午 餐過程中，餐廳裡的所有人都根據自己的需要取用餐巾紙。當垃圾收集機器人想收集廢舊餐巾紙的時候，它會讓所有用餐的人先停下來，然後，依次詢問餐廳裡的每 一個人：“你正在用餐巾紙嗎？你用的是哪一張餐巾紙？”機器人根據每個人的回答将人們正在使用的餐巾紙畫上記号。詢問過程結束後，機器人在餐廳裡尋找所有 散落在餐桌上且沒有記号的餐巾紙（這些顯然都是用過的廢舊餐巾紙），把它們統統扔到垃圾箱裡。 北京大學軟體與微電子學院超級部落格Xo!D*Pg`(J

6HY+jM$F D4D0 正 如其名稱所暗示的那樣，标記－清除算法的執行過程分為“标記”和“清除”兩大階段。這種分步執行的思路奠定了現代垃圾收集算法的思想基礎。與引用計數算法 不同的是，标記－清除算法不需要運作環境監測每一次記憶體配置設定和指針操作，而隻要在“标記”階段中跟蹤每一個指針變量的指向——用類似思路實作的垃圾收集器 也常被後人統稱為跟蹤收集器（ Tracing Collector ）

/n0s3YH@"?o�I0K0 北京大學軟體與微電子學院超級部落格,bE1V"c+C%{(zg"/

伴 随着 Lisp 語言的成功，标記－清除算法也在大多數早期的 Lisp 運作環境中大放異彩。盡管最初版本的标記－清除算法在今天看來還存在效率不高（标記和清除是兩個相當耗時的過程）等諸多缺陷，但在後面的讨論中，我們可以 看到，幾乎所有現代垃圾收集算法都是标記－清除思想的延續，僅此一點， J. McCarthy 等人在垃圾收集技術方面的貢獻就絲毫不亞于他們在 Lisp 語言上的成就了。

;aJ.fHj(Y0

['G;JMO+W7Q h"W0 複制（ Copying ）算法

L$fY0O%s3v0 北京大學軟體與微電子學院超級部落格5~u} x9iU.HA}

為 了解決标記－清除算法在垃圾收集效率方面的缺陷， M. L. Minsky 于 1963 年發表了著名的論文“一種使用雙存儲區的 Lisp 語言垃圾收集器（ A LISP Garbage Collector Algorithm Using Serial Secondary Storage ）”。 M. L. Minsky 在該論文中描述的算法被人們稱為複制算法，它也被 M. L. Minsky 本人成功地引入到了 Lisp 語言的一個實作版本中。

O9G!GP0_)A a0

.E]N)Kc6aV0 複制算法别出心裁地将堆空間一分為二，并使用簡單的複制操作來完成垃圾收集工作，這個思路相當有趣。借用餐巾紙的比喻，我們可以這樣了解 M. L. Minsky 的複制算法：

:@~j�a!C7M9m0 北京大學軟體與微電子學院超級部落格SSa id�k

餐廳被垃圾收集機器人分成南區和北區兩個大小完全相同的部分。午餐時，所有人都先在南區用餐（因為空間有限，用餐人數自然也将減少一半），用餐時可以随意 使用餐巾紙。當垃圾收集機器人認為有必要回收 廢 舊餐巾紙時，它會要求所有用餐者以最快的速度從南區轉移到北區，同時随身攜帶自己正在使用的餐巾紙。等所有人都轉移到北區之後，垃圾收集機器人隻要簡單地 把南區中所有散落的餐巾紙扔進垃圾箱就算完成任務了。下一次垃圾收集的工作過程也大緻類似，惟一的不同隻是人們的轉移方向變成了從北區到南區。如此循環往 複，每次垃圾收集都隻需簡單地轉移（也就是複制）一次，垃圾收集速度無與倫比——當然，對于用餐者往返奔波于南北兩區之間的辛勞，垃圾收集機器人是決不會 流露出絲毫憐憫的。 北京大學軟體與微電子學院超級部落格{;E9pV g

3T:[email protected]*|)s?0 M. L. Minsky 的發明絕對算得上一種奇思妙想。分區、複制的思路不僅大幅提高了垃圾收集的效率，而且也将原本繁紛複雜的記憶體配置設定算法變得前所未有地簡明和扼要（既然每次 記憶體回收都是對整個半區的回收，記憶體配置設定時也就不用考慮記憶體碎片等複雜情況，隻要移動堆頂指針，按順序配置設定記憶體就可以了），這簡直是個奇迹！不過，任何奇 迹的出現都有一定的代價，在垃圾收集技術中，複制算法提高效率的代價是人為地将可用記憶體縮小了一半。實話實說，這個代價未免也太高了一些。

(r.R@(V;[_c pX+C0

W8_eo,K(om0 标記－整理（ Mark-Compact ）算法北京大學軟體與微電子學院超級部落格B5`uc(@_us;O

:sv_f ?4CO)^k0 标 記－整理算法是标記－清除算法和複制算法的有機結合。把标記－清除算法在記憶體占用上的優點和複制算法在執行效率上的特長綜合起來，這是所有人都希望看到的 結果。不過，兩種垃圾收集算法的整合并不像 1 加 1 等于 2 那樣簡單，我們必須引入一些全新的思路。 1970 年前後， G. L. Steele ， C. J. Cheney 和 D. S. Wise 等研究者陸續找到了正确的方向，标記－整理算法的輪廓也逐漸清晰了起來： 北京大學軟體與微電子學院超級部落格0K'YIi~1IBg

8? v!q$pQ&o,W3N8M0 在 我們熟悉的餐廳裡，這一次，垃圾收集機器人不再把餐廳分成兩個南北區域了。需要執行垃圾收集任務時，機器人先執行标記－清除算法的第一個步驟，為所有使用 中的餐巾紙畫好标記，然後，機器人指令所有就餐者帶上有标記的餐巾紙向餐廳的南面集中，同時把沒有标記的廢舊餐巾紙扔向餐廳北面。這樣一來，機器人隻消站 在餐廳北面，懷抱垃圾箱，迎接撲面而來的廢舊餐巾紙就行了。 北京大學軟體與微電子學院超級部落格v U/&YH2P/_+K

p bLO;k(ue0 實驗表明，标記－整理算法的總體執行效率高于标記－清除算法，又不像複制算法那樣需要犧牲一半的存儲空間，這顯然是一種非常理想的結果。在許多現代的垃圾收集器中，人們都使用了标記－整理算法或其改進版本。 北京大學軟體與微電子學院超級部落格r Q!k�WS@/U

北京大學軟體與微電子學院超級部落格X.aK[#`$Sc

增量收集（ Incremental Collecting ）算法 北京大學軟體與微電子學院超級部落格p!|6j KF*Jp ^]"v

北京大學軟體與微電子學院超級部落格(h;G%Mz ]&p'I

對實時垃圾收集算法的研究直接導緻了增量收集算法的誕生。 北京大學軟體與微電子學院超級部落格%@"Z d)hwb}0d`m

bS)yP1/x zn0 最初，人們關于實時垃圾收集的想法是這樣的：為了進行實時的垃圾收集，可以設計一個多程序的運作環境，比如用一個程序執行垃圾收集工作，另一個程序執行程式代碼。這樣一來，垃圾收集工作看上去就仿佛是在背景悄悄完成的，不會打斷程式代碼的運作。

2/'T]scU;K_1~0 北京大學軟體與微電子學院超級部落格TSg6i#j;i

在 收集餐巾紙的例子中，這一思路可以被了解為：垃圾收集機器人在人們用餐的同時尋找廢棄的餐巾紙并将它們扔到垃圾箱裡。這個看似簡單的思路會在設計和實作時 碰上程序間沖突的難題。比如說，如果垃圾收集程序包括标記和清除兩個工作階段，那麼，垃圾收集器在第一階段中辛辛苦苦标記出的結果很可能被另一個程序中的 記憶體操作代碼修改得面目全非，以至于第二階段的工作沒有辦法開展。

0x9I.?"Nv0Nb0 北京大學軟體與微電子學院超級部落格H yUkE@

M. L. Minsky 和 D. E. Knuth 對實時垃圾收集過程中的技術難點進行了早期的研究， G. L. Steele 于 1975 年發表了題為“多程序整理的垃圾收集（ Multiprocessing compactifying garbage collection ）”的論文，描述了一種被後人稱為“ Minsky-Knuth-Steele 算法”的實時垃圾收集算法。 E. W. Dijkstra ， L. Lamport ， R. R. Fenichel 和 J. C. Yochelson 等人也相繼在此領域做出了各自的貢獻。 1978 年， H. G. Baker 發表了“串行計算機上的實時表處理技術（ List Processing in Real Time on a Serial Computer ）”一文，系統闡述了多程序環境下用于垃圾收集的增量收集算法。 北京大學軟體與微電子學院超級部落格3o8N/v1^G(~:s

s7Ja8C*g(N ih0 增 量收集算法的基礎仍是傳統的标記－清除和複制算法。增量收集算法通過對程序間沖突的妥善處理，允許垃圾收集程序以分階段的方式完成标記、清理或複制工作。 詳細分析各種增量收集算法的内部機理是一件相當繁瑣的事情，在這裡，讀者們需要了解的僅僅是： H. G. Baker 等人的努力已經将實時垃圾收集的夢想變成了現實，我們再也不用為垃圾收集打斷程式的運作而煩惱了北京大學軟體與微電子學院超級部落格jqEO6@

0w%h(_l?C S0 分代收集（ Generational Collecting ）算法北京大學軟體與微電子學院超級部落格@FIJ(|,B M+vT

北京大學軟體與微電子學院超級部落格C4[3Pcd

和 大多數軟體開發技術一樣，統計學原理總能在技術發展的過程中起到強力催化劑的作用。 1980 年前後，善于在研究中使用統計分析知識的技術人員發現，大多數記憶體塊的生存周期都比較短，垃圾收集器應當把更多的精力放在檢查和清理新配置設定的記憶體塊上。這 個發現對于垃圾收集技術的價值可以用餐巾紙的例子概括如下： 北京大學軟體與微電子學院超級部落格B?0f$@'Y`N0b

北京大學軟體與微電子學院超級部落格5o j8Vs7[C

如 果垃圾收集機器人足夠聰明，事先摸清了餐廳裡每個人在用餐時使用餐巾紙的習慣——比如有些人喜歡在用餐前後各用掉一張餐巾紙，有的人喜歡自始至終攥着一張 餐巾紙不放，有的人則每打一個噴嚏就用去一張餐巾紙——機器人就可以制定出更完善的餐巾紙回收計劃，并總是在人們剛扔掉餐巾紙沒多久就把垃圾撿走。這種基 于統計學原理的做法當然可以讓餐廳的整潔度成倍提高。

![~k:wy�h0

t p#Y-bP/FI0 D. E. Knuth ， T. Knight ， G. Sussman 和 R. Stallman 等人對記憶體垃圾的分類處理做了最早的研究。 1983 年， H. Lieberman 和 C. Hewitt 發表了題為“基于對象壽命的一種實時垃圾收集器（ A real-time garbage collector based on the lifetimes of objects ）”的論文。這篇著名的論文标志着分代收集算法的正式誕生。此後，在 H. G. Baker ， R. L. Hudson ， J. E. B. Moss 等人的共同努力下，分代收集算法逐漸成為了垃圾收集領域裡的主流技術。 北京大學軟體與微電子學院超級部落格PbE?_N

北京大學軟體與微電子學院超級部落格7ZNg^ V*nO-v

分 代收集算法通常将堆中的記憶體塊按壽命分為兩類，年老的和年輕的。垃圾收集器使用不同的收集算法或收集政策，分别處理這兩類記憶體塊，并特别地把主要工作時間 花在處理年輕的記憶體塊上。分代收集算法使垃圾收集器在有限的資源條件下，可以更為有效地工作——這種效率上的提高在今天的 Java 虛拟機中得到了最好的證明。