術(shù)語介紹

賦值器:說白了就是你寫的程序代碼，在程序的執(zhí)行過程中，可能會改變對象的引用關(guān)系，或者創(chuàng)建新的引用。

回收器:垃圾回收器的責(zé)任就是去干掉那些程序中不再被引用得對象。

STW:全稱是stop the word，GC期間某個(gè)階段會停止所有的賦值器，中斷你的程序邏輯，以確定引用關(guān)系。即STW停止程序運(yùn)行。

root對象:根對象是指不需要通過其他對象就可以直接訪問到的對象，通過root對象, 可以追蹤到其他存活的對象。
常見的root對:

1. 全局變量：程序在編譯期就能確定的那些存在于程序整個(gè)生命周期的變量（這些變量是可能引用堆上的對象或者是指針指向堆上的變量）。
2. 執(zhí)行棧：每個(gè) goroutine (包括main函數(shù))都擁有自己的執(zhí)行棧，這些執(zhí)行棧上包含棧上的變量(這些變量本身就可能內(nèi)存逃逸到堆上或者引用堆上的變量)及指向堆內(nèi)存地址的指針變量。
3. 寄存器：寄存器的值可能是一個(gè)指針，而這個(gè)指針可能指向堆內(nèi)存地址。

標(biāo)記清除法(V1.3)

步驟

1. 開啟STW，從根對象開始標(biāo)記對象
2. 清除未被標(biāo)記的對象，關(guān)閉STW
   

缺點(diǎn)

GC期間全程STW，GC和用戶程序互相干擾，不能同時(shí)執(zhí)行。

三色標(biāo)記法

背景

基于標(biāo)記清除算法的缺點(diǎn)，Golang團(tuán)隊(duì)對GC算法進(jìn)行優(yōu)化，減少STW以便GC和用戶程序可以互不干擾，并發(fā)進(jìn)行，于是就產(chǎn)生了三色標(biāo)記法。

步驟

1. GC開始前，所有對象都，都被標(biāo)記為白色
2. GC開始時(shí)，把所有根對象標(biāo)記為灰色
3. GC進(jìn)行時(shí)，遍歷灰色對象，把灰色對象可達(dá)的對象標(biāo)記為黑色，把自己標(biāo)記為黑色
4. 重復(fù)第3步，直到標(biāo)記完所有對象
5. GC結(jié)束時(shí)，回收白色對象

缺點(diǎn)

上述三色標(biāo)記法仍然需要STW，因?yàn)槲覀兊膽?yīng)用程序會改變對象的應(yīng)用關(guān)系，從而影響標(biāo)記結(jié)果的正確性。
比如：

1. 一個(gè)白色對象被灰色對象引用
2. 此時(shí)有一個(gè)黑色對象改變引用指向這個(gè)白色對象，而灰色對象到白色對象之間的引用關(guān)系又被破壞了
3. 此時(shí)這個(gè)白色對象只被一個(gè)黑色對象引用，這個(gè)白色對象不可能會標(biāo)記了，因此該白色對象丟失

總結(jié)

其實(shí)總結(jié)來看，在三色標(biāo)記法的過程中對象丟失，需要同時(shí)滿足下面兩個(gè)條件：

條件一：白色對象被黑色對象引用
條件二：灰色對象與白色對象之間的可達(dá)關(guān)系遭到破壞

看來只要把上面兩個(gè)條件破壞掉一個(gè)，就可以保證對象不丟失?？梢允褂貌迦雽懫琳虾蛣h除寫屏障來破壞上面其中一個(gè)條件。

插入寫屏障

規(guī)則：當(dāng)一個(gè)對象引用另外一個(gè)對象時(shí)，將另外一個(gè)對象標(biāo)記為灰色。

解釋：用來破壞條件一，單黑色對象引用白色對象是，白色對象就被標(biāo)記成了灰色對象，就不可能出現(xiàn)條件一這種情況出現(xiàn)。

注意

插入屏障僅會在堆內(nèi)存中生效，不對棧內(nèi)存空間生效。這是因?yàn)間o在并發(fā)運(yùn)行時(shí)，大部分的操作都發(fā)生在棧上，函數(shù)調(diào)用會非常頻繁。數(shù)十萬goroutine的棧都進(jìn)行屏障保護(hù)自然會有性能問題。

