天天看點

聊一聊作業系統線程排程與Go協程

前言

我們計算機上面跑的每個任務,都是作業系統層面的資源配置設定,從啟動程序到建立線程,在核數固定的情況下,多線程并發地執行。Go協程是一個比系統線程更細粒度的資源,輕量級和易切換。

這幾天看了一些相關的文章,這次嘗試從作業系統到Go協程,簡單聊聊它們是如何關聯上的以及我個人的了解。

基本概念

作業系統(OS)

作業系統負責着底層硬體的排程,它配置設定CPU,記憶體,磁盤的資源,并且替我們配置設定不同線程在不同CPU核的執行,保證各個程式如預期的指令進行執行。我們送出的每個程式,最終都會轉換成一系列給作業系統識别的指令。

線程(Thread)

上述經過轉換的一系列指令,作業系統會通過線程來幫我們執行,本質上線程是

a path of execution

,一段可執行的程式路徑。

線程有下面三個狀态:

  • 運作中:正在執行任務,理想狀态是所有線程都處于這個狀态。
  • 就緒:可以随時加入運作,從就緒到運作的狀态切換,叫做上下文切換,它需要一定的代價。
  • 等待就緒:需要等待資源配置設定或者IO(網絡/裝置)阻塞中,需要經過就緒才能運作,這是在使用者角度最不想看到的,它成為了程式大部分的性能瓶頸。

系統排程器

排程器肩負着巨大的使命,主要在于排程CPU與線程關系,保證不會有CPU閑下來,想象一下CPU就是倉鼠籠子裡面的倉鼠,排程器一旦發現有倉鼠(CPU)在打瞌睡,就推動它們到輪子(線程)上跑,一刻也不能停。畢竟CPU的運算能力是很強悍的,一毫秒的空閑都是巨大的浪費。

往細處說,倉鼠隻有4隻(四核),哪個輪子(線程)優先跑,取決于輪子(線程)的優先級。排程器肩負着運籌帷幄的使命,既要減少催促倉鼠跑動的延遲,同時還要保證不能有任務一直得不到執行,線程如果一直得不到倉鼠處理被稱作“饑餓現象”。

任務類型

不同的任務對系統資源有不同的要求

  • I/O頻繁切換:

    未雨綢缪,IO指的是Input/Output,輸入輸出等待。這種等待資源輸入/輸出的job,主要瓶頸在資源是否配置設定到位,比如系統調用/檔案IO等,其線程切換的時間遠遠小于IO裝置/網絡延遲,主要短闆在于等待I/O,而不是線程上下文切換,是以可以配置設定較多線程,在“糧草”還沒送到的這段時間,執行作戰前的準備。

  • 計算密集型:

    這種任務主要耗CPU,比如用一個線程計算圓周率π的第N位。如果配置設定大量的線程給它,系統既要保證各個線程對計算狀态的共享,先不考慮會發生髒讀/髒寫操作,還需要頻繁進行線程切換,這會造成大量時間浪費,線程每次重新喚醒都要在程式計數器(PC)尋找下一個執行指令的位置,在核數固定的情況下,配置設定過多線程會有事倍功半的效果。

    If your program is focused on CPU-Bound work, then context switches are going to be a performance nightmare. Since the Thead always has work to do, the context switch is stopping that work from progressing.
    當然也有例外的情況,比如Map-Reduce,指的是先拆分後聚合。當你的計算任務可以拆分成很多子產品,在各個子產品不同執行順序不會影響最終結果的情況下,嘗試“逐個擊破”,最終再彙聚的情況,如果能合理配置設定任務,多線程肯定是優于單線程的。

後面嘗試通過列舉幾個Go的簡單程式,通過單/多協程處理,比對兩者在不同情景的性能差異情況。

Map-Reduce:

這個例子比較簡單,我們目标是累加一個等差數列

var PIXEL_ARRAY []int
//初始化一個等差數列,後面嘗試将等差數列傳到單協程/多協程函數進行累加
func init()  {
	for i := 1; i <= 100000; i++ {
		PIXEL_ARRAY = append(PIXEL_ARRAY, i)
	}
}
           

後面我們用單協程/多協程版本,區分開兩個實作方式

//單協程暴力版本
func SumWithSingle(arr []int) int32 {
	var sum int32
	//周遊累加,相當暴力!
	for i := 0; i < len(arr); i++ {
		sum += int32(arr[i])
	}
	return sum
}

