[[384450]]

系統(tǒng)設(shè)計精要是一系列深入研究系統(tǒng)設(shè)計方法的系列文章，文中不僅會分析系統(tǒng)設(shè)計的理論，還會分析多個實際場景下的具體實現(xiàn)。這是一個季更或者半年更的系列，如果你有想要了解的問題，可以在文章下面留言。

持久存儲的磁盤在今天已經(jīng)不是稀缺的資源了，但是 CPU 和內(nèi)存仍然是相對比較昂貴的資源，作者在 調(diào)度系統(tǒng)設(shè)計精要 中曾經(jīng)介紹操作系統(tǒng)和編程語言對 CPU 資源的調(diào)度策略和原理，本文將會介紹計算機(jī)中常見的另一個稀缺資源 — 內(nèi)存，是如何管理的。

圖 1 - 內(nèi)存系統(tǒng)設(shè)計精要

 

內(nèi)存管理系統(tǒng)和模塊在操作系統(tǒng)以及編程語言中都占有著重要的地位，任何資源的使用都離不開申請和釋放兩個動作，內(nèi)存管理中的兩個重要過程就是內(nèi)存分配和垃圾回收，內(nèi)存管理系統(tǒng)如何利用有限的內(nèi)存資源為盡可能多的程序或者模塊提供服務(wù)是它的核心目標(biāo)。

圖 2 - 文章脈絡(luò)和內(nèi)容

 

雖然多數(shù)系統(tǒng)都會將內(nèi)存管理拆分成多個復(fù)雜的模塊并引入一些中間層提供緩存和轉(zhuǎn)換的功能，但是內(nèi)存管理系統(tǒng)實際上都可以簡化成兩個模塊，即內(nèi)存分配器(Allocator)、垃圾收集器(Collector)。當(dāng)然除了這兩個模塊之外，在研究內(nèi)存管理時都會引入第三個模塊 — 用戶程序(Mutator)，幫助我們理解整個系統(tǒng)的工作流程。

圖 3 - 內(nèi)存管理系統(tǒng)模塊

 

用戶程序(Mutator)- 可以通過分配器創(chuàng)建對象或者更新對象持有的指針;

內(nèi)存分配器(Allocator)— 處理用戶程序的的內(nèi)存分配請求;

垃圾收集器(Collector)- 標(biāo)記內(nèi)存中的對象并回收不需要的內(nèi)存;

上述的三個模塊是內(nèi)存管理系統(tǒng)中的核心，它們在應(yīng)用程序運(yùn)行期間可以維護(hù)管理內(nèi)存達(dá)到相對平衡的狀態(tài)，我們在介紹內(nèi)存管理時也會圍繞這三個不同的組件，本節(jié)將從基本概念、內(nèi)存分配和垃圾回收三個方面詳細(xì)介紹內(nèi)存管理的相關(guān)理論。

基本概念

基本概念這一節(jié)將介紹內(nèi)存管理中的基本問題，我們會簡單介紹應(yīng)用程序的內(nèi)存布局、內(nèi)存管理中的設(shè)計的常見概念以及廣義上的幾種不同內(nèi)存管理方式，這里會幫助各位讀者從頂層了解內(nèi)存管理。

內(nèi)存布局

操作系統(tǒng)會為在其上運(yùn)行的應(yīng)用程序分配一片巨大的虛擬內(nèi)存，需要注意的是，與操作系統(tǒng)的主存和物理內(nèi)存不一樣，虛擬內(nèi)存并不是在物理上真正存在的概念，它是操作系統(tǒng)構(gòu)建的邏輯概念。應(yīng)用程序的內(nèi)存一般會分成以下幾個不同的區(qū)域：

圖 4 - 內(nèi)存布局

 

• 棧區(qū)(Stack)— 存儲程序執(zhí)行期間的本地變量和函數(shù)的參數(shù)，從高地址向低地址生長;
• 堆區(qū)(Heap)— 動態(tài)內(nèi)存分配區(qū)域，通過 malloc、new、free 和 delete 等函數(shù)管理;
• 未初始化變量區(qū)(BSS)— 存儲未被初始化的全局變量和靜態(tài)變量;
• 數(shù)據(jù)區(qū)(Data)— 存儲在源代碼中有預(yù)定義值的全局變量和靜態(tài)變量;
• 代碼區(qū)(Text)— 存儲只讀的程序執(zhí)行代碼，即機(jī)器指令;

上述五種不同段雖然存儲著不同的數(shù)據(jù)，但是我們可以將它們分成三種不同的內(nèi)存分配類型，也就是靜態(tài)內(nèi)存、棧內(nèi)存和堆內(nèi)存。

靜態(tài)內(nèi)存

靜態(tài)內(nèi)存可以最早追溯到 1960 年的 ALGOL 語言[^1]，靜態(tài)變量的生命周期可以貫穿整個程序。所有靜態(tài)內(nèi)存的布局都是在編譯期間確認(rèn)的，運(yùn)行期間也不會分配新的靜態(tài)內(nèi)存，因為所有的靜態(tài)內(nèi)存都是在編譯期間確認(rèn)的，所以會為這些變量申請固定大小的內(nèi)存空間，這些固定的內(nèi)存空間也會導(dǎo)致靜態(tài)內(nèi)存無法支持函數(shù)的遞歸調(diào)用：

圖 5 - 靜態(tài)內(nèi)存的特性

 

因為編譯器可以確定靜態(tài)變量的地址，所以它們是程序中唯一可以使用絕對地址尋址的變量。當(dāng)程序被加載到內(nèi)存中時，靜態(tài)變量會直接存儲在程序的 BSS 區(qū)或者數(shù)據(jù)區(qū)，這些變量也會在程序退出時被銷毀，正是因為靜態(tài)內(nèi)存的這些特性，我們并不需要在程序運(yùn)行時引入靜態(tài)內(nèi)存的管理機(jī)制。

棧內(nèi)存

棧是應(yīng)用程序中常見的內(nèi)存空間，它遵循后進(jìn)先出的規(guī)則管理存儲的數(shù)據(jù)[^2]。當(dāng)應(yīng)用程序調(diào)用函數(shù)時，它會將函數(shù)的參數(shù)加入棧頂，當(dāng)函數(shù)返回時，它會將當(dāng)前函數(shù)使用的棧全部銷毀。棧內(nèi)存管理的指令也都是由編譯器生成的，我們會使用 BP 和 SP 這兩個寄存器存儲當(dāng)前棧的相關(guān)信息，完全不需要工程師的參與，不過我們也只能在棧上分配大塊固定的數(shù)據(jù)結(jié)構(gòu)。

圖 6 - 棧內(nèi)存的特性

 

因為棧內(nèi)存的釋放是動態(tài)的并且是線性的，所以它可以支持函數(shù)的遞歸調(diào)用，不過運(yùn)行時動態(tài)棧分配策略的引入也會導(dǎo)致程序棧內(nèi)存的溢出，如果我們在編程語言中使用的遞歸函數(shù)超出了程序內(nèi)存的上限，會造成棧溢出錯誤。

堆內(nèi)存

堆內(nèi)存也是應(yīng)用程序中的常見內(nèi)存，與超過函數(shù)作用域會自動回收的棧內(nèi)存相比，它能夠讓函數(shù)的被調(diào)用方向調(diào)用方返回內(nèi)存并在內(nèi)存的分配提供更大的靈活性，不過它提供的靈活性也帶來了內(nèi)存泄漏和懸掛指針等內(nèi)存安全問題。

