作者 |?Draveness

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：空間域名、網(wǎng)絡(luò)空間、營銷軟件、網(wǎng)站建設(shè)、龍華網(wǎng)站維護(hù)、網(wǎng)站推廣。

導(dǎo)讀：本文作者寫這篇文章前前后后大概 2 個月的時間，全文大概 2w 字，建議收藏后閱讀或者通過電腦閱讀。

調(diào)度是一個非常廣泛的概念，很多領(lǐng)域都會使用調(diào)度這個術(shù)語，在計算機(jī)科學(xué)中，調(diào)度就是一種將任務(wù)（Work）分配給資源的方法。任務(wù)可能是虛擬的計算任務(wù)，例如線程、進(jìn)程或者數(shù)據(jù)流，這些任務(wù)會被調(diào)度到硬件資源上執(zhí)行，例如：處理器 CPU 等設(shè)備。

圖 1?- 調(diào)度系統(tǒng)設(shè)計精要

本文會介紹調(diào)度系統(tǒng)的常見場景以及設(shè)計過程中的一些關(guān)鍵問題，調(diào)度器的設(shè)計最終都會歸結(jié)到一個問題上 — 如何對資源高效的分配和調(diào)度以達(dá)到我們的目的，可能包括對資源的合理利用、最小化成本、快速匹配供給和需求。

圖 2?- 文章脈絡(luò)和內(nèi)容

除了介紹調(diào)度系統(tǒng)設(shè)計時會遇到的常見問題之外，本文還會深入分析幾種常見的調(diào)度器的設(shè)計、演進(jìn)與實(shí)現(xiàn)原理，包括操作系統(tǒng)的進(jìn)程調(diào)度器，Go 語言的運(yùn)行時調(diào)度器以及 Kubernetes 的工作負(fù)載調(diào)度器，幫助我們理解調(diào)度器設(shè)計的核心原理。

設(shè)計原理

調(diào)度系統(tǒng)其實(shí)就是調(diào)度器（Scheduler），我們在很多系統(tǒng)中都能見到調(diào)度器的身影，就像我們在上面說的，不止操作系統(tǒng)中存在調(diào)度器，編程語言、容器編排以及很多業(yè)務(wù)系統(tǒng)中都會存在調(diào)度系統(tǒng)或者調(diào)度模塊。

這些調(diào)度模塊的核心作用就是對有限的資源進(jìn)行分配，以實(shí)現(xiàn)最大化資源的利用率或者降低系統(tǒng)的尾延遲，調(diào)度系統(tǒng)面對的就是資源的需求和供給不平衡的問題。

圖 3 - 調(diào)度器的任務(wù)和資源

我們在這一節(jié)中將從多個方面介紹調(diào)度系統(tǒng)設(shè)計時需要重點(diǎn)考慮的問題，其中包括調(diào)度系統(tǒng)的需求調(diào)研、調(diào)度原理以及架構(gòu)設(shè)計。

1. 需求調(diào)研

在著手構(gòu)建調(diào)度系統(tǒng)之前，首要的工作就是進(jìn)行詳細(xì)的需求調(diào)研和分析，在這個過程中需要完成以下兩件事：

• 調(diào)研調(diào)度系統(tǒng)的應(yīng)用場景，深入研究場景中待執(zhí)行的任務(wù)（Work）和能用來執(zhí)行任務(wù)的資源（Resource）的特性；
• 分析調(diào)度系統(tǒng)的目的，可能是成本優(yōu)先、質(zhì)量優(yōu)先、最大化資源的利用率等，調(diào)度目的一般都是動態(tài)的，會隨著需求的變化而轉(zhuǎn)變；

應(yīng)用場景

調(diào)度系統(tǒng)應(yīng)用的場景是我們首先需要考慮的問題，對應(yīng)用場景的分析至關(guān)重要，我們需要深入了解當(dāng)前場景下待執(zhí)行任務(wù)和能用來執(zhí)行任務(wù)的資源的特點(diǎn)。我們需要分析待執(zhí)行任務(wù)的以下特征：

• 任務(wù)是否有截止日期，必須在某個時間點(diǎn)之前完成；
• 任務(wù)是否支持搶占，搶占的具體規(guī)則是什么；
• 任務(wù)是否包含前置的依賴條件；
• 任務(wù)是否只能在指定的資源上運(yùn)行；
• ...

而用于執(zhí)行任務(wù)的資源也可能存在資源不平衡，不同資源處理任務(wù)的速度不一致的問題。

資源和任務(wù)特點(diǎn)的多樣性決定了調(diào)度系統(tǒng)的設(shè)計，我們在這里舉幾個簡單的例子幫助各位讀者理解調(diào)度系統(tǒng)需求分析的過程。

圖 4 - Linux 操作系統(tǒng)

在操作系統(tǒng)的進(jìn)程調(diào)度器中，待調(diào)度的任務(wù)就是線程，這些任務(wù)一般只會處于正在執(zhí)行或者未執(zhí)行（等待或者終止）的狀態(tài)；而用于處理這些任務(wù)的 CPU 往往都是不可再分的，同一個 CPU 在同一時間只能執(zhí)行一個任務(wù)，這是物理上的限制。簡單總結(jié)一下，操作系統(tǒng)調(diào)度器的任務(wù)和資源有以下特性：

• 任務(wù) —— Thread。狀態(tài)簡單：只會處于正在執(zhí)行或者未被執(zhí)行兩種狀態(tài)；優(yōu)先級不同：待執(zhí)行的任務(wù)可能有不同的優(yōu)先級，在考慮優(yōu)先級的情況下，需要保證不同任務(wù)的公平性；
• 資源 —— CPU 時間。資源不可再分：同一時間只能運(yùn)行一個任務(wù)；

在上述場景中，待執(zhí)行的任務(wù)是操作系統(tǒng)調(diào)度的基本單位 —— 線程，而可分配的資源是 CPU 的時間。Go 語言的調(diào)度器與操作系統(tǒng)的調(diào)度器面對的是幾乎相同的場景，其中的任務(wù)是 Goroutine，可以分配的資源是在 CPU 上運(yùn)行的線程。

圖 5 - 容器編排系統(tǒng) Kubernetes

除了操作系統(tǒng)和編程語言這種較為底層的調(diào)度器之外，容器和計算任務(wù)調(diào)度在今天也很常見，Kubernetes 作為容器編排系統(tǒng)會負(fù)責(zé)調(diào)取集群中的容器，對它稍有了解的人都知道，Kubernetes 中調(diào)度的基本單元是 Pod，這些 Pod 會被調(diào)度到節(jié)點(diǎn) Node 上執(zhí)行：

• 任務(wù) —— Pod。優(yōu)先級不同：Pod 的優(yōu)先級可能不同，高優(yōu)先級的系統(tǒng) Pod 可以搶占低優(yōu)先級 Pod 的資源；有狀態(tài)：Pod 可以分為無狀態(tài)和有狀態(tài)，有狀態(tài)的 Pod 需要依賴持久存儲卷；

• 資源 —— Node。類型不同：不同節(jié)點(diǎn)上的資源類型不同，包括 CPU、GPU 和內(nèi)存等，這些資源可以被拆分但是都屬于當(dāng)前節(jié)點(diǎn)；不穩(wěn)定：節(jié)點(diǎn)可能由于突發(fā)原因不可用，例如：無網(wǎng)絡(luò)連接、磁盤損壞等；

調(diào)度系統(tǒng)在生活和工作中都很常見，除了上述的兩個場景之外，其他需要調(diào)度系統(tǒng)的場景包括 cdn 的資源調(diào)度、訂單調(diào)度以及離線任務(wù)調(diào)度系統(tǒng)等。在不同場景中，我們都需要深入思考任務(wù)和資源的特性，它們對系統(tǒng)的設(shè)計起者指導(dǎo)作用。

調(diào)度目的

在深入分析調(diào)度場景后，我們需要理解調(diào)度的目的。我們可以將調(diào)度目的理解成機(jī)器學(xué)習(xí)中的成本函數(shù)（Cost function），確定調(diào)度目的就是確定成本函數(shù)的定義，調(diào)度理論一書中曾經(jīng)介紹過常見的調(diào)度目的，包含以下內(nèi)容：

• 完成跨度（Makesapan） — 第一個到最后一個任務(wù)完成調(diào)度的時間跨度；
• 最大延遲（Maximum Lateness） — 超過截止時間最長的任務(wù)；
• 加權(quán)完成時間的和（Total weighted completion time）— 權(quán)重乘完成時間的總和；
• ...

這些都是偏理論的調(diào)度的目的，多數(shù)業(yè)務(wù)調(diào)度系統(tǒng)的調(diào)度目的都是優(yōu)化與業(yè)務(wù)聯(lián)系緊密的指標(biāo) — 成本和質(zhì)量。如何在成本和質(zhì)量之間達(dá)到平衡是需要仔細(xì)思考和設(shè)計的，由于篇幅所限以及業(yè)務(wù)場景的復(fù)雜，本文不會分析如何權(quán)衡成本和質(zhì)量，這往往都是需要結(jié)合業(yè)務(wù)考慮的事情，不具有足夠的相似性。

2. 調(diào)度原理

性能優(yōu)異的調(diào)度器是實(shí)現(xiàn)特定調(diào)度目的前提，我們在討論調(diào)度場景和目的時往往都會忽略調(diào)度的額外開銷，然而調(diào)度器執(zhí)行時的延時和吞吐量等指標(biāo)在調(diào)度負(fù)載較重時是不可忽視的。本節(jié)會分析與調(diào)度器實(shí)現(xiàn)相關(guān)的一些重要概念，這些概念能夠幫助我們實(shí)現(xiàn)高性能的調(diào)度器：

• 協(xié)作式調(diào)度與搶占式調(diào)度；
• 單調(diào)度器與多調(diào)度器；
• 任務(wù)分享與任務(wù)竊取；

協(xié)作式與搶占式