//多協程版本,每個協程均等計算自己配置設定的切片區間, gNum是起多少個協程并發處理
func SumWithMulti(arr []int, gNum int) int32 {
	var wg sync.WaitGroup
	//用于等待gNum個協程執行完
	wg.Add(gNum)

	var sum int32
	//各個任務的平均長度
	div := len(arr) / gNum
	
	//注意切割長度需要向上取整,此處非本demo側重點,為了簡單化一律使用整除切開原數組.
	//div := int(math.Ceil(float64(float64(len(arr)) / float64(gNum))))
	
	for i := 0; i < gNum; i++ {
		Left := i * div
		Right := Left + div
		if i == gNum {
			Right = len(arr)
		}
		go func() {
		    //每個協程獨立的彙總
			ps := 0
			for _, value := range arr[Left:Right] {
				ps += value
			}
			//處理完累積到全局變量,由于僅有累加操作,可以用原子加實作互斥, 這裡無需加鎖.
			atomic.AddInt32(&sum, int32(ps))
			wg.Done()
		}()
	}

	//等待各個子協程計算完畢
	wg.Wait()
	return sum
}
           

性能分析

下面嘗試用BenchMark分析性能,輸出如下:

import "testing"

var PIXEL_ARRAY []int

func init()  {
	for i := 1; i <= 100000; i++ {
		PIXEL_ARRAY = append(PIXEL_ARRAY, i)
	}
}

func BenchmarkSumWithSingle(b *testing.B) {
	for i := 0; i < b.N; i++ {
		SumWithSingle(PIXEL_ARRAY)
	}
}

func BenchmarkSumWithMulti(b *testing.B) {
	for i := 0; i < b.N; i++ {
		SumWithMulti(PIXEL_ARRAY, 10)
	}
}
           

結果示例:

在4核電腦上,啟動10個協程去并發處理,針對這個例子多協程是優于單協程的,符合預期。

$ GOGC=off go test -run none -bench . -benchtime 3s
goos: windows
goarch: amd64
pkg: HelloGo/basic/Multi
BenchmarkSumWithSingle-4           50000             63583 ns/op
BenchmarkSumWithMulti-4           100000             39216 ns/op
PASS
ok      HelloGo/basic/Multi     8.623s
           

在作業系統層面,每個線程的執行先後順序是無法保證的。Go中,協程也是如此。拿上個例子來說,Map-Reduce的Map操作是切開等差數列,配置設定到任務的不同Go協程執行時間是不确定的,有可能

1+2+3+...

, 也有可能是

21+22+23+...

如果程式要控制相應線程執行的順序,需要在作業系統的上一層,比如程式設計語言中加入排程指令,如++原子操作,同步鎖,互斥量++,程式的性能也和鎖的粒度有關系,這個相關知識可以作為以後拓展。

Go排程器的實作是基于作業系統排程這些理念實作的,後面我們嘗試往更高層(使用者态)走,以Go協程是如何被排程的角度來分析。

Go Scheduler

衆所周知,Go排程器有下面幾個主要的元件:

  • M: 工作線程, 由P建立,關聯上OS線程,可以了解為M就是OS線程
  • P: 上下文,處理代碼的所需資源, 建立數量與CPU核數相關,每個P會配置設定一個OS線程(M)
  • G: 目前go協程,如果關聯上OS線程(M),代表即将或者正在執行的go代碼。G可以在兩個隊列中找到它們,本地/全局隊列,我們後面再細談。
At any time, M goroutines need to be scheduled on N OS threads that runs on at most GOMAXPROCS numbers of processors.

P,邏輯CPU

GO的P和你的CPU核心數量有關,注意這裡并不是真正CPU數量,是++邏輯CPU數量++。檢視任務管理器,在4核CPU的情況下,假如說你的機器具備超線程(i7處理器),每個實體核有兩個線程,那麼意味着在Go程式裡邏輯上有8個可用的處理器,邏輯CPU數量應該是8。即上面所提到的P。

我目前機器是(i5處理器),每個核一個線程,是以下面輸出的邏輯CPU(P)數量是4,這代表當啟動多個線程的時候,我的機器最多可以支援并行4個系統線程,多出來的線程就是并發了。

可以通過在你的機器執行下列Go代碼,看下邏輯P的數量,

package main

import (
	"fmt"
	"runtime"
)

func main() {
    // NumCPU returns the number of logical
    // CPUs usable by the current process.
    //我的機器輸出 4
    fmt.Println(runtime.NumCPU())
}
           

每一個P會配置設定一個系統線程M,相當于說在這個機器的Go程式中,我有4個系統線程可以用來執行我的任務,每個都獨立與其中一個核,P挂鈎。

M個Go協程會配置設定在N個系統線程上,每個要運作的G都必須關聯上P(邏輯CPU),程式可以幹涉

GOMAXPROCS

的數量,以控制最多有多少個P可以使用。

下面用圖示可能會更加直覺:

聊一聊作業系統線程排程與Go協程

在Go中,每個上下文P會配置設定一個本地的協程隊列(LRQ),叫做Local Run Queue ,一個M必須關聯所需的資源P才能運作相應的G隊列,正如作業系統層面上每個線程隊列需要配置設定關聯上CPU才能得到執行,類比前面的栗子,輪子(M)需要倉鼠(P)去帶動,才能執行(跑G協程任務)。