圖 7 - 堆內(nèi)存的特性

 

因為堆上的內(nèi)存是工程師手動申請的，所以需要在使用結(jié)束時釋放，一旦用過的內(nèi)存沒有釋放，就會造成內(nèi)存泄漏，占用更多的系統(tǒng)內(nèi)存;如果在使用結(jié)束前釋放，會導(dǎo)致危險的懸掛指針，其他對象指向的內(nèi)存已經(jīng)被系統(tǒng)回收或者重新使用。雖然進(jìn)程的內(nèi)存可以劃分成很多區(qū)域，但是當(dāng)我們在談內(nèi)存管理時，一般指的都是堆內(nèi)存的管理，也就是如何解決內(nèi)存泄漏和懸掛指針的問題。

管理方式

我們可以將內(nèi)存管理簡單地分成手動管理和自動管理兩種方式，手動管理內(nèi)存一般是指由工程師在需要時通過 malloc 等函數(shù)手動申請內(nèi)存并在不需要時調(diào)用 free 等函數(shù)釋放內(nèi)存;自動管理內(nèi)存由編程語言的內(nèi)存管理系統(tǒng)自動管理，在大多數(shù)情況下不需要工程師的參與，能夠自動釋放不再使用的內(nèi)存。

圖 8 - 手動管理和自動管理

 

手動管理和自動管理只是內(nèi)存管理的兩種不同方式，本節(jié)將分別介紹兩種內(nèi)存管理的方式以及不同編程語言做出的不同選擇。

手動管理

手動管理內(nèi)存是一種比較傳統(tǒng)的內(nèi)存管理方式，C/C++ 這類系統(tǒng)級的編程語言不包含狹義上的自動內(nèi)存管理機(jī)制，工程師需要主動申請或者釋放內(nèi)存。如果存在理想的工程師能夠精準(zhǔn)地確定內(nèi)存的分配和釋放時機(jī)，人肉的內(nèi)存管理策略只要做到足夠精準(zhǔn)，使用手動管理內(nèi)存的方式可以提高程序的運(yùn)行性能，也不會造成內(nèi)存安全問題，

但是這種理想的工程師往往不存在于現(xiàn)實中，人類因素(Human Factor)總會帶來一些錯誤，內(nèi)存泄漏和懸掛指針基本是 C/C++ 這類語言中最常出現(xiàn)的錯誤，手動的內(nèi)存管理也會占用工程師的大量精力，很多時候都需要思考對象應(yīng)該分配到棧上還是堆上以及堆上的內(nèi)存應(yīng)該何時釋放，維護(hù)成本相對來說還是比較高的，這也是必然要做的權(quán)衡。

自動管理

自動管理內(nèi)存基本是現(xiàn)代編程語言的標(biāo)配，因為內(nèi)存管理模塊的功能非常確定，所以我們可以在編程語言的編譯期或者運(yùn)行時中引入自動的內(nèi)存管理方式，最常見的自動內(nèi)存管理機(jī)制就是垃圾回收，不過除了垃圾回收之外，一些編程語言也會使用自動引用計數(shù)輔助內(nèi)存的管理。

自動的內(nèi)存管理機(jī)制可以幫助工程師節(jié)省大量的與內(nèi)存打交道的時間，讓工程師將全部的精力都放在核心的業(yè)務(wù)邏輯上，提高開發(fā)的效率;在一般情況下，這種自動的內(nèi)存管理機(jī)制都可以很好地解決內(nèi)存泄漏和懸掛指針的問題，但是這也會帶來額外開銷并影響語言的運(yùn)行時性能。

對象頭

對象頭是實現(xiàn)自動內(nèi)存管理的關(guān)鍵元信息，內(nèi)存分配器和垃圾收集器都會訪問對象頭以獲取相關(guān)的信息。當(dāng)我們通過 malloc 等函數(shù)申請內(nèi)存時，往往都需要將內(nèi)存按照指針的大小對齊(32 位架構(gòu)上為 4 字節(jié)，64 位架構(gòu)上為 8 字節(jié))，除了用于對齊的內(nèi)存之外，每一個堆上的對象也都需要對應(yīng)的對象頭：

圖 9 - 對象頭與對象

 

不同的自動內(nèi)存管理機(jī)制會在對象頭中存儲不同的信息，使用垃圾回收的編程語言會存儲標(biāo)記位 MarkBit/MarkWord，例如：Java 和 Go 語言;使用自動引用計數(shù)的會在對象頭中存儲引用計數(shù) RefCount，例如：Objective-C。

編程語言會選擇將對象頭與對象存儲在一起，不過因為對象頭的存儲可能影響數(shù)據(jù)訪問的局部性，所以有些編程語言可能會單獨(dú)開辟一片內(nèi)存空間來存儲對象頭并通過內(nèi)存地址建立兩者之間的隱式聯(lián)系。

內(nèi)存分配

內(nèi)存分配器是內(nèi)存管理系統(tǒng)中的重要組件，它的主要職責(zé)是處理用戶程序的內(nèi)存申請。雖然內(nèi)存分配器的職責(zé)非常重要，但是內(nèi)存的分配和使用其是一個增加系統(tǒng)中熵的過程，所以內(nèi)存分配器的設(shè)計與工作原理相對比較簡單，我們在這里介紹內(nèi)存分配器的兩種類型。

內(nèi)存分配器只包含線性內(nèi)存分配器(Sequential Allocator)和空閑鏈表內(nèi)存分配器(Free-list Allocator)兩種，內(nèi)存管理機(jī)制中的所有內(nèi)存分配器其實都是上述兩種不同分配器的變種，它們的設(shè)計思路完全不同，同時也有著截然不同的應(yīng)用場景和特性，我們在這里依次介紹這兩種內(nèi)存分配器的原理。

線性分配器

線性分配(Bump Allocator)是一種高效的內(nèi)存分配方法，但是有較大的局限性。當(dāng)我們在編程語言中使用線性分配器，我們只需要在內(nèi)存中維護(hù)一個指向內(nèi)存特定位置的指針，當(dāng)用戶程序申請內(nèi)存時，分配器只需要檢查剩余的空閑內(nèi)存、返回分配的內(nèi)存區(qū)域并修改指針在內(nèi)存中的位置，即移動下圖中的指針：

圖 10 - 線性分配器

 

根據(jù)線性分配器的原理，我們可以推測它有較快的執(zhí)行速度，以及較低的實現(xiàn)復(fù)雜度;但是線性分配器無法在內(nèi)存被釋放時重用內(nèi)存。如下圖所示，如果已經(jīng)分配的內(nèi)存被回收，線性分配器是無法重新利用紅色的這部分內(nèi)存的：

圖 11 - 線性分配器回收內(nèi)存

 

正是因為線性分配器的這種特性，我們需要合適的垃圾回收算法配合使用。標(biāo)記壓縮(Mark-Compact)、復(fù)制回收(Copying GC)和分代回收(Generational GC)等算法可以通過拷貝的方式整理存活對象的碎片，將空閑內(nèi)存定期合并，這樣就能利用線性分配器的效率提升內(nèi)存分配器的性能了。

因為線性分配器的使用需要配合具有拷貝特性的垃圾回收算法，所以 C 和 C++ 等需要直接對外暴露指針的語言就無法使用該策略，我們會在下一節(jié)詳細(xì)介紹常見垃圾回收算法的設(shè)計原理。

空閑鏈表分配器