協(xié)作式（Cooperative）與搶占式（Preemptive）調(diào)度是操作系統(tǒng)中常見的多任務(wù)運(yùn)行策略。這兩種調(diào)度方法的定義完全不同：

• 協(xié)作式調(diào)度允許任務(wù)執(zhí)行任意長的時間，直到任務(wù)主動通知調(diào)度器讓出資源；
• 搶占式調(diào)度允許任務(wù)在執(zhí)行過程中被調(diào)度器掛起，調(diào)度器會重新決定下一個運(yùn)行的任務(wù)；

圖 6 - 協(xié)作式調(diào)度與搶占式調(diào)度

任務(wù)的執(zhí)行時間和任務(wù)上下文切換的額外開銷決定了哪種調(diào)度方式會帶來更好的性能。如下圖所示，圖 7 展示了一個協(xié)作式調(diào)度器調(diào)度任務(wù)的過程，調(diào)度器一旦為某個任務(wù)分配了資源，它就會等待該任務(wù)主動釋放資源，圖中 4 個任務(wù)盡管執(zhí)行時間不同，但是它們都會在任務(wù)執(zhí)行完成后釋放資源，整個過程也只需要 4 次上下文的切換。

圖 7 - 協(xié)作式調(diào)度

圖 8 展示了搶占式調(diào)度的過程，由于調(diào)度器不知道所有任務(wù)的執(zhí)行時間，所以它為每一個任務(wù)分配了一段時間切片。任務(wù) 1 和任務(wù) 4 由于執(zhí)行時間較短，所以在第一次被調(diào)度時就完成了任務(wù)；但是任務(wù) 2 和任務(wù) 3 因為執(zhí)行時間較長，超過了調(diào)度器分配的上限，所以為了保證公平性會觸發(fā)搶占，等待隊列中的其他任務(wù)會獲得資源。在整個調(diào)度過程中，一共發(fā)生了 6 次上下文切換。

圖 8 - 搶占式調(diào)度

如果部分任務(wù)的執(zhí)行時間很長，協(xié)作式的任務(wù)調(diào)度會使部分執(zhí)行時間長的任務(wù)餓死其他任務(wù)；不過如果待執(zhí)行的任務(wù)執(zhí)行時間較短并且?guī)缀跸嗤?，那么使用協(xié)作式的任務(wù)調(diào)度能減少任務(wù)中斷帶來的額外開銷，從而帶來更好的調(diào)度性能。

因為多數(shù)情況下任務(wù)執(zhí)行的時間都不確定，在協(xié)作式調(diào)度中一旦任務(wù)沒有主動讓出資源，那么就會導(dǎo)致其它任務(wù)等待和阻塞，所以調(diào)度系統(tǒng)一般都會以搶占式的任務(wù)調(diào)度為主，同時支持任務(wù)的協(xié)作式調(diào)度。

單調(diào)度器與多調(diào)度器

使用單個調(diào)度器還是多個調(diào)度器也是設(shè)計調(diào)度系統(tǒng)時需要仔細(xì)考慮的，多個調(diào)度器并不一定意味著多個進(jìn)程，也有可能是一個進(jìn)程中的多個調(diào)度線程，它們既可以選擇在多核上并行調(diào)度、在單核上并發(fā)調(diào)度，也可以同時利用并行和并發(fā)提高性能。

圖 9 - 單調(diào)度器調(diào)度任務(wù)和資源

不過對于調(diào)度系統(tǒng)來說，因為它做出的決策會改變資源的狀態(tài)和系統(tǒng)的上下文進(jìn)而影響后續(xù)的調(diào)度決策，所以單調(diào)度器的串行調(diào)度是能夠精準(zhǔn)調(diào)度資源的唯一方法。單個調(diào)度器利用不同渠道收集調(diào)度需要的上下文，并在收到調(diào)度請求后會根據(jù)任務(wù)和資源情況做出當(dāng)下最優(yōu)的決策。

隨著調(diào)度器的不斷演變，單調(diào)度器的性能和吞吐量可能會受到限制，我們還是需要引入并行或者并發(fā)調(diào)度來解決性能上的瓶頸，這時我們需要將待調(diào)度的資源分區(qū)，讓多個調(diào)度器分別負(fù)責(zé)調(diào)度不同區(qū)域中的資源。

圖 10 - 多調(diào)度器與資源分區(qū)

多調(diào)度器的并發(fā)調(diào)度能夠極大提升調(diào)度器的整體性能，例如 Go 語言的調(diào)度器。Go 語言運(yùn)行時會將多個 CPU 交給不同的處理器分別調(diào)度，這樣通過并行調(diào)度能夠提升調(diào)度器的性能。

上面介紹的兩種調(diào)度方法都建立在需要精準(zhǔn)調(diào)度的前提下，多調(diào)度器中的每一個調(diào)度器都會面對無關(guān)的資源，所以對于同一個分區(qū)的資源，調(diào)度還是串行的。

圖 11 - 多調(diào)度器粗粒度調(diào)度

使用多個調(diào)度器同時調(diào)度多個資源也是可行的，只是可能需要犧牲調(diào)度的精確性 — 不同的調(diào)度器可能會在不同時間接收到狀態(tài)的更新，這就會導(dǎo)致不同調(diào)度器做出不同的決策。負(fù)載均衡就可以看做是多線程和多進(jìn)程的調(diào)度器，因為對任務(wù)和資源掌控的信息有限，這種粗粒度調(diào)度的結(jié)果很可能就是不同機(jī)器的負(fù)載會有較大差異，所以無論是小規(guī)模集群還是大規(guī)模集群都很有可能導(dǎo)致某些實(shí)例的負(fù)載過高。

工作分享與工作竊取

這一小節(jié)將繼續(xù)介紹在多個調(diào)度器間重新分配任務(wù)的兩個調(diào)度范式?— 工作分享（Work Sharing）和工作竊取（Work Stealing）。獨(dú)立的調(diào)度器可以同時處理所有的任務(wù)和資源，所以它不會遇到多調(diào)度器的任務(wù)和資源的不平衡問題。在多數(shù)的調(diào)度場景中，任務(wù)的執(zhí)行時間都是不確定的，假設(shè)多個調(diào)度器分別調(diào)度相同的資源，由于任務(wù)的執(zhí)行時間不確定，多個調(diào)度器中等待調(diào)度的任務(wù)隊列最終會發(fā)生差異 — 部分隊列中包含大量任務(wù)，而另外一些隊列不包含任務(wù)，這時就需要引入任務(wù)再分配策略。

工作分享和工作竊取是完全不同的兩種再分配策略。在工作分享中，當(dāng)調(diào)度器創(chuàng)建了新任務(wù)時，它會將一部分任務(wù)分給其他調(diào)度器；而在工作竊取中，當(dāng)調(diào)度器的資源沒有被充分利用時，它會從其他調(diào)度器中竊取一些待分配的任務(wù)，如下圖所示：

圖 12 - 工作竊取調(diào)度器

這兩種任務(wù)再分配的策略都為系統(tǒng)增加了額外的開銷，與工作分享相比，工作竊取只會在當(dāng)前調(diào)度器的資源沒有被充分利用時才會觸發(fā)，所以工作竊取引入的額外開銷更小。工作竊取在生產(chǎn)環(huán)境中更加常用，Linux 操作系統(tǒng)和 Go 語言都選擇了工作竊取策略。

3.?架構(gòu)設(shè)計

本節(jié)將從調(diào)度器內(nèi)部和外部兩個角度分析調(diào)度器的架構(gòu)設(shè)計，前者分析調(diào)度器內(nèi)部多個組件的關(guān)系和做出調(diào)度決策的過程；后者分析多個調(diào)度器應(yīng)該如何協(xié)作，是否有其他的外部服務(wù)可以輔助調(diào)度器做出更合理的調(diào)度決策。

調(diào)度器內(nèi)部

當(dāng)調(diào)度器收到待調(diào)度任務(wù)時，會根據(jù)采集到的狀態(tài)和待調(diào)度任務(wù)的規(guī)格（Spec）做出合理的調(diào)度決策，我們可以從下圖中了解常見調(diào)度系統(tǒng)的內(nèi)部邏輯。

圖 13 - 調(diào)度器做出調(diào)度決策

常見的調(diào)度器一般由兩部分組成 — 用于收集狀態(tài)的狀態(tài)模塊和負(fù)責(zé)做決策的決策模塊。

• 狀態(tài)模塊

狀態(tài)模塊會從不同途徑收集盡可能多的信息為調(diào)度提供豐富的上下文，其中可能包括資源的屬性、利用率和可用性等信息。根據(jù)場景的不同，上下文可能需要存儲在 MySQL 等持久存儲中，一般也會在內(nèi)存中緩存一份以減少調(diào)度器訪問上下文的開銷。

• 決策模塊

決策模塊會根據(jù)狀態(tài)模塊收集的上下文和任務(wù)的規(guī)格做出調(diào)度決策，需要注意的是做出的調(diào)度決策只是在當(dāng)下有效，在未來某個時間點(diǎn)，狀態(tài)的改變可能會導(dǎo)致之前做的決策不符合任務(wù)的需求，例如：當(dāng)我們使用 Kubernetes 調(diào)度器將工作負(fù)載調(diào)度到某些節(jié)點(diǎn)上，這些節(jié)點(diǎn)可能由于網(wǎng)絡(luò)問題突然不可用，該節(jié)點(diǎn)上的工作負(fù)載也就不能正常工作，即調(diào)度決策失效。

調(diào)度器在調(diào)度時都會通過以下的三個步驟為任務(wù)調(diào)度合適的資源：

1. 通過優(yōu)先級、任務(wù)創(chuàng)建時間等信息確定不同任務(wù)的調(diào)度順序；
2. 通過過濾和打分兩個階段為任務(wù)選擇合適的資源；
3. 不存在滿足條件的資源時，選擇犧牲的搶占對象。

圖 14 - 調(diào)度框架