如下圖所示:

聊一聊作業系統線程排程與Go協程

P1,P2是相對固定的,M和G是可以随排程器配置設定選擇的。

Go協程的切換

了解完上面的一些概念之後,現在我們看下Go是如何對協程進行切換,文章前面提到,假如線程建立過多,由于系統排程的不确定性,線程得不到執行,可能會長期處于饑餓。同理Go協程也會有“靠邊停車”的現象,是以Go排程器需要一些的條件來觸發協程切換,避免停完車就不再啟動了,具體的切換本質上就是Go排程器對P-M-G三者之間的斷開與重連。

下列情景可能會讓排程器對執行上下文,即go協程的切換做出決定:

  • go關鍵字,建立新的協程
  • 垃圾回收
  • 系統調用
  • 同步/互斥/

    Gosched()

    等操作

程式示例:

下面展示一個簡單而且比較常見的例子,我們通過限制邏輯CPU的個數,嘗試幹涉Go排程器。

func main() {

    //設定最多一個P可以關聯上
	runtime.GOMAXPROCS(1)
	go func() {
		for {
			//保持空轉,如果沒有其他函數調用,在單個處理器下該協程不會切換
			;
		}
	}()

	//嘗試切換協程
	runtime.Gosched()
	println("main done.")
}
           

我們通過

runtime.GOMAXPROCS(1)

設定本次運作的邏輯CPU個數,代表可用的P隻有1,意味着最多隻能同時配置設定給一個協程去執行。如果執行這個程式,由于主協程執行了讓步Gosched(),獲得運作權的的Go協程會得到執行,由于該協程在死循環一直執行空語句,導緻程式不會有任何輸出,而且主協程得不到運作權,是以這個程式永遠不會退出。

題外話:注意這裡差別于上面的

runtime.NumCPU(int)

方法,

NumCPU()

是在啟動時候直接調用系統方法,是以和經過GOMAXPROCS的設定之後,并不會改變

NumCPU()

原有的傳回值,

GOMAXPROCS

僅是對本次運作時P數量進行限制。

協程偷竊

從Go排程器角度看,執行的協程任務有點快有的慢,既然我的職責是不能讓CPU空閑,那當我有空的時候,我肯定要從别人那裡偷一些任務來跑。

聊一聊作業系統線程排程與Go協程

是的,是明目張膽的偷!我覺得這張圖很貼切,是以我把這張圖也偷來了哈哈哈。

原文參考:Go: Work-Stealing in Go Scheduler (可能需要科學上網)

前面提到兩個隊列,全局/本地隊列:

  • 本地隊列:指的是目前上下文P關聯上的Go協程隊列(LRQ),本地隊列,在go1.13版本每個本地協程隊列的最大值是256,超過256就會放到全局隊列裡面去。本地隊列是可以被其他P偷走的,在某些情況下,當有P發現本地的G隊列空了,就會去偷其他P的本地隊列,每次會從其它P的本地隊列裡面偷走一半的G。
  • 全局隊列:在其他情況,當有空閑P發現其他P的本地隊列沒有G可以偷的情況下,會嘗試擷取全局隊列的G去執行。
runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}
           

上面的注釋表明了偷竊各個部分的優先級,隻有1/61的時間會去檢查全局隊列。

優先級:本地隊列 > 其他P的隊列 > 全局隊列

根據這張我從别處偷來的這張圖,此時P2的本地隊列已經是空的,是以這個時候P2即将要從P1偷走3個G

聊一聊作業系統線程排程與Go協程

總結

Go排程的思想是基于上述系統排程實作的,歸根結底Go中的協程切換是P-M-G三者之間的斷開與重連。是以G協程在目前線程M的切換,就像從系統角度看,線程在CPU上面的切換。

Your workload is naturally stopped and this allows a different Goroutine to leverage the same OS/hardware thread efficiently instead of letting the OS/hardware thread sit idle.

因為Go協程比線程粒度更小,更加輕量級,是以Go協程切換會比OS直接切換線程代價更小。

到這裡隻是淺嘗辄止的梳理Go排程的情況,大家如果有興趣深入挖掘的話可以參考郝林老師的《Go并發程式設計實戰》,或者直接看源碼,相關的Go排程政策可以在

src/runtime/proc.go

找到。

參考連結

Scheduling In Go : Part II - Go Scheduler

Ardanlabs素質三連:

https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part2.html

dotGo 2017 - JBD - Go’s work stealing scheduler

https://www.youtube.com/watch?v=Yx6FBsGNOp4

Go: Goroutine and Preemption

https://medium.com/a-journey-with-go/go-goroutine-and-preemption-d6bc2aa2f4b7

Go’s work-stealing scheduler

https://rakyll.org/scheduler/

繼續閱讀