作者 | mingguangtu

本文主要是中村成洋、相川光寫的《垃圾回收的算法與實(shí)現(xiàn)》一書的讀書筆記，沒有輸出的學(xué)習(xí)就是一盤散沙。我們要學(xué)習(xí)GC就要系統(tǒng)性的學(xué)，形成自己的知識(shí)框架，后面再學(xué)習(xí)其他的GC實(shí)現(xiàn)，就知道該放在框架的哪個(gè)地方，本文起到了作為GC知識(shí)框架的作用。不管技術(shù)風(fēng)云怎么變化，打牢基礎(chǔ)總是不會(huì)錯(cuò)的。

一、為什么要有GC

1. 什么是GC

GC 是 Garbage Collection 的簡(jiǎn)稱，中文稱為“垃圾回收”。GC ，是指程序把不用的內(nèi)存空間視為垃圾并回收掉的整套動(dòng)作。

GC 要做的有兩件事：

• 找到內(nèi)存空間里的垃圾；
• 回收垃圾，讓程序能再次利用這部分空間。

滿足這兩項(xiàng)功能的程序就是 GC。

2. 為什么要有GC

在沒有 GC 的世界里，程序員必須自己手動(dòng)進(jìn)行內(nèi)存管理，必須清楚地確保必要的內(nèi)存空間，釋放不要的內(nèi)存空間。

程序員在手動(dòng)進(jìn)行內(nèi)存管理時(shí)，申請(qǐng)內(nèi)存尚不存在什么問題，但在釋放不要的內(nèi)存空間時(shí)，就必須一個(gè)不漏地釋放。這非常地麻煩。容易發(fā)生下面三種問題：內(nèi)存泄露，懸垂指針，錯(cuò)誤釋放引發(fā)BUG。

• 如果忘記釋放內(nèi)存空間，該內(nèi)存空間就會(huì)發(fā)生內(nèi)存泄露(內(nèi)存空間在使用完畢后未釋放)，即無(wú)法被使用，但它又會(huì)持續(xù)存在下去。如果將發(fā)生內(nèi)存泄露的程序放著不管，總有一刻內(nèi)存會(huì)被占滿，甚至還可能導(dǎo)致系統(tǒng)崩潰。
• 在釋放內(nèi)存空間時(shí)，如果忘記初始化指向已經(jīng)回收的內(nèi)存地址(對(duì)象已釋放)的指針，這個(gè)指針就會(huì)一直指向釋放完畢的內(nèi)存空間。此時(shí)，這個(gè)指針處于一種懸掛的狀態(tài)，我們稱其為“懸垂指針”(dangling pointer)。如果在程序中錯(cuò)誤地引用了懸垂指針， 就會(huì)產(chǎn)生無(wú)法預(yù)期的 BUG。
• 一旦錯(cuò)誤釋放了使用中的內(nèi)存空間，下一次程序使用此空間時(shí)就會(huì)發(fā)生故障。大多數(shù)情況下會(huì)發(fā)生段錯(cuò)誤，運(yùn)氣不好的話還可能引發(fā)惡性 BUG，甚至引發(fā)安全漏洞。

為了省去上述手動(dòng)內(nèi)存管理的麻煩，人們鉆研開發(fā)出了 GC。如果把內(nèi)存管理交給計(jì)算機(jī)， 程序員就不用去想著釋放內(nèi)存了。

當(dāng)然，技術(shù)領(lǐng)域的不變法則就是萬(wàn)事皆有代價(jià)，GC 也會(huì)帶來(lái)一些麻煩，比如后臺(tái)程序需要耗費(fèi)一定的CPU和內(nèi)存資源去釋放內(nèi)存，在系統(tǒng)繁忙的情況下會(huì)對(duì)業(yè)務(wù)程序性能造成一定的不利影響，為了解決GC帶來(lái)的問題，最近幾年出現(xiàn)了一門新的沒有GC的Rust語(yǔ)言，大有替代C語(yǔ)言的趨勢(shì)，不過學(xué)習(xí)曲線比較陡峭，感興趣的同學(xué)可以自行鉆研。

二、GC相關(guān)的基本術(shù)語(yǔ)

1. 對(duì)象、指針、活動(dòng)對(duì)象、非活動(dòng)對(duì)象、堆、根

GC操作的基本單元可以叫做對(duì)象。對(duì)象是內(nèi)存空間的某些數(shù)據(jù)的集合。在本文中，對(duì)象由頭(header)和域(field)構(gòu)成。

對(duì)象的頭，主要包含對(duì)象的大小、種類信息。對(duì)象中可訪問的部分稱為“域”，可以認(rèn)為是 C 語(yǔ)言中結(jié)構(gòu)體的成員變量。如圖2.1所示。

圖2.1 對(duì)象、頭、域

指針是指向內(nèi)存空間中某塊區(qū)域的值。GC 是根據(jù)對(duì)象的指針指向去搜尋其他對(duì)象的。對(duì)象和指針的關(guān)系如圖2.2所示。

圖2.2 對(duì)象和指針

我們將內(nèi)存空間中被其他對(duì)象通過指針引用的對(duì)象成為活動(dòng)對(duì)象，沒有對(duì)象引用的對(duì)象是非活動(dòng)對(duì)象，也就是GC需要回收的垃圾。如圖2.3所示。

圖2.3 活動(dòng)對(duì)象和非活動(dòng)對(duì)象

根(root)是“根基”“根底”。在 GC 的世界里，根是指向?qū)ο蟮闹羔樀摹捌瘘c(diǎn)” 部分。堆指的是用于動(dòng)態(tài)(也就是執(zhí)行程序時(shí))存放對(duì)象的內(nèi)存空間。當(dāng)應(yīng)用程序申請(qǐng)存放對(duì)象時(shí)， 所需的內(nèi)存空間就會(huì)從這個(gè)堆中被分配給 應(yīng)用程序。如圖2.4所示。

圖2.4 根和堆里的對(duì)象

2. GC算法性能的評(píng)價(jià)標(biāo)準(zhǔn)

評(píng)價(jià) GC 算法的性能時(shí)，我們采用以下 4 個(gè)標(biāo)準(zhǔn)。

• 吞吐量
• 最大暫停時(shí)間
• 堆使用效率
• 訪問的局部性

(1) 吞吐量

GC的吞吐量是：運(yùn)行用戶代碼時(shí)間 / (運(yùn)行用戶代碼時(shí)間 + 垃圾收集時(shí)間)。

如圖2.5所示，在程序運(yùn)行的整個(gè)過程中，應(yīng)用程序的時(shí)間是X、Y、Z，應(yīng)用程序的總時(shí)間是 X + Y + Z。GC一共啟動(dòng)了兩次，花費(fèi)的時(shí)間為A、B，則GC總花費(fèi)的時(shí)間是 A + B。這種情況下 GC 的吞吐量為 (X + Y + Z) /(X + Y + Z + A + B)。

圖2.5 應(yīng)用程序和GC的執(zhí)行示意圖

從這里的描述可知，GC的吞吐量就是應(yīng)用程序執(zhí)行的時(shí)間(不是內(nèi)存大小哦)和GC時(shí)間的比值，GC執(zhí)行的總時(shí)間越短，GC吞吐量越大。

人們通常都喜歡吞吐量高的 GC 算法。然而判斷各算法吞吐量的好壞時(shí)不能一概而論。因?yàn)楣こ碳夹g(shù)中，任何好處都是有代價(jià)的。

(2) 最大暫停時(shí)間

本文介紹的所有GC算法，都會(huì)在GC執(zhí)行過程中另應(yīng)用程序暫停執(zhí)行。最大暫停時(shí)間指的是“因執(zhí)行GC而暫停執(zhí)行應(yīng)用程序的最長(zhǎng)時(shí)間”。

當(dāng)編寫像動(dòng)作游戲這樣追求即時(shí)性的程序時(shí)，就必須盡量壓低 GC 導(dǎo)致的最大暫停時(shí)間。如果因?yàn)?GC 導(dǎo)致玩家頻繁卡頓，相信誰(shuí)都會(huì)想摔手柄。對(duì)音樂和動(dòng)畫這樣類似于編碼應(yīng)用的程序來(lái)說(shuō)，GC 的最大暫停時(shí)間就不那么重要了。更為重要的是，我們必須選擇一個(gè)整體處理時(shí)間更短的算法。

不管嘗試哪種 GC 算法，我們都會(huì)發(fā)現(xiàn)較大的吞吐量和較短的最大暫停時(shí)間不可兼得。所以應(yīng)根據(jù)執(zhí)行的應(yīng)用所重視的指標(biāo)的不同，來(lái)分別采用不同的 GC 算法。

(3) 堆使用效率

堆使用效率，是指：程序在運(yùn)行過程中，單位時(shí)間內(nèi)能使用的堆內(nèi)存空間的大小。舉個(gè)例子，GC 復(fù)制算法中將堆二等分，每次只使用一半，交替進(jìn)行，因此總是只能利用堆的一半。相對(duì)而言，GC 標(biāo)記-清除算法和引用計(jì)數(shù)法就能利用整個(gè)堆。

