一. 什么是垃圾回收

曾幾何時(shí)，內(nèi)存管理是程序員開發(fā)應(yīng)用的一大難題。傳統(tǒng)的系統(tǒng)級編程語言（主要指C/C ）中，程序員必須對內(nèi)存小心的進(jìn)行管理操作，控制內(nèi)存的申請及釋放。稍有不慎，就可能產(chǎn)生內(nèi)存泄露問題，這種問題不易發(fā)現(xiàn)并且難以定位，一直成為困擾開發(fā)者的噩夢。如何解決這個(gè)頭疼的問題呢？

過去一般采用兩種辦法：

1. 內(nèi)存泄露檢測工具。這種工具的原理一般是靜態(tài)代碼掃描，通過掃描程序檢測可能出現(xiàn)內(nèi)存泄露的代碼段。然而檢測工具難免有疏漏和不足，只能起到輔助作用。(Valgrind)
2. 智能指針。這是c 中引入的自動(dòng)內(nèi)存管理方法，通過擁有自動(dòng)內(nèi)存管理功能的指針對象來引用對象，是程序員不用太關(guān)注內(nèi)存的釋放，而達(dá)到內(nèi)存自動(dòng)釋放的目的。這種方法是采用最廣泛的做法，但是對程序員有一定的學(xué)習(xí)成本（并非語言層面的原生支持），而且一旦有忘記使用的場景依然無法避免內(nèi)存泄露。

為了解決這個(gè)問題，后來開發(fā)出來的幾乎所有新語言（java，python，php等等）都引入了語言層面的自動(dòng)內(nèi)存管理 – 也就是語言的使用者只用關(guān)注內(nèi)存的申請而不必關(guān)心內(nèi)存的釋放，內(nèi)存釋放由虛擬機(jī)（virtual machine）或運(yùn)行時(shí)（runtime）來自動(dòng)進(jìn)行管理。而這種對不再使用的內(nèi)存資源進(jìn)行自動(dòng)回收的行為就被稱為垃圾回收。

二. 常見的垃圾回收算法

① 引用計(jì)數(shù)

這是最簡單的一種垃圾回收算法，和之前提到的智能指針異曲同工。對每個(gè)對象維護(hù)一個(gè)引用計(jì)數(shù)，當(dāng)引用該對象的對象被銷毀或更新時(shí)被引用對象的引用計(jì)數(shù)自動(dòng)減一，當(dāng)被引用對象被創(chuàng)建或被賦值給其他對象時(shí)引用計(jì)數(shù)自動(dòng)加一。當(dāng)引用計(jì)數(shù)為0時(shí)則立即回收對象。

這種方法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，并且內(nèi)存的回收很及時(shí)。這種算法在內(nèi)存比較緊張和實(shí)時(shí)性比較高的系統(tǒng)中使用的比較廣泛，如ios cocoa框架，php，python等。簡單引用計(jì)數(shù)算法也有明顯的缺點(diǎn)：

1. 頻繁更新引用計(jì)數(shù)降低了性能。一種簡單的解決方法就是編譯器將相鄰的引用計(jì)數(shù)更新操作合并到一次更新；還有一種方法是針對頻繁發(fā)生的臨時(shí)變量引用不進(jìn)行計(jì)數(shù)，而是在引用達(dá)到0時(shí)通過掃描堆棧確認(rèn)是否還有臨時(shí)對象引用而決定是否釋放。等等還有很多其他方法，具體可以參考這里。
2. 循環(huán)引用問題。當(dāng)對象間發(fā)生循環(huán)引用時(shí)引用鏈中的對象都無法得到釋放。最明顯的解決辦法是避免產(chǎn)生循環(huán)引用，如cocoa引入了strong指針和weak指針兩種指針類型?；蛘呦到y(tǒng)檢測循環(huán)引用并主動(dòng)打破循環(huán)鏈。當(dāng)然這也增加了垃圾回收的復(fù)雜度。

② 標(biāo)記清除

該方法分為兩步，標(biāo)記從根變量開始迭代得遍歷所有被引用的對象，對能夠通過應(yīng)用遍歷訪問到的對象都進(jìn)行標(biāo)記為“被引用”；標(biāo)記完成后進(jìn)行清除操作，對沒有標(biāo)記過的內(nèi)存進(jìn)行回收（回收同時(shí)可能伴有碎片整理操作）。

這種方法解決了引用計(jì)數(shù)的不足，但是也有比較明顯的問題：每次啟動(dòng)垃圾回收都會暫停當(dāng)前所有的正常代碼執(zhí)行，回收是系統(tǒng)響應(yīng)能力大大降低！當(dāng)然后續(xù)也出現(xiàn)了很多mark&sweep算法的變種（如三色標(biāo)記法）優(yōu)化了這個(gè)問題。