上圖展示了常見調(diào)度器決策模塊執(zhí)行的幾個步驟，確定優(yōu)先級、對閑置資源進(jìn)行打分、確定搶占資源的犧牲者，上述三個步驟中的最后一個往往都是可選的，部分調(diào)度系統(tǒng)不需要支持搶占式調(diào)度的功能。

調(diào)度器外部

如果我們將調(diào)度器看成一個整體，從調(diào)度器外部看架構(gòu)設(shè)計就會得到完全不同的角度 — 如何利用外部系統(tǒng)增強(qiáng)調(diào)度器的功能。在這里我們將介紹兩種調(diào)度器外部的設(shè)計，分別是多調(diào)度器和反調(diào)度器（Descheduler）。

• 多調(diào)度器

串行調(diào)度與并行調(diào)度一節(jié)已經(jīng)分析了多調(diào)度器的設(shè)計，我們可以將待調(diào)度的資源進(jìn)行分區(qū)，讓多個調(diào)度器線程或者進(jìn)程分別負(fù)責(zé)各個區(qū)域中資源的調(diào)度，充分利用多和 CPU 的并行能力。

• 反調(diào)度器

反調(diào)度器是一個比較有趣的概念，它能夠移除決策不再正確的調(diào)度，降低系統(tǒng)中的熵，讓調(diào)度器根據(jù)當(dāng)前的狀態(tài)重新決策。

圖 15 - 調(diào)度器與反調(diào)度器

反調(diào)度器的引入使得整個調(diào)度系統(tǒng)變得更加健壯。調(diào)度器負(fù)責(zé)根據(jù)當(dāng)前的狀態(tài)做出正確的調(diào)度決策，反調(diào)度器根據(jù)當(dāng)前的狀態(tài)移除錯誤的調(diào)度決策，它們的作用看起來相反，但是目的都是為任務(wù)調(diào)度更合適的資源。

反調(diào)度器的使用沒有那么廣泛，實(shí)際的應(yīng)用場景也比較有限。作者第一次發(fā)現(xiàn)這個概念是在 Kubernetes 孵化的descheduler?項目中，不過因為反調(diào)度器移除調(diào)度關(guān)系可能會影響正在運(yùn)行的線上服務(wù)，所以 Kubernetes 也只會在特定場景下使用。

操作系統(tǒng)

調(diào)度器是操作系統(tǒng)中的重要組件，操作系統(tǒng)中有進(jìn)程調(diào)度器、網(wǎng)絡(luò)調(diào)度器和 I/O 調(diào)度器等組件，本節(jié)介紹的是操作系統(tǒng)中的進(jìn)程調(diào)度器。

有一些讀者可能會感到困惑，操作系統(tǒng)調(diào)度的最小單位不是線程么，為什么這里使用的是進(jìn)程調(diào)度。在 Linux 操作系統(tǒng)中，調(diào)度器調(diào)度的不是進(jìn)程也不是線程，它調(diào)度的是 task_struct 結(jié)構(gòu)體，該結(jié)構(gòu)體既可以表示線程，也可以表示進(jìn)程，而調(diào)度器會將進(jìn)程和線程都看成任務(wù)，我們在這里先說明這一問題，避免讀者感到困惑。我們會使用進(jìn)程調(diào)度器這個術(shù)語，但是一定要注意 Linux 調(diào)度器中并不區(qū)分線程和進(jìn)程。

Linux incorporates process and thread scheduling by treating them as one in the same. A process can be viewed as a single thread, but a process can contain multiple threads that share some number of resources (code and/or data).

接下來，本節(jié)會研究操作系統(tǒng)中調(diào)度系統(tǒng)的類型以及 Linux 進(jìn)程調(diào)度器的演進(jìn)過程。

1.?調(diào)度系統(tǒng)類型

操作系統(tǒng)會將進(jìn)程調(diào)度器分成三種不同的類型，即長期調(diào)度器、中期調(diào)度器和短期調(diào)度器。這三種不同類型的調(diào)度器分別提供了不同的功能，我們將在這一節(jié)中依次介紹它們。

長期調(diào)度器

長期調(diào)度器（Long-Term Scheduler）也被稱作任務(wù)調(diào)度器（Job Scheduler），它能夠決定哪些任務(wù)會進(jìn)入調(diào)度器的準(zhǔn)備隊列。當(dāng)我們嘗試執(zhí)行新的程序時，長期調(diào)度器會負(fù)責(zé)授權(quán)或者延遲該程序的執(zhí)行。長期調(diào)度器的作用是平衡同時正在運(yùn)行的 I/O 密集型或者 CPU 密集型進(jìn)程的任務(wù)數(shù)量：

• 如果 I/O 密集型任務(wù)過多，就緒隊列中就不存在待調(diào)度的任務(wù)，短期調(diào)度器不需要執(zhí)行調(diào)度，CPU 資源就會面臨閑置；
• 如果 CPU 密集型任務(wù)過多，I/O 等待隊列中就不存在待調(diào)度的任務(wù)，I/O 設(shè)備就會面臨閑置；

長期調(diào)度器能平衡同時正在運(yùn)行的 I/O 密集型和 CPU 密集型任務(wù)，最大化的利用操作系統(tǒng)的 I/O 和 CPU 資源。

中期調(diào)度器

中期調(diào)度器會將不活躍的、低優(yōu)先級的、發(fā)生大量頁錯誤的或者占用大量內(nèi)存的進(jìn)程從內(nèi)存中移除，為其他的進(jìn)程釋放資源。

圖 16 - 中期調(diào)度器

當(dāng)正在運(yùn)行的進(jìn)程陷入 I/O 操作時，該進(jìn)程只會占用計算資源，在這種情況下，中期調(diào)度器就會將它從內(nèi)存中移除等待 I/O 操作完成后，該進(jìn)程會重新加入就緒隊列并等待短期調(diào)度器的調(diào)度。

短期調(diào)度器

短期調(diào)度器應(yīng)該是我們最熟悉的調(diào)度器，它會從就緒隊列中選出一個進(jìn)程執(zhí)行。進(jìn)程的選擇會使用特定的調(diào)度算法，它會同時考慮進(jìn)程的優(yōu)先級、入隊時間等特征。因為每個進(jìn)程能夠得到的執(zhí)行時間有限，所以短期調(diào)度器的執(zhí)行十分頻繁。

2. 設(shè)計與演進(jìn)

本節(jié)將重點(diǎn)介紹 Linux 的 CPU 調(diào)度器，也就是短期調(diào)度器。Linux 的 CPU 調(diào)度器并不是從設(shè)計之初就是像今天這樣復(fù)雜的，在很長的一段時間里（v0.01 ~ v2.4），Linux 的進(jìn)程調(diào)度都由幾十行的簡單函數(shù)負(fù)責(zé)，我們先了解一下不同版本調(diào)度器的歷史：

• 初始調(diào)度器 · v0.01 ~ v2.4。由幾十行代碼實(shí)現(xiàn)，功能非常簡陋；同時最多處理 64 個任務(wù)；

• 調(diào)度器 · v2.4 ~ v2.6。調(diào)度時需要遍歷全部任務(wù)當(dāng)待執(zhí)行的任務(wù)較多時，同一個任務(wù)兩次執(zhí)行的間隔很長，會有比較嚴(yán)重的饑餓問題；

• 調(diào)度器 · v2.6.0 ~ v2.6.22。通過引入運(yùn)行隊列和優(yōu)先數(shù)組實(shí)現(xiàn)??的時間復(fù)雜度；使用本地運(yùn)行隊列替代全局運(yùn)行隊列增強(qiáng)在對稱多處理器的擴(kuò)展性；引入工作竊取保證多個運(yùn)行隊列中任務(wù)的平衡；

• 完全公平調(diào)度器 · v2.6.23 ~ 至今。引入紅黑樹和運(yùn)行時間保證調(diào)度的公平性；引入調(diào)度類實(shí)現(xiàn)不同任務(wù)類型的不同調(diào)度策略；

這里會詳細(xì)介紹從最初的調(diào)度器到今天復(fù)雜的完全公平調(diào)度器（Completely Fair Scheduler，CFS）的演變過程。

初始調(diào)度器

Linux 最初的進(jìn)程調(diào)度器僅由 sched.h 和 sched.c 兩個文件構(gòu)成。你可能很難想象 Linux 早期版本使用只有幾十行的 schedule 函數(shù)負(fù)責(zé)了操作系統(tǒng)進(jìn)程的調(diào)度：

void schedule(void) {
    int i,next,c;
    struct task_struct ** p;
    for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) {
       ...
    }
    while (1) {
        c = -1;
        next = 0;
        i = NR_TASKS;
        p = &task[NR_TASKS];
        while (--i) {
            if (!*--p) continue;
            if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
                c = (*p)->counter, next = i;
        }
        if (c) break;
        for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
            if (*p)
                (*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
    }
    switch_to(next);
}

無論是進(jìn)程還是線程，在 Linux 中都被看做是 task_struct 結(jié)構(gòu)體，所有的調(diào)度進(jìn)程都存儲在上限僅為 64 的數(shù)組中，調(diào)度器能夠處理的進(jìn)程上限也只有 64 個。

圖 17 - 最初的進(jìn)程調(diào)度器

上述函數(shù)會先喚醒獲得信號的可中斷進(jìn)程，然后從隊列倒序查找計數(shù)器 counter 最大的可執(zhí)行進(jìn)程，counter 是進(jìn)程能夠占用的時間切片數(shù)量，該函數(shù)會根據(jù)時間切片的值執(zhí)行不同的邏輯：

• 如果最大的 counter 時間切片大于 0，調(diào)用匯編語言的實(shí)現(xiàn)的 switch_to 切換進(jìn)程；
• 如果最大的 counter 時間切片等于 0，意味著所有進(jìn)程的可執(zhí)行時間都為 0，那么所有進(jìn)程都會獲得新的時間切片；

Linux 操作系統(tǒng)的計時器會每隔 10ms 觸發(fā)一次 do_timer 將當(dāng)前正在運(yùn)行進(jìn)程的 counter 減一，當(dāng)前進(jìn)程的計數(shù)器歸零時就會重新觸發(fā)調(diào)度。