與吞吐量和最大暫停時(shí)間一樣，堆使用效率也是 GC 算法的重要評(píng)價(jià)指標(biāo)之一。

然而，堆使用效率和吞吐量，以及最大暫停時(shí)間不可兼得。簡(jiǎn)單地說(shuō)就是：可用的堆越大，GC 運(yùn)行越快；相反，越想有效地利用有限的堆，GC 花費(fèi)的時(shí)間就越長(zhǎng)。

(4) 訪問的局部性

計(jì)算機(jī)上有 4 種存儲(chǔ)器，分別是寄存器、緩存、內(nèi)存、輔助存儲(chǔ)器。它們之間有著如圖 2.6 所示的層級(jí)關(guān)系。

圖2.6 存儲(chǔ)器的層次結(jié)構(gòu)

眾所周知，越是可實(shí)現(xiàn)高速存取的存儲(chǔ)器容量就越小。計(jì)算機(jī)會(huì)盡可能地利用較高速的存儲(chǔ)器，但由于高速的存儲(chǔ)器容量小，不可能把所有要利用的數(shù)據(jù)都放在寄存器和高速緩存里。一般我們會(huì)把所有的數(shù)據(jù)都放在內(nèi)存里，當(dāng) CPU 訪問數(shù)據(jù)時(shí)，僅把要使用的數(shù)據(jù)從內(nèi)存讀取到緩存。由于數(shù)據(jù)是分塊讀取，我們還將它附近的所有數(shù)據(jù)都讀取到高速緩存中， 從而壓縮讀取數(shù)據(jù)所需要的時(shí)間。這種內(nèi)存空間中相鄰的數(shù)據(jù)很可能存在連續(xù)訪問因而帶來(lái)訪問效率提升的情況，稱為“訪問的局部性”。

部分GC算法會(huì)利用這種局部性原理，把具有引用關(guān)系的對(duì)象安排在堆中較近的位置，就能提高在緩存Cache中讀取到想要的數(shù)據(jù)的概率，令應(yīng)用程序高速運(yùn)行。

三、常用的GC算法

三種最基本的GC算法是標(biāo)記-清除法、引用計(jì)數(shù)法、GC復(fù)制算法。后面延伸出來(lái)的4種不過是三種基本算法的組合而已。

1. GC標(biāo)記-清除法

GC 標(biāo)記-清除算法由標(biāo)記階段和清除階段構(gòu)成。標(biāo)記階段是把所有活動(dòng)對(duì)象都做上標(biāo)記的階段。清除階段是把那些沒有標(biāo)記的對(duì)象，也就是非活動(dòng)對(duì)象回收的階段。通過這兩個(gè)階段，就可以令不能利用的內(nèi)存空間重新得到利用。

說(shuō)了說(shuō)明GC標(biāo)記-清除算法的工作原理，下面分為標(biāo)記、清除兩個(gè)階段來(lái)描述。

(1) 標(biāo)記階段

圖3.1 執(zhí)行GC前堆的狀態(tài)

執(zhí)行GC前堆的狀態(tài)如圖3.1所示。

在標(biāo)記階段中，垃圾回收器Collector 會(huì)為堆里的所有活動(dòng)對(duì)象打上標(biāo)記。為此，我們首先要標(biāo)記通過根直接引用的對(duì)象。首先我們標(biāo)記這樣的對(duì)象，然后遞歸地標(biāo)記通過指針數(shù)組能訪問到的對(duì)象。這樣就能把所有活動(dòng)對(duì)象都標(biāo)記上了。

標(biāo)記Mark對(duì)象，是在對(duì)象的頭部進(jìn)行置位操作。如圖3.2所示，是程序標(biāo)記對(duì)象的動(dòng)作示意。

圖3.2 標(biāo)記對(duì)象的動(dòng)作示意

標(biāo)記完所有活動(dòng)對(duì)象后，標(biāo)記階段就結(jié)束了。標(biāo)記階段結(jié)束時(shí)的堆如圖 3.3 所示，從根對(duì)象沿著指針引用找下去，會(huì)發(fā)現(xiàn)有四個(gè)對(duì)象被引用，都需要打上標(biāo)記位。

在標(biāo)記階段中，程序會(huì)標(biāo)記所有活動(dòng)對(duì)象。毫無(wú)疑問，標(biāo)記所花費(fèi)的時(shí)間是與“活動(dòng)對(duì) 象的總數(shù)”成正比的。

圖3.3 標(biāo)記階段結(jié)束后的堆狀態(tài)

用一句話概括，標(biāo)記階段就是“遍歷對(duì)象并標(biāo)記”的處理過程。

(2) 清除階段

在清除階段中，垃圾回收器Collector 會(huì)遍歷整個(gè)堆，回收沒有打上標(biāo)記的對(duì)象(即垃圾)，使其能再次得到利用。

在清除階段，GC程序會(huì)遍歷堆，具體來(lái)說(shuō)就是從堆首地址開始，按順序一個(gè)個(gè)遍歷對(duì)象的標(biāo)志位。如果一個(gè)對(duì)象設(shè)置了標(biāo)記位，就說(shuō)明這個(gè)對(duì)象是活動(dòng)對(duì)象，必然是不能被回收的。

GC程序會(huì)把非活動(dòng)對(duì)象回收再利用?；厥諏?duì)象就是把對(duì)象作為分塊，連接到被稱為“空閑鏈表”的單向鏈表。在之后進(jìn)行分配時(shí)只要遍歷這個(gè)空閑鏈表，就可以找到分塊了。

圖3.4 清除階段結(jié)束后的堆狀態(tài)

在清除階段，程序會(huì)遍歷所有堆，進(jìn)行垃圾回收。也就是說(shuō)，所花費(fèi)時(shí)間與堆大小成正 比。堆越大，清除階段所花費(fèi)的時(shí)間就會(huì)越長(zhǎng)。

在GC的標(biāo)記-清除過程中，還會(huì)不斷進(jìn)行的兩個(gè)動(dòng)態(tài)操作那就是分配和合并。

① 分配

分配是指將回收的垃圾進(jìn)行再利用。

GC程序在清除階段已經(jīng)把垃圾對(duì)象連接到空閑鏈表了。當(dāng)應(yīng)用程序創(chuàng)建新對(duì)象時(shí)，搜索空閑鏈表并尋找大小合適的分塊，這項(xiàng)操作就叫作分配。

② 合并

根據(jù)分配策略的不同可能會(huì)產(chǎn)生大量的小分塊。但如果它們是連續(xù)的， 我們就能把所有的小分塊連在一起形成一個(gè)大分塊。這種“連接連續(xù)分塊”的操作就叫作合并(coalescing)，合并是在清除階段進(jìn)行的。

(3) 標(biāo)記清除法的優(yōu)點(diǎn)

• 實(shí)現(xiàn)簡(jiǎn)單，很容易在基本的GC標(biāo)記清除法基礎(chǔ)上改進(jìn)，或者容易和其他算法組合形成新的GC算法。
• GC 標(biāo)記-清除算法因?yàn)椴粫?huì)移動(dòng)對(duì)象，所以非常適合搭配保守式 GC 算法。

(4) 標(biāo)記清除法的缺點(diǎn)

• 碎片化。使用過程中會(huì)逐漸產(chǎn)生被細(xì)化的分塊，不久后就會(huì)導(dǎo)致無(wú)數(shù)的小分塊散布在堆的各處。
• 分配速度慢。GC 標(biāo)記-清除算法中分塊不是連續(xù)的，因此每次分配都必須遍歷空閑鏈表，找到足夠大的分塊才行。
• 與寫時(shí)復(fù)制技術(shù)(copy-on-write)不兼容。這里不展開說(shuō)了。

(5) GC標(biāo)記-清除法的改進(jìn)

① 改進(jìn)一：分配速度的改進(jìn)——多個(gè)空閑鏈表

之前介紹的基本標(biāo)記-清除算法中只用到了一個(gè)空閑鏈表，在這個(gè)空閑鏈表中，對(duì)大的分塊和小的分塊進(jìn)行同樣的處理。但是這樣一來(lái)，每次分配的時(shí)候都要遍歷一次空閑鏈表來(lái)尋找合適大小的分塊，這樣非常浪費(fèi)時(shí)間。

可以尋求一種改進(jìn)的方法，利用分塊大小不同的空閑鏈表，即創(chuàng)建只連接大分塊的空閑鏈表和只連接小分塊的空閑鏈表，甚至不同規(guī)格大小的分塊采用不同的空閑鏈表管理。這樣一來(lái)，只要按照應(yīng)用程序所申請(qǐng)的對(duì)象大小選擇空閑鏈表，就能在短時(shí)間內(nèi)找到符合條件的分塊了。我們知道，Golang的內(nèi)存分配里就是這么做的了。

圖3.5 利用多個(gè)空閑鏈表提高分配速度

② 改進(jìn)二：碎片化分塊問題的改進(jìn)——BiBOP法

BiBOP 是 Big Bag Of Pages 的縮寫。用一句話概括就是“將大小相近的對(duì)象整理成固定大小的塊進(jìn)行管理的做法”。