空閑鏈表分配器(Free-List Allocator)可以重用已經(jīng)被釋放的內(nèi)存，它在內(nèi)部會維護(hù)一個類似鏈表的數(shù)據(jù)結(jié)構(gòu)。當(dāng)用戶程序申請內(nèi)存時，空閑鏈表分配器會依次遍歷空閑的內(nèi)存塊，找到足夠大的內(nèi)存，然后申請新的資源并修改鏈表：

圖 12 - 空閑鏈表分配器

 

因為不同的內(nèi)存塊以鏈表的方式連接，所以使用這種方式分配內(nèi)存的分配器可以重新利用回收的資源，但是因為分配內(nèi)存時需要遍歷鏈表，所以它的時間復(fù)雜度就是 O(n)。空閑鏈表分配器可以選擇不同的策略在鏈表中的內(nèi)存塊中進(jìn)行選擇，最常見的就是以下四種方式：

• 首次適應(yīng)(First-Fit)— 從鏈表頭開始遍歷，選擇第一個大小大于申請內(nèi)存的內(nèi)存塊;
• 循環(huán)首次適應(yīng)(Next-Fit)— 從上次遍歷的結(jié)束位置開始遍歷，選擇第一個大小大于申請內(nèi)存的內(nèi)存塊;
• 最優(yōu)適應(yīng)(Best-Fit)— 從鏈表頭遍歷整個鏈表，選擇最合適的內(nèi)存塊;
• 隔離適應(yīng)(Segregated-Fit)— 將內(nèi)存分割成多個鏈表，每個鏈表中的內(nèi)存塊大小相同，申請內(nèi)存時先找到滿足條件的鏈表，再從鏈表中選擇合適的內(nèi)存塊;

上述四種策略的前三種就不過多介紹了，Go 語言使用的內(nèi)存分配策略與第四種策略有些相似，我們通過下圖了解一下該策略的原理：

圖 13 - 隔離適應(yīng)策略

 

如上圖所示，該策略會將內(nèi)存分割成由 4、8、16、32 字節(jié)的內(nèi)存塊組成的鏈表，當(dāng)我們向內(nèi)存分配器申請 8 字節(jié)的內(nèi)存時，我們會在上圖中的第二個鏈表找到空閑的內(nèi)存塊并返回。隔離適應(yīng)的分配策略減少了需要遍歷的內(nèi)存塊數(shù)量，提高了內(nèi)存分配的效率。

垃圾回收

垃圾回收是一種自動的內(nèi)存管理形式[^3]，垃圾收集器是內(nèi)存管理系統(tǒng)的重要組件，內(nèi)存分配器會負(fù)責(zé)在堆上申請內(nèi)存，而垃圾收集器會釋放不再被用戶程序使用的對象。談到垃圾回收，很多人的第一反應(yīng)可能都是暫停程序(stop-the-world、STW)和垃圾回收暫停(GC Pause)，垃圾回收確實會帶來 STW，但是這不是垃圾回收的全部，本節(jié)將詳細(xì)介紹垃圾回收以及垃圾收集器的相關(guān)概念和理論。

什么是垃圾

在深入分析垃圾回收之前，我們需要先明確垃圾回收中垃圾的定義，明確定義能夠幫助我們更精確地理解垃圾回收解決的問題以及它的職責(zé)。計算機(jī)科學(xué)中的垃圾包括對象、數(shù)據(jù)和計算機(jī)系統(tǒng)中的其他的內(nèi)存區(qū)域，這些數(shù)據(jù)不會在未來的計算中使用，因為內(nèi)存資源是有限的，所以我們需要將這些垃圾占用的內(nèi)存交還回堆并在未來復(fù)用[^4]。

圖 14 - 語義和語法垃圾

 

垃圾可以分成語義垃圾和語法垃圾兩種，*語義垃圾(Semantic Garbage)*是計算機(jī)程序中永遠(yuǎn)不會被程序訪問到的對象或者數(shù)據(jù);*語法垃圾(Syntactic Garbage)*是計算機(jī)程序內(nèi)存空間中從根對象無法達(dá)到(Unreachable)的對象或者數(shù)據(jù)。

語義垃圾是不會被使用的的對象，可能包括廢棄的內(nèi)存、不使用的變量，垃圾收集器無法解決程序中語義垃圾的問題，我們需要通過編譯器來一部分語義垃圾。語法垃圾是在對象圖中不能從根節(jié)點達(dá)到的對象，所以語法垃圾在一般情況下都是語義垃圾：

圖 15 - 無法達(dá)到的語法垃圾

 

垃圾收集器能夠發(fā)現(xiàn)并回收的就是對象圖中無法達(dá)到的語法垃圾，通過分析對象之間的引用關(guān)系，我們可以得到圖中根節(jié)點不可達(dá)的對象，這些不可達(dá)的對象會在垃圾收集器的清理階段被回收。

收集器性能

吞吐量(Throughput)和最大暫停時間(Pause time)是兩個衡量垃圾收集器的主要指標(biāo)，除了這兩個指標(biāo)之外，堆內(nèi)存的使用效率和訪問的局部性也是垃圾收集的常用指標(biāo)，我們簡單介紹以下這些指標(biāo)對垃圾收集器的影響。

吞吐量

垃圾收集器的吞吐量其實有兩種解釋，一種解釋是垃圾收集器在執(zhí)行階段的速度，也就是單位時間的標(biāo)記和清理內(nèi)存的能力，我們可以用堆內(nèi)存除以 GC 使用的總時間來計算。

HEAP_SIZE / TOTAL_GC_TIME 

另一種吞吐量計算方法是使用程序運(yùn)行的總時間除以所有 GC 循環(huán)運(yùn)行的總時間，GC 的時間對于整個應(yīng)用程序來說是額外開銷，這個指標(biāo)能看出額外開銷占用資源的百分比，從這一點，我們也能看出 GC 的執(zhí)行效率。

最大暫停時間

由于在垃圾回收的某些階段會觸發(fā) STW，所以用戶程序是不能執(zhí)行的，最長的 STW 時間會嚴(yán)重影響程序處理請求或者提供服務(wù)的尾延遲，所以這一點也是我們在測量垃圾收集器性能時需要考慮的指標(biāo)。

圖 16 - 最大暫停時間

 

使用 STW 垃圾收集器的編程語言，用戶程序在垃圾回收的全部階段都不能執(zhí)行。并發(fā)標(biāo)記清除的垃圾收集器將可以與用戶程序并發(fā)執(zhí)行的工作全部并發(fā)執(zhí)行，能夠減少最大程序暫停時間，

堆使用效率

堆的使用效率也是衡量垃圾收集器的重要指標(biāo)。為了能夠標(biāo)識垃圾，我們需要在內(nèi)存空間中引入包含特定信息的對象頭，這些對象頭都是垃圾收集器帶來的額外開銷，正如網(wǎng)絡(luò)帶寬可能不是最終的下載速度，協(xié)議頭和校驗碼的傳輸會占用網(wǎng)絡(luò)帶寬，對象頭的大小最終也會影響堆內(nèi)存的使用效率;除了對象頭之外，堆在使用過程中出現(xiàn)的碎片也會影響內(nèi)存的使用效率，為了保證內(nèi)存的對齊，我們會在內(nèi)存中留下很多縫隙，這些縫隙也是內(nèi)存管理帶來的開銷。

訪問局部性