③ 分代收集

經(jīng)過大量實(shí)際觀察得知，在面向?qū)ο缶幊陶Z言中，絕大多數(shù)對象的生命周期都非常短。分代收集的基本思想是，將堆劃分為兩個(gè)或多個(gè)稱為 代（generation）的空間。新創(chuàng)建的對象存放在稱為 新生代（young generation）中（一般來說，新生代的大小會比 老年代小很多），隨著垃圾回收的重復(fù)執(zhí)行，生命周期較長的對象會被 提升（promotion）到老年代中。因此，新生代垃圾回收和老年代垃圾回收兩種不同的垃圾回收方式應(yīng)運(yùn)而生，分別用于對各自空間中的對象執(zhí)行垃圾回收。新生代垃圾回收的速度非常快，比老年代快幾個(gè)數(shù)量級，即使新生代垃圾回收的頻率更高，執(zhí)行效率也仍然比老年代垃圾回收強(qiáng)，這是因?yàn)榇蠖鄶?shù)對象的生命周期都很短，根本無需提升到老年代。

三. Go的GC工作機(jī)制

Go的GC自打一開始就被很多人詬病，經(jīng)過這么多年的發(fā)展Go的GC已經(jīng)變得非常的優(yōu)秀了，以下是Go的GC算法里程碑

1. v1.1 STW （stop the world）
2. v1.3 Mark STW, Sweep 并行
3. v1.5 三色標(biāo)記法
4. v1.8 hybrid write barrier

Go語言GC算法主要是基于Mark and Sweep (標(biāo)記清除)算法，在此基礎(chǔ)上進(jìn)行改進(jìn)和優(yōu)化。

① Mark and Sweep

Mark and Sweep(標(biāo)記清除)算法主要是以下2個(gè)步驟

1. 標(biāo)記(Mark): 找出所有不可達(dá)對象，然后做上標(biāo)記
2. 清除(Sweep): 回收標(biāo)記好的對象

我們通過以下圖解來解釋 標(biāo)記清除 算法是如何工作的

1. 開始標(biāo)記，程序暫停，此時(shí)程序和對象的關(guān)系如下圖所示
   
2. 找到所有可達(dá)對象，并做上標(biāo)記
   
3. 標(biāo)記完成后開始清除未標(biāo)記的對象
   
4. 清除完成后，對象如下圖所示
   

標(biāo)記清除算法存在以下幾個(gè)問題

1. STW (stop the world) 標(biāo)記對象的時(shí)候程序需要暫停，導(dǎo)致程序出現(xiàn)卡頓 (最主要的問題)
2. 標(biāo)記需要掃描整個(gè)堆
3. 清除對象會產(chǎn)生堆碎片

STW指的是runtime把所有的協(xié)程都凍結(jié)了，意味著用戶邏輯是暫停的，這樣所有的對象都不會被修改，這個(gè)時(shí)候去掃描是絕對安全的。

② Tri-color Marking

為了解決標(biāo)記清除算法帶來的問題，Go在標(biāo)記清除算法基礎(chǔ)上提出來Tri-color Marking(三色標(biāo)記法)算法來優(yōu)化GC過程，大體流程如下

1. 最開始所有的對象都是白色的
   
2. GC開始，掃描所有可達(dá)的對象，標(biāo)記為灰色
   
3. 從灰色對象中找到其引用對象并標(biāo)記為灰色，自己標(biāo)記為黑色
   
4. 監(jiān)控對象修改，循環(huán)步驟3，直到?jīng)]有任何灰色對象
   
5. GC回收白色對象
   
6. 最后把所有黑色對象變成白色
   

三色標(biāo)記法是怎么優(yōu)化STW問題的呢，主要是以下2點(diǎn)

1. 標(biāo)記操作和用戶邏輯并行: 用戶邏輯經(jīng)常會生成或改變對象引用，那如何保證標(biāo)記和用戶邏輯并行呢？Go為了解決這個(gè)問題引入了寫屏障機(jī)制，在GC的過程中會監(jiān)控對象的內(nèi)存修改，并對對象進(jìn)行重新標(biāo)記，這個(gè)時(shí)候用戶邏輯也可以執(zhí)行 (實(shí)際上是很短暫的STW，然后對對象重新標(biāo)記)，所以標(biāo)記操作可以做到一定程度和用戶邏輯并行。
2. 清除操作和用戶邏輯并行: 我們知道三色標(biāo)記法中最后只剩下的黑白兩種對象，黑色對象是程序恢復(fù)后接著使用的對象，如果不碰觸黑色對象，只清除白色的對象，肯定不會影響程序邏輯，所以清除白色對象和用戶邏輯可以并行。

通過允許用戶邏輯在標(biāo)記和清除操作上做到并行處理來縮短STW的時(shí)間，提升整體GC的性能。