如圖3.6所示，是BiBOP 法的示意圖。把堆分割成多個(gè)規(guī)格大小的空間，讓每個(gè)規(guī)格的空間只能配置同樣大小的分塊。

2個(gè)字的分塊只能在最左邊的堆空間里分配，3個(gè)字的分塊只能在中間的堆空間分配，4個(gè)字的塊在最右邊。像這樣配置對(duì)象，就會(huì)提高內(nèi)存的使用效率。

圖 3.6 BiBOP法的示意圖

2. 引用計(jì)數(shù)法

(1) 引用計(jì)數(shù)法的基本原理

引用計(jì)數(shù)法(Reference Counting)就是，讓所有對(duì)象事先記錄下“有多少程序引用自己”。形象點(diǎn)兒說(shuō)，就是讓各對(duì)象知道自己的“人氣指數(shù)”，讓沒有人氣的對(duì)象自己消失。

引用計(jì)數(shù)法依靠“計(jì)數(shù)器”記錄有多少對(duì)象引用了自己(被引用數(shù))。

圖3.7 引用計(jì)數(shù)法中的對(duì)象

如圖3.8所示，是A的指針由指向B改為指向C時(shí)，各對(duì)象的計(jì)數(shù)器的變化情況。初始狀態(tài)下從根引用 A 和 C，從 A 引用 B。A 持有唯一指向 B 的指針，假設(shè)現(xiàn)在將該指針更新到了 C，B 的計(jì)數(shù)器值變成了 0，計(jì)數(shù)器變更時(shí)，計(jì)數(shù)器為0的對(duì)象會(huì)被回收，因此 B 被回收了。且 B 連接上了空閑鏈表， 能夠再被利用了。又因?yàn)樾滦纬闪擞?A 指向 C 的指針，所以 C 的計(jì)數(shù)器的值增量為 2。

圖3.8 在對(duì)象引用變更時(shí)各對(duì)象的計(jì)數(shù)器的變化情況

(2) 引用計(jì)數(shù)法的優(yōu)點(diǎn)

• 可即刻回收垃圾。在引用計(jì)數(shù)法中，每個(gè)對(duì)象始終都知道自己的被引用數(shù)(就是計(jì)數(shù)器的值)。當(dāng)被引用數(shù)的值為 0 時(shí)，對(duì)象馬上就會(huì)把自己作為空閑空間被GC程序連接到空閑鏈表。也就是說(shuō)，各個(gè)對(duì)象在變成垃圾的同時(shí)就會(huì)立刻被回收。另一方面，在其他的 GC 算法中，即使對(duì)象變成了垃圾，程序也無(wú)法立刻判別。只有當(dāng)內(nèi)存分塊用盡后 GC 開始執(zhí)行時(shí)，才能知道哪個(gè)對(duì)象是垃圾，哪個(gè)對(duì)象不是垃圾。
• 最大暫停時(shí)間短。在引用計(jì)數(shù)法中，只有當(dāng)應(yīng)用程序更新指針時(shí)(計(jì)數(shù)器變更)程序才會(huì)執(zhí)行垃圾回收。也就是說(shuō)， 每次生成垃圾時(shí)這部分垃圾都會(huì)被回收，因而大幅度地削減了GC的最大暫停時(shí)間。
• 沒有必要沿著指針查找被引用對(duì)象。引用計(jì)數(shù)法和 GC 標(biāo)記-清除算法不一樣，沒必要由根沿著指針查找。當(dāng)我們想減少沿著指針查找的次數(shù)時(shí)，它就派上用場(chǎng)了。打個(gè)比方，在分布式環(huán)境中，如果要沿各個(gè)計(jì)算節(jié)點(diǎn)之間的指針進(jìn)行查找，成本就會(huì)增大。

(3) 引用計(jì)數(shù)法的缺點(diǎn)

• 計(jì)數(shù)器值的增減處理繁重。在程序繁忙的情況下，指針都會(huì)頻繁地更新。特別是有根的指針，會(huì)以極快的速度進(jìn)行更新。在引用計(jì)數(shù)法中，每當(dāng)指針更新時(shí)，計(jì)數(shù)器的值都會(huì)隨之更新，因此值的增減處理必然會(huì)變得繁重。
• 計(jì)數(shù)器需要占用很多位。用于引用計(jì)數(shù)的計(jì)數(shù)器最大必須能數(shù)完堆中所有對(duì)象的引用數(shù)。打個(gè)比方，假如我們用的是 32 位機(jī)器，那么就有可能要讓 2 的 32 次方個(gè)對(duì)象同時(shí)引用一個(gè)對(duì)象。考慮到這種情況， 就有必要確保各對(duì)象的計(jì)數(shù)器有 32 位大小。也就是說(shuō)，對(duì)于所有對(duì)象，必須留有 32 位的空間。這就害得內(nèi)存空間的使用效率大大降低了。
• 實(shí)現(xiàn)煩瑣復(fù)雜。該算法本身很簡(jiǎn)單，但事實(shí)上實(shí)現(xiàn)起來(lái)卻不容易。進(jìn)行指針更新操作時(shí)，需要同時(shí)變更對(duì)象引用和計(jì)數(shù)器，這容易導(dǎo)致遺漏，一旦遺漏了某處，內(nèi)存管理就無(wú)法正確 進(jìn)行，就會(huì)產(chǎn)生 BUG。
• 循環(huán)引用無(wú)法回收。因?yàn)閮蓚€(gè)對(duì)象互相引用，所以各對(duì)象的計(jì)數(shù)器的值都是 1。但是這些對(duì)象組并沒有被其他任何對(duì)象引用。因此想一并回收這兩個(gè)對(duì)象都不行，只要它們的計(jì)數(shù)器值都 是 1，就無(wú)法回收。

圖3.9 循環(huán)引用對(duì)象

最后，盡管引用計(jì)數(shù)法有很多缺點(diǎn)，引用計(jì)數(shù)法也不是一個(gè)“完全沒法用”的算法。事實(shí)上，很多處理系統(tǒng)和應(yīng)用都在使用引用計(jì)數(shù)法。

因?yàn)橐糜?jì)數(shù)法只要稍加改良，就會(huì)變得非常具有實(shí)用性了。

(4) 引用計(jì)數(shù)法的改進(jìn)

① 改進(jìn)一：延遲引用計(jì)數(shù)法

針對(duì)引用計(jì)數(shù)法“計(jì)數(shù)器增減處理繁重”的缺點(diǎn)，有人提出了延遲引用計(jì)數(shù)法(Deferred Reference Counting)。計(jì)數(shù)器值增減處理繁重的原因之一是從根的引用變化頻繁。延遲引用計(jì)數(shù)法就是讓從根引用的指針的變化不反映在計(jì)數(shù)器上，而是采用一個(gè)零數(shù)表ZCT(Zero Count Table)來(lái)存儲(chǔ)從根引用的各對(duì)象的被引用數(shù)，即使這個(gè)值變?yōu)?，程序也先不回收這個(gè)對(duì)象（延遲一詞體現(xiàn)在這），而是等零數(shù)表ZCT爆滿或者空閑鏈表為空時(shí)再掃描零數(shù)表ZCT，刪除確實(shí)沒有被引用的對(duì)象。這樣一來(lái)即使頻繁重寫堆中對(duì)象的引用關(guān)系，對(duì)象的計(jì)數(shù)器值也不會(huì)有所變化，因而大大改善了“計(jì)數(shù)器值的增減處理繁重”這一缺點(diǎn)。

圖3.10 用零數(shù)表ZCT記錄根引用的各對(duì)象的被引用數(shù)

• 優(yōu)點(diǎn)：在延遲引用計(jì)數(shù)法中，程序延遲了根引用的計(jì)數(shù)。通過延遲，減輕了因根引用頻繁發(fā)生變化而導(dǎo)致的計(jì)數(shù)器增減所帶來(lái)的額外負(fù)擔(dān)。
• 缺點(diǎn)：為了延遲計(jì)數(shù)器值的增減，垃圾不能馬上得到回收，這樣一來(lái)垃圾就會(huì)壓迫堆，程序也就失去了引用計(jì)數(shù)法的一大優(yōu)點(diǎn)——可即刻回收垃圾。

② 改進(jìn)二：減少計(jì)數(shù)器位數(shù)的Sticky 引用計(jì)數(shù)法

我們假設(shè)用于計(jì)數(shù)器的位數(shù)為 5 位，那么這種計(jì)數(shù)器最多只能數(shù)到 2 的 5 次方減 1，也就是 31 個(gè)引用數(shù)。如果此對(duì)象被大于 31 個(gè)對(duì)象引用，那么計(jì)數(shù)器就會(huì)溢出。對(duì)于計(jì)數(shù)器溢出的對(duì)象，有兩種處理方法：1）什么都不做，2）通過GC標(biāo)記-清除法進(jìn)行管理。