訪問的局部性是我們在討論內(nèi)存管理時不得不談的話題，空間的局部性是指處理器在短時間內(nèi)總會重復(fù)地訪問同一片或者相鄰的內(nèi)存區(qū)域，操作系統(tǒng)會以內(nèi)存頁為單位管理內(nèi)存空間，在理想情況下，合理的內(nèi)存布局可以使得垃圾收集器和應(yīng)用程序都能充分地利用空間局部性提高程序的執(zhí)行效率。

收集器類型

垃圾收集器的類型在總體上可以分成直接(Direct)垃圾收集器和跟蹤(Tracing)垃圾收集器。直接垃圾收集器包括引用計數(shù)(Refernce-Counting)，跟蹤垃圾收集器包含標(biāo)記清理、標(biāo)記壓縮、復(fù)制垃圾回收等策略，而引用計數(shù)收集器卻不是特別常見，少數(shù)編程語言會使用這種方式管理內(nèi)存。

圖 17 - 垃圾收集器類型

 

除了直接和跟蹤垃圾收集器這些相對常見的垃圾回收方法之外，也有使用所有權(quán)或者手動的方式管理內(nèi)存，我們在本節(jié)中會介紹引用計數(shù)、標(biāo)記清除、標(biāo)記壓縮和復(fù)制垃圾回收四種不同類型垃圾收集器的設(shè)計原理以及它們的優(yōu)缺點。

引用計數(shù)

基于引用計數(shù)的垃圾收集器是直接垃圾收集器，當(dāng)我們改變對象之間的引用關(guān)系時會修改對象之間的引用計數(shù)，每個對象的引用計數(shù)都記錄了當(dāng)前有多少個對象指向了該對象，當(dāng)對象的引用計數(shù)歸零時，當(dāng)前對象就會被自動釋放。在使用引用計數(shù)的編程語言中，垃圾收集是在用戶程序運(yùn)行期間實時發(fā)生的，所以在理論上也就不存在 STW 或者明顯地垃圾回收暫停。

圖 18 - 對象的引用計數(shù)

 

如上圖所示，基于引用計數(shù)的垃圾收集器需要應(yīng)用程序在對象頭中存儲引用計數(shù)，引用計數(shù)就是該類型的收集器在內(nèi)存中引入的額外開銷。我們在這里舉一個例子介紹引用計數(shù)的工作原理，如果在使用引用計數(shù)回收器的編程語言中使用如下所示賦值語句時：

obj.field = new_ref; 

1. 對象 obj 原來引用的對象 old_ref 的引用計數(shù)會減一;
2. 對象 obj 引用的新對象 new_ref 的引用計數(shù)會加一;
3. 如果 old_ref 對象的引用計數(shù)歸零，我們會釋放該對象回收它的內(nèi)存;

這種類型的垃圾收集器會帶來兩個比較常見的問題，分別是遞歸的對象回收和循環(huán)引用：

• 遞歸回收 — 每當(dāng)對象的引用關(guān)系發(fā)生改變時，我們都需要計算對象的新引用計數(shù)，一旦對象被釋放，我們就需要遞歸地訪問所有該對象的引用并將被引用對象的計數(shù)器減一，一旦涉及到較多的對象就可能會造成 GC 暫停;
• 循環(huán)引用 — 對象的相互引用在對象圖中也非常常見，如果對象之間的引用都是強(qiáng)引用，循環(huán)引用會導(dǎo)致多個對象的計數(shù)器都不會歸零，最終會造成內(nèi)存泄漏;

遞歸回收是使用引用計數(shù)時不得不面對的問題，我們很難在工程上解決該問題;不過使用引用計數(shù)的編程語言卻可以利用弱引用來解決循環(huán)引用的問題，弱引用也是對象之間的引用關(guān)系，建立和銷毀弱引用關(guān)系都不會修改雙方的引用計數(shù)，這就能避免對象之間的弱引用關(guān)系，不過這也需要工程師對引用關(guān)系作出額外的并且正確的判斷。

圖 19 - 強(qiáng)引用與弱引用

 

除了弱引用之外，一些編程語言也會在引用計數(shù)的基礎(chǔ)上加入標(biāo)記清除技術(shù)，通過遍歷和標(biāo)記堆中不再被使用的對象解決循環(huán)引用的問題。

引用計數(shù)垃圾收集器是一種非移動(Non-moving)的垃圾回收策略，它在回收內(nèi)存的過程中不會移動已有的對象，很多編程語言都會對工程師直接暴露內(nèi)存的指針，所以 C、C++ 以及 Objective-C 等編程語言其實都可以使用引用計數(shù)來解決內(nèi)存管理的問題。

標(biāo)記清除

標(biāo)記清除(Mark-Sweep)是最簡單也最常見的垃圾收集策略，它的執(zhí)行過程可以分成標(biāo)記和清除兩個階段，標(biāo)記階段會使用深度優(yōu)先或者廣度優(yōu)先算法掃描堆中的存活對象，而清除階段會回收內(nèi)存中的垃圾。當(dāng)我們使用該策略回收垃圾時，它會首先從根節(jié)點出發(fā)沿著對象的引用遍歷堆中的全部對象，能夠被訪問到的對象是存活的對象，不能被訪問到的對象就是內(nèi)存中的垃圾。

如下圖所示，內(nèi)存空間中包含多個對象，我們從根對象出發(fā)依次遍歷對象的子對象并將從根節(jié)點可達(dá)的對象都標(biāo)記成存活狀態(tài)，即 A、C 和 D 三個對象，剩余的 B、E 和 F 三個對象因為從根節(jié)點不可達(dá)，所以會被當(dāng)做垃圾：

圖 20 - 標(biāo)記清除的標(biāo)記階段

 

標(biāo)記階段結(jié)束后會進(jìn)入清除階段，在該階段中收集器會依次遍歷堆中的所有對象，釋放其中沒有被標(biāo)記的 B、E 和 F 三個對象并將新的空閑內(nèi)存空間以鏈表的結(jié)構(gòu)串聯(lián)起來，方便內(nèi)存分配器的使用。

圖 21 - 標(biāo)記清除的收集階段

 

使用標(biāo)記清除算法的編程語言需要在對象頭中加入表示對象存活的標(biāo)記位(Mark Bit)，標(biāo)記位與操作系統(tǒng)的寫時復(fù)制不兼容，因為即使內(nèi)存頁中的對象沒有被修改，垃圾收集器也會修改內(nèi)存頁中對象相鄰的標(biāo)記位導(dǎo)致內(nèi)存頁的復(fù)制。我們可以使用位圖(Bitmap)標(biāo)記避免這種情況，表示對象存活的標(biāo)記與對象分別存儲，清理對象時也只需要遍歷位圖，能夠降低清理過程的額外開銷。

如上圖所示，使用標(biāo)記清除算法的垃圾收集器一般會使用基于空閑鏈表的分配器，因為對象在不被使用時會被就地回收，所以長時間運(yùn)行的程序會出現(xiàn)很多內(nèi)存碎片，這會降低內(nèi)存分配器的分配效率，在實現(xiàn)上我們可以將空閑鏈表按照對象大小分成不同的區(qū)以減少內(nèi)存中的碎片。

標(biāo)記清除策略是一種實現(xiàn)簡單的垃圾收集策略，但是它的內(nèi)存碎片化問題也比較嚴(yán)重，簡單的內(nèi)存回收策略也增加了內(nèi)存分配的開銷和復(fù)雜度，當(dāng)用戶程序申請內(nèi)存時，我們也需要在內(nèi)存中找到足夠大的塊分配內(nèi)存。

標(biāo)記壓縮

