《英雄聯(lián)盟》夏季賽總決賽今日開打！JDG對陣LNG首發(fā)名單來了 Knight：準(zhǔn)備三連冠
8月5日消息，今日17:00，《英雄聯(lián)盟》2023LPL夏季賽總決賽將正式開打，由JDG對陣LNG。對兩支隊(duì)伍來說，這場比賽不僅要爭奪夏季賽冠軍，更要決定誰才是LPL賽區(qū)一
除非你一直生活在石頭下，否則你可能已經(jīng)聽說過 Golang。Golang 或 Go 是 Google 在21世紀(jì)初開發(fā)的一種編程語言。其最有趣的特性之一是它通過使用 goroutines 來支持并發(fā)，這些 goroutines 就像輕量級的線程。Goroutines 比實(shí)際的線程要便宜得多，甚至每秒可以調(diào)度數(shù)百萬的 goroutines。
但 Go 是如何實(shí)現(xiàn)這一令人難以置信的壯舉的呢？它是如何提供這種能力的？讓我們看看 Golang 調(diào)度器在背后是如何工作的。
在我們深入探討之前，有一些前提條件我必須談?wù)摗Ｈ绻阋呀?jīng)對它們非常熟悉，可以跳過它們。
系統(tǒng)調(diào)用是向內(nèi)核的接口。就像 web 服務(wù)為用戶暴露一個 REST API 接口一樣。
系統(tǒng)調(diào)用為 Linux 內(nèi)核提供了一個接口。
為了更多地了解這些系統(tǒng)調(diào)用，讓我們寫一點(diǎn)代碼！你可能首先問的問題是，選擇哪種語言？
答案有點(diǎn)復(fù)雜，但讓我們先了解如何在 C 語言中做，然后再花一些時間思考如何在其他語言中執(zhí)行相同的操作。
現(xiàn)在，讓我們嘗試 stat 系統(tǒng)調(diào)用。該調(diào)用非常簡單。它接受一個文件路徑并返回有關(guān)該文件的大量信息。現(xiàn)在，我們將打印返回的幾個值，即文件的所有者和文件的大小（以字節(jié)為單位）。
#include<stdio.h>#include<sys/stat.h>int main(){ //pointer to stat struct struct stat sfile; //stat system call stat("myfile", &sfile); //accessing some data returned from stat printf("uid = %o/nfileszie = %lld/n", sfile.st_uid, sfile.st_size); return 0;}輸出是相當(dāng)容易預(yù)測的，如下所示：
uid = 765filesize = 11所有的語言在內(nèi)部都調(diào)用相同的系統(tǒng)調(diào)用，因?yàn)槟阒荒苁褂眠@些系統(tǒng)調(diào)用與內(nèi)核進(jìn)行交互。例如，看一些 NodeJS 代碼這里，你可以看到它是如何聲明文件路徑的。他們圍繞這些系統(tǒng)調(diào)用做了很多工作，為開發(fā)者提供了更簡單的接口，但在底層，它們使用內(nèi)核提供的相同的系統(tǒng)調(diào)用。
我相信大多數(shù)人在生活中某個時候都聽說過線程，但你真的知道它們是什么嗎？它們是如何工作的？
我會盡快為你解釋。
你可能已經(jīng)讀到過有多個核心的處理器。這些核心中的每一個都像一個可以獨(dú)立工作的獨(dú)立處理單元。
線程是基于這一點(diǎn)的抽象，我們可以在我們的程序中“創(chuàng)建”線程，并在每個線程上運(yùn)行代碼，然后由內(nèi)核調(diào)度在單個核心上運(yùn)行。
所以，在任何時候，單個核心都在運(yùn)行一個執(zhí)行線程。
我們?nèi)绾蝿?chuàng)建線程？通過系統(tǒng)調(diào)用！
那為什么不直接使用核心呢？為什么我們不直接寫new Core()而是通過new Thread()創(chuàng)建線程？因?yàn)樵诓僮飨到y(tǒng)中可能有多個程序正在運(yùn)行，每個程序可能都想并行執(zhí)行代碼。由于核心數(shù)量有限，每個程序都必須知道有多少可用的核心，如果一個程序占用了所有的核心，它基本上可以完全阻塞操作系統(tǒng)。操作系統(tǒng)可能還需要執(zhí)行比任何單個程序更重要或優(yōu)先級更高的工作，所以需要一層抽象。
正如我上面解釋的，goroutines類似于輕量級的線程，它們可以并發(fā)運(yùn)行并且可以在單獨(dú)的線程中運(yùn)行。
在繼續(xù)之前，沒有真正需要了解Golang，但我認(rèn)為至少在繼續(xù)之前，看一下一個非常簡單的goroutine的實(shí)現(xiàn)是有意義的。
package mainimport ( "fmt" "sync" "time")func printForever(s string) { // This is an infinite loop that prints the string s forever for { fmt.Println(s) time.Sleep(time.Millisecond) }}func main() { var wg sync.WaitGroup // A waitgroup is just a way to wait for goroutines to finish wg.Add(2) // Any function executed with the "go" keyword will run as a goroutine go printForever("HELLO") go printForever("WORLD") // This line of code blocks until both goroutines are finished wg.Wait()}輸出，你可能猜到了，是連續(xù)打印的單詞“HELLO”和“WORLD”。
既然用go關(guān)鍵字標(biāo)記的兩個函數(shù)調(diào)用都是并行運(yùn)行的。
你的直覺可能會讓你認(rèn)為這些 goroutines 只是并行運(yùn)行在 CPU 上的單獨(dú)線程，并由操作系統(tǒng)管理，但這不是真的。盡管現(xiàn)在每次調(diào)用都可以是單個線程，但我們很快會發(fā)現(xiàn)這并不實(shí)際。
讓我們討論 Go 調(diào)度器，就好像我們正在創(chuàng)建自己的調(diào)度器一樣。我知道這個任務(wù)可能看起來很艱巨，但本質(zhì)上，我們有一些工作單元，比如說一些函數(shù)，我們需要將它們調(diào)度到有限的線程上。
所以，為了更正式地描述這一點(diǎn)，函數(shù)是單一的工作單位。它是執(zhí)行某些處理的代碼行的序列。現(xiàn)在，讓我們不要用像 async/await 這樣的東西來混淆自己，我們說一個函數(shù)只包含非常基本的代碼。也許像這樣，
int add(int a, int b) { int sum = a + b; cout << "Calculated the sum: " << sum; return sum;}它應(yīng)該在線程上運(yùn)行，這些線程在內(nèi)部在處理器的核心上進(jìn)行多路復(fù)用。核心是有限的，但線程可以是無限的。管理這些線程并在有限的CPU核心上運(yùn)行它們是操作系統(tǒng)調(diào)度器的工作，所以我們不需要關(guān)心核心。我們可以簡單地將線程視為實(shí)現(xiàn)并行性的單位。
我們確實(shí)有一套系統(tǒng)調(diào)用，我們可以運(yùn)行它們在操作系統(tǒng)上創(chuàng)建線程。系統(tǒng)調(diào)用往往是昂貴的，所以我們需要確保我們不經(jīng)常創(chuàng)建/刪除線程。
我們調(diào)度器的工作很簡單，將這些函數(shù)或 goroutines 運(yùn)行在線程上。我們的調(diào)度器可以在任何時候被賦予新的函數(shù)/goroutines，它將必須在線程上調(diào)度它們。
在下一部分，讓我們繼續(xù)明確所有的需求。
讓我們列出我們調(diào)度器中想要的一些優(yōu)先事項(xiàng)，這與 Golang 所設(shè)置的優(yōu)先級相似，這些將影響我們在設(shè)計調(diào)度器時所做的設(shè)計決策。
(1) 輕量級 goroutines
我們希望我們的 goroutines 非常輕量級。我們希望能夠處理每秒調(diào)度的數(shù)百萬 goroutines。這意味著我們想要做的所有事情，如創(chuàng)建一個 goroutine 或在線程上切換一個 goroutine 必須非常快。
(2) 處理系統(tǒng)調(diào)用和 I/O
系統(tǒng)調(diào)用可能難以處理，但我們?nèi)匀幌Ｍ麨槲覀兊暮瘮?shù)提供能夠進(jìn)行系統(tǒng)調(diào)用和執(zhí)行 I/O 操作的能力。這意味著某個函數(shù)可以打開并讀取一個文件，例如。系統(tǒng)調(diào)用有點(diǎn)棘手，因?yàn)橐坏╅_始了系統(tǒng)調(diào)用，我們就看不到它何時結(jié)束或需要多長時間。在某種意義上，我們不能再控制或透明地看到函數(shù)了。當(dāng)我們開始設(shè)計我們的調(diào)度器時，這個問題會出現(xiàn)。
(3) 并行
我們當(dāng)然希望同時運(yùn)行多個 goroutines。記住，我們不需要擔(dān)心核心，我們只需考慮如何將這些函數(shù)多路復(fù)用到線程上。
(4) 公平
我們希望一個系統(tǒng)確保運(yùn)行在其中的 goroutines 是公平的。這意味著一個 goroutine 不應(yīng)該阻塞其他 goroutines 很長時間。公平可能有點(diǎn)難以客觀定義，但其思路是每個 goroutine 都應(yīng)該在線程上獲得公平的執(zhí)行時間。這似乎是合乎邏輯的，因?yàn)闆]有定義某種優(yōu)先級系統(tǒng)的要求，沒有理由給予任何這些函數(shù)優(yōu)先權(quán)。
(5) 避免過度訂閱
重要的是要控制任何程序?qū)⑹褂玫木€程數(shù)。當(dāng)確保我們不會無謂地獲取操作系統(tǒng)級別的線程并阻塞機(jī)器上運(yùn)行的其他進(jìn)程時，這可能會很有用。因此，我們應(yīng)該嘗試限制我們使用的線程數(shù)量。如果我們超出這個限制，我們將過度訂閱，為了對系統(tǒng)上運(yùn)行的其他進(jìn)程公平，我們會認(rèn)為這是一件很糟糕的事情，并盡量避免它。
一個非常簡單的系統(tǒng)是我們?yōu)槊總€ goroutine 創(chuàng)建一個線程。這意味著我們在 goroutines 和線程之間有一個1:1的映射。
因此，每當(dāng)用戶嘗試創(chuàng)建一個 goroutine，我們的調(diào)度器創(chuàng)建一個線程，該線程開始執(zhí)行 goroutine。
這導(dǎo)致了很多問題：
這里的邏輯步驟是使用 M:N 映射。這意味著M個 goroutines 需要映射到N個線程。因此，用戶可以創(chuàng)建他們想要的任意數(shù)量的 goroutines，但我們對一組有限的線程有控制權(quán)，并且我們將他們的 goroutines 調(diào)度到一個線程上一段時間。我們也可以暫停/恢復(fù)線程上運(yùn)行的 goroutines。
這樣做有點(diǎn)復(fù)雜，因?yàn)槲覀儸F(xiàn)在需要了解如何將一個 goroutine/function 映射到一個線程上。我們可能只在每個線程上運(yùn)行一個函數(shù)很短的時間，所以我們需要做一些繁重的工作以確保我們得到正確的邏輯。
一個好的比喻可能是餐館。餐廳通常會有不同數(shù)量的侍者和廚師。侍者的數(shù)量取決于餐廳的客人或桌子的數(shù)量，而廚師的數(shù)量取決于訂單的數(shù)量和烹飪所需的時間。
在這個比喻中，我們可以把函數(shù)想象成侍者，線程想象成廚師。
為每個侍者提供一個廚師并不真正有意義，因?yàn)橐苍S一個廚師可以很快地烹飪食物，也許餐廳在高峰時間有很多客人，但在慢時，也許需要更少的侍者。所以為了正確管理這家餐廳，你需要某種系統(tǒng)來將M個侍者分配給N個廚師。這正是我們必須在調(diào)度器中做的事情！
為了進(jìn)一步延續(xù)這個比喻，也許一個簡單的系統(tǒng)是有一個訂單隊(duì)列，每個訂單都有一個數(shù)字，廚師們一個接一個地選擇數(shù)字。這也將是我們調(diào)度器的起點(diǎn)！
讓我們首先設(shè)計一個基本的系統(tǒng)，并對其進(jìn)行迭代。
我們設(shè)置一個全局的先入先出的運(yùn)行隊(duì)列，其中包含需要運(yùn)行的一組 goroutines。每個線程從這個隊(duì)列中選擇一個 goroutine 并執(zhí)行它。當(dāng)它執(zhí)行完一個 goroutine 后，它再次選擇一個新的 goroutine 并繼續(xù)反復(fù)進(jìn)行相同的過程。
為了更好地理解，讓我們編寫一些基本的偽代碼，描述每個線程將執(zhí)行的內(nèi)容。
void runThread() { while (true) { // Check if there is an empty goroutine bool isEmpty = globalRunQueue.empty(); // If not empty if (!isEmpty) { goroutine g = globalRunQueue.getNextGoroutine(); g(); } }}重要的是要記住，每一個線程都在并行地運(yùn)行相同的代碼。
這個系統(tǒng)中的一個問題是，每個線程都在訪問相同的共享變量，即globalRunQueue。所以，一個線程，比如說 ThreadA，檢查隊(duì)列是否為空，但在它能夠從隊(duì)列中獲取 goroutine 之前，另一個線程訪問了隊(duì)列并選擇了 goroutine。
我們需要一種方法來確保任何時候只有一個線程可以訪問運(yùn)行隊(duì)列。
解決這個問題的一種方法是引入一個互斥鎖。互斥鎖只是一個鎖，每個線程在訪問隊(duì)列之前都必須獲取它。只有線程擁有互斥鎖時，它才能執(zhí)行操作。完成后，它可以釋放互斥鎖，供其他線程獲取。
把它想象成一個鎖，確保只有一個線程可以訪問全局運(yùn)行隊(duì)列。
繼續(xù)我們的偽代碼：
void runThread() { while (true) { // First acquire the mutex // This call would block execution until the mutex is free mutex m = globalRunQueue.getMutex(); // Check if there is an empty goroutine bool isEmpty = globalRunQueue.empty(); // If not empty if (!isEmpty) { goroutine g = globalRunQueue.getNextGoroutine(); g(); } // Release the mutex m.release(); }}現(xiàn)在，下一個問題是每個線程都必須等待獲取一個互斥鎖來對運(yùn)行隊(duì)列執(zhí)行任何操作。在未來，我們也可能增加暫停 goroutines、恢復(fù) goroutines 等功能。如果所有操作都需要互斥鎖，那么它可能成為我們系統(tǒng)的瓶頸。
為了解決單一互斥鎖的問題，我們?yōu)槊總€線程提供了它自己的本地運(yùn)行隊(duì)列。
每個 goroutine 在創(chuàng)建時開始在全局運(yùn)行隊(duì)列中執(zhí)行，但在某個時候由不同的系統(tǒng)分配給一個本地運(yùn)行隊(duì)列。每個線程大多與它自己的本地運(yùn)行隊(duì)列進(jìn)行交互，選擇一個 goroutine 并執(zhí)行它。這樣，我們把大部分工作轉(zhuǎn)移到了每個線程的本地運(yùn)行隊(duì)列。由于本地運(yùn)行隊(duì)列只被一個線程訪問，所以它甚至不需要互斥鎖。
我們現(xiàn)在不再需要互斥鎖，我們的代碼變得更簡單了。
void runThread() { while (true) { // Check if there is an empty goroutine bool isEmpty = this.localRunQueue.empty(); // If not empty if (!isEmpty) { goroutine g = this.localRunQueue.getNextGoroutine(); g(); } }}我們需要明白的是，我們?nèi)匀挥幸粋€帶有互斥鎖的全局運(yùn)行隊(duì)列，但我們可以大大減少對全局運(yùn)行隊(duì)列的調(diào)用，因?yàn)橐粋€單獨(dú)的線程主要是從其自己的本地運(yùn)行隊(duì)列中取出 goroutines。它可能偶爾從全局運(yùn)行隊(duì)列中獲取，比如當(dāng)其自己的本地運(yùn)行隊(duì)列為空時，但那是一個罕見的情況（如果你感興趣，這里是找到一個正在運(yùn)行的 goroutine 執(zhí)行的代碼，你可以清楚地看到，如果它在本地運(yùn)行隊(duì)列中找不到一個 goroutine，它將會輪詢?nèi)诌\(yùn)行隊(duì)列）。
我們可以為我們的系統(tǒng)添加的另一個有趣的特性是“工作竊取”的概念。每當(dāng)線程的本地運(yùn)行隊(duì)列為空時，它可以嘗試從其他本地運(yùn)行隊(duì)列中竊取工作。這也有助于平衡 goroutines 的負(fù)載。
void runThread() { while (true) { // Check if there is an empty goroutine bool isEmpty = this.localRunQueue.empty(); // If not empty if (!isEmpty) { goroutine g = this.localRunQueue.getNextGoroutine(); g(); } else { // Steal work from other local run queues for (int i = 0; i < localRunQueueCount; i += 1) { // Check if there is an empty goroutine in this local run queue bool isEmpty = localRunQueues[i].empty(); // If not, steal the next goroutine, and run it goroutine g = localRunQueues[i].getNextGoroutine(); g(); } } }}在這個系統(tǒng)中，即使一個線程執(zhí)行一個 goroutine 需要很長時間，它的本地運(yùn)行隊(duì)列中的其他 goroutines 也不會被餓死。最終，另一個線程會“竊取”這些 goroutines 并執(zhí)行它們。
如我之前所提到的，系統(tǒng)調(diào)用可能有點(diǎn)難以處理，因?yàn)樗鼈兛赡苄枰喈?dāng)長的時間。當(dāng)一個 goroutine 執(zhí)行一個系統(tǒng)調(diào)用，比如從一個文件中讀取數(shù)據(jù)，它可能需要很長時間才能返回。我們甚至不知道它是否會返回，或者操作系統(tǒng)在幕后到底在做什么。
在操作系統(tǒng)返回之前，該線程不會被賦予任何新的工作，基本上是處于睡眠狀態(tài)。我們可能會遇到一個情況，即分配給我們程序的所有線程都只是等待系統(tǒng)調(diào)用完成。
我們?nèi)绾谓鉀Q這個問題呢？在進(jìn)行系統(tǒng)調(diào)用之前，我們創(chuàng)建一個新的線程。由于我們是在編寫語言，以及編寫打開文件的函數(shù)，我們可以在打開文件之前簡單地添加一行來創(chuàng)建一個新線程。新線程創(chuàng)建后，當(dāng)前線程進(jìn)入睡眠狀態(tài)，直到系統(tǒng)調(diào)用完成。
從技術(shù)上講，這并不是過度訂閱，因?yàn)楫?dāng)前線程正在休眠，因此不會占用操作系統(tǒng)的資源。
但這意味著我們可能有很多我們不使用的休眠線程。
再次說，這并不是過度訂閱，但它為我們帶來了一個不同的問題。由于我們?yōu)槊總€線程提供資源（本地運(yùn)行隊(duì)列），如果我們有很多線程，我們將為每個線程分配內(nèi)存。
此外，我們尚未深入探討的系統(tǒng)的其他部分也可能會出現(xiàn)一些問題，例如將 goroutines 分配給本地運(yùn)行隊(duì)列的系統(tǒng)可能會將一個 goroutine 分配給一個當(dāng)前被系統(tǒng)調(diào)用阻塞的線程。
此外，工作竊取也可能變得有點(diǎn)繁瑣。如果我們有很多線程，工作竊取將需要檢查很多本地運(yùn)行隊(duì)列。
為了解決這個問題，我們增加了另一層抽象，稱為處理器。
每個線程都會獲取一個處理器，該處理器包含執(zhí)行 Go 代碼所需的變量。所以我們將本地運(yùn)行隊(duì)列以及我們可能擁有的任何其他變量（如緩存等）移動到處理器中。
當(dāng)一個線程在系統(tǒng)調(diào)用上被阻塞時，它將釋放處理器，另一個線程將獲取它并從中斷的地方繼續(xù)。
這并不顯著地改變了我們的偽代碼，除了我們現(xiàn)在在使用本地運(yùn)行隊(duì)列時使用了一個處理器。
void runThread() { while (true) { // Check if there is an empty goroutine bool isEmpty = this.processor.localRunQueue.empty(); // If not empty if (!isEmpty) { goroutine g = this.processor.localRunQueue.getNextGoroutine(); g(); } else { // Steal work from other local run queues for (int i = 0; i < localRunQueueCount; i += 1) { // Check if there is an empty goroutine in this local run queue bool isEmpty = localRunQueues[i].empty(); // If not, steal the next goroutine, and run it goroutine g = localRunQueues[i].getNextGoroutine(); g(); } } }}為了確保沒有單一的 goroutine 長時間占用一個線程，我們可以添加一個非常簡單的機(jī)制，如果一個 goroutine 的執(zhí)行時間超過了一定的時間段，比如說10ms，那么它會被預(yù)先暫停。然后我們將它加到運(yùn)行隊(duì)列的尾部。
有一種可能性是，goroutines 不斷地在全局運(yùn)行隊(duì)列中被填充，而每個處理器都繼續(xù)在其自己的本地運(yùn)行隊(duì)列上工作。這可能導(dǎo)致全局運(yùn)行隊(duì)列中的 goroutines 基本上餓死。
這個問題的簡單解決方案是什么呢？讓我們偶爾檢查全局運(yùn)行隊(duì)列，而不是本地運(yùn)行隊(duì)列。
其實(shí)在代碼中理解這一點(diǎn)非常容易。
void runThread() { // A simple variable to keep track of the number of goroutines // we are running int schedTick = 0; while (true) { // Occasionally poll the global run queue instead of the local run queue // 61 is the actual number they use to decide to poll the global run queue! // https://github.com/golang/go/blob/master/src/runtime/proc.go#L2753 if (schedTick % 61 == 0) { // Polling the global run queue goroutine g = pollGlobalRunQueue() if (g != nil) { g(); } } // Check if there is an empty goroutine bool isEmpty = this.processor.localRunQueue.empty(); // If not empty if (!isEmpty) { goroutine g = this.processor.localRunQueue.getNextGoroutine(); g(); // Increment the schedTick variable schedTick ++; } else { // Steal work from other local run queues for (int i = 0; i < localRunQueueCount; i += 1) { // Check if there is an empty goroutine in this local run queue bool isEmpty = localRunQueues[i].empty(); // If not, steal the next goroutine, and run it goroutine g = localRunQueues[i].getNextGoroutine(); g(); } } }}這是我嘗試簡要描述 Golang 并發(fā)是如何工作的。我可能做了一些簡化，但這大致是并發(fā)模型的方向。歡迎查看 Go 源代碼中的 findRunnable 函數(shù)的實(shí)際代碼這里，現(xiàn)在你應(yīng)該能夠理解它的大部分內(nèi)容。
我們確實(shí)跳過了一些概念，比如網(wǎng)絡(luò)輪詢器，但這篇文章已經(jīng)變得非常長，我不想在這樣一個預(yù)計10-15分鐘的閱讀中塞入太多的信息。
我選擇這個主題的原因是，我一直認(rèn)為并發(fā)和并行這樣的概念更偏理論而不是實(shí)際，我發(fā)現(xiàn)自己難以理解它內(nèi)部是如何工作的。在我看來，重要的是要認(rèn)識到，歸根結(jié)底，這些看似非常困難且像魔法一樣的底層概念只不過是代碼片段，理解它們以及導(dǎo)致它們的決策不應(yīng)該比理解任何其他代碼更難。
本文鏈接：http://www.tebozhan.com/showinfo-26-14812-0.html理解 Go 調(diào)度器并探索其工作原理
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號