• 對(duì)于計(jì)數(shù)器溢出的對(duì)象，什么都不做。這樣一來(lái)，即使這個(gè)對(duì)象成了垃圾(即被引用數(shù)為 0)，也不能將其回收。也就是說(shuō)， 白白浪費(fèi)了內(nèi)存空間。然而事實(shí)上有很多研究表明，很多對(duì)象一生成馬上就死了。也就是說(shuō)， 在很多情況下，計(jì)數(shù)器的值會(huì)在 0 到 1 的范圍內(nèi)變化，鮮少出現(xiàn) 5 位計(jì)數(shù)器溢出這樣的情況。
• 對(duì)于計(jì)數(shù)器溢出的對(duì)象，通過GC標(biāo)記-清除法進(jìn)行管理。具體實(shí)現(xiàn)就不展開了。這種方式，在計(jì)數(shù)器溢出后即使對(duì)象成了垃圾，程序還是能回收它。另外還有一個(gè)優(yōu)點(diǎn)，那就是還能回收循環(huán)的垃圾。

3. GC復(fù)制算法

(1) 基本原理

GC 復(fù)制算法(Copying GC)，就是只把某個(gè)空間里的活動(dòng)對(duì)象復(fù)制到其他空間，把原空間里的所有對(duì)象都回收掉。在此，我們將復(fù)制活動(dòng)對(duì)象的原空間稱為 From 空間，將粘貼活動(dòng)對(duì)象的新空間稱為 To 空間。

GC 復(fù)制算法是利用 From 空間進(jìn)行分配的。當(dāng) From 空間被完全占滿時(shí)，GC 會(huì)將活動(dòng)對(duì)象全部復(fù)制到 To 空間。當(dāng)復(fù)制完成后，該算法會(huì)把 From 空間和 To 空間互換，GC 也就結(jié)束了。From 空間和 To 空間大小必須一致。這是為了保證能把 From 空間中的所有活動(dòng)對(duì)象都收納到 To 空間里。GC 復(fù)制算法的概要如圖 3.11 所示。

圖3.11 GC復(fù)制算法的示意圖

(2) GC復(fù)制算法的執(zhí)行過程

我們通過下面一個(gè)例子來(lái)說(shuō)明GC復(fù)制算法的執(zhí)行過程。如圖3.12所示，堆里From空間已經(jīng)分配滿了部分對(duì)象，對(duì)象間的引用關(guān)系如連線所示，即將開始GC，To空間目前沒有被使用，有個(gè)空閑分塊起始指針需要指向空間的開頭，對(duì)象復(fù)制到了空間放在free指向的位置。

圖3.12 初始狀態(tài)

開始GC后，首先復(fù)制的是從根引用的對(duì)象B和G，對(duì)象B先被復(fù)制到To空間，空閑分塊起始指針$free移到B對(duì)象之后。B 被復(fù)制后生成的對(duì)象稱為 B*'，原對(duì)象B還在From空間，B里保存了指向B’的指針，因?yàn)樵璅rom空間還有其他對(duì)象要通過B找到B’。* 如圖3.13所示。

圖3.13 B被復(fù)制之后

目前只把 B*'*復(fù)制了過來(lái)，它的子對(duì)象 A 還在 From 空間里。下面要把這個(gè) A 復(fù)制到 To 空間里。

圖3.14 A被復(fù)制之后

這次才可以說(shuō)在真正意義上復(fù)制了 B。因?yàn)?A 沒有子對(duì)象，所以對(duì) A 的復(fù)制也就完成了。

接下來(lái)，我們要復(fù)制和 B 一樣從根引用的 G，以及其子對(duì)象 E。雖然 B 也是 G 的子對(duì)象， 不過因?yàn)橐呀?jīng)復(fù)制完 B 了，所以只要把從 G 指向 B 的指針換到 B? 上就行了。

最后只要把 From 空間和 To 空間互換，GC 就結(jié)束了。GC 結(jié)束時(shí)堆的狀態(tài)如圖 3.15 所示。

圖3.15 GC結(jié)束后

從GC復(fù)制算法的執(zhí)行過程可以知道，從根開始搜索對(duì)象，采用的是深度優(yōu)先搜索的方式。如圖3.16所示。

圖3.16 GC復(fù)制算法目前查找引用對(duì)象使用的是深度優(yōu)先搜索

(3) GC復(fù)制算法的優(yōu)點(diǎn)

• 優(yōu)秀的吞吐量。GC 標(biāo)記-清除算法消耗的吞吐量是搜索活動(dòng)對(duì)象(標(biāo)記階段)所花費(fèi)的時(shí)間和搜索整體堆(清除階段)所花費(fèi)的時(shí)間之和。因?yàn)?GC 復(fù)制算法只搜索并復(fù)制活動(dòng)對(duì)象，所以跟一般的 GC 標(biāo)記-清除算法相比，它能在較短時(shí)間內(nèi)完成 GC。也就是說(shuō)，其吞吐量?jī)?yōu)秀。
• 可實(shí)現(xiàn)內(nèi)存的高速分配。GC 復(fù)制算法不使用空閑鏈表。這是因?yàn)榉謮K是一個(gè)連續(xù)的內(nèi)存空間。因此，調(diào)查這個(gè)分塊的大小，只要這個(gè)分塊大小不小于所申請(qǐng)的大小，那么移動(dòng)空閑分塊的指針就可以進(jìn)行分配了。
• 不會(huì)發(fā)生碎片化。基于算法性質(zhì)，活動(dòng)對(duì)象被集中安排在 From 空間的開頭。像這樣把對(duì)象重新集中，放在堆的一端的行為就叫作壓縮。在 GC 復(fù)制算法中，每次運(yùn)行 GC 時(shí)都會(huì)執(zhí)行壓縮。因此 GC 復(fù)制算法有個(gè)非常優(yōu)秀的特點(diǎn)，就是不會(huì)發(fā)生碎片化。
• 滿足高速緩存的局部性原理。在 GC 復(fù)制算法中有引用關(guān)系的對(duì)象會(huì)被安排在堆里離彼此較近的位置。訪問效率更高。

(4) GC復(fù)制算法的缺點(diǎn)

• 堆使用效率低下。GC 復(fù)制算法把堆二等分，通常只能利用其中的一半來(lái)安排對(duì)象。也就是說(shuō)，只有一半 堆能被使用。相比其他能使用整個(gè)堆的 GC 算法而言，可以說(shuō)這是 GC 復(fù)制算法的一個(gè)重大的缺陷。
• 不兼容保守式 GC 算法。因?yàn)镚C復(fù)制算法會(huì)移動(dòng)對(duì)象到另外的位置，保守式GC算法要求對(duì)象的位置不能移動(dòng)，這在某些情況下有一點(diǎn)的優(yōu)勢(shì)。而GC復(fù)制算法沒有這種優(yōu)勢(shì)。
• 遞歸調(diào)用函數(shù)。復(fù)制某個(gè)對(duì)象時(shí)要遞歸復(fù)制它的子對(duì)象。因此在每次進(jìn)行復(fù)制的時(shí)候都要調(diào)用遞歸函數(shù)，由此帶來(lái)的額外負(fù)擔(dān)不容忽視。比起這種遞歸算法，迭代算法更能高速地執(zhí)行。此外，因?yàn)樵诿看芜f歸調(diào)用時(shí)都會(huì)消耗棧，所以還有棧溢出的可能。

(5) GC復(fù)制算法的改進(jìn)

① 改進(jìn)一：Cheney 的 GC 復(fù)制算法

Cheney的GC復(fù)制算法說(shuō)起來(lái)也沒什么復(fù)雜的，就是將基本GC的深度優(yōu)先搜索改為廣度優(yōu)先搜索。這樣可以將遞歸復(fù)制改為迭代復(fù)制。

圖3.17 Cheney的GC復(fù)制算法將深度優(yōu)先搜索改為廣度優(yōu)先搜索

Cheney的GC復(fù)制算法的過程用下面幾張圖來(lái)描述。GC開始前的初始狀態(tài)如圖3.18所示。只是在指向To空間開頭的指針多了一個(gè)$scan，用來(lái)掃描已復(fù)制對(duì)象的指針，該指針是實(shí)現(xiàn)廣度優(yōu)先搜索查找對(duì)象的關(guān)鍵。

圖3.18 初始狀態(tài)

在 Cheney 的算法中，首先復(fù)制所有從根直接引用的對(duì)象，在這里就是復(fù)制 B 和 G。由于負(fù)責(zé)對(duì)已復(fù)制完的對(duì)象進(jìn)行搜索并向右移動(dòng)指針，free 負(fù)責(zé)對(duì)沒復(fù)制的對(duì)象進(jìn)行復(fù)制并向右移動(dòng)指針，此時(shí)仍然指著空間的開頭，free 從 To 空間的開頭向右移動(dòng)了 B 和 G 個(gè)長(zhǎng)度。如圖3.19所示。

圖3.19 復(fù)制B和G之后

由于根引用的兩個(gè)對(duì)象B、G已經(jīng)復(fù)制完成，接下來(lái)移動(dòng)$scan指針?biāo)阉饕褟?fù)制對(duì)象B的子對(duì)象，然后把被 B? 引用的 A 復(fù)制到了 To 空間，同時(shí)把 scan 和 $free 分別向右移動(dòng)了。

圖3.20 搜索 B' 之后

下面該搜索的是 G*'。搜索 G'后，E 被復(fù)制到了 To 空間，從 G'* 指向 B 的指針被換到了 B*'*。