標(biāo)記壓縮(Mark-Compact)也是比較常見的垃圾收集算法，與標(biāo)記清除算法類似，標(biāo)記壓縮的執(zhí)行過程可以分成標(biāo)記和壓縮兩個階段。該算法在標(biāo)記階段也會從根節(jié)點遍歷對象，查找并標(biāo)記所有存活的對象;在壓縮階段，我們會將所有存活的對象緊密排列，『擠出』存活對象之間的縫隙：

圖 22 - 標(biāo)記壓縮算法

 

因為在壓縮階段我們需要移動存活的對象，所以這一種 moving 收集器，如果編程語言支持使用指針訪問對象，那么我們就無法使用該算法。標(biāo)記的過程相對比較簡單，我們在這里以 Lisp 2 壓縮算法為例重點介紹該算法的壓縮階段：

1. 計算當(dāng)前對象遷移后的最終位置并將位置存儲在轉(zhuǎn)發(fā)地址(Forwarding Address)中;
2. 根據(jù)當(dāng)前對象子對象的轉(zhuǎn)發(fā)地址，將引用指向新的位置;
3. 將所有存活的對象移動到對象頭中轉(zhuǎn)發(fā)地址的位置;

從上述過程我們可以看出，使用標(biāo)記壓縮算法的編程語言不僅要在對象頭中存儲標(biāo)記位，還需要存儲當(dāng)前對象的轉(zhuǎn)發(fā)地址，這增加了對象在內(nèi)存中的額外開銷。

標(biāo)記壓縮算法的實現(xiàn)比較復(fù)雜，在執(zhí)行的過程中需要遍歷三次堆中的對象，作為 moving 的垃圾收集器，它不適用于 C、C++ 等編程語言;壓縮算法的引入可以減少程序中的內(nèi)存碎片，我們可以直接使用最簡單的線性分配器為用戶程序快速分配內(nèi)存。

復(fù)制垃圾回收

復(fù)制垃圾回收(Copying GC)也是跟蹤垃圾收集器的一種，它會將應(yīng)用程序的堆分成兩個大小相等的區(qū)域，如下圖所示，其中左側(cè)區(qū)域負(fù)責(zé)為用戶程序分配內(nèi)存空間，而右側(cè)區(qū)域用于垃圾回收。

圖 23 - 復(fù)制垃圾回收

 

當(dāng)用戶程序使用的內(nèi)存超過上圖中的左側(cè)區(qū)域就會出現(xiàn)內(nèi)存不足(Out-of memory、OOM)，垃圾收集器在這時會開啟新的垃圾收集循環(huán)，復(fù)制垃圾回收的執(zhí)行過程可以非常以下的四個階段：

1. 復(fù)制階段 — 從 GC 根節(jié)點出發(fā)遍歷內(nèi)存中的對象，將發(fā)現(xiàn)的存活對象遷移到右側(cè)的內(nèi)存中;
2. 轉(zhuǎn)發(fā)階段 — 在原始對象的對象頭或者在原位置設(shè)置新對象的轉(zhuǎn)發(fā)地址(Forwarding Address)，如果其他對象引用了該對象可以從轉(zhuǎn)發(fā)地址轉(zhuǎn)到新的地址;
3. 修復(fù)指針 — 遍歷當(dāng)前對象持有的引用，如果引用指向了左側(cè)堆中的對象，回到第一步遷移發(fā)現(xiàn)的新對象;
4. 交換階段 — 當(dāng)內(nèi)存中不存在需要遷移的對象之后，交換左右兩側(cè)的內(nèi)存區(qū)域;

圖 24 - 復(fù)制垃圾回收的復(fù)制階段

 

如上圖所示，當(dāng)我們把 A 對象復(fù)制到右側(cè)的區(qū)域后，會將原始的 A 對象指向新的 A 對象，這樣其他引用 A 的對象可以快速找到它的新地址;因為 A 對象的復(fù)制是『像素級復(fù)制』，所以 A 對象仍然會指向左側(cè)內(nèi)存的 C 對象，這時需要將 C 對象復(fù)制到新的內(nèi)存區(qū)域并修改 A 對象的指針。在最后，當(dāng)不存在需要拷貝的對象時，我們可以直接交換兩個內(nèi)存區(qū)域的指針。

復(fù)制垃圾回收與標(biāo)記壓縮算法一樣都會拷貝對象，能夠減少程序中的內(nèi)存碎片，我們可以使用線性的分配器快速為用戶程序分配內(nèi)存。因為只需要掃描一半的堆，遍歷堆的次數(shù)也會減少，所以可以減少垃圾回收的時間，但是這也會降低內(nèi)存的利用率。

高級垃圾回收

內(nèi)存管理是一個相對比較大的話題，我們在上一小節(jié)介紹了垃圾回收的一些基本概念，其中包括常見的垃圾回收算法：引用計數(shù)、標(biāo)記清除、標(biāo)記壓縮和復(fù)制垃圾回收，這些算法都是比較基本的垃圾回收算法，我們在這一節(jié)中將詳細(xì)介紹一些高級的垃圾回收算法，它們會利用基本的垃圾回收算法和新的數(shù)據(jù)結(jié)構(gòu)構(gòu)建更復(fù)雜的收集器。

分代垃圾收集器

分代垃圾回收(Generational garbage collection)是在生產(chǎn)環(huán)境中比較常見的垃圾收集算法，該算法主要建立在弱分代假設(shè)(Weak Generational Hypothesis)上 —— 大多數(shù)的對象會在生成后馬上變成垃圾，只有極少數(shù)的對象可以存活很久[^5]。根據(jù)該經(jīng)驗，分代垃圾回收會把堆中的對象分成多個代，不同代垃圾回收的觸發(fā)條件和算法都完全不同。

圖 25 - 青年代和老年代

 

常見的分代垃圾回收會將堆分成青年代(Young、Eden)和老年代(Old、Tenured)，所有的對象在剛剛初始化時都會進(jìn)入青年代，而青年代觸發(fā) GC 的頻率也更高;而老年代的對象 GC 頻率相對比較低，只有青年代的對象經(jīng)過多輪 GC 沒有被釋放才可能被晉升(Promotion)到老年代，晉升的過程與復(fù)制垃圾回收算法的執(zhí)行過程相差無幾。

青年代的垃圾回收被稱作是 Minor GC 循環(huán)，而老年代的垃圾回收被稱作 Major GC 循環(huán)，F(xiàn)ull GC 循環(huán)一般是指整個堆的垃圾回收，需要注意的是很多時候我們都會混淆 Major GC 循環(huán)和 Full GC 循環(huán)，在討論時一定要先搞清楚雙方對這些名詞的理解是否一致。

青年代的垃圾回收只會掃描整個堆的一部分，這能夠減少一次垃圾回收需要的掃描的堆大小和程序的暫停時間，提高垃圾回收的吞吐量。然而分代也為垃圾回收引入了復(fù)雜度，其中最常見的問題是跨代引用(Intergenerational Pointer)，即老年代引用了青年代的對象，如果堆中存在跨代引用，那么在 Minor GC 循環(huán)中我們不僅應(yīng)該遍歷垃圾回收的根對象，還需要從包含跨代引用的對象出發(fā)標(biāo)記青年代中的對象。

圖 26 - 跨代引用

 

為了處理分代垃圾回收的跨代引用，我們需要解決兩個問題，分別是如何識別堆中的跨代引用以及如何存儲識別的跨代引用，在通常情況下我們會使用*寫屏障(Write Barrier)識別跨代引用并使用卡表(Card Table)*存儲相關(guān)的數(shù)據(jù)。