O(n)調(diào)度器

?調(diào)度器是 Linux 在 v2.4 ~ v2.6 版本使用的調(diào)度器，由于該調(diào)取器在最壞的情況下會遍歷所有的任務(wù)，所以它調(diào)度任務(wù)的時間復(fù)雜度就是?。Linux 調(diào)度算法將 CPU 時間分割成了不同的時期（Epoch），也就是每個任務(wù)能夠使用的時間切片。

我們可以在 sched.h 和 sched.c 兩個文件中找到調(diào)度器的源代碼。與上一個版本的調(diào)度器相比，?調(diào)度器的實(shí)現(xiàn)復(fù)雜了很多，該調(diào)度器會在 schedule 函數(shù)中遍歷運(yùn)行隊列中的所有任務(wù)并調(diào)用 goodness 函數(shù)分別計算它們的權(quán)重獲得下一個運(yùn)行的進(jìn)程：

asmlinkage void schedule(void){
    ...
still_running_back:
    list_for_each(tmp, &runqueue_head) {
        p = list_entry(tmp, struct task_struct, run_list);
        if (can_schedule(p, this_cpu)) {
            int weight = goodness(p, this_cpu, prev->active_mm);
            if (weight > c)
                c = weight, next = p;
        }
    }
    ...
}

在每個時期開始時，上述代碼都會為所有的任務(wù)計算時間切片，因為需要執(zhí)行 n 次，所以調(diào)度器被稱作??調(diào)度器。在默認(rèn)情況下，每個任務(wù)在一個周期都會分配到 200ms 左右的時間切片，然而這種調(diào)度和分配方式是??調(diào)度器的最大問題：

• 每輪調(diào)度完成之后就會陷入沒有任務(wù)需要調(diào)度的情況，需要提升交互性能的場景會受到嚴(yán)重影響，例如：在桌面拖動鼠標(biāo)會感覺到明顯的卡頓；
• 每次查找權(quán)重最高的任務(wù)都需要遍歷數(shù)組中的全部任務(wù)；
• 調(diào)度器分配的平均時間片大小為 210ms，當(dāng)程序中包含 100 個進(jìn)程時，同一個進(jìn)程被運(yùn)行兩次的間隔是 21s，這嚴(yán)重影響了操作系統(tǒng)的可用性.

正是因為調(diào)度器存在了上述的問題，所以 Linux 內(nèi)核在兩個版本后使用新的??調(diào)度器替換該實(shí)現(xiàn)。

O(1)調(diào)度器

調(diào)度器在 v2.6.0 到 v2.6.22 的 Linux 內(nèi)核中使用了四年的時間，它能夠在常數(shù)時間內(nèi)完成進(jìn)程調(diào)度，你可以在sched.h 和 sched.c 中查看??調(diào)度器的源代碼。因為實(shí)現(xiàn)和功能復(fù)雜性的增加，調(diào)度器的代碼行數(shù)從??的 2100 行增加到 5000 行，它在調(diào)度器的基礎(chǔ)上進(jìn)行了如下的改進(jìn)：

• 調(diào)度器支持了??時間復(fù)雜度的調(diào)度；
• 調(diào)度器支持了對稱多處理（Symmetric multiprocessing，SMP）的擴(kuò)展性；
• 調(diào)度器優(yōu)化了對稱多處理的親和性。

數(shù)據(jù)結(jié)構(gòu)

調(diào)度器通過運(yùn)行隊列 runqueue 和優(yōu)先數(shù)組 prio_array 兩個重要的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了??的時間復(fù)雜度。每一個運(yùn)行隊列都持有兩個優(yōu)先數(shù)組，分別存儲活躍的和過期的進(jìn)程數(shù)組：

struct runqueue {
    ...
    prio_array_t *active, *expired, arrays[2];
    ...
}
struct prio_array {
    unsignedint nr_active;
    unsignedlong bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];
};

優(yōu)先數(shù)組中的 nr_active 表示活躍的進(jìn)程數(shù)，而 bitmap 和 list_head 共同組成了如下圖所示的數(shù)據(jù)結(jié)構(gòu)：

圖 18 - 優(yōu)先數(shù)組

優(yōu)先數(shù)組的 bitmap 總共包含 140 位，每一位都表示對應(yīng)優(yōu)先級的進(jìn)程是否存在。圖 17 中的優(yōu)先數(shù)組包含 3 個優(yōu)先級為 2 的進(jìn)程和 1 個優(yōu)先級為 5 的進(jìn)程。每一個優(yōu)先級的標(biāo)志位都對應(yīng)一個 list_head 數(shù)組中的鏈表。?調(diào)度器使用上述的數(shù)據(jù)結(jié)構(gòu)進(jìn)行如下所示的調(diào)度：

• 調(diào)用 sched_find_first_bit 按照優(yōu)先級分配 CPU 資源；
• 調(diào)用 schedule 從鏈表頭選擇進(jìn)程執(zhí)行；
• 通過 schedule 輪訓(xùn)調(diào)度同一優(yōu)先級的進(jìn)程，該函數(shù)在每次選中待執(zhí)行的進(jìn)程后，將進(jìn)程添加到隊列的末尾，這樣可以保證同一優(yōu)先級的進(jìn)程會依次執(zhí)行（Round-Robin）；
• 計時器每隔 1ms 會觸發(fā)一次 scheduler_tick 函數(shù)，如果當(dāng)前進(jìn)程的執(zhí)行時間已經(jīng)耗盡，就會將其移入過期數(shù)組；
• 當(dāng)活躍隊列中不存在待運(yùn)行的進(jìn)程時，schedule 會交換活躍優(yōu)先數(shù)組和過期優(yōu)先數(shù)組；

上述的這些規(guī)則是??調(diào)度器運(yùn)行遵守的主要規(guī)則，除了上述規(guī)則之外，調(diào)度器還需要支持搶占、CPU 親和等功能，不過在這里就不展開介紹了。

本地運(yùn)行隊列

全局的運(yùn)行隊列是??調(diào)度器難以在對稱多處理器架構(gòu)上擴(kuò)展的主要原因。為了保證運(yùn)行隊列的一致性，調(diào)度器在調(diào)度時需要獲取運(yùn)行隊列的全局鎖，隨著處理器數(shù)量的增加，多個處理器在調(diào)度時會導(dǎo)致更多的鎖競爭，嚴(yán)重影響調(diào)度性能。?調(diào)度器通過引入本地運(yùn)行隊列解決這個問題，不同的 CPU 可以通過 this_rq 獲取綁定在當(dāng)前 CPU 上的運(yùn)行隊列，降低了鎖的粒度和沖突的可能性。

#define this_rq()        (&__get_cpu_var(runqueues))

圖 19 - 全局運(yùn)行隊列和本地運(yùn)行隊列

多個處理器由于不再需要共享全局的運(yùn)行隊列，所以增強(qiáng)了在對稱對處理器架構(gòu)上的擴(kuò)展性，當(dāng)我們增加新的處理器時，只需要增加新的運(yùn)行隊列，這種方式不會引入更多的鎖沖突。

優(yōu)先級和時間切片

調(diào)度器中包含兩種不同的優(yōu)先級計算方式，一種是靜態(tài)任務(wù)優(yōu)先級，另一種是動態(tài)任務(wù)優(yōu)先級。在默認(rèn)情況下，任務(wù)的靜態(tài)任務(wù)優(yōu)先級都是 0，不過我們可以通過系統(tǒng)調(diào)用 nice 改變?nèi)蝿?wù)的優(yōu)先級；?調(diào)度器會獎勵 I/O 密集型任務(wù)并懲罰 CPU 密集型任務(wù)，它會通過改變?nèi)蝿?wù)的靜態(tài)優(yōu)先級來完成優(yōu)先級的動態(tài)調(diào)整，因為與用戶交互的進(jìn)程時 I/O 密集型的進(jìn)程，這些進(jìn)程由于調(diào)度器的動態(tài)策略會提高自身的優(yōu)先級，從而提升用戶體驗。

完全公平調(diào)度器

完全公平調(diào)度器（Completely Fair Scheduler，CFS）是 v2.6.23 版本被合入內(nèi)核的調(diào)度器，也是內(nèi)核的默認(rèn)進(jìn)程調(diào)度器，它的目的是最大化 CPU 利用率和交互的性能。Linux 內(nèi)核版本 v2.6.23 中的 CFS 由以下的多個文件組成：

• include/linux/sched.h
• kernel/sched_stats.h
• kernel/sched.c
• kernel/sched_fair.c
• kernel/sched_idletask.c
• kernel/sched_rt.c

通過 CFS 的名字我們就能發(fā)現(xiàn)，該調(diào)度器的能為不同的進(jìn)程提供完全公平性。一旦某些進(jìn)程受到了不公平的待遇，調(diào)度器就會運(yùn)行這些進(jìn)程，從而維持所有進(jìn)程運(yùn)行時間的公平性。這種保證公平性的方式與『水多了加面，面多了加水』有一些相似：

• 調(diào)度器會查找運(yùn)行隊列中受到最不公平待遇的進(jìn)程，并為進(jìn)程分配計算資源，分配的計算資源是與其他資源運(yùn)行時間的差值加上最小能夠運(yùn)行的時間單位；
• 進(jìn)程運(yùn)行結(jié)束之后發(fā)現(xiàn)運(yùn)行隊列中又有了其他的進(jìn)程受到了最不公平的待遇，調(diào)度器又會運(yùn)行新的進(jìn)程；
• ...

調(diào)度器算法不斷計算各個進(jìn)程的運(yùn)行時間并依次調(diào)度隊列中的受到最不公平對待的進(jìn)程，保證各個進(jìn)程的運(yùn)行時間差不會大于最小運(yùn)行的時間單位。

數(shù)據(jù)結(jié)構(gòu)

