# 8.3 觸發頻率及其調步算法
## 8.3.1 GC 的調控方式
```
// src/runtime/debug
func SetGCPercent(percent int) int
func SetMaxStack(bytes int) int
```
GOGC
## 8.3.2 調步算法及其數學模型
目前觸發 GC 的條件使用的是從 Go 1.5 時提出的**調步（Pacing）算法**， 調步算法是優化并發執行時 GC 的步調，換句話說就是解決什么時候應該觸發下一次 GC 的這個問題。
調步算法包含四個部分：
1. GC 周期所需的掃描估計器
2. 為用戶代碼根據堆分配到目標堆大小的時間估計掃描工作量的機制
3. 用戶代碼為未充分利用 CPU 預算時進行后臺掃描的調度程序
4. GC 觸發比率的控制器
現在我們從兩個不同的視角來對這個問題進行建模。
### 模型的建立
從用戶的角度而言，我們希望給定一個給定的增長率，使堆在給定增長率的情況下觸發下一次 GC。 這時設hghg為**目標增長率**（即 GOGC / 100），則完成 n 個 GC 周期后標記對象的總大小為：
H(n)g\=(1+hg)H(n?1)mHg(n)\=(1+hg)Hm(n?1)
**圖1：調步算法的模型**
這時的Hg(n)Hg(n)是作為用戶的我們所希望的堆的增長結果，GC 必須將堆的大小限制在此結果以內。
從 GC 的角度而言，我們需要在觀察到給定數量的新的內存分配后，開始執行 GC，設觸發時刻的堆大小為HTHT， 在執行 GC 的期間由于用戶代碼并發執行，同樣會產生一定數量的內存分配，不妨設該次 GC 完成時堆的大小為HaHa。 在不同的情況下，一個 GC 周期后得到的實際堆大小既可以大于也可以小于堆大小。但我們的優化還需要考慮這這個因素：
* 因素1: 我們應該盡可能的使得第 n 次 GC 周期的目標堆大小H(n)a<H(n)gHa(n)<Hg(n)從而避免不斷增加的內存消耗。
* 因素2: 我們應該盡可能的避免第 n 次 GC 周期的目標堆大小H(n)a?H(n)gHa(n)?Hg(n)的指過大，從而產生過量的 CPU 消耗，進而導致應用的執行速度減慢。
顯然，如果我們沒有并行 GC，即需要對用戶代碼執行 STW，則 GC 期間不會產生新的分配， 問題將變得異常簡單：當堆增長到H(n)gHg(n)時開始執行下一階段的 GC。 但當需要 GC 并行的與用戶代碼執行時，我們則需要提前在堆大小為HTHT時候觸發 GC， 以得到最優的 GC 觸發條件，則我們可以將合適觸發 GC 這個問題轉化為以下優化問題：
**優化問題1**：尋找H(n)THT(n)，使得min|H(n)g?H(n)a|\=min|(1+hg)H(n?1)m?H(n)a|min|Hg(n)?Ha(n)|\=min|(1+hg)Hm(n?1)?Ha(n)|。
而對于第二個因素而言，為了控制 GC 對 CPU 的使用率，并發階段的 GC 應該盡可能接近 GOMAXPROCS 的 25%。這包括后臺收集器中的時間和來自用戶代碼的富足，但不是寫屏障的時間（僅因為計數會增加寫屏障的開銷）。如果設ugug為目標 CPU 使用率（goal utilization），而uaua為實際 CPU 使用率（actual utilization），于是我們有第二個優化問題：
**優化問題2**：尋找H(n)THT(n)，同時使得min|u(n)g?u(n)a|min|ug(n)?ua(n)|。
### 模型的解
TODO: 求解的具體數學建模過程
綜上所述，計算HTHT的最終結論（從 Go 1.10 時開始htht增加了上界0.95ρ0.95ρ，從 Go 1.14 開始時htht增加了下界 0.6）是：
* 設第 n 次觸發 GC 時 (n > 1)，估計得到的堆增長率為h(n)tht(n)、運行過程中的實際堆增長率為h(n)aha(n)，用戶設置的增長率為ρ\=GOGC/100ρ\=GOGC/100（ρ\>0ρ\>0）則第n+1n+1次出觸發 GC 時候，估計的堆增長率為：
h(n+1)t\=h(n)t+0.5\[H(n)g?H(n)aH(n)a?h(n)t?u(n)au(n)g(h(n)a?h(n)t)\]ht(n+1)\=ht(n)+0.5\[Hg(n)?Ha(n)Ha(n)?ht(n)?ua(n)ug(n)(ha(n)?ht(n))\]
* 特別的，h(1)t\=7/8ht(1)\=7/8，u(1)a\=0.25ua(1)\=0.25，u(1)g\=0.3ug(1)\=0.3。第一次觸發 GC 時，如果當前的堆小于4ρ4ρMB，則強制調整到4ρ4ρMB 時觸發 GC
* 特別的，當h(n)t0.95ρht(n)\>0.95ρ時，將其設置為0.95ρ0.95ρ
* 默認情況下，ρ\=1ρ\=1（即 GOGC = 100），第一次觸發 GC 時強制設置觸發第一次 GC 為 4MB，
### 結論的驗證
我們可以編寫如下程序對我們的求解過程進行驗證：
```
main
import (
"os"
"runtime"
"runtime/trace"
"sync/atomic"
)
var stop uint64
// 通過對象 P 的釋放狀態，來確定 GC 是否已經完成
func gcfinished() *int {
p := 1
runtime.SetFinalizer(&p, func(_ *int) {
println("gc finished")
atomic.StoreUint64(&stop, 1) // 通知停止分配
})
return &p
}
func allocate() {
// 每次調用分配 0.25MB
_ = make([]byte, int((1<<20)*0.25))
}
func main() {
f, _ := os.Create("trace.out")
defer f.Close()
trace.Start(f)
defer trace.Stop()
gcfinished()
// 當完成 GC 時停止分配
for n := 1; atomic.LoadUint64(&stop) != 1; n++ {
println("#allocate: ", n)
allocate()
}
println("terminate")
}
```
我們先來驗證最簡單的一種情況，即第一次觸發 GC 時的堆大小：
~~~
$ go build -o main
$ GODEBUG=gctrace=1 ./main
#allocate: 1
...
#allocate: 20
gc finished
gc 1 @0.001s 3%: 0.016+0.23+0.019 ms clock, 0.20+0.11/0.060/0.13+0.22 ms cpu, 4->5->1 MB, 5 MB goal, 12 P
scvg: 8 KB released
scvg: inuse: 1, idle: 62, sys: 63, released: 58, consumed: 5 (MB)
terminate
~~~
通過這一行數據我們可以看到：
~~~
gc 1 @0.001s 3%: 0.016+0.23+0.019 ms clock, 0.20+0.11/0.060/0.13+0.22 ms cpu, 4->5->1 MB, 5 MB goal, 12 P
~~~
1. 程序在完成第一次 GC 后便終止了程序，符合我們的設想
2. 第一次 GC 開始時的堆大小為 4MB，符合我們的設想
3. 當標記終止時，堆大小為 5MB，此后開始執行清掃，這時分配執行到第 20 次，即 20\*0.25 = 5MB，符合我們的設想
我們將分配次數調整到 50 次
```
for n := 1; n < 50; n++ {
println("#allocate: ", n)
allocate()
}
```
來驗證第二次 GC 觸發時是否滿足公式所計算得到的值（為 GODEBUG 進一步設置`gcpacertrace=1`）：
~~~
$ go build -o main
$ GODEBUG=gctrace=1,gcpacertrace=1 ./main
#allocate: 1
...
pacer: H_m_prev=2236962 h_t=+8.750000e-001 H_T=4194304 h_a=+2.387451e+000 H_a=7577600 h_g=+1.442627e+000 H_g=5464064 u_a=+2.652227e-001 u_g=+3.000000e-001 W_a=152832 goalΔ=+5.676271e-001 actualΔ=+1.512451e+000 u_a/u_g=+8.840755e-001
#allocate: 28
gc 1 @0.001s 5%: 0.032+0.32+0.055 ms clock, 0.38+0.068/0.053/0.11+0.67 ms cpu, 4->7->3 MB, 5 MB goal, 12 P
...
#allocate: 37
pacer: H_m_prev=3307736 h_t=+6.000000e-001 H_T=5292377 h_a=+7.949171e-001 H_a=5937112 h_g=+1.000000e+000 H_g=6615472 u_a=+2.658428e-001 u_g=+3.000000e-001 W_a=154240 goalΔ=+4.000000e-001 actualΔ=+1.949171e-001 u_a/u_g=+8.861428e-001
#allocate: 38
gc 2 @0.002s 9%: 0.017+0.26+0.16 ms clock, 0.20+0.079/0.058/0.12+1.9 ms cpu, 5->5->0 MB, 6 MB goal, 12 P
~~~
我們可以得到數據：
* 第一次估計得到的堆增長率為h(1)t\=0.875ht(1)\=0.875
* 第一次的運行過程中的實際堆增長率為h(1)a\=0.2387451ha(1)\=0.2387451
* 第一次實際的堆大小為H(1)a\=7577600Ha(1)\=7577600
* 第一次目標的堆大小為H(1)g\=5464064Hg(1)\=5464064
* 第一次的 CPU 實際使用率為u(1)a\=0.2652227ua(1)\=0.2652227
* 第一次的 CPU 目標使用率為u(1)g\=0.3ug(1)\=0.3
我們據此計算第二次估計的堆增長率：
h(2)t\=h(1)t+0.5\[H(1)g?H(1)aH(1)a?h(1)t?u(1)au(1)g(h(1)a?h(1)t)\]ht(2)\=ht(1)+0.5\[Hg(1)?Ha(1)Ha(1)?ht(1)?ua(1)ug(1)(ha(1)?ht(1))\]\=0.875+0.5\[5464064?75776005464064?0.875?0.26522270.3(0.2387451?0.875)\]\=0.875+0.5\[5464064?75776005464064?0.875?0.26522270.3(0.2387451?0.875)\]≈0.52534543909≈0.52534543909
因為0.52534543909<0.6ρ\=0.60.52534543909<0.6ρ\=0.6，因此下一次的觸發率為h2t\=0.6ht2\=0.6，與我們實際觀察到的第二次 GC 的觸發率 0.6 吻合。
## 8.3.3 實現細節
### 掃描工作估計器
### 掃描協助
### 賦值器協助
### 觸發比率控制器
```
// gcTrigger 是一個 GC 周期開始的謂詞。具體而言，它是一個 _GCoff 階段的退出條件
type gcTrigger struct {
kind gcTriggerKind
now int64 // gcTriggerTime: 當前時間
n uint32 // gcTriggerCycle: 開始的周期數
}
type gcTriggerKind int
const (
// gcTriggerHeap 表示當堆大小達到控制器計算的觸發堆大小時開始一個周期
gcTriggerHeap gcTriggerKind = iota
// gcTriggerTime 表示自上一個 GC 周期后當循環超過
// forcegcperiod 納秒時應開始一個周期。
gcTriggerTime
// gcTriggerCycle 表示如果我們還沒有啟動第 gcTrigger.n 個周期
// （相對于 work.cycles）時應開始一個周期。
gcTriggerCycle
)
// test 報告當前出發條件是否滿足，換句話說 _GCoff 階段的退出條件已滿足。
// 退出條件應該在分配階段已完成測試。
func (t gcTrigger) test() bool {
// 如果已禁用 GC
if !memstats.enablegc || panicking != 0 || gcphase != _GCoff {
return false
}
// 根據類別做不同判斷
switch t.kind {
case gcTriggerHeap:
// 上個周期結束時剩余的加上到目前為止分配的內存 超過 觸發標記階段標準的內存
// 考慮性能問題，對非原子操作訪問 heap_live 。如果我們需要觸發該條件，
// 則所在線程一定會原子的寫入 heap_live，從而我們會觀察到我們的寫入。
return memstats.heap_live >= memstats.gc_trigger
case gcTriggerTime:
if gcpercent < 0 { // 因為允許在運行時動態調整 gcpercent，因此需要額外再檢查一遍
return false
}
// 計算上次 gc 開始時間是否大于強制執行 GC 周期的時間
lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
return lastgc != 0 && t.now-lastgc > forcegcperiod // 兩分鐘
case gcTriggerCycle:
// 進行測試的周期 t.n 大于實際觸發的，需要進行 GC 則通過測試
return int32(t.n-work.cycles) > 0
}
return true
}
```
TODO:
```
type mstats struct {
...
last_gc_nanotime uint64 // 上次 gc (monotonic 時間)
...
// triggerRatio is the heap growth ratio that triggers marking.
//
// E.g., if this is 0.6, then GC should start when the live
// heap has reached 1.6 times the heap size marked by the
// previous cycle. This should be ≤ GOGC/100 so the trigger
// heap size is less than the goal heap size. This is set
// during mark termination for the next cycle's trigger.
triggerRatio float64
// gc_trigger 指觸發標記階段的堆大小
//
// 當 heap_live ≥ gc_trigger 時，標記階段將開始執行
// 它同樣用來表示必須完成的成比例清掃時的堆大小。
//
// 該字段在 triggerRatio 在標記終止階段為下一個周期的觸發器進行計算。
gc_trigger uint64
// heap_live 是 GC 認為的實際字節數。即：最近一次 GC 保留的加上從那之后分配的字節數。
// heap_live <= heap_alloc ，因為 heap_alloc 包括尚未掃描的未標記對象
// （因此在我們掃描時分配和向下），而 heap_live 不包含這些對象（因此只在 GC 之間上升）。
//
// 該字段是在沒有鎖的情況下原子更新的。
// 為了減少競爭，只有在從 mcentral 獲取 span 時才會更新，
// 并且此時它會計算該 span 中的所有未分配的插槽（將在該 mcache 從該 mcentral 獲取另一個 span 之前分配）。
// 因此，它對 “真正的” 實時堆大小的估計略微偏高了。之所以高估而非低估的原因是
// 1) 在必要時提前觸發 GC 2) 這會導致保守的 GC 率而而非過低的 GC 率。
//
// 讀取同樣應該是原子的（或在 STW 期間）。
//
// 每當更新該字段時，請調用 traceHeapAlloc() 和 gcController.revise()
heap_live uint64
(>..)
// heap_marked 表示前一個 GC 中標記的字節數。標記終止階段結束后，heap_live == heap_marked,
// 與 heap_live 不同的是，heap_marked 在下一個 mark_termination 之前都不會發生變化
heap_marked uint64
}
//go:linkname setGCPercent runtime/debug.setGCPercent
func setGCPercent(in int32) (out int32) {
lock(&mheap_.lock)
out = gcpercent
if in < 0 {
in = -1
}
gcpercent = in
heapminimum = defaultHeapMinimum * uint64(gcpercent) / 100
gcSetTriggerRatio(memstats.triggerRatio) // 更新步調來響應 gcpercent 變化
unlock(&mheap_.lock)
...
return out
}
func gcSetTriggerRatio(triggerRatio float64) {
// Compute the next GC goal, which is when the allocated heap
// has grown by GOGC/100 over the heap marked by the last
// cycle.
goal := ^uint64(0)
if gcpercent >= 0 {
goal = memstats.heap_marked + memstats.heap_marked*uint64(gcpercent)/100
}
// Set the trigger ratio, capped to reasonable bounds.
if triggerRatio < 0 {
// This can happen if the mutator is allocating very
// quickly or the GC is scanning very slowly.
triggerRatio = 0
} else if gcpercent >= 0 {
// Ensure there's always a little margin so that the
// mutator assist ratio isn't infinity.
maxTriggerRatio := 0.95 * float64(gcpercent) / 100
if triggerRatio > maxTriggerRatio {
triggerRatio = maxTriggerRatio
}
}
memstats.triggerRatio = triggerRatio
// 根據觸發器比率來計算絕對的 GC 觸發器
//
// 當分配的堆的大小超過標記的堆大小時，我們觸發下一個 GC 循環。
trigger := ^uint64(0)
if gcpercent >= 0 {
trigger = uint64(float64(memstats.heap_marked) * (1 + triggerRatio))
// 小于最小堆大小時不觸發
minTrigger := heapminimum
if !isSweepDone() { // 即 mheap_.sweepdone != 0
// Concurrent sweep happens in the heap growth
// from heap_live to gc_trigger, so ensure
// that concurrent sweep has some heap growth
// in which to perform sweeping before we
// start the next GC cycle.
sweepMin := atomic.Load64(&memstats.heap_live) + sweepMinHeapDistance
if sweepMin > minTrigger {
minTrigger = sweepMin
}
}
if trigger < minTrigger {
trigger = minTrigger
}
...
if trigger > goal {
// The trigger ratio is always less than GOGC/100, but
// other bounds on the trigger may have raised it.
// Push up the goal, too.
goal = trigger
}
}
// Commit to the trigger and goal.
memstats.gc_trigger = trigger
memstats.next_gc = goal
...
// Update mark pacing.
if gcphase != _GCoff {
gcController.revise()
}
// Update sweep pacing.
if isSweepDone() {
mheap_.sweepPagesPerByte = 0
} else {
// Concurrent sweep needs to sweep all of the in-use
// pages by the time the allocated heap reaches the GC
// trigger. Compute the ratio of in-use pages to sweep
// per byte allocated, accounting for the fact that
// some might already be swept.
heapLiveBasis := atomic.Load64(&memstats.heap_live)
heapDistance := int64(trigger) - int64(heapLiveBasis)
// Add a little margin so rounding errors and
// concurrent sweep are less likely to leave pages
// unswept when GC starts.
heapDistance -= 1024 * 1024
if heapDistance < _PageSize {
// Avoid setting the sweep ratio extremely high
heapDistance = _PageSize
}
pagesSwept := atomic.Load64(&mheap_.pagesSwept)
sweepDistancePages := int64(mheap_.pagesInUse) - int64(pagesSwept)
if sweepDistancePages <= 0 {
mheap_.sweepPagesPerByte = 0
} else {
mheap_.sweepPagesPerByte = float64(sweepDistancePages) / float64(heapDistance)
mheap_.sweepHeapLiveBasis = heapLiveBasis
// Write pagesSweptBasis last, since this
// signals concurrent sweeps to recompute
// their debt.
atomic.Store64(&mheap_.pagesSweptBasis, pagesSwept)
}
}
gcPaceScavenger()
}
```
- 第一部分 :基礎篇
- 第1章 Go語言的前世今生
- 1.2 Go語言綜述
- 1.3 順序進程通訊
- 1.4 Plan9匯編語言
- 第2章 程序生命周期
- 2.1 從go命令談起
- 2.2 Go程序編譯流程
- 2.3 Go 程序啟動引導
- 2.4 主Goroutine的生與死
- 第3 章 語言核心
- 3.1 數組.切片與字符串
- 3.2 散列表
- 3.3 函數調用
- 3.4 延遲語句
- 3.5 恐慌與恢復內建函數
- 3.6 通信原語
- 3.7 接口
- 3.8 運行時類型系統
- 3.9 類型別名
- 3.10 進一步閱讀的參考文獻
- 第4章 錯誤
- 4.1 問題的演化
- 4.2 錯誤值檢查
- 4.3 錯誤格式與上下文
- 4.4 錯誤語義
- 4.5 錯誤處理的未來
- 4.6 進一步閱讀的參考文獻
- 第5章 同步模式
- 5.1 共享內存式同步模式
- 5.2 互斥鎖
- 5.3 原子操作
- 5.4 條件變量
- 5.5 同步組
- 5.6 緩存池
- 5.7 并發安全散列表
- 5.8 上下文
- 5.9 內存一致模型
- 5.10 進一步閱讀的文獻參考
- 第二部分 運行時篇
- 第6章 并發調度
- 6.1 隨機調度的基本概念
- 6.2 工作竊取式調度
- 6.3 MPG模型與并發調度單
- 6.4 調度循環
- 6.5 線程管理
- 6.6 信號處理機制
- 6.7 執行棧管理
- 6.8 協作與搶占
- 6.9 系統監控
- 6.10 網絡輪詢器
- 6.11 計時器
- 6.12 非均勻訪存下的調度模型
- 6.13 進一步閱讀的參考文獻
- 第7章 內存分配
- 7.1 設計原則
- 7.2 組件
- 7.3 初始化
- 7.4 大對象分配
- 7.5 小對象分配
- 7.6 微對象分配
- 7.7 頁分配器
- 7.8 內存統計
- 第8章 垃圾回收
- 8.1 垃圾回收的基本想法
- 8.2 寫屏幕技術
- 8.3 調步模型與強弱觸發邊界
- 8.4 掃描標記與標記輔助
- 8.5 免清掃式位圖技術
- 8.6 前進保障與終止檢測
- 8.7 安全點分析
- 8.8 分代假設與代際回收
- 8.9 請求假設與實務制導回收
- 8.10 終結器
- 8.11 過去,現在與未來
- 8.12 垃圾回收統一理論
- 8.13 進一步閱讀的參考文獻
- 第三部分 工具鏈篇
- 第9章 代碼分析
- 9.1 死鎖檢測
- 9.2 競爭檢測
- 9.3 性能追蹤
- 9.4 代碼測試
- 9.5 基準測試
- 9.6 運行時統計量
- 9.7 語言服務協議
- 第10章 依賴管理
- 10.1 依賴管理的難點
- 10.2 語義化版本管理
- 10.3 最小版本選擇算法
- 10.4 Vgo 與dep之爭
- 第12章 泛型
- 12.1 泛型設計的演進
- 12.2 基于合約的泛型
- 12.3 類型檢查技術
- 12.4 泛型的未來
- 12.5 進一步閱讀的的參考文獻
- 第13章 編譯技術
- 13.1 詞法與文法
- 13.2 中間表示
- 13.3 優化器
- 13.4 指針檢查器
- 13.5 逃逸分析
- 13.6 自舉
- 13.7 鏈接器
- 13.8 匯編器
- 13.9 調用規約
- 13.10 cgo與系統調用
- 結束語: Go去向何方?