譯者 | 李睿

審校 | 重樓

本文對垃圾回收進行介紹，其中包括垃圾回收算法的概述，以及垃圾回收是如何在一些流行的編程語言(包括Java和Python)中實現的。在討論這個問題之前，首先考慮垃圾回收機制的優點和缺點。為什么它是內存分配錯誤的常見解決方案？以下從不使用垃圾回收的C和C++等語言中內存管理的風險開始。

C/ C ++中內存管理的風險

內存分配問題只是C/C++常見問題的一個子集，這些問題會導致潛在的錯誤和漏洞，但它們是一個很大的子集，很難追蹤和修復。內存分配錯誤包括以下場景：

• 未能釋放已分配的內存，最終可能會耗盡系統中的所有內存，不僅會使程序崩潰，還會使計算機崩潰。
• 在釋放內存之后，嘗試通過指針讀取或寫入緩沖區，可能會產生隨機結果（也稱為懸空指針）。
• 雙重釋放內存塊，這可能會導致內存管理器崩潰，最終導致程序甚至整個系統崩潰。

其他常見的C/C++漏洞包括緩沖區溢出和字符串操作，它們可以用數據覆蓋代碼。“有趣”的部分是網絡攻擊者對數據進行處理，使其成為惡意可執行代碼，然后設法運行代碼。

很多人說這種情況不會再發生了，因為在保護模式系統中有單獨的代碼和數據段。不幸的是，這種情況仍然會發生。例如，一個程序在字符串中構造SQL語句，然后將其發送到數據庫執行，這通常會創建SQL注入漏洞。當然，在避免SQL注入漏洞方面有一些良好的記錄的最佳實踐，但是在數據庫客戶端中不斷出現這類錯誤，表明不是每一位程序員都會遵循最佳實踐。

垃圾回收：具有缺陷的糾正方法

使用垃圾回收可以完全消除主要的內存分配和回收問題，但這是有代價的。最大的問題是垃圾回收器的開銷；當垃圾回收器運行時出現不可預測的暫停；并且當服務器進程停止時增加了延遲。后一個問題經常出現在基于Java的服務器程序中。

垃圾回收的開銷可能很大，涉及內存和性能之間的權衡。開發人員Matthew Hertz和Emery D.Berger在2005年發表的一篇論文指出：“具有五倍內存的蘋果風格的分代回收器具有非復制的成熟空間，與基于訪問的顯式內存管理的性能相匹配。而如果只有三倍的內存，回收器的運行速度比顯式內存管理平均慢17%。然而，如果只有兩倍的內存，垃圾回收的性能降低了近70%。當物理內存不足時，分頁導致垃圾回收的運行速度比顯式內存管理慢一個數量級。”

蘋果風格的分代回收器是保守的垃圾回收器，更具攻擊性的垃圾回收器有時可以用更少的內存表現得更好。

停滯和延遲意味著基于垃圾回收的語言對于需要最小化延遲的實時程序和高吞吐量服務器來說可能不是最優的。例如，在實時Lisp和實時Java方面已經有了一些嘗試，所有這些嘗試都修改或消除了垃圾回收器。

最近，一些Java和Scala服務器采用非垃圾回收的編程語言進行了重寫，例如Scylla（用C++重寫Cassandra）和Redpanda（用C++替換Kafka插件）。在“Scylla”和“Redpanda”中，與最初的服務器相比，已經顯著減少了延遲。對于相同的負載，兩者都需要更小的集群。

垃圾回收算法

垃圾回收有幾十種算法，以下來看看一些最重要的算法及其顯著特征。

引用計數

在引用計數中，程序將對資源的引用、指針或句柄的數量存儲為分配資源的一部分，并在添加或刪除引用時增加或減少計數。當引用計數為零時，資源可以被釋放。內存垃圾回收只是引用計數的應用之一；它也用于系統對象、Windows COM對象和文件系統塊或文件的釋放控制。

引用計數有兩個主要的缺點：過于頻繁的更新和循環引用。控制更新頻率的一種方法是允許編譯器對相關對象進行批處理。處理循環引用的一種方法是不定期運行跟蹤垃圾以刪除不可訪問的循環，循環引用使計數不會達到零。

跟蹤垃圾回收

跟蹤垃圾回收是引用計數的主要替代方案，包括以下所有算法以及更多的算法。通常跟蹤垃圾回收的思想是，跟蹤過程從一些根對象(如當前局部變量、全局變量和當前函數參數)開始，并根據引用確定哪些對象是可訪問的，然后對所有無法訪問的對象進行垃圾回收。跟蹤垃圾回收是如此普遍，有時簡單地稱之為垃圾回收。