雖然我們還是會延用運(yùn)行隊列這一術(shù)語，但是 CFS 的內(nèi)部已經(jīng)不再使用隊列來存儲進(jìn)程了，cfs_rq 是用來管理待運(yùn)行進(jìn)程的新結(jié)構(gòu)體，該結(jié)構(gòu)體會使用紅黑樹（Red-black tree）替代鏈表：

struct cfs_rq {
    struct load_weight load;
    unsignedlong nr_running;
    s64 fair_clock;
    u64 exec_clock;
    s64 wait_runtime;
    u64 sleeper_bonus;
    unsignedlong wait_runtime_overruns, wait_runtime_underruns;
    struct rb_root tasks_timeline;
    struct rb_node *rb_leftmost;
    struct rb_node *rb_load_balance_curr;
    struct sched_entity *curr;
    struct rq *rq;
    struct list_head leaf_cfs_rq_list;
};

紅黑樹（Red-black tree）是平衡的二叉搜索樹，紅黑樹的增刪改查操作的最壞時間復(fù)雜度為?，也就是樹的高度，樹中最左側(cè)的節(jié)點(diǎn) rb_leftmost 運(yùn)行的時間最短，也是下一個待運(yùn)行的進(jìn)程。

注：在最新版本的 CFS 實(shí)現(xiàn)中，內(nèi)核使用虛擬運(yùn)行時間 vruntime 替代了等待時間，但是基本的調(diào)度原理和排序方式?jīng)]有太多變化。

調(diào)度過程

CFS 的調(diào)度過程還是由 schedule 函數(shù)完成的，該函數(shù)的執(zhí)行過程可以分成以下幾個步驟：

• 關(guān)閉當(dāng)前 CPU 的搶占功能；
• 如果當(dāng)前 CPU 的運(yùn)行隊列中不存在任務(wù)，調(diào)用 idle_balance 從其他 CPU 的運(yùn)行隊列中取一部分執(zhí)行；
• 調(diào)用 pick_next_task 選擇紅黑樹中優(yōu)先級最高的任務(wù)；
• 調(diào)用 context_switch 切換運(yùn)行的上下文，包括寄存器的狀態(tài)和堆棧；
• 重新開啟當(dāng)前 CPU 的搶占功能。

CFS 的調(diào)度過程與??調(diào)度器十分類似，當(dāng)前調(diào)度器與前者的區(qū)別只是增加了可選的工作竊取機(jī)制并改變了底層的數(shù)據(jù)結(jié)構(gòu)。

調(diào)度類

CFS 中的調(diào)度類是比較有趣的概念，調(diào)度類可以決定進(jìn)程的調(diào)度策略。每個調(diào)度類都包含一組負(fù)責(zé)調(diào)度的函數(shù)，調(diào)度類由如下所示的 sched_class 結(jié)構(gòu)體表示：

struct sched_class {
    struct sched_class *next;
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
    void (*yield_task) (struct rq *rq, struct task_struct *p);
    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);
    struct task_struct * (*pick_next_task) (struct rq *rq);
    void (*put_prev_task) (struct rq *rq, struct task_struct *p);
    unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
            struct rq *busiest,
            unsigned long max_nr_move, unsigned long max_load_move,
            struct sched_domain *sd, enum cpu_idle_type idle,
            int *all_pinned, int *this_best_prio);
    void (*set_curr_task) (struct rq *rq);
    void (*task_tick) (struct rq *rq, struct task_struct *p);
    void (*task_new) (struct rq *rq, struct task_struct *p);
};

調(diào)度類中包含任務(wù)的初始化、入隊和出隊等函數(shù)，這里的設(shè)計與面向?qū)ο笾械脑O(shè)計稍微有些相似。內(nèi)核中包含 SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE、SCHED_FIFO 和 SCHED_RR 調(diào)度類，這些不同的調(diào)度類分別實(shí)現(xiàn)了 sched_class 中的函數(shù)以提供不同的調(diào)度行為。

3. 小結(jié)

本節(jié)介紹了操作系統(tǒng)調(diào)度器的設(shè)計原理以及演進(jìn)的歷史，從 2007 年合入 CFS 到現(xiàn)在已經(jīng)過去了很長時間，目前的調(diào)度器也變得更加復(fù)雜，社區(qū)也在不斷改進(jìn)進(jìn)程調(diào)度器。

我們可以從 Linux 調(diào)度器的演進(jìn)的過程看到主流系統(tǒng)架構(gòu)的變化，最初幾十行代碼的調(diào)度器就能完成基本的調(diào)度功能，而現(xiàn)在要使用幾萬行代碼來完成復(fù)雜的調(diào)度，保證系統(tǒng)的低延時和高吞吐量。

由于篇幅有限，我們很難對操作系統(tǒng)的調(diào)度器進(jìn)行面面俱到的分析，你可以在 這里 找到作者使用的 Linux 源代碼，親自動手分析不同版本的進(jìn)程調(diào)度器。

4. 延伸閱讀

• Understanding the Linux 2.6.8.1 CPU Scheduler
  
• CFS Scheduler
  
• Inside the Linux 2.6 Completely Fair Scheduler
  
• The Linux desktop may soon be a lot faster
  
• Modular Scheduler Core and Completely Fair Scheduler
  
• The Linux Scheduler: A Decade of Wasted Cores

Go 語言

Go 語言是誕生自 2009 年的編程語言，相信很多人對 Go 語言的印象都是語法簡單，能夠支撐高并發(fā)的服務(wù)。語法簡單是編程語言的頂層設(shè)計哲學(xué)，而語言的高并發(fā)支持依靠的是運(yùn)行時的調(diào)度器，這也是本節(jié)將要研究的內(nèi)容。

對 Go 語言稍微有了解的人都知道，通信順序進(jìn)程（Communicating sequential processes，CSP）影響著 Go 語言的并發(fā)模型，其中的 Goroutine 和 Channel 分別表示實(shí)體和用于通信的媒介。

圖 20 - Go 和 Erlang 的并發(fā)模型

『不要通過共享內(nèi)存來通信，我們應(yīng)該使用通信來共享內(nèi)存』不只是 Go 語言鼓勵的設(shè)計哲學(xué)，更為古老的 Erlang 語言其實(shí)也遵循了同樣的設(shè)計，但是 Erlang 選擇使用了Actor 模型，我們在這里就不介紹 CSP 和 Actor 的區(qū)別和聯(lián)系的，感興趣的讀者可以在推薦閱讀和應(yīng)引用中找到相關(guān)資源。

1. 設(shè)計與演進(jìn)

今天的 Go 語言調(diào)度器有著非常優(yōu)異的性能，但是如果我們回過頭重新看 Go 語言的 v0.x 版本的調(diào)度器就會發(fā)現(xiàn)最初的調(diào)度器非常簡陋，也無法支撐高并發(fā)的服務(wù)。整個調(diào)度器經(jīng)過幾個大版本的迭代才有了今天的優(yōu)異性能。

• 單線程調(diào)度器 · 0.x - 源代碼。只包含 40 多行代碼；只能單線程調(diào)度，由 G-M 模型組成；
• 多線程調(diào)度器 · 1.0 - 源代碼。引入了多線程調(diào)度；全局鎖導(dǎo)致競爭嚴(yán)重；
• 任務(wù)竊取調(diào)度器 · 1.1 - 源代碼。引入了處理器 P，構(gòu)成了目前的 G-M-P 模型；在處理器 P 的基礎(chǔ)上實(shí)現(xiàn)了基于工作竊取的調(diào)度器；在某些情況下，Goroutine 不會讓出線程造成饑餓問題；時間過長的程序暫停（Stop-the-world，STW）會導(dǎo)致程序無法工作；
• 搶占式調(diào)度器 · 1.2 ~ 至今 - 源代碼。實(shí)現(xiàn)基于信號的真搶占式調(diào)度；垃圾回收對棧進(jìn)行掃描時會觸發(fā)搶占調(diào)度；搶占的時間點(diǎn)不夠多，還不能覆蓋全部的邊緣情況；通過編譯器在函數(shù)調(diào)用時插入檢查指令，實(shí)現(xiàn)基于協(xié)作的搶占式調(diào)度；GC 和循環(huán)可能會導(dǎo)致 Goroutine 長時間占用資源導(dǎo)致程序暫停；協(xié)作的搶占式調(diào)度器 - 1.2 ~ 1.13；搶占式調(diào)度器 - 1.14 ~ 至今；
• 非均勻存儲訪問調(diào)度器 · 提案。對運(yùn)行時中的各種資源進(jìn)行分區(qū)；實(shí)現(xiàn)非常復(fù)雜，到今天還沒有提上日程；

除了多線程、任務(wù)竊取和搶占式調(diào)度器之外，Go 語言社區(qū)目前還有一個非均勻存儲訪問（Non-uniform memory access，NUMA）調(diào)度器的提案，將來有一天可能 Go 語言會實(shí)現(xiàn)這個調(diào)度器。在這一節(jié)中，我們將依次介紹不同版本調(diào)度器的實(shí)現(xiàn)以及未來可能會實(shí)現(xiàn)的調(diào)度器提案。

單線程調(diào)度器

Go 語言在 0.x 版本調(diào)度器中只包含表示 Goroutine 的 G 和表示線程的 M 兩種結(jié)構(gòu)體，全局也只有一個線程。我們可以在 clean up scheduler 提交中找到單線程調(diào)度器的源代碼，在這時 Go 語言的 調(diào)度器 還是由 C 語言實(shí)現(xiàn)的，調(diào)度函數(shù) schedule 中也只包含 40 多行代碼 ：

static void scheduler(void) {
    G* gp;
    lock(&sched);
    if(gosave(&m->sched)){
        lock(&sched);
        gp = m->curg;
        switch(gp->status){
        case Grunnable:
        case Grunning:
            gp->status = Grunnable;
            gput(gp);
            break;
        ...
        }
        notewakeup(&gp->stopped);
    }
    gp = nextgandunlock();
    noteclear(&gp->stopped);
    gp->status = Grunning;
    m->curg = gp;
    g = gp;
    gogo(&gp->sched);
}

該函數(shù)會遵循如下所示的過程執(zhí)行：

