歡迎光臨
每天分享高質量文章

Golang – 調度剖析【第一部分】

簡介

首先,Golang 調度器的設計和實現讓我們的 Go 程式在多執行緒執行時效率更高,性能更好。這要歸功於 Go 調度器與操作系統(OS)調度器的協同合作。不過在本篇文章中,多執行緒 Go 程式在設計和實現上是否與調度器的工作原理完全契合不是重點。重要的是對系統調度器和 Go 調度器,它們是如何正確地設計多執行緒程式,有一個全面且深入的理解。

本章多數內容將側重於討論調度器的高級機制和語意。我將展示一些細節,讓你可以通過圖像來理解它們是如何工作的,可以讓你在寫代碼時做出更好的決策。因為原理和語意是必備的基礎知識中的關鍵。

系統調度

操作系統調度器是一個複雜的程式。它們要考慮到運行時的硬體設計和設置,其中包括但不限於多處理器核心、CPU 快取和 NUMA,只有考慮全面,調度器才能做到盡可能地高效。值得高興的是,你不需要深入研究這些問題,就可以大致上瞭解操作系統調度器是如何工作的。

你的代碼會被翻譯成一系列機器指令,然後依次執行。為了實現這一點,操作系統使用執行緒(Thread)的概念。執行緒負責順序執行分配給它的指令。一直執行到沒有指令為止。這就是我將執行緒稱為“執行流”的原因。

你運行的每個程式都會創建一個行程,每個行程都有一個初始執行緒。而後執行緒可以創建更多的執行緒。每個執行緒互相獨立地運行著,調度是在執行緒級別而不是在行程級別做出的。執行緒可以併發運行(每個執行緒在單個內核上輪流運行),也可以並行運行(每個執行緒在不同的內核上同時運行)。執行緒還維護自己的狀態,以便安全、本地和獨立地執行它們的指令。

如果有執行緒可以執行,操作系統調度器就會調度它到空閑的 CPU 核心上去執行,保證 CPU 不閑著。它還必須模擬一個假象,即所有可以執行的執行緒都在同時地執行著。在這個過程中,調度器還會根據優先級不同選擇執行緒執行的先後順序,高優先級的先執行,低優先級的後執行。當然,低優先級的執行緒也不會被餓著。調度器還需要通過快速而明智的決策盡可能減少調度延遲。

為了實現這一標的,演算法在其中做了很多工作,且幸運的是,這個領域已經積累了幾十年經驗。為了我們能更好地理解這一切,接下來我們來看幾個重要的概念。

執行指令

程式計數器(PC),有時稱為指令指標(IP),執行緒利用它來跟蹤下一個要執行的指令。在大多數處理器中,PC指向的是下一條指令,而不是當前指令。

如果你之前看過 Go 程式的堆棧跟蹤,那麼你可能已經註意到了每行末尾的這些十六進制數字。如下:

goroutine 1 [running]:
   main.example(0xc000042748, 0x2, 0x4, 0x106abae, 0x5, 0xa)
       stack_trace/example1/example1.go:13 +0x39                    main.main()
       stack_trace/example1/example1.go:8 +0x72                  

這些數字表示 PC 值與相應函式頂部的偏移量。+0x39PC 偏移量表示在程式沒中斷的情況下,執行緒即將執行的下一條指令。如果控制權回到主函式中,則主函式中的下一條指令是0+x72PC 偏移量。更重要的是,指標前面的指令是當前正在執行的指令。

下麵是對應的代碼
https://github.com/ardanlabs/gotraining/blob/master/topics/go/profiling/stack_trace/example1/example1.go07 func main() {08     example(make([]string, 2, 4), "hello", 10)09 }12 func example(slice []string, str string, i int) {13    panic("Want stack trace")14 }

十六進制數+0x39表示示例函式內的一條指令的 PC 偏移量,該指令位於函式的起始指令後面第57條(10進制)。接下來,我們用 objdump 來看一下彙編指令。找到第57條指令,註意,runtime.gopanic那一行。

$ 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              

記住: PC 是下一個指令,而不是當前指令。上面是基於 amd64 的彙編指令的一個很好的例子,該 Go 程式的執行緒負責順序執行。

執行緒狀態

