GC

GC全稱Garbage Collection

目前主流的垃圾回收算法有兩類(lèi)，分別是追蹤式垃圾回收算法（Tracing garbage collection）和引用計(jì)數(shù)法（ Reference counting ）。
而三色標(biāo)記法是屬于追蹤式垃圾回收算法的一種。

追蹤式算法的核心思想是判斷一個(gè)對(duì)象是否可達(dá)，因?yàn)橐坏┻@個(gè)對(duì)象不可達(dá)就可以立刻被 GC 回收了。

如何判斷一個(gè)對(duì)象是否可達(dá)

分為兩步：

• 第一步找出所有的全局變量和當(dāng)前函數(shù)棧里的變量，標(biāo)記為可達(dá)。
• 第二步，從已經(jīng)標(biāo)記的數(shù)據(jù)開(kāi)始，進(jìn)一步標(biāo)記它們可訪問(wèn)的變量，周而復(fù)始，這一過(guò)程也叫傳遞閉包。

在go推出三色標(biāo)記法之前，go所使用的gc算法叫Mark-And-Sweep（標(biāo)記清掃）

這個(gè)算法就是嚴(yán)格按照追蹤式算法的思路來(lái)實(shí)現(xiàn)的。

• 先設(shè)置一個(gè)標(biāo)志位來(lái)記錄對(duì)象是否被使用，最開(kāi)始所有的標(biāo)記位都是 0。
• 如果發(fā)現(xiàn)對(duì)象是可達(dá)的就會(huì)置為1，一步步下去就會(huì)呈現(xiàn)一個(gè)類(lèi)似樹(shù)狀的結(jié)果。
• 等標(biāo)記的步驟完成后，會(huì)將沒(méi)有被標(biāo)記的對(duì)象統(tǒng)一清理，再次把所有的標(biāo)記位設(shè)置成 0， 以便下次進(jìn)行清理。

這個(gè)算法最大的問(wèn)題是 GC 執(zhí)行期間需要把整個(gè)程序完全暫停，不能異步進(jìn)行GC操作。因?yàn)樵诓煌A段標(biāo)記清掃法的標(biāo)志位 0 和 1 有不同的含義，那么新增的對(duì)象無(wú)論標(biāo)記為什么都有可能意外刪除這個(gè)對(duì)象。對(duì)實(shí)時(shí)性要求高的系統(tǒng)來(lái)說(shuō)，這種需要長(zhǎng)時(shí)間掛起的標(biāo)記清掃法是不可接受的。所以就需要一個(gè)算法來(lái)解決 GC 運(yùn)行時(shí)程序長(zhǎng)時(shí)間掛起的問(wèn)題，那就三色標(biāo)記法。

三色標(biāo)記法

三色標(biāo)記法是傳統(tǒng) Mark-Sweep 的一個(gè)改進(jìn)，它是一個(gè)并發(fā)的 GC 算法。on-the-fly

原理如下

整個(gè)進(jìn)程空間里申請(qǐng)每個(gè)對(duì)象占據(jù)的內(nèi)存可以視為一個(gè)圖， 初始狀態(tài)下每個(gè)內(nèi)存對(duì)象都是白色標(biāo)記。

先stop the world，將掃描任務(wù)作為多個(gè)并發(fā)的goroutine立即入隊(duì)給調(diào)度器，進(jìn)而被CPU處理，第一輪先掃描所有可達(dá)的內(nèi)存對(duì)象，標(biāo)記為灰色放入隊(duì)列

第二輪可以恢復(fù)start the world，將第一步隊(duì)列中的對(duì)象引用的對(duì)象置為灰色加入隊(duì)列，一個(gè)對(duì)象引用的所有對(duì)象都置灰并加入隊(duì)列后，這個(gè)對(duì)象才能置為黑色并從隊(duì)列之中取出。循環(huán)往復(fù)，最后隊(duì)列為空時(shí)，整個(gè)圖剩下的白色內(nèi)存空間即不可到達(dá)的對(duì)象，即沒(méi)有被引用的對(duì)象；

第三輪再次stop the world，將第二輪過(guò)程中新增對(duì)象申請(qǐng)的內(nèi)存進(jìn)行標(biāo)記（灰色），這里使用了writebarrier（寫(xiě)屏障）去記錄這些內(nèi)存的身份；

這個(gè)算法可以實(shí)現(xiàn) on-the-fly，也就是在程序執(zhí)行的同時(shí)進(jìn)行收集，并不需要暫停整個(gè)程序。

簡(jiǎn)化步驟如下：

1、首先創(chuàng)建三個(gè)集合：白、灰、黑。

2、將所有對(duì)象放入白色集合中。

3、然后從根節(jié)點(diǎn)開(kāi)始遍歷所有對(duì)象（注意這里并不遞歸遍歷），把遍歷到的對(duì)象從白色集合放入灰色集合。

因?yàn)閞oot set 指向了A、F，所以從根結(jié)點(diǎn)開(kāi)始遍歷的是A、F，所以是把A、F放到灰色集合中。

4、之后遍歷灰色集合，將灰色對(duì)象引用的對(duì)象從白色集合放入灰色集合，之后將此灰色對(duì)象放入黑色集合
我們可以發(fā)現(xiàn)這個(gè)A指向了B，C，D所以也就是把BCD放到灰色中，把A放到黑色中，而F沒(méi)有指任何的對(duì)象，所以直接放到黑色中。

5、重復(fù) 4 直到灰色中無(wú)任何對(duì)象

因?yàn)镈指向了A所以D也放到了黑色中，而B(niǎo)和C能放到黑色集合中的道理和F一樣，已經(jīng)沒(méi)有了可指向的對(duì)象了。

6、通過(guò)write-barrier檢測(cè)對(duì)象有無(wú)變化，重復(fù)以上操作

由于這個(gè)EGH并沒(méi)有和RootSet有直接或是間接的關(guān)系，所以就會(huì)被清除。

7、收集所有白色對(duì)象（垃圾）

所以我們可以看出這里的情況，只要是和root set根集合直接相關(guān)的對(duì)象或是間接相關(guān)的對(duì)象都不會(huì)被清楚。只有不相關(guān)的才會(huì)被回收。

參考文檔：

一張圖講解GC
關(guān)于write-barrier寫(xiě)屏障

以上就是Go語(yǔ)言七篇入門(mén)教程GC垃圾回收三色標(biāo)記的詳細(xì)內(nèi)容，更多關(guān)于Go語(yǔ)言GC垃圾回收三色標(biāo)記的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

如何學(xué)習(xí)Go

如果你是小白，你可以這樣學(xué)習(xí)Go語(yǔ)言~

七篇入門(mén)Go語(yǔ)言

第一篇：Go簡(jiǎn)介初識(shí)

第二篇：程序結(jié)構(gòu)&&數(shù)據(jù)類(lèi)型的介紹

第三篇：函數(shù)方法接口的介紹

第四篇：通道與Goroutine的并發(fā)編程

第五篇：文件及包的操作與處理

第六篇：網(wǎng)絡(luò)編程

最新評(píng)論