• 獲取調(diào)度器的全局鎖；
• 調(diào)用 gosave 保存棧寄存器和程序計數(shù)器；
• 調(diào)用 nextgandunlock 獲取下一個線程 M 需要運(yùn)行的 Goroutine 并解鎖調(diào)度器；
• 修改全局線程 m 上要執(zhí)行的 Goroutine；
• 調(diào)用 gogo 函數(shù)運(yùn)行最新的 Goroutine。

這個單線程調(diào)度器的唯一優(yōu)點(diǎn)就是能跑，不過從這次提交中我們能看到 G 和 M 兩個重要的數(shù)據(jù)結(jié)構(gòu)，它建立了 Go 語言調(diào)度器的框架。

多線程調(diào)度器

Go 語言 1.0 版本在正式發(fā)布時就支持了多線程的調(diào)度器，與上一個版本完全不可用的調(diào)度器相比，Go 語言團(tuán)隊在這一階段完成了從不可用到可用。我們可以在 proc.c 中找到 1.0.1 版本的調(diào)度器，多線程版本的調(diào)度函數(shù) schedule 包含 70 多行代碼，我們在這里保留了其中的核心邏輯：

static void schedule(G *gp) {
    schedlock();
    if(gp != nil) {
        gp->m = nil;
        uint32 v = runtime·xadd(&runtime·sched.atomic, -1< maxgomaxprocs)
            runtime·throw("negative mcpu in scheduler");
        switch(gp->status){
        case Grunning:
            gp->status = Grunnable;
            gput(gp);
            break;
        case ...:
        }
    } else {
        ...
    }
    gp = nextgandunlock();
    gp->status = Grunning;
    m->curg = gp;
    gp->m = m;
    runtime·gogo(&gp->sched, 0);
}

整體的邏輯與單線程調(diào)度器沒有太多區(qū)別，多線程調(diào)度器引入了 GOMAXPROCS 變量幫助我們控制程序中的最大線程數(shù)，這樣我們的程序中就可能同時存在多個活躍線程。

多線程調(diào)度器的主要問題是調(diào)度時的鎖競爭，Scalable Go Scheduler Design Doc 中對調(diào)度器做的性能測試發(fā)現(xiàn) 14% 的時間都花費(fèi)在 runtime.futex 函數(shù)上，目前的調(diào)度器實(shí)現(xiàn)有以下問題需要解決：

• 全局唯一的調(diào)度器和全局鎖，所有的調(diào)度狀態(tài)都是中心化存儲的，帶來了鎖競爭；
• 線程需要經(jīng)常互相傳遞可運(yùn)行的 Goroutine，引入了大量的延遲和額外開銷；
• 每個線程都需要處理內(nèi)存緩存，導(dǎo)致大量的內(nèi)存占用并影響數(shù)據(jù)局部性（Data locality）；
• 系統(tǒng)調(diào)用頻繁阻塞和解除阻塞正在運(yùn)行的線程，增加了額外開銷。

這里的全局鎖問題和 Linux 操作系統(tǒng)調(diào)度器在早期遇到的問題比較相似，解決方案也都大同小異。

任務(wù)竊取調(diào)度器

2012 年 Google 的工程師 Dmitry Vyukov 在 Scalable Go Scheduler Design Doc 中指出了現(xiàn)有多線程調(diào)度器的問題并在多線程調(diào)度器上提出了兩個改進(jìn)的手段：

• 在當(dāng)前的 G-M 模型中引入了處理器 P；
• 在處理器 P 的基礎(chǔ)上實(shí)現(xiàn)基于工作竊取的調(diào)度器。

基于任務(wù)竊取的 Go 語言調(diào)度器使用了沿用至今的 G-M-P 模型，我們能在 runtime: improved scheduler 提交中找到任務(wù)竊取調(diào)度器剛被實(shí)現(xiàn)時的源代碼，調(diào)度器的 schedule 函數(shù)到現(xiàn)在反而更簡單了：

static void schedule(void) {
    G *gp;
 top:
    if(runtime·gcwaiting) {
        gcstopm();
        goto top;
    }
    gp = runqget(m->p);
    if(gp == nil)
        gp = findrunnable();
    ...
    execute(gp);
}

• 如果當(dāng)前運(yùn)行時在等待垃圾回收，調(diào)用 gcstopm 函數(shù)；
• 調(diào)用 runqget 和 findrunnable 從本地的或者全局的運(yùn)行隊列中獲取待執(zhí)行的 Goroutine；
• 調(diào)用 execute 函數(shù)在當(dāng)前線程 M 上運(yùn)行 Goroutine。

當(dāng)前處理器本地的運(yùn)行隊列中不包含 Goroutine 時，調(diào)用 findrunnable 函數(shù)會觸發(fā)工作竊取，從其他的處理器的隊列中隨機(jī)獲取一些 Goroutine。

運(yùn)行時 G-M-P 模型中引入的處理器 P 是線程 M 和 Goroutine 之間的中間層，我們從它的結(jié)構(gòu)體中就能看到 P 與 M 和 G 的關(guān)系：

struct P {
    Lock;
    uint32  status;  // one of Pidle/Prunning/...
    P*  link;
    uint32  tick;   // incremented on every scheduler or system call
    M*  m;  // back-link to associated M (nil if idle)
    MCache* mcache;
    G** runq;
    int32   runqhead;
    int32   runqtail;
    int32   runqsize;
    G*  gfree;
    int32   gfreecnt;
};

處理器 P 持有一個運(yùn)行隊列 runq，這是由可運(yùn)行的 Goroutine 組成的數(shù)組，它還反向持有一個線程 M 的指針。調(diào)度器在調(diào)度時會從處理器的隊列中選擇隊列頭的 Goroutine 放到線程 M 上執(zhí)行。如下所示的圖片展示了 Go 語言中的線程 M、處理器 P 和 Goroutine 的關(guān)系。

圖 21 - G-M-P 模型

基于工作竊取的多線程調(diào)度器將每一個線程綁定到了獨(dú)立的 CPU 上并通過不同處理器分別管理，不同處理器中通過工作竊取對任務(wù)進(jìn)行再分配，提升了調(diào)度器和 Go 語言程序的整體性能，今天所有的 Go 語言服務(wù)的高性能都受益于這一改動。

搶占式調(diào)度器

對 Go 語言并發(fā)模型的修改提升了調(diào)度器的性能，但是在 1.1 版本中的調(diào)度器仍然不支持搶占式調(diào)度，程序只能依靠 Goroutine 主動讓出 CPU 資源。Go 語言的調(diào)度器在1.2 版本中引入了基于協(xié)作的搶占式調(diào)度解決下面的問題：

• 單獨(dú)的 Goroutine 可以一直占用線程運(yùn)行，不會切換到其他的 Goroutine，造成饑餓問題；
• 垃圾回收需要暫停整個程序（Stop-the-world，STW），如果沒有搶占可能需要等待幾分鐘的時間，導(dǎo)致整個程序無法工作。

然而 1.2 版本中實(shí)現(xiàn)的搶占式調(diào)度是基于協(xié)作的，在很長的一段時間里 Go 語言的調(diào)度器都包含一些無法被搶占的邊緣情況，直到 1.14 才實(shí)現(xiàn)了基于信號的真搶占式調(diào)度解決部分問題。

基于協(xié)作的搶占式調(diào)度

我們可以在 proc.c 文件中找到引入搶占式調(diào)度后的調(diào)度器實(shí)現(xiàn)。Go 語言會在當(dāng)前的分段棧機(jī)制上實(shí)現(xiàn)搶占式的調(diào)度，所有的 Goroutine 在函數(shù)調(diào)用時都有機(jī)會進(jìn)入運(yùn)行時檢查是否需要執(zhí)行搶占?；趨f(xié)作的搶占是通過以下的多個提交實(shí)現(xiàn)的：

• runtime: mark runtime.goexit as nosplit
• runtime: add stackguard0 to G。為 Goroutine 引入 stackguard0 字段，當(dāng)該字段被設(shè)置成 StackPreempt 時，Goroutine 會被搶占；
• runtime: introduce preemption function (not used for now)。引入搶占函數(shù) preemptone 和 preemptall，這兩個函數(shù)會設(shè)置 Goroutine 的 StackPreempt；引入搶占請求 StackPreempt；
• runtime: preempt goroutines for GC。在垃圾回收調(diào)用的 runtime·stoptheworld 中調(diào)用 preemptall 函數(shù)設(shè)置所有處理器上 Goroutine 的 StackPreempt；在 runtime·newstack 函數(shù)中增加搶占的代碼，當(dāng) stackguard0 等于 StackPreempt 時觸發(fā)調(diào)度器的搶占；
• runtime: preempt long-running goroutines。在系統(tǒng)監(jiān)控中，如果一個 Goroutine 的運(yùn)行時間超過 10ms，就會調(diào)用 retake 和 preemptone；
• runtime: more reliable preemption。修復(fù) Goroutine 因為周期性執(zhí)行非阻塞的 CGO 或者系統(tǒng)調(diào)用不會被搶占的問題。

從上述一系列的提交中，我們會發(fā)現(xiàn) Go 語言運(yùn)行時會在垃圾回收暫停程序、系統(tǒng)監(jiān)控發(fā)現(xiàn) Goroutine 運(yùn)行超過 10ms 時提出搶占請求 StackPreempt；因為編譯器會在函數(shù)調(diào)用中插入 runtime.newstack，所以函數(shù)調(diào)用時會通過 runtime.newstack 檢查 Goroutine 的 stackguard0 是否為 StackPreempt 進(jìn)而觸發(fā)搶占讓出當(dāng)前線程。

這種做法沒有帶來運(yùn)行時的過多額外開銷，實(shí)現(xiàn)也相對比較簡單，不過增加了運(yùn)行時的復(fù)雜度，總體來看還是一種比較成功的實(shí)現(xiàn)。因為上述的搶占是通過編譯器在特定時機(jī)插入函數(shù)實(shí)現(xiàn)的，還是需要函數(shù)調(diào)用作為入口才能觸發(fā)搶占，所以這是一種協(xié)作式的搶占式調(diào)度。