注意：卡表只是標(biāo)記或者存儲跨代引用的一種方式，除了卡表我們也可以使用記錄集(Record Set)存儲跨代引用的老年代對象或者使用頁面標(biāo)記按照操作系統(tǒng)內(nèi)存頁的維度標(biāo)記老年代的對象。

寫屏障是當(dāng)對象之間的指針發(fā)生改變時調(diào)用的代碼片段，這段代碼會判斷該指針是不是從老年代對象指向青年代對象的跨代引用。如果該指針是跨代引用，我們會在如下所示的卡表中標(biāo)記老年代對象所在的區(qū)域：

圖 27 - 卡表

 

卡表與位圖比較相似，它也由一系列的比特位組成，其中每一個比特位都對應(yīng)著老年區(qū)中的一塊內(nèi)存，如果該內(nèi)存中的對象存在指向青年代對象的指針，那么這塊內(nèi)存在卡表中就會被標(biāo)記，當(dāng)觸發(fā) Minor GC 循環(huán)時，除了從根對象遍歷青年代堆之外，我們還會從卡表標(biāo)記區(qū)域內(nèi)的全部老年代對象開始遍歷青年代。

分代垃圾回收基于弱分代假說，結(jié)合了復(fù)制垃圾回收、寫屏障以及卡表等技術(shù)，將內(nèi)存中的堆區(qū)分割成了青年代和老年代等區(qū)域，為不同的代使用不同的內(nèi)存分配和垃圾回收算法，可以有效地減少 GC 循環(huán)遍歷的堆大小和處理時間，但是寫屏障技術(shù)也會帶了額外開銷，移動收集器的特性也使它無法在 C、C++ 等編程語言中使用，在部分場景下弱分代假說不一定會成立，如果大多數(shù)的對象都會活得很久，那么使用分代垃圾回收可能會起到反效果。

標(biāo)記區(qū)域收集器

標(biāo)記區(qū)域收集器(Mark-Region Garbage Collector)是 2008 年提出的垃圾收集算法[^6]，這個算法也被稱作混合垃圾回收(Immix GC)，它結(jié)合了標(biāo)記清除和復(fù)制垃圾回收算法，我們使用前者來追蹤堆中的存活對象，使用后者減少內(nèi)存中存在的碎片。

圖 28 - 標(biāo)記區(qū)域收集器

 

Immix 垃圾回收算法包含兩個組件，分別是用于標(biāo)記區(qū)域的收集器和去碎片化機(jī)制[^7]。標(biāo)記區(qū)域收集器與標(biāo)記清除收集器比較類似，它將堆內(nèi)存拆分成特定大小的內(nèi)存塊，再將所有的內(nèi)存塊拆分成特定大小的線。當(dāng)用戶程序申請內(nèi)存時，它會在上述內(nèi)存塊中查找空閑的線并使用線性分配器快速分配內(nèi)存;通過引入粗粒度的內(nèi)存塊和細(xì)粒度的線，可以更好地控制內(nèi)存的分配和釋放。

圖 29 - 線性分配器的光標(biāo)

 

標(biāo)記區(qū)域收集器與標(biāo)記清除收集器比較類似，因為它們不會移動對象，所以都會面臨內(nèi)存碎片化的問題。如下圖所示，標(biāo)記區(qū)域收集器在回收內(nèi)存時都是以塊和線為單位進(jìn)行回收的，所以只要當(dāng)前內(nèi)存線中包含存活對象，收集器就會保留該片內(nèi)存區(qū)域，這會帶來我們在上面提到的內(nèi)存碎片。

Immix 引入的機(jī)會轉(zhuǎn)移(Opportunistic Evacuation)機(jī)制能夠有效地減少程序中的碎片化，當(dāng)收集器在內(nèi)存塊中遇到可以被轉(zhuǎn)移的對象，它就會使用復(fù)制垃圾回收算法將當(dāng)前塊中的存活對象移動到新的塊中并釋放原塊中的內(nèi)存。

標(biāo)記區(qū)域收集器將堆內(nèi)存分成了粗粒度的內(nèi)存塊和細(xì)粒度的內(nèi)存線，結(jié)合了標(biāo)記清除算法和復(fù)制垃圾回收幾種基本垃圾收集器的特性，既能夠提升垃圾收集器的吞吐量，還能夠利用線性分配器提高內(nèi)存的分配速度，但是該收集器的實現(xiàn)相對比較復(fù)雜。

增量并發(fā)收集器

相信很多人對垃圾收集器的印象都是暫停程序(Stop the world，STW)，隨著用戶程序申請越來越多的內(nèi)存，系統(tǒng)中的垃圾也逐漸增多;當(dāng)程序的內(nèi)存占用達(dá)到一定閾值時，整個應(yīng)用程序就會全部暫停，垃圾收集器會掃描已經(jīng)分配的所有對象并回收不再使用的內(nèi)存空間，當(dāng)這個過程結(jié)束后，用戶程序才可以繼續(xù)執(zhí)行。

傳統(tǒng)的垃圾收集算法會在垃圾收集的執(zhí)行期間暫停應(yīng)用程序，一旦觸發(fā)垃圾收集，垃圾收集器就會搶占 CPU 的使用權(quán)占據(jù)大量的計算資源以完成標(biāo)記和清除工作，然而很多追求實時的應(yīng)用程序無法接受長時間的 STW。

圖 30 - 垃圾收集與暫停程序

 

遠(yuǎn)古時代的計算資源還沒有今天這么豐富，今天的計算機(jī)往往都是多核的處理器，垃圾收集器一旦開始執(zhí)行就會浪費(fèi)大量的計算資源，為了減少應(yīng)用程序暫停的最長時間和垃圾收集的總暫停時間，我們會使用下面的策略優(yōu)化現(xiàn)代的垃圾收集器：

• 增量垃圾收集 — 增量地標(biāo)記和清除垃圾，降低應(yīng)用程序暫停的最長時間;
• 并發(fā)垃圾收集 — 利用多核的計算資源，在用戶程序執(zhí)行時并發(fā)標(biāo)記和清除垃圾;

因為增量和并發(fā)兩種方式都可以與用戶程序交替運(yùn)行，所以我們需要使用屏障技術(shù)保證垃圾收集的正確性;與此同時，應(yīng)用程序也不能等到內(nèi)存溢出時觸發(fā)垃圾收集，因為當(dāng)內(nèi)存不足時，應(yīng)用程序已經(jīng)無法分配內(nèi)存，這與直接暫停程序沒有什么區(qū)別，增量和并發(fā)的垃圾收集需要提前觸發(fā)并在內(nèi)存不足前完成整個循環(huán)，避免程序的長時間暫停。

增量式(Incremental)的垃圾收集是減少程序最長暫停時間的一種方案，它可以將原本時間較長的暫停時間切分成多個更小的 GC 時間片，雖然從垃圾收集開始到結(jié)束的時間更長了，但是這也減少了應(yīng)用程序暫停的最大時間：

圖 31 - 增量垃圾收集器

 

需要注意的是，增量式的垃圾收集需要與三色標(biāo)記法一起使用，為了保證垃圾收集的正確性，我們需要在垃圾收集開始前打開寫屏障，這樣用戶程序?qū)?nèi)存的修改都會先經(jīng)過寫屏障的處理，保證了堆內(nèi)存中對象關(guān)系的強(qiáng)三色不變性或者弱三色不變性。雖然增量式的垃圾收集能夠減少最大的程序暫停時間，但是增量式收集也會增加一次 GC 循環(huán)的總時間，在垃圾收集期間，因為寫屏障的影響用戶程序也需要承擔(dān)額外的計算開銷，所以增量式的垃圾收集也不是只有優(yōu)點的。