標記和掃描

1960年發布的“na?ve”標記和掃描算法可以追溯到John McCarthy開發的Lisp編程語言，它的工作原理是首先凍結系統，然后將從根集中可訪問的所有對象標記為“正在使用”。第三步是清除所有內存并釋放未標記為“正在使用”的任何塊。最后，清除所有剩余內存塊中的“正在使用”位，為下一次回收做準備，并允許系統繼續執行。顯然，這對于實時系統是不合適的。

標記和掃描的一種變體使用了三種“顏色”的內存塊：白色塊是不可訪問的，如果算法結束時它們仍然在白色集合中，則將釋放它們；黑色塊可以從根訪問，并且沒有對白色集合中的對象的外向引用；灰色塊可以從根訪問，但還需要掃描對“白色”對象的引用。在算法完成后，灰色塊全部進入黑色集合。通常情況下，初始標記將根引用的所有塊放入灰色集合中，將所有其他塊放入白色集合中。

三色標記算法分為三步：

（1）從灰色集合中選擇一個對象，并將其移動到黑色集合中。

（2）將其引用的每個白色對象移動到灰色集合。這確保了該對象及其引用的任何對象都不能被垃圾回收。

（3）重復最后兩個步驟，直到灰色集合為空。

當灰色集合為空時，所有白色塊都可以釋放。三色標記算法可以在程序運行時在后臺執行;開銷仍然存在，但它不會讓“整個世界停止”。

復制回收

復制回收(又名半空間垃圾回收)的思想是將內存分為兩個大小相等的區域，分別稱為“從空間”和“到空間”。在空間中按順序分配內存塊，直到空間填滿，然后執行回收。這交換了區域的角色，并將活動對象從“從空間”復制到“到空間”，在“到空間”的末尾留下一塊空閑空間(對應于所有不可訪問對象使用的內存)。

復制回收存在復雜性。最大的一個問題是，當復制數據塊時，它們的地址會發生變化；一種解決方案是維護轉發地址表。另一個主要問題是，復制集合所需的內存是標記和掃描所需內存的兩倍。如果大部分內存是垃圾，復制回收比標記和掃描要快，但如果大部分內存可訪問，則復制回收較慢。

標記和壓縮

標記和壓縮回收的本質是復制在單個內存空間內運行的回收。標記和壓縮回收器掃描所有可訪問的對象，并將它們壓縮在堆的底部，這使得堆的頂部可供使用。標記和壓縮回收的最大缺點是比較耗時。

分代回收

分代回收根據對象的年齡(也就是代)將堆劃分為多個空間(通常是兩個或三個)。一般來說，最近的對象比舊的對象更可能是垃圾，因此在大多數情況下掃描新對象以尋找垃圾，而不使用舊對象是有意義的。一些分代回收器在不同的代上使用不同的掃描頻率或回收算法。

哪些編程語言使用垃圾回收?

自從John McCarthy在1958年開發Lisp編程語言以來，Lisp就一直在用于垃圾回收。Java、Scala、Python和.Net/C#都是流行的垃圾回收語言。其他垃圾回收語言包括相對年輕的Go、Ruby、D、OCaml和Swift，以及較老的語言Eiffel、Haskell、ML、Modula-3、Perl、Prolog、Scheme和Smalltalk。

Java、Python和.Net/C#是一些比較流行的實現垃圾回收的編程語言。Java虛擬機(JVM)實際上提供了四種不同的垃圾回收器：串行、并行、并發標記、掃描，以及第一個垃圾回收器G1GC。G1GC現在是Java中的默認值，它是一個區域化和世代并行壓縮收集器，可實現軟實時目標。

Python（特別是標準的CPython實現）將引用計數與僅專注于清理容器對象的三級代收集相結合。.NETCLR（公共語言運行時）使用三級生成標記和緊湊收集算法。CLR還將內存對象分為兩個堆，一個用于大型對象（85000字節或更高），另一個用于小型對象；大型對象堆通常不會被壓縮，只是被標記和掃描，但如果需要可以被壓縮。

結論

正如人們所看到的，處理垃圾回收的方法有很多，其中大多數都有自己的用途。更成熟的垃圾回收實現結合了多種算法，并且多年來進行了大量調優，以盡量減少延遲。

原文標題：What is garbage collection? Automated memory management for your programs，作者：Martin Heller