調(diào)度相關(guān)的一系列文章主要參考 Scheduling In Go : Part I - OS Scheduler 翻譯來(lái)的。
因?yàn)樵趯W(xué)習(xí)的過(guò)程中偶然發(fā)現(xiàn)，感覺(jué)總結(jié)得蠻好的，就不造輪子了，干脆直接翻譯過(guò)來(lái)作為自己的學(xué)習(xí)筆記了，英文好的建議直接閱讀原文。
作者：達(dá)菲格
轉(zhuǎn)自：簡(jiǎn)書(shū) http://www.itdecent.cn/p/db0aea4d60ed
來(lái)源：簡(jiǎn)書(shū)
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
介紹
Go 調(diào)度器使你編寫(xiě)的 Go 程序并發(fā)性更好，性能更高。這主要是因?yàn)?Go 調(diào)度器很好的運(yùn)用了系統(tǒng)調(diào)度器的機(jī)制原理。但是，如果你不了解調(diào)度器基本的工作原理，那你寫(xiě)的 Go 服務(wù)很可能對(duì)調(diào)度器很不友好，使得 Go 調(diào)度器發(fā)揮不出它的優(yōu)勢(shì)。想要正確的設(shè)計(jì)一個(gè)優(yōu)秀的高并發(fā)服務(wù)，對(duì)操作系統(tǒng)和 Go 的調(diào)度機(jī)制的一定的理解是很重要的。
這一系列的文章主要專注在調(diào)度器的一些宏觀機(jī)制上。我會(huì)形象化的詳細(xì)解釋它是如何工作的，使你可以在編碼時(shí)做出更好的工程判斷。盡管在并發(fā)編程中你還有很多其他知識(shí)點(diǎn)要了解，但在調(diào)度器的機(jī)制是其中比較基礎(chǔ)的一部分。。
操作系統(tǒng)調(diào)度
操作系統(tǒng)調(diào)度器是軟件開(kāi)發(fā)中很復(fù)雜的一塊。他們必須考慮硬件設(shè)施的布局和設(shè)計(jì)。這其中就包括了多處理器和多核的存在，CPU 緩存和 NUMA。沒(méi)有這些知識(shí)，調(diào)度器就無(wú)法達(dá)到高效。慶幸的是，你仍然可以通過(guò)構(gòu)造一個(gè)宏觀的心理模型來(lái)理解操作系統(tǒng)調(diào)度程序的工作原理，而無(wú)需深入研究這一主題。
你的程序其實(shí)就是一堆需要按照順序一個(gè)接一個(gè)執(zhí)行的機(jī)器指令。為此，操作系統(tǒng)使用了一個(gè)線程的概念。線程的工作就是按順序執(zhí)行分配給它的指令集，直到?jīng)]有指令可以執(zhí)行了為止。
你運(yùn)行的每一個(gè)程序都會(huì)創(chuàng)建一個(gè)進(jìn)程，并且每一個(gè)進(jìn)程都會(huì)有一個(gè)初始線程。線程擁有創(chuàng)建更多線程的能力。這些不同的線程都是獨(dú)立運(yùn)行的，調(diào)度策略都是在線程這一級(jí)別上的，而不是進(jìn)程級(jí)別（或者說(shuō)調(diào)度的最小單元是線程而不是進(jìn)程）。線程是可以并發(fā)執(zhí)行的（輪流使用同一個(gè)核），或并行（每個(gè)線程互不干擾的同時(shí)在不同的核上跑）。線程還維護(hù)這他們自己狀態(tài)，好保證安全、隔離、獨(dú)立的執(zhí)行自己的指令。
系統(tǒng)調(diào)度器負(fù)責(zé)保證當(dāng)有線程可以執(zhí)行時(shí)，CPU 是不能處于空閑狀態(tài)的。它還必須創(chuàng)建一個(gè)所有線程同時(shí)都在運(yùn)行的假象。在創(chuàng)造這個(gè)假象的過(guò)程中，調(diào)度器需要優(yōu)先運(yùn)行優(yōu)先級(jí)更高的線程。但是低優(yōu)先級(jí)的線程又不能被餓死（就是一直不被運(yùn)行）。調(diào)度器還需要通過(guò)快速、明智的決策盡可能的最小化調(diào)度延遲。
這方面有很多種算法，不過(guò)幸運(yùn)的是，這方面有行業(yè)里數(shù)十年的工作經(jīng)驗(yàn)可以參考。
執(zhí)行指令
Program counter(PC)，有時(shí)候也被叫做指令指針(instruction pointer, 簡(jiǎn)稱IP)，線程用它來(lái)跟蹤下一個(gè)要執(zhí)行的指令。在大多數(shù)處理器中，PC 指向的是下一個(gè)指令，而不是當(dāng)前指令。
如果你曾經(jīng)看過(guò) Go 程序的 stack trace，你可能注意到了每行的最后都有一個(gè) 16 進(jìn)制數(shù)字。比如 +0x39和0x72。
goroutine 1 [running]:
main.example(0xc000042748, 0x2, 0x4, 0x106abae, 0x5, 0xa)
stack_trace/example1/example1.go:13 +0x39 <- LOOK HERE
main.main()
stack_trace/example1/example1.go:8 +0x72 <- LOOK HERE
這些數(shù)字表示的是 PC 值距離所在函數(shù)的頂部的偏移量。0x39 這個(gè) PC 偏移量代表了線程要執(zhí)行的在 example 函數(shù)中的下一個(gè)指令（如果程序沒(méi)有崩潰）。0x72 代表的是程序返回到 main 后，要執(zhí)行的下一個(gè)指令。更重要的是，在這個(gè)指針之前的那個(gè)指令，表示的是正在執(zhí)行的指令。
來(lái)看一下上述 stack trace 的源代碼。
func main() {
example(make([]string, 2, 4), "hello", 10)
}
func example(slice []string, str string, i int) {
panic("Want stack trace")
}
16 進(jìn)制數(shù)字 +0x39 代表了距離 example 函數(shù)第一條指令后面 57(0x39的10進(jìn)制值) 字節(jié)的那個(gè)指令。下面我們通過(guò)對(duì)二進(jìn)制文件執(zhí)行 objdump，來(lái)看看這個(gè) example 函數(shù)。從下面的匯編代碼中找到第 12 條指令。注意上面代碼中調(diào)用 panic 的那條指令。
$ go tool objdump -S -s "main.example" ./example1
TEXT main.example(SB) stack_trace/example1/example1.go
func example(slice []string, str string, i int) {
0x104dfa0 65488b0c2530000000 MOVQ GS:0x30, CX
0x104dfa9 483b6110 CMPQ 0x10(CX), SP
0x104dfad 762c JBE 0x104dfdb
0x104dfaf 4883ec18 SUBQ $0x18, SP
0x104dfb3 48896c2410 MOVQ BP, 0x10(SP)
0x104dfb8 488d6c2410 LEAQ 0x10(SP), BP
panic("Want stack trace")
0x104dfbd 488d059ca20000 LEAQ runtime.types+41504(SB), AX
0x104dfc4 48890424 MOVQ AX, 0(SP)
0x104dfc8 488d05a1870200 LEAQ main.statictmp_0(SB), AX
0x104dfcf 4889442408 MOVQ AX, 0x8(SP)
0x104dfd4 e8c735fdff CALL runtime.gopanic(SB)
0x104dfd9 0f0b UD2 <--- LOOK HERE PC(+0x39)
線程狀態(tài)
另一個(gè)重要的概念就是線程狀態(tài)，它決定了線程在調(diào)度器中的角色。一個(gè)線程有 3 中狀態(tài)：阻塞態(tài)、就緒態(tài)和運(yùn)行態(tài)。
譯者注：實(shí)際情況中不止這 3 個(gè)，阻塞也分可中斷和不可中斷 2 種，此外還有僵尸態(tài)、初始化狀態(tài)等。
但如作者所說(shuō)，我們只是在宏觀上建立一個(gè)簡(jiǎn)單心理模型來(lái)理解調(diào)度原理，不深入細(xì)節(jié)。
阻塞態(tài)：表示線程已經(jīng)停止，需要等待一些事情發(fā)生后才可繼續(xù)。這有很多種原因，比如需要等待硬件（磁盤(pán)或網(wǎng)絡(luò)），系統(tǒng)調(diào)用，或者互斥鎖（atomic, mutexes）。這類情況導(dǎo)致的延遲，往往是性能不佳的根本原因。
譯者注：如果你發(fā)現(xiàn)，機(jī)器的 CPU 利用率很低，同時(shí)程序的 QPS 還很低，待處理的請(qǐng)求還有很多堆在后面，速度就是上不去。那說(shuō)明你的線程都處于阻塞態(tài)等待被喚醒，沒(méi)有干活。
就緒態(tài)：這代表線程想要一個(gè) CPU 核來(lái)執(zhí)行被分配的機(jī)器指令。如果你有很多個(gè)線程需要 CPU，那么線程就不得不等待更長(zhǎng)時(shí)間。此時(shí)，因?yàn)樵S多的線程都在爭(zhēng)用 CPU，每個(gè)線程得到的運(yùn)行時(shí)間也就縮短了。
運(yùn)行態(tài)：這表示線程已經(jīng)被分配了一個(gè) CPU 核，正在執(zhí)行它的指令。與應(yīng)用相關(guān)的工作正在被完成。這是每個(gè)人都想要的狀態(tài)。
負(fù)荷類型
線程的工作有 2 種類型的負(fù)荷。第一種叫做 CPU密集型，第二種叫 IO密集型。
CPU密集：處理這種工作的線程從來(lái)不會(huì)主動(dòng)進(jìn)入阻塞態(tài)。它一直都需要使用 CPU。這種工作通常都是數(shù)學(xué)計(jì)算。比如計(jì)算圓周率的第 n 位的工作就屬于 CPU密集型的工作。
IO密集：這種工作會(huì)使得線程進(jìn)入阻塞態(tài)。常見(jiàn)于通過(guò)網(wǎng)絡(luò)請(qǐng)求資源，或者進(jìn)行了系統(tǒng)調(diào)用。一個(gè)需要訪問(wèn)數(shù)據(jù)庫(kù)的線程屬于 IO密集的?；コ怄i的使用也屬于這種。
上下文切換
Linux，Mac 或者 Windows 系統(tǒng)上都擁有搶占式調(diào)度器。這表明了很重要的幾點(diǎn)。
第一，線程何時(shí)被調(diào)度器選中，被分配 CPU 時(shí)間片是不可預(yù)測(cè)的。線程的優(yōu)先級(jí)和事件同時(shí)都會(huì)對(duì)調(diào)度結(jié)果有影響，這導(dǎo)致你不可能確定調(diào)度去什么時(shí)候能調(diào)度你的線程。
譯者注：你動(dòng)一下鼠標(biāo)，敲一下鍵盤(pán)，這些動(dòng)作都會(huì)觸發(fā) CPU 的中斷響應(yīng)，也就是事件。這都會(huì)對(duì)調(diào)度器的結(jié)果產(chǎn)生影響的，所以說(shuō)它是不可預(yù)測(cè)的。
第二，這表明了，你絕不能憑感覺(jué)來(lái)寫(xiě)代碼，因?yàn)槟愕慕?jīng)驗(yàn)不能保證總是應(yīng)驗(yàn)。人是很容易平感覺(jué)下定論的，同樣的事情反復(fù)出現(xiàn)了上千次，就認(rèn)為它是百分百的。如果你想要有百分百的確定性，必須在線程中使用互斥鎖。
在同一個(gè) CPU 核上交換線程的行為過(guò)程，稱為上下文切換。上下文切換發(fā)生時(shí)，調(diào)度器把一個(gè)線程從核上拿下來(lái)，把另一個(gè)就緒態(tài)的線程放到核上。從就緒隊(duì)列中選中的這個(gè)線程，就這樣被置成了運(yùn)行態(tài)。而被從核上拿來(lái)下的那個(gè)線程，被置為就緒態(tài)（如果它仍然可以被執(zhí)行），或者進(jìn)入阻塞態(tài)（如果它是因?yàn)閳?zhí)行了 IO 操作才被替換的）。
上下文切換是昂貴的，因?yàn)樵谝粋€(gè)核上交換線程需要時(shí)間片。上下文切換造成的計(jì)算損失受很多因素影響，一般是 50 到 100 納秒左右。
假設(shè)一個(gè) CPU 核平均每納秒可執(zhí)行 12 個(gè)機(jī)器指令，一次上下文切換要執(zhí)行 600 到 1200 條指令，那么本質(zhì)上，你的程序在上下文切換期間丟失了可以執(zhí)行大量指令的機(jī)會(huì)。
如果你有一個(gè) IO 密集的工作，那么上下文切換會(huì)有一定的優(yōu)勢(shì)。一旦一個(gè)線程進(jìn)入了阻塞態(tài)，另一個(gè)就緒態(tài)的線程就可以立馬執(zhí)行。這使得 CPU 一直都在工作。這是調(diào)度中最重要的目標(biāo)，就是如果有線程可執(zhí)行（處于就緒態(tài)），就不能讓 CPU 閑著。
如果你的程序是 CPU 密集的，那么上下文切換將會(huì)是性能的噩夢(mèng)。因?yàn)榫€程總是有指令要執(zhí)行，而上下文切換中斷了這個(gè)過(guò)程。這與 IO 密集型的工作形成了鮮明的對(duì)比。
少即是多
在早期，CPU 只有單核的。調(diào)度也就沒(méi)那么復(fù)雜。因?yàn)槟阒挥幸粋€(gè)單核 CPU。在任意一個(gè)時(shí)間點(diǎn)，只有一個(gè)線程可以運(yùn)行。有一種輪詢調(diào)度的方法，它嘗試對(duì)每個(gè)就緒態(tài)的線程都執(zhí)行一段時(shí)間。使用調(diào)度周期，除以線程總數(shù)，就是每個(gè)線程應(yīng)該執(zhí)行的時(shí)間。
比如，如果你定義你的調(diào)度周期是 10 毫秒，現(xiàn)在有 2 個(gè)線程，那么在一個(gè)調(diào)度周期內(nèi)，每個(gè)線程可以執(zhí)行 5 毫秒。如果你有 5 個(gè)線程，那么每個(gè)線程可以執(zhí)行 2 毫秒。但是，如果你有 1000 個(gè)線程呢？每個(gè)線程執(zhí)行 10 微妙是沒(méi)有意義的，因?yàn)槟愦蟛糠謺r(shí)間都花在了上下文切換上。
這時(shí)你就需要限制最短的執(zhí)行時(shí)間應(yīng)該是多少。在上面的那個(gè)場(chǎng)景中，如果最短的執(zhí)行時(shí)間是 2 毫秒，同時(shí)你有 100 個(gè)線程，那么調(diào)度周期就需要增加到 2000 毫秒（2秒）。如果你有 1000 個(gè)線程，調(diào)度周期就要變成 20 秒。這個(gè)簡(jiǎn)單的例子中，一個(gè)線程要等 20 秒才能執(zhí)行一次。
要知道這我們只是舉了最簡(jiǎn)單調(diào)度場(chǎng)景。實(shí)際上調(diào)度器在做調(diào)度策略時(shí)需要考慮很多事情。這是你應(yīng)該會(huì)想到一個(gè)常見(jiàn)并發(fā)手段，就是線程池的使用。讓線程的數(shù)量在控制之內(nèi)。
所以游戲規(guī)則就是『少即是多』，越少的就緒態(tài)線程意味著越少的調(diào)度工作，每個(gè)線程就會(huì)得到更多的時(shí)間。越多的就緒態(tài)線程意味著每個(gè)線程會(huì)得到越少的時(shí)間，也就意味著同一時(shí)間你能完成的工作越少（其他的 CPU 時(shí)間都被操作系統(tǒng)拿去做調(diào)度用了）。
尋找平衡
你需要在 CPU 核數(shù)和線程數(shù)量上尋找一個(gè)平衡，來(lái)使你的應(yīng)用能夠擁有最高的吞吐。當(dāng)需要維持這個(gè)平衡時(shí)，線程池是一個(gè)最好的解決方案。在下一篇文章中我會(huì)想你展示，在 Go 語(yǔ)言中根本不需要線程池。我認(rèn)為 Go 語(yǔ)言最優(yōu)秀的一點(diǎn)就是，它使得并發(fā)編程更簡(jiǎn)單了。
在寫(xiě) Go 之前，我使用 C++ 和 C# 在 NT 上開(kāi)發(fā)。在那個(gè)操作系統(tǒng)上，主要是使用 IOCP 線程池來(lái)完成并發(fā)編程的。作為一個(gè)工程師，你需要指定需要多少線程池，每個(gè)線程池的最大線程數(shù)是多少，來(lái)保證在固定核上達(dá)到最高的性能。
當(dāng)寫(xiě) web 服務(wù)的時(shí)候，需要和數(shù)據(jù)庫(kù)打交道，每核 3 個(gè)線程的配置，似乎總能在 NT 平臺(tái)上德奧最高的吞吐量。換句話說(shuō)，就是每核 3 個(gè)線程可以使上下文切換的代價(jià)最小，從而最大化線程的執(zhí)行時(shí)間。
如果配置每核只用 2 個(gè)線程，它會(huì)花費(fèi)更多時(shí)間把工作完成，因?yàn)?CPU 會(huì)經(jīng)常處在空閑狀態(tài)。如果我一個(gè)核創(chuàng)建 4 個(gè)線程，它也會(huì)花費(fèi)更長(zhǎng)時(shí)間，因?yàn)樯舷挛那袚Q的代價(jià)會(huì)升高。每核 3 個(gè)線程的平衡，總是能得到最好的結(jié)果，不知道什么原因，它就是個(gè)魔法數(shù)字。
那如果你的服務(wù)的即有 CPU 密集的工作也有 IO 密集的工作呢？這可能會(huì)產(chǎn)生不同類型的延遲。這種情況就不太可能找到一個(gè)魔法數(shù)字來(lái)適用于所有情況。當(dāng)使用線程池來(lái)調(diào)整服務(wù)的性能時(shí)，找到一個(gè)正確的一致配置是很復(fù)雜的。
Cache Line
訪問(wèn)主內(nèi)存中的數(shù)據(jù)是有很高延遲的。大約 100 ~ 300 個(gè)時(shí)鐘周期。所以 CPU 往往都會(huì)有一個(gè)本地 cache，使得數(shù)據(jù)距離需要它的線程所在的核更近。訪問(wèn) cache 中的數(shù)據(jù)是很快的，和訪問(wèn)寄存器差不多。今天，性能優(yōu)化中很重要的一部分就是怎么才能讓 CPU 更快的得到數(shù)據(jù)，來(lái)減少數(shù)據(jù)訪問(wèn)的延遲。寫(xiě)多線程應(yīng)用時(shí)面對(duì)狀態(tài)異變問(wèn)題時(shí)，需要考慮 cache 系統(tǒng)的機(jī)制。
cache line 是 cache 與主內(nèi)存交換數(shù)據(jù)的最小單位。一個(gè) cache line 是一塊 64 字節(jié)的內(nèi)存，用以在主內(nèi)存和 cache 系統(tǒng)之間交換數(shù)據(jù)。每個(gè)核都有一份它自己所需要數(shù)據(jù)的拷貝。這就是為什么在多線程應(yīng)用中，內(nèi)存異變是導(dǎo)致性能問(wèn)題的噩夢(mèng)。因?yàn)?CPU Core 上運(yùn)行的線程變了，不同的線程需要訪問(wèn)的數(shù)據(jù)不同，cache 里的數(shù)據(jù)也就失效了。
當(dāng)多線程并行時(shí)，如果他們?cè)L問(wèn)同樣的數(shù)據(jù)，或者相鄰很近的數(shù)據(jù)。他們將會(huì)訪問(wèn)同一個(gè) cache line 中的數(shù)據(jù)。運(yùn)行這些線程的任何一個(gè)核，都會(huì)在自己的 cache 上對(duì)數(shù)據(jù)做一份拷貝。也就是說(shuō)，每個(gè) CPU 核的 cache 中都有同樣的一份數(shù)據(jù)拷貝，這些拷貝對(duì)應(yīng)于內(nèi)存中的同一塊地址。
如果一個(gè)核上的線程，對(duì)拷貝數(shù)據(jù)進(jìn)行了修改，那么硬件會(huì)將其他所有核上的 cache line 拷貝都標(biāo)記為『臟』。當(dāng)其他核上的線程試圖訪問(wèn)或修改這個(gè)數(shù)據(jù)時(shí)，需要重新從主內(nèi)存上拷貝最新的數(shù)據(jù)到自己的 cache 中。
也許 2 核的 CPU，不會(huì)出大問(wèn)題，但如果是 32 核的 CPU 并行的運(yùn)行著 32 個(gè)線程呢？如果系統(tǒng)有 2 個(gè) CPU ，每個(gè) CPU 有 16 核呢？這更糟糕，因?yàn)樵黾恿?CPU 之間的的通信延遲。這個(gè)應(yīng)用將會(huì)出現(xiàn)內(nèi)存顛簸現(xiàn)象，性能會(huì)急劇下降，然而你可能都不知道為什么。
調(diào)度決策場(chǎng)景
假如現(xiàn)在要求你在以上給出信息的基礎(chǔ)上，設(shè)計(jì)一個(gè)系統(tǒng)調(diào)度器了。想象一下你需要解決的這種場(chǎng)景。記住，上面所描述的，只是做調(diào)度決策時(shí)，需要考慮的眾多情況之一。
現(xiàn)在假設(shè)機(jī)器只有一個(gè)單核CPU。你啟動(dòng)了應(yīng)用，線程被創(chuàng)建了并且在一個(gè) CPU 核上運(yùn)行。隨著線程開(kāi)始執(zhí)行它的指令，cache line 也開(kāi)始檢索數(shù)據(jù)，因?yàn)橹噶钚枰獢?shù)據(jù)?，F(xiàn)在線程要?jiǎng)?chuàng)建一個(gè)新的線程做一些并發(fā)處理?，F(xiàn)在的問(wèn)題是。
線程一旦創(chuàng)建并進(jìn)入了就緒態(tài)，調(diào)度器有以下幾種選擇：
- 直接進(jìn)行上下文切換，把主線程從 CPU 上拿掉？
這是對(duì)性能有益的，因?yàn)樾戮€程需要同樣的數(shù)據(jù)，而這些數(shù)據(jù)之前已經(jīng)存在與 cache 上了。但主線程就不得不把時(shí)間片分給子線程了。 - 讓新線程等待主線程執(zhí)行完它的所有時(shí)間片？
線程沒(méi)執(zhí)行，執(zhí)行時(shí)不必從主內(nèi)存中同步數(shù)據(jù)到 local cache 了。 - 讓線程等待其他可用核？
這就意味著被選中的核，要拷貝一份 cache line 中的數(shù)據(jù)，這會(huì)導(dǎo)致一定的延遲。但是新線程會(huì)立刻開(kāi)始執(zhí)行，主線程也能繼續(xù)完成自己的工作。
用哪種方式呢？這就是系統(tǒng)調(diào)度在做調(diào)度決策時(shí)需要考慮的一個(gè)有趣的問(wèn)題。答案是，如果有空閑的核，那就直接用。我們的目標(biāo)是，如果有工作要做，就決不讓 CPU 閑著。
結(jié)論
文章帶你了解了，當(dāng)編寫(xiě)多線程應(yīng)用時(shí)，關(guān)于線程和系統(tǒng)調(diào)度器需要考慮的一些事情。這些也是 Go 語(yǔ)言調(diào)度器需要考慮的事情。下一篇文章中，我會(huì)描述狗語(yǔ)言調(diào)度程序的實(shí)現(xiàn)，以及它與本篇所述內(nèi)容的關(guān)系。