并發(fā)(Concurrent)的垃圾收集不僅能夠減少程序的最長暫停時間，還能減少整個垃圾收集階段的時間，通過開啟讀寫屏障、利用多核優(yōu)勢與用戶程序并行執(zhí)行，并發(fā)垃圾收集器確實能夠減少垃圾收集對應(yīng)用程序的影響：

圖 32 - 并發(fā)垃圾收集器

 

雖然并發(fā)收集器能夠與用戶程序一起運(yùn)行，但是并不是所有階段都可以與用戶程序一起運(yùn)行，部分階段還是需要暫停用戶程序的，不過與傳統(tǒng)的算法相比，并發(fā)的垃圾收集可以將能夠并發(fā)執(zhí)行的工作盡量并發(fā)執(zhí)行;當(dāng)然，因為讀寫屏障的引入，并發(fā)的垃圾收集器也一定會帶來額外開銷，不僅會增加垃圾收集的總時間，還會影響用戶程序，這是我們在設(shè)計垃圾收集策略時必須要注意的。

但是因為增量并發(fā)收集器的并發(fā)標(biāo)記階段會與用戶程序一同或者交替運(yùn)行，所以可能出現(xiàn)標(biāo)記為垃圾的對象被用戶程序中的其他對象重新引用，當(dāng)垃圾回收的標(biāo)記階段結(jié)束后，被錯誤標(biāo)記為垃圾的對象會被直接回收，這就會帶來非常嚴(yán)重的問題，想要解決增量并發(fā)收集器的這個問題，我們需要了解三色抽象和屏障技術(shù)。

三色抽象

為了解決原始標(biāo)記清除算法帶來的長時間 STW，多數(shù)現(xiàn)代的追蹤式垃圾收集器都會實現(xiàn)三色標(biāo)記算法的變種以縮短 STW 的時間。三色標(biāo)記算法將程序中的對象分成白色、黑色和灰色三類[^8]：

• 白色對象 — 潛在的垃圾，其內(nèi)存可能會被垃圾收集器回收;
• 黑色對象 — 活躍的對象，包括不存在任何引用外部指針的對象以及從根對象可達(dá)的對象;
• 灰色對象 — 活躍的對象，因為存在指向白色對象的外部指針，垃圾收集器會掃描這些對象的子對象;

圖 33 - 三色的對象

 

在垃圾收集器開始工作時，程序中不存在任何的黑色對象，垃圾收集的根對象會被標(biāo)記成灰色，垃圾收集器只會從灰色對象集合中取出對象開始掃描，當(dāng)灰色集合中不存在任何對象時，標(biāo)記階段就會結(jié)束。

圖 34 - 三色標(biāo)記垃圾收集器的執(zhí)行過程

 

三色標(biāo)記垃圾收集器的工作原理很簡單，我們可以將其歸納成以下幾個步驟：

1. 從灰色對象的集合中選擇一個灰色對象并將其標(biāo)記成黑色;
2. 將黑色對象指向的所有對象都標(biāo)記成灰色，保證該對象和被該對象引用的對象都不會被回收;
3. 重復(fù)上述兩個步驟直到對象圖中不存在灰色對象;

當(dāng)三色的標(biāo)記清除的標(biāo)記階段結(jié)束之后，應(yīng)用程序的堆中就不存在任何的灰色對象，我們只能看到黑色的存活對象以及白色的垃圾對象，垃圾收集器可以回收這些白色的垃圾，下面是使用三色標(biāo)記垃圾收集器執(zhí)行標(biāo)記后的堆內(nèi)存，堆中只有對象 D 為待回收的垃圾：

圖 35 - 三色標(biāo)記后的堆

 

因為用戶程序可能在標(biāo)記執(zhí)行的過程中修改對象的指針，所以三色標(biāo)記清除算法本身是不可以并發(fā)或者增量執(zhí)行的，它仍然需要 STW，在如下所示的三色標(biāo)記過程中，用戶程序建立了從 A 對象到 D 對象的引用，但是因為程序中已經(jīng)不存在灰色對象了，所以 D 對象會被垃圾收集器錯誤地回收。

圖 36 - 三色標(biāo)記與用戶程序

 

本來不應(yīng)該被回收的對象卻被回收了，這在內(nèi)存管理中是非常嚴(yán)重的錯誤，我們將這種錯誤成為懸掛指針，即指針沒有指向特定類型的合法對象，影響了內(nèi)存的安全性[^9]，想要并發(fā)或者增量地標(biāo)記對象還是需要使用屏障技術(shù)。

垃圾回收屏障

內(nèi)存屏障技術(shù)是一種屏障指令，它可以讓 CPU 或者編譯器在執(zhí)行內(nèi)存相關(guān)操作時遵循特定的約束，目前的多數(shù)的現(xiàn)代處理器都會亂序執(zhí)行指令以最大化性能，但是該技術(shù)能夠保證代碼對內(nèi)存操作的順序性，在內(nèi)存屏障前執(zhí)行的操作一定會先于內(nèi)存屏障后執(zhí)行的操作[^10]。

想要在并發(fā)或者增量的標(biāo)記算法中保證正確性，我們需要達(dá)成以下兩種三色不變性(Tri-color invariant)中的任意一種：

• 強(qiáng)三色不變性 — 黑色對象不會指向白色對象，只會指向灰色對象或者黑色對象;
• 弱三色不變性 — 黑色對象指向的白色對象必須包含一條從灰色對象經(jīng)由多個白色對象的可達(dá)路徑[^11];

 

 

圖 37 - 三色不變性

 

 

上圖分別展示了遵循強(qiáng)三色不變性和弱三色不變性的堆內(nèi)存，遵循上述兩個不變性中的任意一個，我們都能保證垃圾收集算法的正確性，而屏障技術(shù)就是在并發(fā)或者增量標(biāo)記過程中保證三色不變性的重要技術(shù)。

垃圾收集中的屏障技術(shù)更像是一個鉤子方法，它是在用戶程序讀取對象、創(chuàng)建新對象以及更新對象指針時執(zhí)行的一段代碼，根據(jù)操作類型的不同，我們可以將它們分成讀屏障(Read barrier)和寫屏障(Write barrier)兩種，因為讀屏障需要在讀操作中加入代碼片段，對用戶程序的性能影響很大，所以編程語言往往都會采用寫屏障保證三色不變性。

我們在這里想要介紹的是以下幾種寫屏障技術(shù)，分別是 Dijkstra 提出的插入寫屏障[^12]和 Yuasa 提出的刪除寫屏障[^13]，這里會分析它們?nèi)绾伪ＷC三色不變性和垃圾收集器的正確性。

插入寫屏障

Dijkstra 在 1978 年提出了插入寫屏障，通過如下所示的寫屏障，用戶程序和垃圾收集器可以在交替工作的情況下保證程序執(zhí)行的正確性：

writePointer(slot, ptr): 
    shade(ptr) 
    *field = ptr 

上述插入寫屏障的偽代碼非常好理解，每當(dāng)我們執(zhí)行類似 *slot = ptr 的表達(dá)式時，我們會執(zhí)行上述寫屏障通過 shade 函數(shù)嘗試改變指針的顏色。如果 ptr 指針是白色的，那么該函數(shù)會將該對象設(shè)置成灰色，其他情況則保持不變。