下面該搜索 A' 和 E' 了，不過它們都沒有子對(duì)象，所以即使搜索了也不能進(jìn)行復(fù)制。因?yàn)樵?E' 搜索完成時(shí) 和free 一致，所以最后只要把 From 空間和 To 空間互換，GC 就結(jié)束了。如圖3.21所示。

圖3.21 GC 結(jié)束后

不用遞歸算法而用迭代算法，可以抑制調(diào)用函數(shù)的額外負(fù)擔(dān)和棧的消耗。但是，帶來(lái)的缺點(diǎn)是有引用關(guān)系的對(duì)象在內(nèi)存中沒有放在一起，沒有利用到高速緩存Cache的局部性原理，在訪問效率上要打個(gè)折扣。當(dāng)然，對(duì)這一問題的改進(jìn)是近似深度優(yōu)先搜索方法，這里就不展開了。

② 改進(jìn)二：多空間復(fù)制算法

GC 復(fù)制算法最大的缺點(diǎn)是只能利用半個(gè)堆。這是因?yàn)樵撍惴▽⒄麄€(gè)堆分成了兩半，每次都要騰出一半。多空間復(fù)制算法可以改進(jìn)GC復(fù)制算法“只能利用半個(gè)堆”的問題。

多空間復(fù)制算法說(shuō)白了就是把堆 N 等分，對(duì)其中 2 塊空間執(zhí)行 GC 復(fù)制算法，對(duì)剩下的 (N-2)塊空間執(zhí)行 GC 標(biāo)記-清除算法，也就是把這 2 種算法組合起來(lái)使用。

下面用四張圖來(lái)說(shuō)明多空間復(fù)制算法的執(zhí)行過程。

首先將堆劃分成四個(gè)大小相同的子空間，分別用heap[0]，heap[1]，heap[2]，heap[3]來(lái)表示。

第1次執(zhí)行GC之前，是heap[0]作為To空間，heap[1]作為From空間，可以分配活動(dòng)對(duì)象。heap[2]和heap[3]也可以分配對(duì)象，不過是采用標(biāo)記-清除算法，它們的空閑分塊用空閑鏈表鏈接起來(lái)。

圖3.22 開始執(zhí)行第1次GC之前

第1次GC之后，作為From空間的heap[1]的活動(dòng)對(duì)象復(fù)制到了作為To空間的heap[0]中。

圖3.23 第1次GC結(jié)束之后

接下來(lái)，將 To 空間和 From 空間分別向右移動(dòng)一個(gè)位置，將 heap[1] 作為 To 空間，將 heap[2] 作為 From 空間。此時(shí)，新對(duì)象可以分配在作為From空間的heap[2]，heap[0]和heap[3]采用標(biāo)記-清除算法，同樣可以分配新對(duì)象。

圖3.24 開始執(zhí)行第2次GC之前

如果作為From空間的heap[2]，heap[0]和heap[3]三個(gè)空間又滿了，需要執(zhí)行第2次GC。此時(shí)，會(huì)把From空間的活動(dòng)對(duì)象復(fù)制到作為To空間的heap[1]中，第2次GC結(jié)束之后的堆狀態(tài)如下圖3.25所示。

圖3.25 第2次GC結(jié)束之后

優(yōu)點(diǎn)：多空間復(fù)制算法沒有將堆二等分，而是分割成了更多塊空間，從而更有效地利用了堆。以往的 GC 復(fù)制算法只能使用半個(gè)堆，而多空間復(fù)制算法僅僅需要空出一個(gè)分塊，不能使用 的只有 1/N 個(gè)堆。

缺點(diǎn)：執(zhí)行 GC 復(fù)制算法的只有N等分中的兩塊空間，對(duì)于剩下的(N-2)塊空間執(zhí)行的是 GC 標(biāo)記-清除算法。因此就出現(xiàn)了 GC 標(biāo)記-清除算法固有的問題——分配耗費(fèi)時(shí)間、分塊碎片化等。只要把執(zhí)行 GC 標(biāo)記-清除算法的空間縮小，就可以緩解這些問題。打個(gè)比方，如果讓N = 3，就能把發(fā)生碎片化的空間控制在整體堆的 1/3。不過這時(shí)候?yàn)榱嗽谑Ｏ碌?2/3 的空間里執(zhí)行GC 復(fù)制算法，我們就不能使用其中的一半，也就是堆空間的 1/3。

從這里我們可以看到，幾乎不存在沒有缺點(diǎn)的萬(wàn)能算法。

4. GC標(biāo)記-壓縮算法

(1) 基本原理

GC 標(biāo)記-壓縮算法(Mark Compact GC)是將 GC 標(biāo)記-清除算法與 GC 復(fù)制算法相結(jié)合的產(chǎn)物。

GC 標(biāo)記-壓縮算法由標(biāo)記階段和壓縮階段構(gòu)成。在 GC 標(biāo)記-壓縮算法中新空間和原空間是同一個(gè)空間。

壓縮階段并不會(huì)改變對(duì)象的排列順序，只是把對(duì)象按順序從堆各處向左移動(dòng)到堆的開頭。這樣就縮小了它們之間的空隙， 把它們聚集到了堆的一端。

(2) GC標(biāo)記-壓縮算法的執(zhí)行過程

GC標(biāo)記-壓縮算法的執(zhí)行過程的簡(jiǎn)化版本，如下圖3.26所示。GC開始后，首先是標(biāo)記階段。搜索根引用的對(duì)象及其子對(duì)象并打上標(biāo)記，這里采用深度優(yōu)先搜索。然后將打上標(biāo)記的活動(dòng)對(duì)象復(fù)制到堆的開頭。壓縮階段并不會(huì)改變對(duì)象的排列順序，只是縮小了它們之間的空隙， 把它們聚集到了堆的一端。

圖3.26 GC標(biāo)記-復(fù)制算法的過程簡(jiǎn)化版

這里需要重點(diǎn)說(shuō)明的是壓縮過程。壓縮過程會(huì)通過從頭到尾按順序掃描堆 3 次，第1次是對(duì)每個(gè)打上標(biāo)記的對(duì)象找到它要移動(dòng)的位置并記錄在它們各自的成員變量forwarding里，第2次是重寫所有活動(dòng)對(duì)象的指針，將它們指向原位置的指針改為指向壓縮后的對(duì)象地址，第3次是搜索整個(gè)堆，將活動(dòng)對(duì)象移動(dòng)到forwarding指針指向的位置完成對(duì)象的移動(dòng)。

下面依次說(shuō)明。

如圖3.27所示，是第1次順序掃描堆，對(duì)每個(gè)打上標(biāo)記的對(duì)象，找到它要移動(dòng)的位置并記錄在它們各自的成員變量forwarding里。

圖3.27 順序掃描堆，對(duì)各個(gè)活動(dòng)對(duì)象用其forwarding指針記錄其要移動(dòng)的目標(biāo)位置

第2次掃描堆，更新重寫所有活動(dòng)對(duì)象的指針，將它們指向原位置的指針改為指向壓縮后的對(duì)象地址，如圖3.28所示。

圖3.28 掃描堆，更新重寫所有活動(dòng)對(duì)象的指針

第3次掃描堆，移動(dòng)活動(dòng)對(duì)象到其目的地址，完成對(duì)象的壓縮過程。

圖3.29 掃描堆，移動(dòng)活動(dòng)對(duì)象到其目的地址

三次堆掃描完成后，GC整個(gè)過程結(jié)束。GC結(jié)束狀態(tài)如圖3.30所示。

圖3.30 GC結(jié)束

(3) GC標(biāo)記-壓縮算法的優(yōu)點(diǎn)

• 可有效利用堆。GC 標(biāo)記-壓縮算法和其他算法相比而言，堆利用效率高。GC 標(biāo)記-壓縮算法不會(huì)出現(xiàn) GC 復(fù)制算法那樣只能利用半個(gè)堆的情況。GC 標(biāo)記-壓縮算法可以在整個(gè)堆中安排對(duì)象，堆使用效率幾乎是 GC 復(fù)制算法的 2 倍。
• 沒有GC標(biāo)記-清除法所帶來(lái)的碎片化問題。

(4) GC標(biāo)記-壓縮算法的缺點(diǎn)

• 壓縮花費(fèi)計(jì)算成本。壓縮有著巨大的好處，但也有相應(yīng)的代價(jià)。必須對(duì)整個(gè)堆進(jìn)行 3 次搜索。執(zhí)行該算法所花費(fèi)的時(shí)間是和堆大小成正比的。
• GC 標(biāo)記-壓縮算法的吞吐量要劣于其他算法。

(5) GC標(biāo)記-壓縮算法的改進(jìn)

① 改進(jìn)一：減少堆搜索次數(shù)的Two-Finger二指算法

Two-Finger 算法有著很大的制約條件，那就是“必須將所有對(duì)象整理成大小一致”。

在基本的GC標(biāo)記-壓縮算法中，通過執(zhí)行壓縮操作使活動(dòng)對(duì)象往左邊滑動(dòng)。而在 Two-Finger 算法中，是通過執(zhí)行壓縮操作來(lái)讓活動(dòng)對(duì)象填補(bǔ)空閑空間。此時(shí)為了讓對(duì)象能恰好填補(bǔ)空閑空間， 必須讓所有對(duì)象大小一致。

