Go 垃圾回收之標記準備
I can make things very fast if they don’t have to be correct.?????????????????????????????????????????????????????????????????????????????????????????—?Russ Cox
Go語言中的垃圾回收
Go語言采用了并發(fā)三色標記算法來進行垃圾回收。三色標記本身是最簡單的一種垃圾回收策略，實現(xiàn)也很簡單。引用計數(shù)由于固有的缺陷，在并發(fā)時不可擴展的特性很少被使用，不適合Go這樣高并發(fā)的語言。真正值得探討的是壓縮GC 與 分代GC。
為什么不選擇壓縮GC？
壓縮算法的主要優(yōu)勢是減少碎片、并且分配快速。在Go語言中，使用了現(xiàn)代內(nèi)存分配算法TCmalloc、雖然沒有壓縮算法那樣極致，但是已經(jīng)很好的解決了內(nèi)存碎片的問題。并且，由于需要加鎖、壓縮算法并不適合在并發(fā)程序的使用。最后在Go語言的設(shè)計初期由于緊迫的時間計劃，放棄了考慮更加復雜的壓縮實現(xiàn)算法，轉(zhuǎn)而使用了更簡單的三色標記[1].
為什么不選擇分代GC？
Go語言并不是沒有嘗試過分代GC。分代GC的主要假定是大部分變成垃圾的對象都是新創(chuàng)建的對象。但是在Go語言中由于編譯器的優(yōu)化，通過內(nèi)存逃逸的機制，將會繼續(xù)使用的對象轉(zhuǎn)移到了堆中。大部分新創(chuàng)建的對象很快變?yōu)槔膶ο髸跅Ｖ蟹峙洹＿@和其他使用隔代GC的編程語言有顯著的不同，這減弱了使用隔代GC的優(yōu)勢。同時， 隔代GC需要額外的寫屏障來保護并發(fā)垃圾回收時對象的隔代性，這會減慢GC的速度。因此，隔代GC是被嘗試過并拋棄的方案。[1]
在后面的小節(jié)中，首先圍繞垃圾回收最重要的兩個問題展開：何時進行垃圾收集 以及如何進行垃圾收集。
標記準備階段
在標記準備階段,最重要的任務(wù)是清掃上一階段gc遺留的需要清掃的對象，因為清掃使用了懶清掃策略，當執(zhí)行下一次GC時，可能沒有垃圾對象沒有清掃完畢。
同時，重置各種狀態(tài)，統(tǒng)計指標，啟動專門用于標記的協(xié)程。統(tǒng)計需要掃描的任務(wù)數(shù)量，開啟寫屏障，啟動標記協(xié)程等。總之，在標記準備階段是為了開始標記而進行的初始階段，并執(zhí)行輕量級的任務(wù)。在標記準備階段、上面大部分步驟需要在STW（stop the world）時進行
關(guān)于STW
stw階段指的是程序暫停所有運行中的協(xié)程，否則不會開始垃圾回收階段。就跟練武功一樣，如果把垃圾回收比作一本武功秘籍，我們來看一看Go語言修煉的過程：
第一層就是Go1，需要STW。紅色的線表示STW，綠色用戶協(xié)程、黃色垃圾回收協(xié)程。并且在垃圾回收階段只有一個協(xié)程執(zhí)行垃圾回收。
Go1.1進入到第二層，并且有多個協(xié)程在并行執(zhí)行垃圾回收
Go1.5進入到第三層，并發(fā)GC，垃圾回收階段用戶協(xié)程與垃圾回收協(xié)程并發(fā)執(zhí)行。
Go1.8進入到第四層，大幅縮短STW時間，小于100微妙。
那么STW是不是必要的呢，其實不是的。理論和實踐都證明，可以實現(xiàn)一種完全不需要STW的并發(fā)三色標記。真正的問題在于，有沒有必要？其實現(xiàn)在在STW中，做的事情已經(jīng)非常的少了，做一些簡單的統(tǒng)計工作，把寫屏障打開，時間已經(jīng)降低到了小于100微妙。而且有STW有一個好處，這樣我們能夠有一個完整的GC的周期，這在做統(tǒng)計GC完成的時間、trace追蹤的時候都很好用。而且要實現(xiàn)完全不需要STW的程序，實現(xiàn)起來也更加的困難了，所以現(xiàn)在有STW還算是OK的。
關(guān)于寫屏障、清掃與懶清掃將在下面的小節(jié)中介紹。標記準備階段會為每個邏輯處理器P啟動一個標記協(xié)程，但并不是所有的標記協(xié)程都能得到執(zhí)行的機會。因為在標記階段，標記協(xié)程與正常執(zhí)行用戶代碼的協(xié)程需要同時并行，減少由于GC而給用戶程序帶來的影響。在這里，筆者關(guān)注于標記準備階段兩個重要的問題：如何決定需要有多少標記協(xié)程進行工作以及如何進行調(diào)度使標記協(xié)程運行。
計算執(zhí)行標記協(xié)程的數(shù)量
在標記準備階段，會計算當前需要多少后臺標記協(xié)程開始工作。在當前，GO語言規(guī)定后臺標記協(xié)程消耗的CPU應(yīng)該接近于25%。其核心代碼位于startCycle()中
func (c *gcControllerState) startCycle() {
...
totalUtilizationGoal := float64(gomaxprocs) * 0.25
c.dedicatedMarkWorkersNeeded = int64(totalUtilizationGoal + 0.5)
utilError := float64(c.dedicatedMarkWorkersNeeded)/totalUtilizationGoal - 1
const maxUtilError = 0.3
if utilError < -maxUtilError || utilError > maxUtilError {
if float64(c.dedicatedMarkWorkersNeeded) > totalUtilizationGoal {
c.dedicatedMarkWorkersNeeded--
}
c.fractionalUtilizationGoal = (totalUtilizationGoal - float64(c.dedicatedMarkWorkersNeeded)) / float64(gomaxprocs)
} else {
c.fractionalUtilizationGoal = 0
}
...
}一種簡單的想法,要實現(xiàn)后臺標記協(xié)程消耗的CPU接近于25%的目標，可以根據(jù)當前有多少邏輯處理器P，開啟的數(shù)量應(yīng)該為0.25 * P 就可以了。為什么startCycle函數(shù)的計算過程卻如此復雜呢？關(guān)鍵在于需要處理當協(xié)程數(shù)量過小，例如P≤3時，0.25 * P 不為整數(shù)的情況。
dedicatedMarkWorkersNeeded代表了執(zhí)行完整的后臺標記協(xié)程的數(shù)量.例如當p=4時，dedicatedMarkWorkersNeeded = 1 。
而fractionalUtilizationGoal是一個附加的參數(shù)，其小于1，例如當P=2時，值為0.25。代表了每個P在標記階段需要花25%的時間去執(zhí)行后臺標記協(xié)程，不需要連續(xù)的如下圖。
設(shè)計fractionalUtilizationGoal的主要目的是專門為P=1，2，3，6時使用的。因為這些數(shù)量和25%的CPU處理時間的差距太大。比如當P=2時，這時2*0.25 = 0.5,即只能花0.5個P來執(zhí)行標記任務(wù)，但如果專門用了一個P來執(zhí)行后臺任務(wù)，這時標記的CPU使用量變?yōu)榱?/2 =0.5, 這和0.25CPU的設(shè)計目標差距太大。
所以，當P=2時，fractionalUtilizationGoal計算結(jié)果為0.25，它表明在整個并發(fā)標記的周期t內(nèi)，每一個P都需要花25%的時間來執(zhí)行后臺標記工作。這是一種基于時間的調(diào)度安排。當超出時間后，意味著當前的后臺標記協(xié)程可以被搶占，從而執(zhí)行其他的協(xié)程。
切換到后臺標記協(xié)程
標記準備階段的第二個問題是如何切換到后臺標記協(xié)程執(zhí)行。在標記準備階段執(zhí)行了STW、在STW階短暫的暫停了所有的協(xié)程。可以預(yù)料到，當關(guān)閉STW準備再次啟動所有的協(xié)程時，每一個邏輯處理器P會進入一輪新的調(diào)度循環(huán)，在調(diào)度循環(huán)的最開始的一步會判斷是否處于GC階段，如果是，嘗試判斷當前P 是否需要執(zhí)行后臺標記任務(wù)。
func schedule() {
// 正在 GC，去找 GC 的 g
if gp == nil && gcBlackenEnabled != 0 {
gp = gcController.findRunnableGCWorker(_g_.m.p.ptr())
tryWakeP = tryWakeP || gp != nil
}
}如果代表了執(zhí)行完整的后臺標記協(xié)程的字段dedicatedMarkWorkersNeeded大于0，則直接執(zhí)行后臺標記任務(wù)。否則，如果協(xié)助協(xié)程字段fractionalUtilizationGoal大于0，并且當前P執(zhí)行標記任務(wù)的時間 小于 fractionalUtilizationGoal*當前標記周期總時間，仍然會執(zhí)行后臺標記任務(wù)，但是并不會在整個標記周期內(nèi)一直執(zhí)行，只會執(zhí)行對應(yīng)的CPU時間，保證總的25%cpu執(zhí)行時間。下一小節(jié)會看到，這對應(yīng)著后臺標記協(xié)程的不同執(zhí)行模式。
if decIfPositive(&c.dedicatedMarkWorkersNeeded) {
_p_.gcMarkWorkerMode = gcMarkWorkerDedicatedMode
} else if c.fractionalUtilizationGoal == 0 {
return nil
} else {
delta := nanotime() - gcController.markStartTime
if delta > 0 && float64(_p_.gcFractionalMarkTime)/float64(delta) > c.fractionalUtilizationGoal {
return nil
}
_p_.gcMarkWorkerMode = gcMarkWorkerFractionalMode
}推薦閱讀