基于信號的搶占式調(diào)度

協(xié)作的搶占式調(diào)度實(shí)現(xiàn)雖然巧妙，但是留下了很多的邊緣情況，我們能在 runtime: non-cooperative goroutine preemption 中找到一些遺留問題：

• runtime: tight loops should be preemptible #10958
• An empty for{} will block large slice allocation in another goroutine, even with GOMAXPROCS > 1 ? #17174
• runtime: tight loop hangs process completely after some time #15442
• ...

Go 語言在 1.14 版本中實(shí)現(xiàn)了非協(xié)作的搶占式調(diào)度，在實(shí)現(xiàn)的過程中我們對已有的邏輯進(jìn)行重構(gòu)并為 Goroutine 增加新的狀態(tài)和字段來支持搶占。Go 團(tuán)隊通過下面提交的實(shí)現(xiàn)了這一功能，我們可以順著提交的順序理解其實(shí)現(xiàn)原理：

• runtime: add general suspendG/resumeG。掛起 Goroutine 的過程是在棧掃描時完成的，我們通過 runtime.suspendG 和 runtime.resumeG 兩個函數(shù)重構(gòu)棧掃描這一過程；調(diào)用 runtime.suspendG 函數(shù)時會將運(yùn)行狀態(tài)的 Goroutine 的 preemptStop 標(biāo)記成 true；調(diào)用 runtime.preemptPark 函數(shù)可以掛起當(dāng)前 Goroutine、將其狀態(tài)更新成 _Gpreempted 并觸發(fā)調(diào)度器的重新調(diào)度，該函數(shù)能夠交出線程控制權(quán)；
• runtime: asynchronous preemption function for x86。在 x86 架構(gòu)上增加異步搶占的函數(shù) runtime.asyncPreempt 和 runtime.asyncPreempt2；
• runtime: use signals to preempt Gs for suspendG。支持通過向線程發(fā)送信號的方式暫停運(yùn)行的 Goroutine；在 runtime.sighandler 函數(shù)中注冊了 SIGURG 信號的處理函數(shù) runtime.doSigPreempt；runtime.preemptM 函數(shù)可以向線程發(fā)送搶占請求；
• runtime: implement async scheduler preemption。修改 runtime.preemptone 函數(shù)的實(shí)現(xiàn)，加入異步搶占的邏輯。

目前的搶占式調(diào)度也只會在垃圾回收掃描任務(wù)時觸發(fā)，我們可以梳理一下觸發(fā)搶占式調(diào)度的過程：

• 程序啟動時，在 runtime.sighandler 函數(shù)中注冊了 SIGURG 信號的處理函數(shù) runtime.doSigPreempt；
• 在觸發(fā)垃圾回收的棧掃描時會調(diào)用 runtime.suspendG 函數(shù)掛起 Goroutine。將 _Grunning 狀態(tài)的 Goroutine 標(biāo)記成可以被搶占，即 preemptStop 設(shè)置成 true；調(diào)用 runtime.preemptM 函數(shù)觸發(fā)搶占；
• runtime.preemptM 函數(shù)會調(diào)用 runtime.signalM 向線程發(fā)送信號 SIGURG；
• 操作系統(tǒng)會中斷正在運(yùn)行的線程并執(zhí)行預(yù)先注冊的信號處理函數(shù) runtime.doSigPreempt；
• runtime.doSigPreempt 函數(shù)會處理搶占信號，獲取當(dāng)前的 SP 和 PC 寄存器并調(diào)用 runtime.sigctxt.pushCall；
• runtime.sigctxt.pushCall 會修改寄存器并在程序回到用戶態(tài)時從 runtime.asyncPreempt 開始執(zhí)行；
• 匯編指令 runtime.asyncPreempt 會調(diào)用運(yùn)行時函數(shù) runtime.asyncPreempt2；
• runtime.asyncPreempt2 會調(diào)用 runtime.preemptPark 函數(shù)；
• runtime.preemptPark 會修改當(dāng)前 Goroutine 的狀態(tài)到 _Gpreempted 并調(diào)用 runtime.schedule 讓當(dāng)前函數(shù)陷入休眠并讓出線程，調(diào)度器會選擇其他的 Goroutine 繼續(xù)執(zhí)行；

上述 9 個步驟展示了基于信號的搶占式調(diào)度的執(zhí)行過程。我們還需要討論一下該過程中信號的選擇，提案根據(jù)以下的四個原因選擇 SIGURG 作為觸發(fā)異步搶占的信號：

• 該信號需要被調(diào)試器透傳；
• 該信號不會被內(nèi)部的 libc 庫使用并攔截；
• 該信號可以隨意出現(xiàn)并且不觸發(fā)任何后果；
• 我們需要處理多個平臺上的不同信號。

目前的搶占式調(diào)度也沒有解決所有潛在的問題，因為 STW 和棧掃描時更可能出現(xiàn)問題，也是一個可以搶占的安全點(diǎn)（Safe-points），所以我們會在這里先加入搶占功能，在未來可能會加入更多搶占時間點(diǎn)。

非均勻內(nèi)存訪問調(diào)度器

非均勻內(nèi)存訪問（Non-uniform memory access，NUMA）調(diào)度器目前只是 Go 語言的提案，因為該提案過于復(fù)雜，而目前的調(diào)度器的性能已經(jīng)足夠優(yōu)異，所以暫時沒有實(shí)現(xiàn)該提案。該提案的原理就是通過拆分全局資源，讓各個處理器能夠就近獲取本地資源，減少鎖競爭并增加數(shù)據(jù)局部性。

在目前的運(yùn)行時中，線程、處理器、網(wǎng)絡(luò)輪訓(xùn)器、運(yùn)行隊列、全局內(nèi)存分配器狀態(tài)、內(nèi)存分配緩存和垃圾收集器都是全局的資源。運(yùn)行時沒有保證本地化，也不清楚系統(tǒng)的拓?fù)浣Y(jié)構(gòu)，部分結(jié)構(gòu)可以提供一定的局部性，但是從全局來看沒有這種保證。

圖 22 - Go 語言 NUMA 調(diào)度器

如上圖所示，堆棧、全局運(yùn)行隊列和線程池會按照 NUMA 節(jié)點(diǎn)進(jìn)行分區(qū)，網(wǎng)絡(luò)輪訓(xùn)器和計時器會由單獨(dú)的處理器持有。這種方式雖然能夠利用局部性提高調(diào)度器的性能，但是本身的實(shí)現(xiàn)過于復(fù)雜，所以 Go 語言團(tuán)隊還沒有著手實(shí)現(xiàn)這一提案。

2. 小結(jié)

Go 語言的調(diào)度器在最初的幾個版本中迅速迭代，但是從 1.2 版本之后調(diào)度器就沒有太多的變化，直到 1.14 版本引入了真正的搶占式調(diào)度解決了自 1.2 以來一直存在的問題。在可預(yù)見的未來，Go 語言的調(diào)度器還會進(jìn)一步演進(jìn)，增加搶占式調(diào)度的時間點(diǎn)減少存在的邊緣情況。

本節(jié)內(nèi)容選擇《Go 語言設(shè)計與實(shí)現(xiàn)》一書中的 Go 語言調(diào)度器實(shí)現(xiàn)原理，你可以點(diǎn)擊鏈接了解更多與 Go 語言設(shè)計與實(shí)現(xiàn)原理相關(guān)的內(nèi)容。

3. 延伸閱讀

• How Erlang does scheduling
  
• Analysis of the Go runtime scheduler
  
• Go's work-stealing scheduler
  
• runtime: clean up async preemption loose ends
  
• The Go netpoller
  
• System Calls Make the World Go Round
  
• Linux Syscall Reference
  

Kubernetes

Kubernetes 是生產(chǎn)級別的容器調(diào)度和管理系統(tǒng)，在過去的一段時間中，Kubernetes 迅速占領(lǐng)市場，成為容器編排領(lǐng)域的實(shí)施標(biāo)準(zhǔn)。

圖 23 - 容器編排系統(tǒng)演進(jìn)

Kubernetes 是希臘語『舵手』的意思，它最開始由 Google 的幾位軟件工程師創(chuàng)立，深受公司內(nèi)部Borg 和 Omega 項目的影響，很多設(shè)計都是從 Borg 中借鑒的，同時也對 Borg 的缺陷進(jìn)行了改進(jìn)，Kubernetes 目前是 Cloud Native Computing Foundation (CNCF) 的項目，也是很多公司管理分布式系統(tǒng)的解決方案。

調(diào)度器是 Kubernetes 的核心組件，它的主要功能是為待運(yùn)行的工作負(fù)載 Pod 綁定運(yùn)行的節(jié)點(diǎn) Node。與其他調(diào)度場景不同，雖然資源利用率在 Kubernetes 中也非常重要，但是這只是 Kubernetes 關(guān)注的一個因素，它需要在容器編排這個場景中支持非常多并且復(fù)雜的業(yè)務(wù)需求，除了考慮 CPU 和內(nèi)存是否充足，還需要考慮其他的領(lǐng)域特定場景，例如：兩個服務(wù)不能占用同一臺機(jī)器的相同端口、幾個服務(wù)要運(yùn)行在同一臺機(jī)器上，根據(jù)節(jié)點(diǎn)的類型調(diào)度資源等。

這些復(fù)雜的業(yè)務(wù)場景和調(diào)度需求使 Kubernetes 調(diào)度器的內(nèi)部設(shè)計與其他調(diào)度器完全不同，但是作為用戶應(yīng)用層的調(diào)度器，我們卻能從中學(xué)到很多有用的模式和設(shè)計。接下來，本節(jié)將介紹 Kubernetes 中調(diào)度器的設(shè)計以及演變。

1. 設(shè)計與演進(jìn)

Kubernetes 調(diào)度器的演變過程比較簡單，我們可以將它的演進(jìn)過程分成以下的兩個階段：