Two-Finger二指算法中對(duì)象的移動(dòng)過程，如下圖3.31所示。主要用到了兩個(gè)指針，空閑分塊指針和活動(dòng)對(duì)象指針live，前者從左往右找，后者從右往左找。當(dāng)找到了空閑分塊，live找到了活動(dòng)對(duì)象，則將活動(dòng)對(duì)象移動(dòng)到空閑分塊$free的位置，實(shí)現(xiàn)對(duì)象的移動(dòng)。

圖3.31 Two-Finger二指算法中對(duì)象的移動(dòng)

• 優(yōu)點(diǎn)：Two-Finger二指算法，壓縮需要的搜索次數(shù)只有 2 次，在吞吐量方面占優(yōu)勢(shì)。
• 缺點(diǎn)：壓縮移動(dòng)對(duì)象時(shí)沒有考慮把有引用關(guān)系的對(duì)象放在一起，無(wú)法利用高速緩存基于局部性原理提升訪存效率。該算法還有一個(gè)限制條件，那就是所有對(duì)象的大小必須一致，導(dǎo)致應(yīng)用受限。不過和第3.1節(jié)介紹的要求“將大小相近的對(duì)象整理成固定大小的塊進(jìn)行管理的做法”的BiBOP算法結(jié)合起來(lái)使用，會(huì)起到珠聯(lián)璧合的效果。

5. 保守式GC

(1) 什么是保守式GC

保守式 GC(Conservative GC)指的是“不能識(shí)別指針和非指針的 GC”。

如下圖所示，在C/C++等高級(jí)語(yǔ)言的早期GC程序里，如果寄存器、函數(shù)調(diào)用?；蛉肿兞靠臻g等這些根空間里有一個(gè)數(shù)值型的變量0x00d0caf0和一個(gè)指針的地址是相同的值0x00d0caf0，則程序無(wú)法識(shí)別這個(gè)值到底是數(shù)值變量還是指針。

圖3.32 貌似指針的非指針

對(duì)于貌似指針的非指針，為了避免錯(cuò)誤回收導(dǎo)致程序故障，采取“寧可放過，不可殺錯(cuò)”的寬容原則，把它們當(dāng)做活動(dòng)對(duì)象而保留下來(lái)，像這樣，在運(yùn)行 GC 時(shí)采取的是一種保守的態(tài)度，即“把可疑的東西看作指針，穩(wěn)妥處理”，所以我們稱這種方法為“保守式 GC ”。

保守式GC的特點(diǎn)是盡量不移動(dòng)對(duì)象的位置，因?yàn)槿菀装逊侵羔樦貙憦亩a(chǎn)生意想不到的BUG。

當(dāng)然，大部分高級(jí)程序語(yǔ)言如Java、Golang在語(yǔ)言設(shè)計(jì)之初就是強(qiáng)類型語(yǔ)言，不存在無(wú)法識(shí)別變量和指針的問題，它們采用的就是跟保守式GC相對(duì)應(yīng)的準(zhǔn)確式GC。

(2) 保守式GC的優(yōu)點(diǎn)

容易編寫語(yǔ)言處理程序（語(yǔ)言處理程序是指將源程序轉(zhuǎn)換成機(jī)器語(yǔ)言、以便計(jì)算機(jī)能夠運(yùn)行的匯編程序、編譯程序和解釋程序）。處理程序基本上不用在意 GC 就可以編寫代碼。語(yǔ)言處理程序的實(shí)現(xiàn)者即使沒有意識(shí)到 GC 的存在，程序也會(huì)自己回收垃圾。因此語(yǔ)言處理程序的實(shí)現(xiàn)要比準(zhǔn)確式 GC 簡(jiǎn)單。

(3) 保守式GC的缺點(diǎn)

• 識(shí)別指針和非指針需要付出成本。在跟空間里，變量和指針的值相同的情況下，程序需要額外通過是否內(nèi)存對(duì)齊、是否指向堆內(nèi)對(duì)象的開頭等手段來(lái)判斷指針和非指針，成本較高。
• 錯(cuò)誤識(shí)別指針會(huì)壓迫堆。當(dāng)存在貌似指針的非指針時(shí)，保守式 GC 會(huì)把被引用的對(duì)象錯(cuò)誤識(shí)別為活動(dòng)對(duì)象。如果這個(gè)對(duì)象存在大量的子對(duì)象，那么它們一律都會(huì)被看成活動(dòng)對(duì)象。這樣容易留下較多的垃圾對(duì)象，從而會(huì)嚴(yán)重壓迫堆。
• 能夠使用的 GC 算法有限。由于保守式GC的特點(diǎn)是盡量不移動(dòng)對(duì)象的位置，因?yàn)槿菀装逊侵羔樦貙憦亩a(chǎn)生意想不到的BUG。所以基本上不能使用 GC 復(fù)制算法等移動(dòng)對(duì)象的 GC 算法。

(4) 保守式GC的改進(jìn)

① 改進(jìn)一：準(zhǔn)確式GC

準(zhǔn)確式 GC(Exact GC)和保守式 GC 正好相反，它是能正確識(shí)別指針和非指針的 GC。

要能精確地識(shí)別指針和非指針，需要依賴程序語(yǔ)言設(shè)計(jì)之初的語(yǔ)言處理程序的支持。

大部分高級(jí)程序語(yǔ)言如Java、Golang，在語(yǔ)言設(shè)計(jì)之初就是強(qiáng)類型語(yǔ)言，不存在無(wú)法識(shí)別變量和指針的問題，它們采用的就是跟保守式GC相對(duì)應(yīng)的準(zhǔn)確式GC。

• 優(yōu)點(diǎn)：不會(huì)錯(cuò)誤識(shí)別指針，不會(huì)將已經(jīng)死了的對(duì)象識(shí)別為活動(dòng)對(duì)象，因此GC回收垃圾會(huì)比較徹底。還可以使用GC復(fù)制算法等需要移動(dòng)對(duì)象的算法，提高GC的吞吐量和效率。
• 缺點(diǎn)：當(dāng)創(chuàng)建準(zhǔn)確式 GC 時(shí)，語(yǔ)言處理程序(語(yǔ)言處理程序是指將源程序轉(zhuǎn)換成機(jī)器語(yǔ)言、以便計(jì)算機(jī)能夠運(yùn)行的匯編程序、編譯程序和解釋程序)必須對(duì) GC 進(jìn)行一些支援。也就是說(shuō)，在創(chuàng)建語(yǔ)言處理程序時(shí)必須顧及 GC。增加了語(yǔ)言處理程序的實(shí)現(xiàn)復(fù)雜度。

② 改進(jìn)二：間接引用

保守式 GC 有個(gè)缺點(diǎn)，就是“不能使用 GC 復(fù)制算法等移動(dòng)對(duì)象的算法”。解決這個(gè)問題的方法之一就是“間接引用”。

根和對(duì)象之間通過句柄連接。每個(gè)對(duì)象都有一個(gè)句柄，它們分別持有指向這些對(duì)象的指針。并且局部變量和全局變量沒有指向?qū)ο蟮闹羔?，只裝著指向句柄的指針。當(dāng)應(yīng)用程序操作對(duì)象時(shí)，要通過經(jīng)由句柄的間接引用來(lái)執(zhí)行。

只要采用了間接引用，那么即使移動(dòng)了引用目標(biāo)的對(duì)象，也不用改寫關(guān)鍵的值——根里面的值，改寫句柄里的指針就可以了。也就是說(shuō)，我們只要采用間接引用來(lái)處理對(duì)象， 就可以移動(dòng)對(duì)象。如下圖所示，在復(fù)制完對(duì)象之后，根的值并沒有重寫。

圖3.33 根到對(duì)象通過句柄間接引用

• 優(yōu)點(diǎn)：因?yàn)樵谑褂瞄g接引用的情況下有可能實(shí)現(xiàn) GC 復(fù)制算法，所以可以得到 GC 復(fù)制算法所帶來(lái)的好處，例如消除碎片化等。
• 缺點(diǎn)：因?yàn)楸仨殞⑺袑?duì)象都(經(jīng)由句柄)間接引用，所以會(huì)降低訪問對(duì)象內(nèi)數(shù)據(jù)的速度，這會(huì)關(guān)系到整個(gè)語(yǔ)言處理程序的速度。

③ 改進(jìn)三：MostlyCopyingGC大部分復(fù)制算法

MostlyCopyingGC 就是“把那些不明確的根指向的對(duì)象以外的對(duì)象都復(fù)制的 GC 算法”。Mostly 是“大部分”的意思。說(shuō)白了，MostlyCopyingGC 就是拋開那些不能移動(dòng)的對(duì)象，將其他“大部分”的對(duì)象都進(jìn)行復(fù)制的 GC 算法。這里不展開細(xì)說(shuō)了。

6. 分代垃圾回收

程序應(yīng)用中的一個(gè)經(jīng)驗(yàn)：大部分的對(duì)象在生成后馬上就變成了垃圾， 很少有對(duì)象能活得很久。

