今天的文章我首先說一下之前文章里的思考題的解決思路，我會(huì)給出完整可運(yùn)行的代碼。之后通過觀察程序的運(yùn)行結(jié)果里的現(xiàn)象簡(jiǎn)單介紹 Go 語言的調(diào)度器是如何對(duì) goroutine 進(jìn)行調(diào)度的。
回答之前的問題
先來回顧一下上周文章里思考題的題目：
假設(shè)有一個(gè)超長(zhǎng)的切片，切片的元素類型為int，切片中的元素為亂序排列。限時(shí)5秒，使用多個(gè)goroutine查找切片中是否存在給定值，在找到目標(biāo)值或者超時(shí)后立刻結(jié)束所有g(shù)oroutine的執(zhí)行。
比如切片為：[23, 32, 78, 43, 76, 65, 345, 762, ...... 915, 86]，查找的目標(biāo)值為345，如果切片中存在目標(biāo)值程序輸出:"Found it!"并且立即取消仍在執(zhí)行查找任務(wù)的 goroutine 。如果在超時(shí)時(shí)間未找到目標(biāo)值程序輸出:"Timeout! Not Found"，同時(shí)立即取消仍在執(zhí)行查找任務(wù)的 goroutine 。
首先題目里提到了 在找到目標(biāo)值或者超時(shí)后立刻結(jié)束所有g(shù)oroutine的執(zhí)行 ，完成這兩個(gè)功能需要借助計(jì)時(shí)器、通道和 context 才行。我能想到的第一點(diǎn)就是要用 context.WithCancel 創(chuàng)建一個(gè)上下文對(duì)象傳遞給每個(gè)執(zhí)行任務(wù)的 goroutine ，外部在滿足條件后（找到目標(biāo)值或者已超時(shí)）通過調(diào)用上下文的取消函數(shù)來通知所有 goroutine 停止工作。
func main() {
timer := time.NewTimer(time.Second * 5)
ctx, cancel := context.WithCancel(context.Background())
resultChan := make(chan bool)
......
select {
case <-timer.C:
fmt.Fprintln(os.Stderr, "Timeout! Not Found")
cancel()
case <- resultChan:
fmt.Fprintf(os.Stdout, "Found it!n")
cancel()
}
}
執(zhí)行任務(wù)的 goroutine 們?nèi)绻业侥繕?biāo)值后需要通知外部等待任務(wù)執(zhí)行的主 goroutine ，這個(gè)工作是典型的應(yīng)用通道的場(chǎng)景，上面代碼也已經(jīng)看到了，我們創(chuàng)建了一個(gè)接收查找結(jié)果的通道，接下來要做的就是把它和上下文對(duì)象一起傳遞給執(zhí)行任務(wù)的 goroutine 。
func SearchTarget(ctx context.Context, data []int, target int, resultChan chan bool) {
for _, v := range data {
select {
case <- ctx.Done():
fmt.Fprintf(os.Stdout, "Task cancelded! n")
return
default:
}
// 模擬一個(gè)耗時(shí)查找，這里只是比對(duì)值，真實(shí)開發(fā)中可以是其他操作
fmt.Fprintf(os.Stdout, "v: %d n", v)
time.Sleep(time.Millisecond * 1500)
if target == v {
resultChan <- true
return
}
}
}
在執(zhí)行查找任務(wù)的 goroutine 里接收上下文的取消信號(hào)，為了不阻塞查找任務(wù)，我們使用了 select 語句加 default 的組合：
select {
case <- ctx.Done():
fmt.Fprintf(os.Stdout, "Task cancelded! n")
return
default:
}
在 goroutine 里面如果找到了目標(biāo)值，則會(huì)通過發(fā)送一個(gè) true 值給 resultChan ，讓外面等待的主 goroutine 收到一個(gè)已經(jīng)找到目標(biāo)值的信號(hào)。
resultChan <- true
這樣通過上下文的 Done 通道和 resultChan 通道， goroutine 們就能相互通信了。
Go 語言中最常見的、也是經(jīng)常被人提及的設(shè)計(jì)模式 — 不要通過共享內(nèi)存的方式進(jìn)行通信，而是應(yīng)該通過通信的方式共享內(nèi)存
完整的源代碼如下：
package main
import (
"context"
"fmt"
"os"
"time"
)
func main() {
timer := time.NewTimer(time.Second * 5)
data := []int{1, 2, 3, 10, 999, 8, 345, 7, 98, 33, 66, 77, 88, 68, 96}
dataLen := len(data)
size := 3
target := 345
ctx, cancel := context.WithCancel(context.Background())
resultChan := make(chan bool)
for i := 0; i < dataLen; i += size {
end := i + size
if end >= dataLen {
end = dataLen - 1
}
go SearchTarget(ctx, data[i:end], target, resultChan)
}
select {
case <-timer.C:
fmt.Fprintln(os.Stderr, "Timeout! Not Found")
cancel()
case <- resultChan:
fmt.Fprintf(os.Stdout, "Found it!n")
cancel()
}
time.Sleep(time.Second * 2)
}
func SearchTarget(ctx context.Context, data []int, target int, resultChan chan bool) {
for _, v := range data {
select {
case <- ctx.Done():
fmt.Fprintf(os.Stdout, "Task cancelded! n")
return
default:
}
// 模擬一個(gè)耗時(shí)查找，這里只是比對(duì)值，真實(shí)開發(fā)中可以是其他操作
fmt.Fprintf(os.Stdout, "v: %d n", v)
time.Sleep(time.Millisecond * 1500)
if target == v {
resultChan <- true
return
}
}
}
為了打印演示結(jié)果所以加了幾處 time.Sleep ，這個(gè)程序更多的是提供思路框架，所以細(xì)節(jié)的地方?jīng)]有考慮。有幾位讀者把他們的答案發(fā)給了我，其中有一位的提供的答案在代碼實(shí)現(xiàn)上考慮的更全面，這個(gè)我們放到文末再說。
上面程序的執(zhí)行結(jié)果如下：
v: 1
v: 88
v: 33
v: 10
v: 345
Found it!
v: 2
v: 999
Task cancelded!
v: 68
Task cancelded!
Task cancelded!
因?yàn)槭遣l(fā)程序所以每次打印的結(jié)果的順序是不一樣的，這個(gè)你們可以自己試驗(yàn)一下。而且也并不是先開啟的 goroutine 就一定會(huì)先執(zhí)行，主要還是看調(diào)度器先調(diào)度哪個(gè)。
Go語言調(diào)度器
所有應(yīng)用程序都是運(yùn)行在操作系統(tǒng)上，真正用來干活(計(jì)算)的是 CPU 。所以談到 Go 語言調(diào)度器，我們也繞不開操作系統(tǒng)、進(jìn)程與線程這些概念。線程是操作系統(tǒng)調(diào)度時(shí)的最基本單元，而 linux 在調(diào)度器并不區(qū)分進(jìn)程和線程的調(diào)度，它們?cè)诓煌僮飨到y(tǒng)上也有不同的實(shí)現(xiàn)，但是在大多數(shù)的實(shí)現(xiàn)中線程都屬于進(jìn)程。
多個(gè)線程可以屬于同一個(gè)進(jìn)程并共享內(nèi)存空間。因?yàn)槎嗑€程不需要?jiǎng)?chuàng)建新的虛擬內(nèi)存空間，所以它們也不需要內(nèi)存管理單元處理上下文的切換，線程之間的通信也正是基于共享的內(nèi)存進(jìn)行的，與重量級(jí)的進(jìn)程相比，線程顯得比較輕量。
雖然線程比較輕量，但是在調(diào)度時(shí)也有比較大的額外開銷。每個(gè)線程會(huì)都占用 1 兆以上的內(nèi)存空間，在對(duì)線程進(jìn)行切換時(shí)不止會(huì)消耗較多的內(nèi)存，恢復(fù)寄存器中的內(nèi)容還需要向操作系統(tǒng)申請(qǐng)或者銷毀對(duì)應(yīng)的資源。
大量的線程出現(xiàn)了新的問題
- 高內(nèi)存占用
- 調(diào)度的CPU高消耗
然后工程師們就發(fā)現(xiàn)，其實(shí)一個(gè)線程分為"內(nèi)核態(tài)"線程和"用戶態(tài)"線程。
一個(gè) 用戶態(tài)線程 必須要綁定一個(gè) 內(nèi)核態(tài)線程 ，但是CPU并不知道有 用戶態(tài)線程 的存在，它只知道它運(yùn)行的是一個(gè) 內(nèi)核態(tài)線程 (Linux的PCB進(jìn)程控制塊)。這樣，我們?cè)偃ゼ?xì)化分類，內(nèi)核線程依然叫線程(thread)，用戶線程叫協(xié)程(co-routine)。既然一個(gè)協(xié)程可以綁定一個(gè)線程，那么也可以通過實(shí)現(xiàn)協(xié)程調(diào)度器把多個(gè)協(xié)程與一個(gè)或者多個(gè)線程進(jìn)行綁定。
Go 語言的 goroutine 來自協(xié)程的概念，讓一組可復(fù)用的函數(shù)運(yùn)行在一組線程之上，即使有協(xié)程阻塞，該線程的其他協(xié)程也可以被 runtime 調(diào)度，轉(zhuǎn)移到其他可運(yùn)行的線程上。最關(guān)鍵的是，程序員看不到這些底層的細(xì)節(jié)，這就降低了編程的難度，提供了更容易的并發(fā)。
Go 中，協(xié)程被稱為 goroutine ，它非常輕量，一個(gè) goroutine 只占幾KB，并且這幾KB就足夠 goroutine 運(yùn)行完，這就能在有限的內(nèi)存空間內(nèi)支持大量 goroutine ，支持了更多的并發(fā)。雖然一個(gè) goroutine 的棧只占幾KB，但實(shí)際是可伸縮的，如果需要更多內(nèi)存， runtime 會(huì)自動(dòng)為 goroutine 分配。
既然我們知道了 goroutine 和系統(tǒng)線程的關(guān)系，那么最關(guān)鍵的一點(diǎn)就是實(shí)現(xiàn)協(xié)程調(diào)度器了。
Go 目前使用的調(diào)度器是2012年重新設(shè)計(jì)的，因?yàn)橹暗恼{(diào)度器性能存在問題，所以使用4年就被廢棄了。重新設(shè)計(jì)的調(diào)度器使用 G-M-P 模型并一直沿用至今。
調(diào)度器G-M-P模型
- G — 表示 goroutine，它是一個(gè)待執(zhí)行的任務(wù)；
- M — 表示操作系統(tǒng)的線程，它由操作系統(tǒng)的調(diào)度器調(diào)度和管理；
- P — 表示處理器，它可以被看做運(yùn)行在線程上的本地調(diào)度器；
G
gorotuine 就是 Go 語言調(diào)度器中待執(zhí)行的任務(wù)，它在運(yùn)行時(shí)調(diào)度器中的地位與線程在操作系統(tǒng)中差不多，但是它占用了更小的內(nèi)存空間，也降低了上下文切換的開銷。
goroutine 只存在于 Go 語言的運(yùn)行時(shí)，它是 Go 語言在用戶態(tài)提供的線程，作為一種粒度更細(xì)的資源調(diào)度單元，如果使用得當(dāng)能夠在高并發(fā)的場(chǎng)景下更高效地利用機(jī)器的 CPU 。
M
Go 語言并發(fā)模型中的 M 是操作系統(tǒng)線程。調(diào)度器最多可以創(chuàng)建 10000 個(gè)線程，但是其中大多數(shù)的線程都不會(huì)執(zhí)行用戶代碼（可能陷入系統(tǒng)調(diào)用），最多只會(huì)有 GOMAXPROCS 個(gè)活躍線程能夠正常運(yùn)行。
在默認(rèn)情況下，運(yùn)行時(shí)會(huì)將 GOMAXPROCS 設(shè)置成當(dāng)前機(jī)器的核數(shù)，我們也可以使用 runtime.GOMAXPROCS 來改變程序中最大的線程數(shù)。一個(gè)四核機(jī)器上會(huì)創(chuàng)建四個(gè)活躍的操作系統(tǒng)線程，每一個(gè)線程都對(duì)應(yīng)一個(gè)運(yùn)行時(shí)中的 runtime.m 結(jié)構(gòu)體。
在大多數(shù)情況下，我們都會(huì)使用 Go 的默認(rèn)設(shè)置，也就是活躍線程數(shù)等于 CPU 個(gè)數(shù)，在這種情況下不會(huì)觸發(fā)操作系統(tǒng)的線程調(diào)度和上下文切換，所有的調(diào)度都會(huì)發(fā)生在用戶態(tài)，由 Go 語言調(diào)度器觸發(fā)，能夠減少非常多的額外開銷。
操作系統(tǒng)線程在 Go 語言中會(huì)使用私有結(jié)構(gòu)體 runtime.m 來表示
type m struct {
g0 *g
curg *g
...
}
其中 g0 是持有調(diào)度棧的 goroutine ， curg 是在當(dāng)前線程上運(yùn)行的用戶 goroutine ，用戶 goroutine 執(zhí)行完后，線程切換回 g0 上， g0 會(huì)從線程 M 綁定的 P 上的等待隊(duì)列中獲取 goroutine 交給線程。
P
調(diào)度器中的處理器 P 是線程和 goroutine 的中間層，它能提供線程需要的上下文環(huán)境，也會(huì)負(fù)責(zé)調(diào)度線程上的等待隊(duì)列，通過處理器 P 的調(diào)度，每一個(gè)內(nèi)核線程都能夠執(zhí)行多個(gè) goroutine ，它能在 goroutine 進(jìn)行一些 I/O 操作時(shí)及時(shí)切換，提高線程的利用率。因?yàn)檎{(diào)度器在啟動(dòng)時(shí)就會(huì)創(chuàng)建 GOMAXPROCS 個(gè)處理器，所以 Go 語言程序的處理器數(shù)量一定會(huì)等于 GOMAXPROCS ，這些處理器會(huì)綁定到不同的內(nèi)核線程上并利用線程的計(jì)算資源運(yùn)行 goroutine 。
此外在調(diào)度器里還有一個(gè)全局等待隊(duì)列，當(dāng)所有P本地的等待隊(duì)列被占滿后，新創(chuàng)建的 goroutine 會(huì)進(jìn)入全局等待隊(duì)列。 P 的本地隊(duì)列為空后， M 也會(huì)從全局隊(duì)列中拿一批待執(zhí)行的 goroutine 放到 P 本地的等待隊(duì)列中。
GMP模型圖示
GMP模型圖示
- 全局隊(duì)列：存放等待運(yùn)行的G。
- P的本地隊(duì)列：同全局隊(duì)列類似，存放的也是等待運(yùn)行的G，存的數(shù)量有限，不超過256個(gè)。新建G時(shí)，G優(yōu)先加入到P的本地隊(duì)列，如果隊(duì)列已滿，則會(huì)把本地隊(duì)列中一半的G移動(dòng)到全局隊(duì)列。
- P列表：所有的P都在程序啟動(dòng)時(shí)創(chuàng)建，并保存在數(shù)組中，最多有GOMAXPROCS(可配置)個(gè)。
- M：線程想運(yùn)行任務(wù)就得獲取P，從P的本地隊(duì)列獲取G，P隊(duì)列為空時(shí)，M也會(huì)嘗試從全局隊(duì)列拿一批G放到P的本地隊(duì)列，或從其他P的本地隊(duì)列偷一半放到自己P的本地隊(duì)列。M運(yùn)行G，G執(zhí)行之后，M會(huì)從P獲取下一個(gè)G，不斷重復(fù)下去。
- goroutine 調(diào)度器和OS調(diào)度器是通過M結(jié)合起來的，每個(gè)M都代表了1個(gè)內(nèi)核線程，OS調(diào)度器負(fù)責(zé)把內(nèi)核線程分配到CPU上執(zhí)行。
調(diào)度器的策略
調(diào)度器的一個(gè)策略是盡可能的復(fù)用現(xiàn)有的活躍線程，通過以下兩個(gè)機(jī)制提高線程的復(fù)用：
- work stealing機(jī)制，當(dāng)本線程無可運(yùn)行的G時(shí)，嘗試從其他線程綁定的P偷取G，而不是銷毀線程。
- hand off機(jī)制，當(dāng)本線程因?yàn)镚進(jìn)行系統(tǒng)調(diào)用阻塞時(shí)，線程釋放綁定的P，把P轉(zhuǎn)移給其他空閑的線程執(zhí)行。
Go 的運(yùn)行時(shí)并不具備操作系統(tǒng)內(nèi)核級(jí)的硬件中斷能力，基于工作竊取的調(diào)度器實(shí)現(xiàn)，本質(zhì)上屬于先來先服務(wù)的協(xié)作式調(diào)度，為了解決響應(yīng)時(shí)間可能較高的問題，目前運(yùn)行時(shí)實(shí)現(xiàn)了協(xié)作式調(diào)度和搶占式調(diào)度兩種不同的調(diào)度策略，保證在大部分情況下，不同的 G 能夠獲得均勻的 CPU 時(shí)間片。
協(xié)作式調(diào)度依靠被調(diào)度方主動(dòng)棄權(quán)，系統(tǒng)監(jiān)控到一個(gè) goroutine 運(yùn)行超過10ms會(huì)通過 runtime.Gosched 調(diào)用主動(dòng)讓出執(zhí)行機(jī)會(huì)。搶占式調(diào)度則依靠調(diào)度器強(qiáng)制將被調(diào)度方被動(dòng)中斷。