• 基于謂詞和優(yōu)先級的調(diào)度器 · v1.0.0 ~ v1.14.0
• 基于調(diào)度框架的調(diào)度器 · v1.15.0 ~ 至今

Kubernetes 從 v1.0.0 版本發(fā)布到 v1.14.0，總共 15 個版本一直都在使用謂詞和優(yōu)先級來管理不同的調(diào)度算法，知道 v1.15.0 開始引入調(diào)度框架（Alpha 功能）來重構(gòu)現(xiàn)有的調(diào)度器。我們在這里將以 v1.14.0 版本的謂詞和優(yōu)先級和 v1.17.0 版本的調(diào)度框架分析調(diào)度器的演進(jìn)過程。

謂詞和優(yōu)先級算法

謂詞（Predicates）和優(yōu)先級（Priorities）調(diào)度器是從 Kubernetes v1.0.0 發(fā)布時就存在的模式，v1.14.0 的最后實(shí)現(xiàn)與最開始的設(shè)計也沒有太多區(qū)別。然而從 v1.0.0 到 v1.14.0 期間也引入了很多改進(jìn)：

• 調(diào)度器擴(kuò)展 · v1.2.0 - Scheduler extension。通過調(diào)用外部調(diào)度器擴(kuò)展的方式改變調(diào)度器的決策；

• Map-Reduce 優(yōu)先級算法 · v1.5.0 - MapReduce-like scheduler priority functions。為調(diào)度器的優(yōu)先級算法支持 Map-Reduce 的計算方式，通過引入可并行的 Map 階段優(yōu)化調(diào)度器的計算性能；

• 調(diào)度器遷移 · v1.10.0 - Move scheduler code out of plugin directory。從 plugin/pkg/scheduler 移到 pkg/scheduler；kube-scheduler 成為對外直接提供的可執(zhí)行文件；

謂詞和優(yōu)先級都是 Kubernetes 在調(diào)度系統(tǒng)中提供的兩個抽象，謂詞算法使用 FitPredicate 類型，而優(yōu)先級算法使用 PriorityMapFunction 和 PriorityReduceFunction 兩個類型：

type FitPredicate func(pod *v1.Pod, meta PredicateMetadata, nodeInfo *schedulernodeinfo.NodeInfo) (bool, []PredicateFailureReason, error)
type PriorityMapFunction func(pod *v1.Pod, meta interface{}, nodeInfo *schedulernodeinfo.NodeInfo) (schedulerapi.HostPriority, error)
type PriorityReduceFunction func(pod *v1.Pod, meta interface{}, nodeNameToInfo map[string]*schedulernodeinfo.NodeInfo, result schedulerapi.HostPriorityList) error

因為 v1.14.0 也是作者剛開始參與 Kubernetes 開發(fā)的第一個版本，所以對當(dāng)時的設(shè)計印象也非常深刻，v1.14.0 的 Kubernetes 調(diào)度器會使用 PriorityMapFunction 和 PriorityReduceFunction 這種 Map-Reduce 的方式計算所有節(jié)點(diǎn)的分?jǐn)?shù)并從其中選擇分?jǐn)?shù)最高的節(jié)點(diǎn)。下圖展示了，v1.14.0 版本中調(diào)度器的執(zhí)行過程：

圖 24 - 謂詞和優(yōu)先級算法

如上圖所示，我們假設(shè)調(diào)度器中存在一個謂詞算法和一個 Map-Reduce 優(yōu)先級算法，當(dāng)我們?yōu)橐粋€ Pod 在 6 個節(jié)點(diǎn)中選擇最合適的一個時，6 個節(jié)點(diǎn)會先經(jīng)過謂詞的篩選，圖中的謂詞算法會過濾掉一半的節(jié)點(diǎn)，剩余的 3 個節(jié)點(diǎn)經(jīng)過 Map 和 Reduce 兩個過程分別得到了 5、10 和 5 分，最終調(diào)度器就會選擇分?jǐn)?shù)最高的 4 號節(jié)點(diǎn)。

genericScheduler.Schedule 是 Kubernetes 為 Pod 選擇節(jié)點(diǎn)的方法，我們省略了該方法中用于檢查邊界條件以及打點(diǎn)的代碼：

func (g *genericScheduler) Schedule(pod *v1.Pod, nodeLister algorithm.NodeLister) (result ScheduleResult, err error) {
    nodes, err := nodeLister.List()
    if err != nil {
        return result, err
    }
    iflen(nodes) == 0 {
        return result, ErrNoNodesAvailable
    }
    filteredNodes, failedPredicateMap, err := g.findNodesThatFit(pod, nodes)
    if err != nil {
        return result, err
    }
    ...
    priorityList, err := PrioritizeNodes(pod, g.nodeInfoSnapshot.NodeInfoMap, ..., g.prioritizers, filteredNodes, g.extenders)
    if err != nil {
        return result, err
    }
    host, err := g.selectHost(priorityList)
    return ScheduleResult{
        SuggestedHost:  host,
        EvaluatedNodes: len(filteredNodes) + len(failedPredicateMap),
        FeasibleNodes:  len(filteredNodes),
    }, err
}

• 從 NodeLister 中獲取當(dāng)前系統(tǒng)中存在的全部節(jié)點(diǎn)；
• 調(diào)用 genericScheduler.findNodesThatFit 方法并行執(zhí)行全部的謂詞算法過濾節(jié)點(diǎn)。謂詞算法會根據(jù)傳入的 Pod 和 Node 對節(jié)點(diǎn)進(jìn)行過濾，這時會過濾掉端口號沖突、資源不足的節(jié)點(diǎn)；調(diào)用所有調(diào)度器擴(kuò)展的 Filter 方法輔助過濾；
• 調(diào)用 PrioritizeNodes 函數(shù)為所有的節(jié)點(diǎn)打分。以 Pod 和 Node 作為參數(shù)并發(fā)執(zhí)行同一優(yōu)先級的 PriorityMapFunction；Pod 和優(yōu)先級返回的 Node 到分?jǐn)?shù)的映射為參數(shù)調(diào)用 PriorityReduceFunction 函數(shù)；調(diào)用所有調(diào)度器擴(kuò)展的 Prioritize 方法；將所有分?jǐn)?shù)按照權(quán)重相加后返回從 Node 到分?jǐn)?shù)的映射；
• 調(diào)用 genericScheduler.selectHost 方法選擇得分最高的節(jié)點(diǎn)。

這就是使用謂詞和優(yōu)先級算法時的調(diào)度過程，我們在這里省略了調(diào)度器的優(yōu)先隊列中的排序，出現(xiàn)調(diào)度錯誤時的搶占以及 Pod 持久存儲卷綁定到 Node 上的過程，只保留了核心的調(diào)度邏輯。

調(diào)度框架

Kubernetes 調(diào)度框架是 Babak Salamat 和 Jonathan Basseri 2018 年提出的最新調(diào)度器設(shè)計，這個提案明確了 Kubernetes 中的各個調(diào)度階段，提供了設(shè)計良好的基于插件的接口。調(diào)度框架認(rèn)為 Kubernetes 中目前存在調(diào)度（Scheduling）和綁定（Binding）兩個循環(huán)：

• 調(diào)度循環(huán)在多個 Node 中為 Pod 選擇最合適的 Node；
• 綁定循環(huán)將調(diào)度決策應(yīng)用到集群中，包括綁定 Pod 和 Node、綁定持久存儲等工作。

除了兩個大循環(huán)之外，調(diào)度框架中還包含 QueueSort、PreFilter、Filter、PostFilter、Score、Reserve、Permit、PreBind、Bind、PostBind 和 Unreserve 11 個擴(kuò)展點(diǎn)（Extension Point），這些擴(kuò)展點(diǎn)會在調(diào)度的過程中觸發(fā)，它們的運(yùn)行順序如下：

圖 25 - Kubernetes 調(diào)度框架

我們可以將調(diào)度器中的 Scheduler.scheduleOne 方法作為入口分析基于調(diào)度框架的調(diào)度器實(shí)現(xiàn)，每次調(diào)用該方法都會完成一遍為 Pod 調(diào)度節(jié)點(diǎn)的全部流程，我們將該函數(shù)的執(zhí)行過程分成調(diào)度和綁定兩個階段，首先是調(diào)度器的調(diào)度階段：

func (sched *Scheduler) scheduleOne(ctx context.Context) {
    fwk := sched.Framework
    podInfo := sched.NextPod()
    pod := podInfo.Pod
    state := framework.NewCycleState()
    scheduleResult, _ := sched.Algorithm.Schedule(schedulingCycleCtx, state, pod)
    assumedPod := podInfo.DeepCopy().Pod
    allBound, _ := sched.VolumeBinder.Binder.AssumePodVolumes(assumedPod, scheduleResult.SuggestedHost)
    if err != nil {
        return
    }
    if sts := fwk.RunReservePlugins(schedulingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost); !sts.IsSuccess() {
        return
    }
    if err := sched.assume(assumedPod, scheduleResult.SuggestedHost); err != nil {
        fwk.RunUnreservePlugins(schedulingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost)
        return
    }
    ...
}

• 調(diào)用內(nèi)部優(yōu)先隊列的 MakeNextPodFunc 返回的函數(shù)從隊列中獲取下一個等待調(diào)度的 Pod，用于維護(hù)等待 Pod 的隊列會執(zhí)行 QueueSort 插件；
• 調(diào)用 genericScheduler.Schedule 函數(shù)選擇節(jié)點(diǎn)，該過程會執(zhí)行 PreFilter、Filter、PostFilter、Score 四個擴(kuò)展點(diǎn)的插件；
• 調(diào)用 framework.RunReservePlugins 函數(shù)運(yùn)行 Reserve 插件用于保留資源并進(jìn)入綁定階段（綁定階段運(yùn)行時間較長，避免資源被搶占）。如果運(yùn)行失敗執(zhí)行，調(diào)用 framework.RunUnreservePlugins 函數(shù)運(yùn)行 Unreserve 插件。