分代垃圾回收(Generational GC)，利用了該經(jīng)驗(yàn)，在對(duì)象中導(dǎo)入了“年齡”的概念，經(jīng)歷過一次 GC 后活下來(lái)的對(duì)象年齡為 1 歲。

(1) 新生代對(duì)象和老年代對(duì)象

分代垃圾回收中把對(duì)象分類成幾代，針對(duì)不同的代使用不同的 GC 算法，我們把剛生成的對(duì)象稱為新生代對(duì)象，到達(dá)一定年齡的對(duì)象則稱為老年代對(duì)象。

由于新生代對(duì)象大部分會(huì)變成垃圾，如果應(yīng)用程序只對(duì)這些新生代對(duì)象執(zhí)行 GC，除了引用計(jì)數(shù)法以外的基本算法，都會(huì)進(jìn)行只尋找活動(dòng)對(duì)象的操作，如 GC 標(biāo)記-清除算法的標(biāo)記階段和 GC 復(fù)制算法等。因此，如果很多對(duì)象都會(huì)死去，花費(fèi)在 GC 上的時(shí)間應(yīng)該就能減少。

我們將對(duì)新對(duì)象執(zhí)行的 GC 稱為新生代 GC(minor GC)。minor 在這里的意思是“小規(guī)模的”。新生代 GC 的前提是大部分新生代對(duì)象都沒存活下來(lái)，GC 在短時(shí)間內(nèi)就結(jié)束了。

另一方面，新生代 GC 將存活了一定次數(shù)的新生代對(duì)象當(dāng)作老年代對(duì)象來(lái)處理。新生代對(duì)象上升為老年代對(duì)象的情況稱為晉升(promotion)。

因?yàn)槔夏甏鷮?duì)象很難成為垃圾，所以我們對(duì)老年代對(duì)象減少執(zhí)行 GC 的頻率。相對(duì)于新生代 GC，將面向老年代對(duì)象的 GC 稱為老年代 GC(major GC)。

需要注意的是，分代垃圾回收不是跟 GC 標(biāo)記-清除算法和 GC 復(fù)制算法并列在一起供開發(fā)人員選擇的算法，而是需要跟這些基本算法一并使用。比如新生代GC使用GC復(fù)制算法，而老年代GC由于頻率較低、可以使用最簡(jiǎn)單的GC標(biāo)記-清除算法。

(2) 分代垃圾回收的基本原理

分代垃圾回收算法把對(duì)分成了四個(gè)空間，分別是生成空間、2 個(gè)大小相等的幸存空間以及老年代空間。新生代對(duì)象會(huì)被分配到新生代空間，老年代對(duì)象則會(huì)被分配到老年代空間里。

圖3.34 分代垃圾回收的堆空間

應(yīng)用程序創(chuàng)建的新對(duì)象一般會(huì)放到新生代空間里，當(dāng)生成空間滿了的時(shí)候，新生代 GC 就會(huì)啟動(dòng)，將生成空間中的所有活動(dòng)對(duì)象復(fù)制，這跟 GC 復(fù)制算法是一個(gè)道理，復(fù)制的目標(biāo)空間是幸存空間。

2 個(gè)幸存空間和 GC 復(fù)制算法里的 From 空間、To 空間很像，我們經(jīng)常只利用其中的一個(gè)。在每次執(zhí)行新生代 GC 的時(shí)候，活動(dòng)對(duì)象就會(huì)被復(fù)制到另一個(gè)幸存空間里。在此我們將正在使用的幸存空間作為 From 幸存空間，將沒有使用的幸存空間作為 To 幸存空間。

新生代 GC 也必須復(fù)制生成空間里的對(duì)象。也就是說(shuō)，生成空間和 From 幸存空間這兩個(gè)空間里的活動(dòng)對(duì)象都會(huì)被復(fù)制到 To 幸存空間里去——這就是新生代 GC。

只有從一定次數(shù)的新生代 GC 中存活下來(lái)的對(duì)象才會(huì)得到晉升，也就是會(huì)被復(fù)制到老年代空間去。

在執(zhí)行新生代 GC 時(shí)需要注意，需要考慮到從老年代空間到新生代空間的引用。新生代對(duì)象不只會(huì)被根和新生代空間引用，也可能被老年代對(duì)象引用。因此，除了一般 GC 里的根，還需要將從老年代空間的引用當(dāng)作根(像根一樣的東西)來(lái)處理。

這里，使用記錄集用來(lái)記錄從老年代對(duì)象到新生代對(duì)象的引用。這樣在新生代 GC 時(shí)就可以不搜索老年代空間的所有對(duì)象，只通過搜索記錄集來(lái)發(fā)現(xiàn)從老年代對(duì)象到新生代對(duì)象的引用。

圖3.35 新對(duì)象分配在生成空間和From空間

圖3.36 MinorGC啟動(dòng)，將活動(dòng)對(duì)象復(fù)制到To空間

圖3.37 MinorGC清理完成后，互換From空間到To空間

通過新生代 GC 得到晉升的對(duì)象把老年代空間占滿后，就要執(zhí)行老年代 GC 了。老年代 GC 沒什么難的地方，它只用到了3.1節(jié)的 GC 標(biāo)記-清除算法。

(3) 分代垃圾回收的優(yōu)點(diǎn)

“很多對(duì)象年紀(jì)輕輕就會(huì)死”這一經(jīng)驗(yàn)適合大多數(shù)情況，新生代 GC 只將剛生成的對(duì)象當(dāng)成對(duì)象，這樣一來(lái)就能減少時(shí)間上的消耗。分代垃圾回收可以改善 GC 所花費(fèi)的時(shí)間(吞吐量)?！皳?jù)實(shí)驗(yàn)表明，分代垃圾回收花費(fèi)的時(shí)間是 GC 復(fù)制算法的 1/4?！?/p>

(4) 分代垃圾回收的缺點(diǎn)

“很多對(duì)象年紀(jì)輕輕就會(huì)死”這個(gè)法則畢竟只適合大多數(shù)情況，并不適用于所有程序。對(duì)對(duì)象會(huì)活得很久的程序執(zhí)行分代垃圾回收，就會(huì)產(chǎn)生以下兩個(gè)問題：

• 新生代GC所花費(fèi)的時(shí)間增多
• 老年代GC頻繁運(yùn)行

(5) 分代垃圾回收的改進(jìn)

① 改進(jìn)一：多代垃圾回收

分代垃圾回收將對(duì)象分為新生代和老年代，通過盡量減少?gòu)男律鷷x升到老年代的對(duì)象， 來(lái)減少在老年代對(duì)象上消耗的垃圾回收的時(shí)間。

基于這個(gè)理論，大家可能會(huì)想到分為 3 代或 4 代豈不更好？這樣一來(lái)能晉升到最老一代的對(duì)象不就更少了嗎？這種方法就叫作多代垃圾回收(Multi-generational GC)。

圖3.38 4代垃圾回收的堆空間

在這個(gè)方法中，除了最老的那一代之外，每代都有一個(gè)記錄集。X 代的記錄集只記錄來(lái)自比 X 老的其他代的引用。

分代數(shù)量越多，對(duì)象變成垃圾的機(jī)會(huì)也就越大，所以這個(gè)方法確實(shí)能減少活到最老代的對(duì)象。

但是我們也不能過度增加分代數(shù)量。分代數(shù)量越多，每代的空間也就相應(yīng)地變小了，這樣一來(lái)各代之間的引用就變多了，各代中垃圾回收花費(fèi)的時(shí)間也就越來(lái)越長(zhǎng)了。

綜合來(lái)看，少設(shè)置一些分代能得到更優(yōu)秀的吞吐量，據(jù)說(shuō)分為 2 代或者 3 代是最好的。

7. 增量式垃圾回收

增量式垃圾回收(Incremental GC)是一種通過逐漸推進(jìn)垃圾回收來(lái)控制應(yīng)用程序最大暫停時(shí)間的方法。

增量(incremental)這個(gè)詞有“慢慢發(fā)生變化” 的意思。就如它的名字一樣， 增量式垃圾回收是將 GC 和應(yīng)用程序一點(diǎn)點(diǎn)交替運(yùn)行的手法。增量式垃圾回收的示意圖如圖 3.39 所示。

圖3.39 增量式垃圾回收示意圖

增量式垃圾回收也叫三色標(biāo)記法(Tri-color marking)。本文中，增量式垃圾回收=三色標(biāo)記法。

(1) 三色標(biāo)記法

三色標(biāo)記法是將對(duì)象根據(jù)搜索情況，分為三種顏色：

• 白色：還未搜索過的對(duì)象
• 灰色：正在搜索的對(duì)象
• 黑色：搜索完成的對(duì)象

GC 開始運(yùn)行前所有的對(duì)象都是白色。GC 一開始運(yùn)行，所有從根能到達(dá)的對(duì)象都會(huì)被標(biāo)記，然后被堆到棧里。GC 只是發(fā)現(xiàn)了這樣的對(duì)象，但還沒有搜索完它們，所以這些對(duì)象就成了灰色對(duì)象。