另一個重要的概念是執行緒狀態,它描述了調度器在執行緒中的角色。
執行緒可以處於三種狀態之一: 等待中(Waiting)待執行(Runnable)執行中(Executing)

等待中(Waiting):這意味著執行緒停止並等待某件事情以繼續。這可能是因為等待硬體(磁盤、網絡)、操作系統(系統呼叫)或同步呼叫(原子、互斥)等原因。這些型別的延遲是性能下降的根本原因。

待執行(Runnable):這意味著執行緒需要內核上的時間,以便執行它指定的機器指令。如果有很多執行緒都需要時間,那麼執行緒需要等待更長的時間才能獲得執行。此外,由於更多的執行緒在競爭,每個執行緒獲得的單個執行時間都會縮短。這種型別的調度延遲也可能導致性能下降。

執行中(Executing):這意味著執行緒已經被放置在一個核心上,並且正在執行它的機器指令。與應用程式相關的工作正在完成。這是每個人都想要的。

工作型別

執行緒可以做兩種型別的工作。第一個稱為 CPU-Bound,第二個稱為 IO-Bound

CPU-Bound:這種工作型別永遠也不會讓執行緒處在等待狀態,因為這是一項不斷進行計算的工作。比如計算 π 的第 n 位,就是一個 CPU-Bound 執行緒。

IO-Bound:這是導致執行緒進入等待狀態的工作型別。比如通過網絡請求對資源的訪問或對操作系統進行系統呼叫。

背景關係切換

諸如 Linux、Mac、 Windows 是一個具有搶占式調度器的操作系統。這意味著一些重要的事情。首先,這意味著調度程式在什麼時候選擇運行哪些執行緒是不可預測的。執行緒優先級和事件混在一起(比如在網絡上接收資料)使得無法確定調度程式將選擇做什麼以及什麼時候做。

其次,這意味著你永遠不能基於一些你曾經歷過但不能保證每次都發生的行為來編寫代碼。如果應用程式中需要確定性,則必須控制執行緒的同步和協調管理。

在核心上交換執行緒的物理行為稱為背景關係切換。當調度器將一個正在執行的執行緒從內核中取出並將其更改狀態為一個可運行的執行緒時,就會發生背景關係切換。

背景關係切換的代價是高昂的,因為在核心上交換執行緒會花費很多時間。背景關係切換的延遲取決於不同的因素,大概在在 50 到 100 納秒之間。考慮到硬體應該能夠合理地(平均)在每個核心上每納秒執行 12 條指令,那麼一次背景關係切換可能會花費 600 到 1200 條指令的延遲時間。實際上,背景關係切換占用了大量程式執行指令的時間。

如果你在執行一個 IO-Bound 程式,那麼背景關係切換將是一個優勢。一旦一個執行緒更改到等待狀態,另一個處於可運行狀態的執行緒就會取而代之。這使得 CPU 總是在工作。這是調度器最重要的之一,最好不要讓 CPU 閑下來。

而如果你在執行一個 CPU-Bound 程式,那麼背景關係切換將成為性能瓶頸的噩夢。由於執行緒總是有工作要做,所以背景關係切換阻礙了工作的進展。這種情況與 IO-Bound 型別的工作形成了鮮明對比。

少即是多

在早期處理器只有一個核心的時代,調度相對簡單。因為只有一個核心,所以物理上在任何時候都只有一個執行緒可以執行。其思想是定義一個調度程式周期,並嘗試在這段時間內執行所有可運行執行緒。演算法很簡單:用調度周期除以需要執行的執行緒數。

例如,如果你將調度器周期定義為 10ms(毫秒),並且你有 2 個執行緒,那麼每個執行緒將分別獲得 5ms。如果你有 5 個執行緒,每個執行緒得到 2ms。但是,如果有 1000 個執行緒,會發生什麼情況呢?給每個執行緒一個時間片 10μs (微秒)?錯了,這麼乾是愚蠢的,因為你會花費大量的時間在背景關係切換上,而真正的工作卻做不成。

你需要限制時間片的長度。在最後一個場景中,如果最小時間片是 2ms,並且有 1000 個執行緒,那麼調度器周期需要增加到 2s(秒)。如果有 10000 個執行緒,那麼調度器周期就是 20s。在這個簡單的例子中,如果每個執行緒使用它的全時間片,那麼所有執行緒運行一次需要花費 20s。