圖 38 - Dijkstra 插入寫屏障

 

假設(shè)我們在應(yīng)用程序中使用 Dijkstra 提出的插入寫屏障，在一個垃圾收集器和用戶程序交替運(yùn)行的場景中會出現(xiàn)如上圖所示的標(biāo)記過程：

1. 垃圾收集器將根對象指向 A 對象標(biāo)記成黑色并將 A 對象指向的對象 B 標(biāo)記成灰色;
2. 用戶程序修改 A 對象的指針，將原本指向 B 對象的指針指向 C 對象，這時觸發(fā)寫屏障將 C 對象標(biāo)記成灰色;
3. 垃圾收集器依次遍歷程序中的其他灰色對象，將它們分別標(biāo)記成黑色;

Dijkstra 的插入寫屏障是一種相對保守的屏障技術(shù)，它會將有存活可能的對象都標(biāo)記成灰色以滿足強(qiáng)三色不變性。在如上所示的垃圾收集過程中，實際上不再存活的 B 對象最后沒有被回收;而如果我們在第二和第三步之間將指向 C 對象的指針改回指向 B，垃圾收集器仍然認(rèn)為 C 對象是存活的，這些被錯誤標(biāo)記的垃圾對象只有在下一個循環(huán)才會被回收。

插入式的 Dijkstra 寫屏障雖然實現(xiàn)非常簡單并且也能保證強(qiáng)三色不變性，但是它也有很明顯的缺點。因為棧上的對象在垃圾收集中也會被認(rèn)為是根對象，所以為了保證內(nèi)存的安全，Dijkstra 必須為棧上的對象增加寫屏障或者在標(biāo)記階段完成重新對棧上的對象對象進(jìn)行掃描，這兩種方法各有各的缺點，前者會大幅度增加寫入指針的額外開銷，后者重新掃描棧對象時需要暫停程序，垃圾收集算法的設(shè)計者需要在這兩者之前做出權(quán)衡。

刪除寫屏障

Yuasa 在 1990 年的論文 Real-time garbage collection on general-purpose machines 中提出了刪除寫屏障，因為一旦該寫屏障開始工作，它就會保證開啟寫屏障時堆上所有對象的可達(dá)，所以也被稱作快照垃圾收集(Snapshot GC)[^14]：

This guarantees that no objects will become unreachable to the garbage collector traversal all objects which are live at the beginning of garbage collection will be reached even if the pointers to them are overwritten.

該算法會使用如下所示的寫屏障保證增量或者并發(fā)執(zhí)行垃圾收集時程序的正確性：

writePointer(slot, ptr) 
    shade(*slot) 
    *slot = ptr 

上述代碼會在老對象的引用被刪除時，將白色的老對象涂成灰色，這樣刪除寫屏障就可以保證弱三色不變性，老對象引用的下游對象一定可以被灰色對象引用。

圖 39 - Yuasa 刪除寫屏障

 

假設(shè)我們在應(yīng)用程序中使用 Yuasa 提出的刪除寫屏障，在一個垃圾收集器和用戶程序交替運(yùn)行的場景中會出現(xiàn)如上圖所示的標(biāo)記過程：

1. 垃圾收集器將根對象指向 A 對象標(biāo)記成黑色并將 A 對象指向的對象 B 標(biāo)記成灰色;
2. 用戶程序?qū)?A 對象原本指向 B 的指針指向 C，觸發(fā)刪除寫屏障，但是因為 B 對象已經(jīng)是灰色的，所以不做改變;
3. 用戶程序?qū)?B 對象原本指向 C 的指針刪除，觸發(fā)刪除寫屏障，白色的 C 對象被涂成灰色;
4. 垃圾收集器依次遍歷程序中的其他灰色對象，將它們分別標(biāo)記成黑色;

上述過程中的第三步觸發(fā)了 Yuasa 刪除寫屏障的著色，因為用戶程序刪除了 B 指向 C 對象的指針，所以 C 和 D 兩個對象會分別違反強(qiáng)三色不變性和弱三色不變性：

• 強(qiáng)三色不變性 — 黑色的 A 對象直接指向白色的 C 對象;
• 弱三色不變性 — 垃圾收集器無法從某個灰色對象出發(fā)，經(jīng)過幾個連續(xù)的白色對象訪問白色的 C 和 D 兩個對象;

Yuasa 刪除寫屏障通過對 C 對象的著色，保證了 C 對象和下游的 D 對象能夠在這一次垃圾收集的循環(huán)中存活，避免發(fā)生懸掛指針以保證用戶程序的正確性。

總結(jié)

內(nèi)存管理在今天仍然是十分重要的話題，當(dāng)我們在討論編程語言的性能和便利程度時，內(nèi)存管理機(jī)制都是繞不開的。編程語言在設(shè)計內(nèi)存管理機(jī)制時，往往需要在手動管理和自動管理之間進(jìn)行抉擇，現(xiàn)代的大多數(shù)編程語言為了減少工程師的負(fù)擔(dān)，多數(shù)都會選擇使用垃圾回收的方式自動管理內(nèi)存，但是也有少數(shù)編程語言通過手動管理追求極致的性能。

想要在一篇文章中詳盡展示內(nèi)存管理的方方面面是不可能的，我們可能需要一本書或者幾本書的厚度才能詳細(xì)地展示內(nèi)存管理的相關(guān)技術(shù)，這里更多側(cè)重的還是垃圾回收，Rust 的所有權(quán)、生命周期以及 C++ 的智能指針等機(jī)制在文章中都沒有提及，感興趣的讀者可以自行了解。

[^1]: Wikipedia: Static variable https://en.wikipedia.org/wiki/Static_variable

[^2]: Wikipedia: Stack-based memory allocation https://en.wikipedia.org/wiki/Stack-based_memory_allocation

[^3]: Wikipedia: Garbage collection (computer science) https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

[^4]: Wikipedia: Garbage (computer science) https://en.wikipedia.org/wiki/Garbage_(computer_science)

[^5]: Garbage Collection in Java (1) - Heap Overview http://insightfullogic.com/2013/Feb/20/garbage-collection-java-1/

[^6]: Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance. Stephen M. Blackburn. Kathryn S. McKinley. 2008. http://www.cs.utexas.edu/users/speedway/DaCapo/papers/immix-pldi-2008.pdf

[^7]: The CS 6120 Course Blog. Siqiu Yao. 2019. https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/immix/

[^8]: "Tri-color marking" https://en.wikipedia.org/wiki/Tracing_garbage_collection#Tri-color_marking

[^9]: "Dangling pointer" https://en.wikipedia.org/wiki/Dangling_pointer

[^10]: "Wikpedia: Memory barrier" https://en.wikipedia.org/wiki/Memory_barrier

[^11]: P. P. Pirinen. Barrier techniques for incremental tracing. In ACM SIGPLAN Notices, 34(3), 20–25, October 1998. https://dl.acm.org/doi/10.1145/301589.286863

[^12]: E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21(11), 966–975, 1978. https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD520.html

[^13]: T. Yuasa. Real-time garbage collection on general-purpose machines. Journal of Systems and Software, 11(3):181–198, 1990. https://www.sciencedirect.com/science/article/pii/016412129090084Y

[^14]: Paul R Wilson. "Uniprocessor Garbage Collection Techniques" https://www.cs.cmu.edu/~fp/courses/15411-f14/misc/wilson94-gc.pdf

本文轉(zhuǎn)載自微信公眾號「真沒什么邏輯」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系真沒什么邏輯公眾號。