灰色對(duì)象會(huì)被依次從棧中取出，其子對(duì)象也會(huì)被涂成灰色。當(dāng)其所有的子對(duì)象都被涂成灰色時(shí)，對(duì)象就會(huì)被涂成黑色。

當(dāng) GC 結(jié)束時(shí)已經(jīng)不存在灰色對(duì)象了，活動(dòng)對(duì)象全部為黑色，垃圾則為白色。

這就是三色標(biāo)記算法的概念。

三色標(biāo)記法和GC標(biāo)記-清除算法結(jié)合起來(lái)增量式執(zhí)行，就是我們本節(jié)要說(shuō)的增量式垃圾回收，或叫增量式標(biāo)記-清除算法。

增量式的 GC 標(biāo)記-清除算法(三色標(biāo)記法)可分為以下三個(gè)階段：

• 根查找階段
• 標(biāo)記階段
• 清除階段

這本書的三色標(biāo)記法解釋的并不清楚，下面我結(jié)合Golang的三色標(biāo)記實(shí)現(xiàn)來(lái)說(shuō)明具體過程。

①根查找階段

在根查找階段中，GC程序?qū)⒅苯訌母玫膶?duì)象打上灰色標(biāo)記，放到灰色隊(duì)列里，將Root根對(duì)象本身標(biāo)記為黑色對(duì)象。根查找階段只在 GC 開始時(shí)運(yùn)行一次。如下圖所示。

圖3.40 根查找階段

② 標(biāo)記階段

從灰色隊(duì)列里取出對(duì)象，將其子對(duì)象涂成灰色，將該灰色對(duì)象本身標(biāo)記為黑色。將這一系列操作執(zhí)行 X 次，在這里“X 次”是重點(diǎn)，不是一次處理所有的灰色對(duì)象，而是只處理一定個(gè)數(shù)，然后暫停 GC，再次開始執(zhí)行應(yīng)用程序。這樣一來(lái)，就能縮短應(yīng)用程序的最大暫停時(shí)間。

圖3.41 標(biāo)記階段

將灰色隊(duì)列里的所有灰色對(duì)象，通過多次搜索階段、搜索并標(biāo)記為黑色，完成后，意味著標(biāo)記結(jié)束。標(biāo)記結(jié)束時(shí)，灰色隊(duì)列為空，所有灰色對(duì)象都成了黑色。這里，黑色對(duì)象意味著活動(dòng)對(duì)象，白色對(duì)象意味著空閑對(duì)象，白色對(duì)象等待著在清除階段被GC回收，也就是掛載到空閑鏈表上以供后面新對(duì)象分配使用。

圖3.42 標(biāo)記結(jié)束

③ 清除階段

在清除階段，將黑色對(duì)象視為活動(dòng)對(duì)象并保留，將白色對(duì)象掛載到空閑鏈表以清除，便于后面新對(duì)象分配時(shí)使用。

圖3.43 清除階段

三色標(biāo)記清除算法本身是不可以并發(fā)或者增量執(zhí)行的，它需要STW暫停應(yīng)用程序，而如果并發(fā)執(zhí)行，用戶程序可能在標(biāo)記執(zhí)行的過程中修改對(duì)象的指針，容易把原本應(yīng)該垃圾回收的死亡對(duì)象錯(cuò)誤的標(biāo)記為存活，或者把原本存活的對(duì)象錯(cuò)誤的標(biāo)記為已死亡，下面以后一種情況舉例說(shuō)明。

如下圖所示。在一輪標(biāo)記暫停的狀態(tài)是：A 被涂成黑色，B 被涂成灰色進(jìn)入灰色隊(duì)列。所以下一輪標(biāo)記，就要對(duì) B 進(jìn)行搜索了。如果在這兩次標(biāo)記之間，應(yīng)用程序把從 A 指向 B 的引用更新為從 A 指向 C 之后的狀態(tài)，然后再刪除從 B 指向 C 的引用，如下圖c)所示。這個(gè)時(shí)候如果重新開始標(biāo)記， B 原本是灰色對(duì)象，經(jīng)過搜索后被涂成了黑色。然而盡管 C 是活動(dòng)對(duì)象，程序卻不會(huì)對(duì)它進(jìn)行搜索。這是因?yàn)橐呀?jīng)搜索完有唯一指向 C 的引用的 A 了。

圖3.44 沒有STW時(shí)活動(dòng)對(duì)象的標(biāo)記遺漏

為了防止這種現(xiàn)象的發(fā)生，最簡(jiǎn)單的方式就是STW，直接禁止掉其他用戶程序?qū)?duì)象引用關(guān)系的干擾，但是STW的過程有明顯的資源浪費(fèi)，對(duì)所有的用戶程序都有很大影響。那么是否可以在保證對(duì)象不丟失的情況下合理的盡可能的提高GC效率，減少STW時(shí)間呢？答案是可以的，就是屏障機(jī)制。

(2) 寫入屏障

寫入屏障的具體操作是：在 A 對(duì)象引用 C 對(duì)象的時(shí)候，C 對(duì)象被標(biāo)記為灰色。(將 C 掛在黑色對(duì)象A的下游，C 必須被標(biāo)記為灰色)

這一操作滿足：不存在黑色對(duì)象引用白色對(duì)象的情況了， 因?yàn)榘咨珪?huì)強(qiáng)制變成灰色。

圖3.45 白色對(duì)象被引用時(shí)強(qiáng)制被標(biāo)記為灰色

(3) 增量式垃圾回收的優(yōu)點(diǎn)

• 增量式垃圾回收不是一口氣運(yùn)行 GC，而是和應(yīng)用程序交替運(yùn)行的，因此不會(huì)長(zhǎng)時(shí)間妨礙到應(yīng)用程序的運(yùn)行。
• 增量式垃圾回收適合那些比起提高吞吐量，更重視縮短最大暫停時(shí)間的應(yīng)用程序。

(4) 增量式垃圾回收的缺點(diǎn)

用到了寫入屏障，就會(huì)增加額外負(fù)擔(dān)。既然有縮短最大暫停時(shí)間的優(yōu)勢(shì)，吞吐量也一般。

(5) 增量式垃圾回收的改進(jìn)

① 改進(jìn)一：Steele的寫入屏障

具體操作：在標(biāo)記過程中發(fā)出引用的對(duì)象是黑色對(duì)象，且新的引用的目標(biāo)對(duì)象為灰色或白色，那么我們就把發(fā)出引用的對(duì)象涂成灰色。如下圖所示，A 原本為黑色，引用白色的 C，這時(shí)，A 需要回退到灰色。

圖3.46 黑色對(duì)象引用白色時(shí)，自身由黑變灰

Steele 的寫入屏障相比上文的寫入屏障來(lái)說(shuō)，標(biāo)記對(duì)象的條件要嚴(yán)格一些， 相應(yīng)地寫入屏障帶來(lái)的額外負(fù)擔(dān)會(huì)增大。但是可以減少被標(biāo)記的對(duì)象，從而防止了因疏忽而造成垃圾殘留的后果。

② 改進(jìn)二：刪除屏障

具體操作: 被刪除的對(duì)象，如果自身為灰色或者白色，那么被標(biāo)記為灰色。如下圖所示，C 被 B 刪除時(shí)，C 本身為白色，所以需要被標(biāo)記為灰色。

圖3.47 對(duì)象被刪除時(shí)，如果自身為灰或白，標(biāo)記為灰色

這種方式實(shí)現(xiàn)相對(duì)簡(jiǎn)單，但是回收精度低，一個(gè)對(duì)象即使被刪除了最后一個(gè)指向它的指針也依舊可以活過這一輪，在下一輪GC中才會(huì)被清理掉。

還有很多提高標(biāo)記效率又能避免誤刪或遺留對(duì)象的屏障機(jī)制，比如混合寫屏障，這里就不多討論了。

四、七種GC算法的對(duì)比分析

五、總結(jié)

內(nèi)存其實(shí)就是一塊連續(xù)的空間，可以看做一個(gè)大數(shù)組，這塊空間在業(yè)務(wù)運(yùn)行時(shí)，經(jīng)常會(huì)或零散或整齊的分布一些大大小小的對(duì)象，怎么樣高效的分配和回收這塊空間，同時(shí)盡量不影響業(yè)務(wù)系統(tǒng)的運(yùn)行，就是GC垃圾回收要做的事，學(xué)習(xí)了七種基本的GC算法之后，我們更加知道，工程技術(shù)中沒有“銀彈”，沒有完美無(wú)缺的算法，只有最適合自己業(yè)務(wù)系統(tǒng)的解法。

本文的重要性在于：我們?cè)诰唧w的工程實(shí)踐中，經(jīng)常會(huì)遇到各種問題場(chǎng)景，每種場(chǎng)景都會(huì)遇到各種方案選型，各個(gè)不同方案的側(cè)重點(diǎn)是什么、有什么缺點(diǎn)、缺點(diǎn)怎樣改進(jìn)，到底哪種方案是當(dāng)前業(yè)務(wù)場(chǎng)景需要的，基于什么方面進(jìn)行考慮選取某種方案，這些問題和疑惑，在思考并學(xué)習(xí)七種基本的GC算法的過程中，會(huì)得到很多啟發(fā)和收獲。