要知道,這是一個非常簡單的場景。在真正進行調度決策時,調度程式需要考慮和處理比這更多的事情。你可以控制應用程式中使用的執行緒數量。當有更多的執行緒要考慮,並且發生 IO-Bound 工作時,就會出現一些混亂和不確定的行為。任務需要更長的時間來調度和執行。

這就是為什麼游戲規則是“少即是多”。處於可運行狀態的執行緒越少,意味著調度開銷越少,每個執行緒執行的時間越長。完成的工作會越多。如此,效率就越高。

尋找一個平衡

你需要在 CPU 核心數和為應用程式獲得最佳吞吐量所需的執行緒數之間找到平衡。當涉及到管理這種平衡時,執行緒池是一個很好的解決方案。將在第二部分中為你解析,Go 並不是這樣做的。

CPU 快取

從主存訪問資料有很高的延遲成本(大約 100 到 300 個時鐘周期),因此處理器核心使用本地高速快取來將資料儲存在需要的硬體執行緒附近。從快取訪問資料的成本要低得多(大約 3 到 40 個時鐘周期),這取決於所訪問的快取。如今,提高性能的一個方面是關於如何有效地將資料放入處理器以減少這些資料訪問延遲。編寫多執行緒應用程式也需要考慮 CPU 快取的機制。

資料通過cache lines在處理器和主儲存器之間交換。cache line是在主存和高速快取系統之間交換的 64 位元組記憶體塊。每個內核都有自己所需的cache line的副本,這意味著硬體使用值語意。這就是為什麼多執行緒應用程式中記憶體的變化會造成性能噩夢。

當並行運行的多個執行緒正在訪問相同的資料值,甚至是相鄰的資料值時,它們將訪問同一cache line上的資料。在任何核心上運行的任何執行緒都將獲得同一cache line的副本。

如果某個核心上的一個執行緒對其cache line的副本進行了更改,那麼同一cache line的所有其他副本都必須標記為dirty的。當執行緒嘗試對dirty cache line進行讀寫訪問時,需要向主存訪問(大約 100 到 300 個時鐘周期)來獲得cache line的新副本。

也許在一個 2 核處理器上這不是什麼大問題,但是如果一個 32 核處理器在同一cache line上同時運行 32 個執行緒來訪問和改變資料,那會發生什麼?如果一個系統有兩個物理處理器,每個處理器有16個核心,那又該怎麼辦呢?這將變得更糟,因為處理器到處理器的通信延遲更大。應用程式將會在主存中周轉,性能將會大幅下降。

這被稱為快取一致性問題,還引入了錯誤共享等問題。在編寫可能會改變共享狀態的多執行緒應用程式時,必須考慮快取系統。

調度決策場景

假設我要求你基於我給你的信息編寫操作系統調度器。考慮一下這個你必須考慮的情況。記住,這是調度程式在做出調度決策時必須考慮的許多有趣的事情之一。

啟動應用程式,創建主執行緒併在核心1上執行。當執行緒開始執行其指令時,由於需要資料,正在檢索cache line。現在,執行緒決定為一些併發處理創建一個新執行緒。下麵是問題:

  1. 進行背景關係切換,切出核心1的主執行緒,切入新執行緒?這樣做有助於提高性能,因為這個新執行緒需要的相同部分的資料很可能已經被快取。但主執行緒沒有得到它的全部時間片。

  2. 新執行緒等待核心1在主執行緒完成之前變為可用?執行緒沒有運行,但一旦啟動,獲取資料的延遲將被消除。

  3. 執行緒等待下一個可用的核心?這意味著所選核心的cache line將被掃清、檢索和複製,從而導致延遲。然而,執行緒將啟動得更快,主執行緒可以完成它的時間片。

有意思嗎?這些是系統調度器在做出調度決策時需要考慮的有趣問題。幸運的是,不是我做的。我能告訴你的就是,如果有一個空閑核心,它將被使用。你希望執行緒在可以運行時運行。

結論

本文的第一部分深入介紹了在編寫多執行緒應用程式時需要考慮的關於執行緒和系統調度器的問題。這些是 Go 調度器也要考慮的事情。在下一篇文章中,我將解析 Go 調度器的語意以及它們如何與這些信息相關聯,並通過一些示例程式來展示。

赞(0)

分享創造快樂