我要補(bǔ)充一下“生效”的具體意思：如果一個(gè)變量是在堆中如果它改變引用關(guān)系指向到另一個(gè)對象，我們把這個(gè)被指向的對象設(shè)置為灰色，如果一個(gè)變量在棧中，如果它改變引用關(guān)系指向到另一個(gè)對象，由于插入寫屏障不生效，所以不用改變被引用的對象顏色為灰色

但是正是因?yàn)闆]有改變?yōu)榛疑圆乓贕C結(jié)束時(shí)打開STW重新掃描棧如果棧和堆都使用插入寫屏障，那就不用掃描重新掃描棧了，但是棧上打開STW效率太低了。

步驟

1. GC開始時(shí)，堆打開插入寫屏障（棧不打開）
2. GC期間， 三色標(biāo)記法進(jìn)行標(biāo)記
3. GC期間，堆中對象改變它的應(yīng)用關(guān)系到另外一個(gè)對象，則把這個(gè)“另外對象”給標(biāo)記為灰色
4. GC結(jié)束時(shí)，打開STW重新掃描棧中對象進(jìn)行掃描標(biāo)記
5. GC結(jié)束時(shí)，進(jìn)行垃圾回收

缺點(diǎn)：GC結(jié)束時(shí)需要，打開STW重新掃描棧，保證引用的白色對象存活（主要保證的是堆中白色對象存活和棧中變量對逃逸到堆中的白色象，這些白色對象的產(chǎn)生是因?yàn)闂]開插入寫屏障）。

刪除寫屏障

規(guī)則：在刪除引用時(shí)，如果被刪除引用的對象自身為灰色或者白色，那么被標(biāo)記為灰色。

解釋：用來破壞條件二，同過把被刪除引用的對象設(shè)置為灰色，把這個(gè)被刪除引用的對象自己當(dāng)成可達(dá)的，那么相當(dāng)于可達(dá)對象（被刪除引用的這個(gè)對象）到白色對象（被刪除引用的這個(gè)對象原本就能遍歷/訪問到的其他對象）之間的可達(dá)關(guān)系又重新建立起來來。這個(gè)被刪除引用的對象和它能到達(dá)的一些對象都保護(hù)了起來，因此就破壞了條件二。

步驟

1. GC開始時(shí)，STW 掃描整個(gè)棧（所有協(xié)程的棧），保證所有堆上在用的對象都處于灰色保護(hù)下，保證的是弱三色不變式；
2. GC期間，三色標(biāo)記
3. GC期間，某個(gè)對象原本引用對象A，后來改變引用到對象B，則把B對象設(shè)置為灰色
4. GC結(jié)束時(shí)，進(jìn)行垃圾回收

缺點(diǎn)

1. 由于起始快照的原因，起始也是執(zhí)行 STW，刪除寫屏障不適用于棧特別大的場景，棧越大，STW 掃描時(shí)間越長，對于現(xiàn)代服務(wù)器上的程序來說，棧地址空間都很大，所以刪除寫屏障都不適用，一般適用于很小的棧內(nèi)存，比如嵌入式，物聯(lián)網(wǎng)的一些程序；
2. 并且刪除寫屏障會導(dǎo)致掃描進(jìn)度（波面）的后退，所以掃描精度不如插入寫屏障；

注意

在上面的GC步驟1為什么要STW 掃描整個(gè)棧（所有協(xié)程的棧）？這個(gè)問題我說一點(diǎn)我個(gè)人的猜測吧，畢竟網(wǎng)上查了半天也沒有一個(gè)人能說明白的（有朋友明白原因的麻煩告知一下）

首先在說刪除寫屏障之前時(shí)有一個(gè)大前提就是不能在棧中使用刪除寫屏障，只在堆中使用。

1. 當(dāng)我們開啟STW后把所有棧道對象都染為黑色，那么棧對象直接引用的所有堆對象都被染色成了灰色（如下圖灰色部門）。
   

2. 因此所有的（不是垃圾的）堆對象都處于灰色的保護(hù)狀態(tài)中（上圖藍(lán)色和綠色部分），換句話說就是，每個(gè)堆中的對象都至少被一個(gè)灰色對象直接或間接引用。

3. 當(dāng)堆中的引用關(guān)系發(fā)生變化時(shí)，根據(jù)刪除寫屏障把被改變引用的那個(gè)堆對象變成灰色，就能一定破壞“條件二了”

我們舉個(gè)反向例子，初始狀態(tài)，有2個(gè)協(xié)程棧：

A 是 g1 棧的一個(gè)對象，g1棧已經(jīng)掃描完了，并且 C 也是掃黑了的對象
B 是 g2 棧的對象，指向了 C 和 D，g2 完全還沒掃描，B 是一個(gè)灰色對象，D 是白色對象

步驟一：g2 進(jìn)行賦值變更，把 C 指向 D 對象，這個(gè)時(shí)候黑色的 C 就指向了白色的 D（由于是刪除屏障，這里是不會把D染色為灰色）
步驟二：把 B 指向 D 的引用刪除，由于是棧對象操作，不會觸發(fā)刪除寫屏障(這里我們討論的大前提是對棧是不使用刪除寫屏障的，即使把B到D引用關(guān)系刪除了也不會把D染成灰色)；

步驟三：GC結(jié)束時(shí)，因?yàn)?C 已經(jīng)是黑色對象了，所以不會再掃描，所以 D 仍然為白色，就會被錯(cuò)誤的清理掉。

總結(jié)

那么如果我不想一次把所有的協(xié)程棧都暫停，就會產(chǎn)生上面例子中的問題，有什么辦法可以解決上面的例子中的問題嗎（在不同時(shí)暫停所有協(xié)程棧道情況下）？這個(gè)當(dāng)然是有的。

解決辦法就是：使用三色標(biāo)記法+插入寫屏障+刪除寫屏障

需要注意：混合寫屏障掃描棧雖然沒有 STW，但是掃描某一個(gè)具體的棧的時(shí)候，還是要停止這個(gè) goroutine 賦值器的工作的哈（針對一個(gè) goroutine 棧來說，是暫停掃的，要么全灰，要么全黑哈，原子狀態(tài)切換）

我們根據(jù)上面的這幅圖可以看出只要我們在目前的GC策略上再添加上插入寫屏障（當(dāng)前的GC策略是三色標(biāo)記法+刪除寫屏障），在C引用D時(shí)直接把D染為灰色，就能解決所有問題了。

三色標(biāo)記法+插入寫屏障(V1.5)

插入寫屏障機(jī)制和刪除寫屏障機(jī)制中任一機(jī)制均可保護(hù)對象不被丟失。在V1.5的版本中采用的是插入寫機(jī)制實(shí)現(xiàn)。

三色標(biāo)記法+混合寫屏障(V1.8)

背景

從上面的分析中，我可以知道：
插入寫屏障，可以做用戶程序和GC同時(shí)運(yùn)行，什么都好就是要在GC結(jié)束時(shí)重新掃描棧中的根對象防止堆中的變量被釋放
刪除寫屏障，也可以做用戶程序和GC同時(shí)運(yùn)行，但是需要在GC開始前把所有的協(xié)程棧暫停，這對協(xié)程數(shù)量非常多的時(shí)候是不可接受的。

那么有沒有一種方法，在GC開始的時(shí)候不需要STW 掃描整個(gè)棧（把整個(gè)棧中的對象標(biāo)記為黑色），在程序結(jié)束時(shí)不需要再次重新掃描棧以防止對象丟失，并且GC程序可以和用戶程序同時(shí)運(yùn)行？

這種方法就是我們的三色標(biāo)記法+混合寫屏障了

步驟

1. GC開始時(shí)優(yōu)先掃描將棧，將棧上可達(dá)對象標(biāo)記為黑色。掃描某個(gè) goroutine 時(shí)停止這個(gè) goroutine 賦值器的工作。即goroutine看來是原子操作，瞬間全灰/黑。棧掃描完成后解鎖。
2. GC期間棧上新建的對象都為黑色
3. 堆上被刪除的對象標(biāo)記為灰色
4. 堆上新添加的對象標(biāo)記為灰色

注意：寫屏障（插入、刪除寫屏障）只在堆上啟用，棧上不開啟寫屏障

優(yōu)點(diǎn)

1. 不用在開始時(shí)像刪除寫屏障那樣，需要同時(shí)STW所有協(xié)程來標(biāo)記根棧上的根對象
2. 不用在結(jié)束時(shí)像插入寫屏障那樣，需要再次打開STW重新掃描棧，保證引用的白色對象存活