排程系統設計精要

作者 | Draveness

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

排程是一個非常廣泛的概念，很多領域都會使用排程這個術語，在計算機科學中，

排程 就是一種将任務（Work）配置設定給資源的方法。任務可能是虛拟的計算任務，例如線程、程序或者資料流，這些任務會被排程到硬體資源上執行，例如：處理器 CPU 等裝置。

圖 1 - 排程系統設計精要

本文會介紹排程系統的常見場景以及設計過程中的一些關鍵問題，排程器的設計最終都會歸結到一個問題上 — 如何對資源高效的配置設定和排程以達到我們的目的，可能包括對資源的合理利用、最小化成本、快速比對供給和需求。

圖 2 - 文章脈絡和内容

除了介紹排程系統設計時會遇到的常見問題之外，本文還會深入分析幾種常見的排程器的設計、演進與實作原理，包括作業系統的程序排程器，Go 語言的運作時排程器以及 Kubernetes 的工作負載排程器，幫助我們了解排程器設計的核心原理。

設計原理

排程系統其實就是排程器（Scheduler），我們在很多系統中都能見到排程器的身影，就像我們在上面說的，不止作業系統中存在排程器，程式設計語言、容器編排以及很多業務系統中都會存在排程系統或者排程子產品。

這些排程子產品的核心作用就是對有限的資源進行配置設定，以實作最大化資源的使用率或者降低系統的尾延遲，排程系統面對的就是資源的需求和供給不平衡的問題。

圖 3 - 排程器的任務和資源

我們在這一節中将從多個方面介紹排程系統設計時需要重點考慮的問題，其中包括排程系統的需求調研、排程原理以及架構設計。

1. 需求調研

在着手建構排程系統之前，首要的工作就是進行詳細的需求調研和分析，在這個過程中需要完成以下兩件事：

• 調研排程系統的應用場景，深入研究場景中待執行的任務（Work）和能用來執行任務的資源（Resource）的特性；
• 分析排程系統的目的，可能是成本優先、品質優先、最大化資源的使用率等，排程目的一般都是動态的，會随着需求的變化而轉變；

應用場景

排程系統應用的場景是我們首先需要考慮的問題，對應用場景的分析至關重要，我們需要深入了解目前場景下待執行任務和能用來執行任務的資源的特點。我們需要分析待執行任務的以下特征：

• 任務是否有截止日期，必須在某個時間點之前完成；
• 任務是否支援搶占，搶占的具體規則是什麼；
• 任務是否包含前置的依賴條件；
• 任務是否隻能在指定的資源上運作；
• ...

而用于執行任務的資源也可能存在資源不平衡，不同資源處理任務的速度不一緻的問題。

資源和任務特點的多樣性決定了排程系統的設計，我們在這裡舉幾個簡單的例子幫助各位讀者了解排程系統需求分析的過程。

圖 4 - Linux 作業系統

在作業系統的程序排程器中，待排程的任務就是線程，這些任務一般隻會處于正在執行或者未執行（等待或者終止）的狀态；而用于處理這些任務的 CPU 往往都是不可再分的，同一個 CPU 在同一時間隻能執行一個任務，這是實體上的限制。簡單總結一下，作業系統排程器的任務和資源有以下特性：

• 任務 —— Thread。狀态簡單：隻會處于正在執行或者未被執行兩種狀态；優先級不同：待執行的任務可能有不同的優先級，在考慮優先級的情況下，需要保證不同任務的公平性；
• 資源 —— CPU 時間。資源不可再分：同一時間隻能運作一個任務；

在上述場景中，待執行的任務是作業系統排程的基本機關 —— 線程，而可配置設定的資源是 CPU 的時間。Go 語言的排程器與作業系統的排程器面對的是幾乎相同的場景，其中的任務是 Goroutine，可以配置設定的資源是在 CPU 上運作的線程。

圖 5 - 容器編排系統 Kubernetes

除了作業系統和程式設計語言這種較為底層的排程器之外，容器和計算任務排程在今天也很常見，Kubernetes 作為容器編排系統會負責調取叢集中的容器，對它稍有了解的人都知道，Kubernetes 中排程的基本單元是 Pod，這些 Pod 會被排程到節點 Node 上執行：

• 任務 —— Pod。優先級不同：Pod 的優先級可能不同，高優先級的系統 Pod 可以搶占低優先級 Pod 的資源；有狀态：Pod 可以分為無狀态和有狀态，有狀态的 Pod 需要依賴持久存儲卷；
• 資源 —— Node。類型不同：不同節點上的資源類型不同，包括 CPU、GPU 和記憶體等，這些資源可以被拆分但是都屬于目前節點；不穩定：節點可能由于突發原因不可用，例如：無網絡連接配接、磁盤損壞等；

排程系統在生活和工作中都很常見，除了上述的兩個場景之外，其他需要排程系統的場景包括 CDN 的資源排程、訂單排程以及離線任務排程系統等。在不同場景中，我們都需要深入思考任務和資源的特性，它們對系統的設計起者指導作用。

排程目的

在深入分析排程場景後，我們需要了解排程的目的。我們可以将排程目的了解成機器學習中的成本函數（Cost function），确定排程目的就是确定成本函數的定義，排程理論一書中曾經介紹過常見的

，包含以下内容：

• 完成跨度（Makesapan） — 第一個到最後一個任務完成排程的時間跨度；
• 最大延遲（Maximum Lateness） — 超過截止時間最長的任務；
• 權重完成時間的和（Total weighted completion time）— 權重乘完成時間的總和；

這些都是偏理論的排程的目的，多數業務排程系統的排程目的都是優化與業務聯系緊密的名額 — 成本和品質。如何在成本和品質之間達到平衡是需要仔細思考和設計的，由于篇幅所限以及業務場景的複雜，本文不會分析如何權衡成本和品質，這往往都是需要結合業務考慮的事情，不具有足夠的相似性。

2. 排程原理

性能優異的排程器是實作特定排程目的前提，我們在讨論排程場景和目的時往往都會忽略排程的額外開銷，然而排程器執行時的延時和吞吐量等名額在排程負載較重時是不可忽視的。本節會分析與排程器實作相關的一些重要概念，這些概念能夠幫助我們實作高性能的排程器：

• 協作式排程與搶占式排程；
• 單排程器與多排程器；
• 任務分享與任務竊取；

協作式與搶占式

協作式（Cooperative）與搶占式（Preemptive）排程是作業系統中常見的多任務運作政策。這兩種排程方法的定義完全不同：

• 協作式排程允許任務執行任意長的時間，直到任務主動通知排程器讓出資源；
• 搶占式排程允許任務在執行過程中被排程器挂起，排程器會重新決定下一個運作的任務；

圖 6 - 協作式排程與搶占式排程

任務的執行時間和任務上下文切換的額外開銷決定了哪種排程方式會帶來更好的性能。如下圖所示，圖 7 展示了一個協作式排程器排程任務的過程，排程器一旦為某個任務配置設定了資源，它就會等待該任務主動釋放資源，圖中 4 個任務盡管執行時間不同，但是它們都會在任務執行完成後釋放資源，整個過程也隻需要 4 次上下文的切換。

圖 7 - 協作式排程

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

圖 8 - 搶占式排程

如果部分任務的執行時間很長，協作式的任務排程會使部分執行時間長的任務餓死其他任務；不過如果待執行的任務執行時間較短并且幾乎相同，那麼使用協作式的任務排程能減少任務中斷帶來的額外開銷，進而帶來更好的排程性能。

因為多數情況下任務執行的時間都不确定，在協作式排程中一旦任務沒有主動讓出資源，那麼就會導緻其它任務等待和阻塞，是以排程系統一般都會以搶占式的任務排程為主，同時支援任務的協作式排程。

單排程器與多排程器

使用單個排程器還是多個排程器也是設計排程系統時需要仔細考慮的，多個排程器并不一定意味着多個程序，也有可能是一個程序中的多個排程線程，它們既可以選擇在多核上并行排程、在單核上并發排程，也可以同時利用并行和并發提高性能。

圖 9 - 單排程器排程任務和資源

不過對于排程系統來說，因為它做出的決策會改變資源的狀态和系統的上下文進而影響後續的排程決策，是以單排程器的串行排程是能夠精準排程資源的唯一方法。單個排程器利用不同管道收集排程需要的上下文，并在收到排程請求後會根據任務和資源情況做出當下最優的決策。

随着排程器的不斷演變，單排程器的性能和吞吐量可能會受到限制，我們還是需要引入并行或者并發排程來解決性能上的瓶頸，這時我們需要将待排程的資源分區，讓多個排程器分别負責排程不同區域中的資源。

圖 10 - 多排程器與資源分區

多排程器的并發排程能夠極大提升排程器的整體性能，例如 Go 語言的排程器。Go 語言運作時會将多個 CPU 交給不同的處理器分别排程，這樣通過并行排程能夠提升排程器的性能。

上面介紹的兩種排程方法都建立在需要精準排程的前提下，多排程器中的每一個排程器都會面對無關的資源，是以對于同一個分區的資源，排程還是串行的。

圖 11 - 多排程器粗粒度排程

使用多個排程器同時排程多個資源也是可行的，隻是可能需要犧牲排程的精确性 — 不同的排程器可能會在不同時間接收到狀态的更新，這就會導緻不同排程器做出不同的決策。負載均衡就可以看做是多線程和多程序的排程器，因為對任務和資源掌控的資訊有限，這種粗粒度排程的結果很可能就是不同機器的負載會有較大差異，是以無論是小規模叢集還是大規模叢集都很有可能導緻某些執行個體的負載過高。

工作分享與工作竊取

這一小節将繼續介紹在多個排程器間重新配置設定任務的

兩個排程範式

 — 工作分享（Work Sharing）和工作竊取（Work Stealing）。獨立的排程器可以同時處理所有的任務和資源，是以它不會遇到多排程器的任務和資源的不平衡問題。在多數的排程場景中，任務的執行時間都是不确定的，假設多個排程器分别排程相同的資源，由于任務的執行時間不确定，多個排程器中等待排程的任務隊列最終會發生差異 — 部分隊列中包含大量任務，而另外一些隊列不包含任務，這時就需要引入任務再配置設定政策。

工作分享和工作竊取是完全不同的兩種再配置設定政策。在工作分享中，當排程器建立了新任務時，它會将一部分任務分給其他排程器；而在工作竊取中，當排程器的資源沒有被充分利用時，它會從其他排程器中竊取一些待配置設定的任務，如下圖所示：

圖 12 - 工作竊取排程器

這兩種任務再配置設定的政策都為系統增加了額外的開銷，與工作分享相比，工作竊取隻會在目前排程器的資源沒有被充分利用時才會觸發，是以工作竊取引入的額外開銷更小。工作竊取在生産環境中更加常用，Linux 作業系統和 Go 語言都選擇了工作竊取政策。

3. 架構設計

本節将從排程器内部和外部兩個角度分析排程器的架構設計，前者分析排程器内部多個元件的關系和做出排程決策的過程；後者分析多個排程器應該如何協作，是否有其他的外部服務可以輔助排程器做出更合理的排程決策。

排程器内部

當排程器收到待排程任務時，會根據采集到的狀态和待排程任務的規格（Spec）做出合理的排程決策，我們可以從下圖中了解常見排程系統的内部邏輯。

圖 13 - 排程器做出排程決策

常見的排程器一般由兩部分組成 — 用于收集狀态的狀态子產品和負責做決策的決策子產品。

• 狀态子產品

狀态子產品會從不同途徑收集盡可能多的資訊為排程提供豐富的上下文，其中可能包括資源的屬性、使用率和可用性等資訊。根據場景的不同，上下文可能需要存儲在 MySQL 等持久存儲中，一般也會在記憶體中緩存一份以減少排程器通路上下文的開銷。

• 決策子產品

決策子產品會根據狀态子產品收集的上下文和任務的規格做出排程決策，需要注意的是做出的排程決策隻是在當下有效，在未來某個時間點，狀态的改變可能會導緻之前做的決策不符合任務的需求，例如：當我們使用 Kubernetes 排程器将工作負載排程到某些節點上，這些節點可能由于網絡問題突然不可用，該節點上的工作負載也就不能正常工作，即排程決策失效。

排程器在排程時都會通過以下的三個步驟為任務排程合适的資源：

1. 通過優先級、任務建立時間等資訊确定不同任務的排程順序；
2. 通過過濾和打分兩個階段為任務選擇合适的資源；
3. 不存在滿足條件的資源時，選擇犧牲的搶占對象。

圖 14 - 排程架構

上圖展示了常見排程器決策子產品執行的幾個步驟，确定優先級、對閑置資源進行打分、确定搶占資源的犧牲者，上述三個步驟中的最後一個往往都是可選的，部分排程系統不需要支援搶占式排程的功能。

排程器外部

如果我們将排程器看成一個整體，從排程器外部看架構設計就會得到完全不同的角度 — 如何利用外部系統增強排程器的功能。在這裡我們将介紹兩種排程器外部的設計，分别是多排程器和反排程器（Descheduler）。

• 多排程器

串行排程與并行排程一節已經分析了多排程器的設計，我們可以将待排程的資源進行分區，讓多個排程器線程或者程序分别負責各個區域中資源的排程，充分利用多和 CPU 的并行能力。

• 反排程器

反排程器是一個比較有趣的概念，它能夠移除決策不再正确的排程，降低系統中的熵，讓排程器根據目前的狀态重新決策。

圖 15 - 排程器與反排程器

反排程器的引入使得整個排程系統變得更加健壯。排程器負責根據目前的狀态做出正确的排程決策，反排程器根據目前的狀态移除錯誤的排程決策，它們的作用看起來相反，但是目的都是為任務排程更合适的資源。

反排程器的使用沒有那麼廣泛，實際的應用場景也比較有限。作者第一次發現這個概念是在 Kubernetes 孵化的

descheduler

 項目中，不過因為反排程器移除排程關系可能會影響正在運作的線上服務，是以 Kubernetes 也隻會在特定場景下使用。

作業系統

排程器是作業系統中的重要元件，作業系統中有程序排程器、網絡排程器和 I/O 排程器等元件，本節介紹的是作業系統中的程序排程器。

有一些讀者可能會感到困惑，作業系統排程的最小機關不是線程麼，為什麼這裡使用的是程序排程。在 Linux 作業系統中，排程器排程的不是程序也不是線程，它排程的是 task_struct 結構體，該結構體既可以表示線程，也可以表示程序，而排程器會将程序和線程都看成任務，我們在這裡先

說明

這一問題，避免讀者感到困惑。我們會使用程序排程器這個術語，但是一定要注意 Linux 排程器中并不區分線程和程序。

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).

接下來，本節會研究作業系統中排程系統的類型以及 Linux 程序排程器的演進過程。

1. 排程系統類型

作業系統會将程序排程器分成三種不同的類型，即長期排程器、中期排程器和短期排程器。這三種不同類型的排程器分别提供了不同的功能，我們将在這一節中依次介紹它們。

長期排程器

長期排程器（Long-Term Scheduler）也被稱作任務排程器（Job Scheduler），它能夠決定哪些任務會進入排程器的準備隊列。當我們嘗試執行新的程式時，長期排程器會負責授權或者延遲該程式的執行。長期排程器的作用是平衡同時正在運作的 I/O 密集型或者 CPU 密集型程序的任務數量：

• 如果 I/O 密集型任務過多，就緒隊列中就不存在待排程的任務，短期排程器不需要執行排程，CPU 資源就會面臨閑置；
• 如果 CPU 密集型任務過多，I/O 等待隊列中就不存在待排程的任務，I/O 裝置就會面臨閑置；

長期排程器能平衡同時正在運作的 I/O 密集型和 CPU 密集型任務，最大化的利用作業系統的 I/O 和 CPU 資源。

中期排程器

中期排程器會将不活躍的、低優先級的、發生大量頁錯誤的或者占用大量記憶體的程序從記憶體中移除，為其他的程序釋放資源。

圖 16 - 中期排程器

當正在運作的程序陷入 I/O 操作時，該程序隻會占用計算資源，在這種情況下，中期排程器就會将它從記憶體中移除等待 I/O 操作完成後，該程序會重新加入就緒隊列并等待短期排程器的排程。

短期排程器

短期排程器應該是我們最熟悉的排程器，它會從就緒隊列中選出一個程序執行。程序的選擇會使用特定的排程算法，它會同時考慮程序的優先級、入隊時間等特征。因為每個程序能夠得到的執行時間有限，是以短期排程器的執行十分頻繁。

2. 設計與演進

本節将重點介紹 Linux 的 CPU 排程器，也就是短期排程器。Linux 的 CPU 排程器并不是從設計之初就是像今天這樣複雜的，在很長的一段時間裡（v0.01 ~ v2.4），Linux 的程序排程都由幾十行的簡單函數負責，我們先了解一下不同版本排程器的曆史：

• 初始排程器 · v0.01 ~ v2.4。由幾十行代碼實作，功能非常簡陋；同時最多處理 64 個任務；
• 排程器 · v2.4 ~ v2.6。排程時需要周遊全部任務當待執行的任務較多時，同一個任務兩次執行的間隔很長，會有比較嚴重的饑餓問題；
• 排程器 · v2.6.0 ~ v2.6.22。通過引入運作隊列和優先數組實作  的時間複雜度；使用本地運作隊列替代全局運作隊列增強在對稱多處理器的擴充性；引入工作竊取保證多個運作隊列中任務的平衡；
• 完全公平排程器 · v2.6.23 ~ 至今。引入紅黑樹和運作時間保證排程的公平性；引入排程類實作不同任務類型的不同排程政策；

這裡會詳細介紹從最初的排程器到今天複雜的完全公平排程器（Completely Fair Scheduler，CFS）的演變過程。

初始排程器

Linux 最初的程序排程器僅由 sched.h 和 sched.c 兩個檔案構成。你可能很難想象 Linux 早期版本使用隻有幾十行的 schedule 函數負責了

作業系統程序的排程

：

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);
}           

無論是程序還是線程，在 Linux 中都被看做是 task_struct 結構體，所有的排程程序都存儲在上限僅為 64 的數組中，排程器能夠處理的程序上限也隻有 64 個。

圖 17 - 最初的程序排程器

上述函數會先喚醒獲得信号的可中斷程序，然後從隊列倒序查找計數器 counter 最大的可執行程序，counter 是程序能夠占用的時間切片數量，該函數會根據時間切片的值執行不同的邏輯：

• 如果最大的 counter 時間切片大于 0，調用彙編語言的實作的 switch_to 切換程序；
• 如果最大的 counter 時間切片等于 0，意味着所有程序的可執行時間都為 0，那麼所有程序都會獲得新的時間切片；

Linux 作業系統的計時器會每隔 10ms 觸發一次 do_timer 将目前正在運作程序的 counter 減一，目前程序的計數器歸零時就會重新觸發排程。

O(n)排程器

 排程器是 Linux 在 v2.4 ~ v2.6 版本使用的排程器，由于該調取器在最壞的情況下會周遊所有的任務，是以它排程任務的時間複雜度就是 。Linux 排程算法将 CPU 時間分割成了不同的時期（Epoch），也就是每個任務能夠使用的時間切片。

我們可以在 sched.h 和 sched.c 兩個檔案中找到排程器的源代碼。與上一個版本的排程器相比， 排程器的實作複雜了很多，該排程器會在 schedule 函數中

周遊

運作隊列中的所有任務并調用 goodness 函數分别計算它們的權重獲得下一個運作的程序：

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;
        }
    }
    ...
}           

在每個時期開始時，上述代碼都會為所有的任務計算時間切片，因為需要執行 n 次，是以排程器被稱作  排程器。在預設情況下，每個任務在一個周期都會配置設定到 200ms 左右的時間切片，然而這種排程和配置設定方式是  排程器的最大問題：

• 每輪排程完成之後就會陷入沒有任務需要排程的情況，需要提升互動性能的場景會受到嚴重影響，例如：在桌面拖動滑鼠會感覺到明顯的卡頓；
• 每次查找權重最高的任務都需要周遊數組中的全部任務；
• 排程器 配置設定 的平均時間片大小為 210ms，當程式中包含 100 個程序時，同一個程序被運作兩次的間隔是 21s，這嚴重影響了作業系統的可用性.

正是因為排程器存在了上述的問題，是以 Linux 核心在兩個版本後使用新的  排程器替換該實作。

O(1)排程器

排程器在 v2.6.0 到 v2.6.22 的 Linux 核心中使用了四年的時間，它能夠在常數時間内完成程序排程，你可以在sched.h 和 sched.c 中檢視  排程器的源代碼。因為實作和功能複雜性的增加，排程器的代碼行數從  的 2100 行增加到 5000 行，它在排程器的基礎上進行了如下的

改進

• 排程器支援了  時間複雜度的排程；
• 排程器支援了對稱多處理（Symmetric multiprocessing，SMP）的擴充性；
• 排程器優化了對稱多處理的親和性。

資料結構

排程器通過運作隊列 runqueue 和優先數組 prio_array 兩個重要的資料結構實作了  的時間複雜度。每一個運作隊列都持有兩個優先數組，分别存儲活躍的和過期的程序數組：

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];
};           

優先數組中的 nr_active 表示活躍的程序數，而 bitmap 和 list_head 共同組成了如下圖所示的資料結構：

圖 18 - 優先數組

優先數組的 bitmap 總共包含 140 位，每一位都表示對應優先級的程序是否存在。圖 17 中的優先數組包含 3 個優先級為 2 的程序和 1 個優先級為 5 的程序。每一個優先級的标志位都對應一個 list_head 數組中的連結清單。 排程器使用上述的資料結構進行如下所示的排程：

• 調用 sched_find_first_bit 按照優先級配置設定 CPU 資源；
• 調用 schedule 從連結清單頭選擇程序執行；
• 通過 schedule 輪訓排程同一優先級的程序，該函數在每次選中待執行的程序後，将程序添加到隊列的末尾，這樣可以保證同一優先級的程序會依次執行（Round-Robin）；
• 計時器每隔 1ms 會觸發一次 scheduler_tick 函數，如果目前程序的執行時間已經耗盡，就會将其移入過期數組；
• 當活躍隊列中不存在待運作的程序時，schedule 會交換活躍優先數組和過期優先數組；

上述的這些規則是  排程器運作遵守的主要規則，除了上述規則之外，排程器還需要支援搶占、CPU 親和等功能，不過在這裡就不展開介紹了。

本地運作隊列

全局的運作隊列是  排程器難以在對稱多處理器架構上擴充的主要原因。為了保證運作隊列的一緻性，排程器在排程時需要擷取運作隊列的全局鎖，随着處理器數量的增加，多個處理器在排程時會導緻更多的鎖競争，嚴重影響排程性能。 排程器通過引入本地運作隊列解決這個問題，不同的 CPU 可以通過 this_rq 擷取綁定在目前 CPU 上的運作隊列，降低了鎖的粒度和沖突的可能性。

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

圖 19 - 全局運作隊列和本地運作隊列

多個處理器由于不再需要共享全局的運作隊列，是以增強了在對稱對處理器架構上的擴充性，當我們增加新的處理器時，隻需要增加新的運作隊列，這種方式不會引入更多的鎖沖突。

優先級和時間切片

排程器中包含兩種不同的優先級計算方式，一種是靜态任務優先級，另一種是動态任務優先級。在預設情況下，任務的靜态任務優先級都是 0，不過我們可以通過系統調用 nice 改變任務的優先級； 排程器會獎勵 I/O 密集型任務并懲罰 CPU 密集型任務，它會通過改變任務的靜态優先級來完成優先級的動态調整，因為與使用者互動的程序時 I/O 密集型的程序，這些程序由于排程器的動态政策會提高自身的優先級，進而提升使用者體驗。

完全公平排程器

完全公平排程器（Completely Fair Scheduler，CFS）是 v2.6.23 版本被合入核心的排程器，也是核心的預設程序排程器，它的目的是最大化 CPU 使用率和互動的

性能

。Linux 核心版本 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 的名字我們就能發現，該排程器的能為不同的程序提供完全公平性。一旦某些程序受到了不公平的待遇，排程器就會運作這些程序，進而維持所有程序運作時間的公平性。這種保證公平性的方式與『水多了加面，面多了加水』有一些相似：

• 排程器會查找運作隊列中受到最不公平待遇的程序，并為程序配置設定計算資源，配置設定的計算資源是與其他資源運作時間的內插補點加上最小能夠運作的時間機關；
• 程序運作結束之後發現運作隊列中又有了其他的程序受到了最不公平的待遇，排程器又會運作新的程序；

排程器算法不斷計算各個程序的運作時間并依次排程隊列中的受到最不公平對待的程序，保證各個程序的運作時間差不會大于最小運作的時間機關。

雖然我們還是會延用運作隊列這一術語，但是 CFS 的内部已經不再使用隊列來存儲程序了，cfs_rq 是用來管理待運作程序的新結構體，該結構體會使用紅黑樹（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）是平衡的

二叉搜尋樹

，紅黑樹的增删改查操作的最壞時間複雜度為 ，也就是樹的高度，樹中最左側的節點 rb_leftmost 運作的時間最短，也是下一個待運作的程序。

注：在最新版本的 CFS 實作中，核心使用虛拟運作時間 vruntime 替代了等待時間，但是基本的排程原理和排序方式沒有太多變化。

排程過程

CFS 的排程過程還是由 schedule 函數完成的，該函數的執行過程可以分成以下幾個步驟：

• 關閉目前 CPU 的搶占功能；
• 如果目前 CPU 的運作隊列中不存在任務，調用 idle_balance 從其他 CPU 的運作隊列中取一部分執行；
• 調用 pick_next_task 選擇紅黑樹中優先級最高的任務；
• 調用 context_switch 切換運作的上下文，包括寄存器的狀态和堆棧；
• 重新開啟目前 CPU 的搶占功能。

CFS 的排程過程與  排程器十分類似，目前排程器與前者的差別隻是增加了可選的工作竊取機制并改變了底層的資料結構。

排程類

CFS 中的排程類是比較有趣的概念，排程類可以決定程序的排程政策。每個排程類都包含一組負責排程的函數，排程類由如下所示的 sched_class 結構體表示：

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);
};           

排程類中包含任務的初始化、入隊和出隊等函數，這裡的設計與面向對象中的設計稍微有些相似。核心中包含 SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE、SCHED_FIFO 和 SCHED_RR 排程類，這些不同的排程類分别實作了 sched_class 中的函數以提供不同的排程行為。

3. 小結

本節介紹了作業系統排程器的設計原理以及演進的曆史，從 2007 年合入 CFS 到現在已經過去了很長時間，目前的

也變得更加複雜，社群也在不斷改進程序排程器。

我們可以從 Linux 排程器的演進的過程看到主流系統架構的變化，最初幾十行代碼的排程器就能完成基本的排程功能，而現在要使用幾萬行代碼來完成複雜的排程，保證系統的低延時和高吞吐量。

由于篇幅有限，我們很難對作業系統的排程器進行面面俱到的分析，你可以在 這裡 找到作者使用的 Linux 源代碼，親自動手分析不同版本的程序排程器。

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 語言的印象都是文法簡單，能夠支撐高并發的服務。文法簡單是程式設計語言的頂層設計哲學，而語言的高并發支援依靠的是運作時的排程器，這也是本節将要研究的内容。

對 Go 語言稍微有了解的人都知道，

通信順序程序

（Communicating sequential processes，CSP）影響着 Go 語言的并發模型，其中的 Goroutine 和 Channel 分别表示實體和用于通信的媒介。

圖 20 - Go 和 Erlang 的并發模型

『不要通過共享記憶體來通信，我們應該使用通信來共享記憶體』不隻是 Go 語言鼓勵的設計哲學，更為古老的 Erlang 語言其實也遵循了同樣的設計，但是 Erlang 選擇使用了

Actor 模型

，我們在這裡就不介紹 CSP 和 Actor 的差別和聯系的，感興趣的讀者可以在推薦閱讀和應引用中找到相關資源。

1. 設計與演進

今天的 Go 語言排程器有着非常優異的性能，但是如果我們回過頭重新看 Go 語言的 v0.x 版本的排程器就會發現最初的排程器非常簡陋，也無法支撐高并發的服務。整個排程器經過幾個大版本的疊代才有了今天的優異性能。

• 單線程排程器 · 0.x - 源代碼。隻包含 40 多行代碼；隻能單線程排程，由 G-M 模型組成；
• 多線程排程器 · 1.0 - 源代碼。引入了多線程排程；全局鎖導緻競争嚴重；
• 任務竊取排程器 · 1.1 - 源代碼。引入了處理器 P，構成了目前的 G-M-P 模型；在處理器 P 的基礎上實作了基于工作竊取的排程器；在某些情況下，Goroutine 不會讓出線程造成饑餓問題；時間過長的程式暫停（Stop-the-world，STW）會導緻程式無法工作；
• 搶占式排程器 · 1.2 ~ 至今 - 源代碼。實作基于信号的真搶占式排程；垃圾回收對棧進行掃描時會觸發搶占排程；搶占的時間點不夠多，還不能覆寫全部的邊緣情況；通過編譯器在函數調用時插入檢查指令，實作基于協作的搶占式排程；GC 和循環可能會導緻 Goroutine 長時間占用資源導緻程式暫停；協作的搶占式排程器 - 1.2 ~ 1.13；搶占式排程器 - 1.14 ~ 至今；
• 非均勻存儲通路排程器 · 提案。對運作時中的各種資源進行分區；實作非常複雜，到今天還沒有提上日程；

除了多線程、任務竊取和搶占式排程器之外，Go 語言社群目前還有一個非均勻存儲通路（Non-uniform memory access，NUMA）排程器的提案，将來有一天可能 Go 語言會實作這個排程器。在這一節中，我們将依次介紹不同版本排程器的實作以及未來可能會實作的排程器提案。

單線程排程器

Go 語言在 0.x 版本排程器中隻包含表示 Goroutine 的 G 和表示線程的 M 兩種結構體，全局也隻有一個線程。我們可以在 clean up scheduler 送出中找到單線程排程器的源代碼，在這時 Go 語言的 排程器 還是由 C 語言實作的，排程函數 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);
}           

該函數會遵循如下所示的過程執行：

• 擷取排程器的全局鎖；
• 調用 gosave 儲存棧寄存器和程式計數器；
• 調用 nextgandunlock 擷取下一個線程 M 需要運作的 Goroutine 并解鎖排程器；
• 修改全局線程 m 上要執行的 Goroutine；
• 調用 gogo 函數運作最新的 Goroutine。

這個單線程排程器的唯一優點就是能跑，不過從這次送出中我們能看到 G 和 M 兩個重要的資料結構，它建立了 Go 語言排程器的架構。

多線程排程器

Go 語言 1.0 版本在正式釋出時就支援了多線程的排程器，與上一個版本完全不可用的排程器相比，Go 語言團隊在這一階段完成了從不可用到可用。我們可以在 proc.c 中找到 1.0.1 版本的排程器，多線程版本的排程函數 schedule 包含 70 多行代碼，我們在這裡保留了其中的核心邏輯：

static void schedule(G *gp) {
    schedlock();
    if(gp != nil) {
        gp->m = nil;
        uint32 v = runtime·xadd(&runtime·sched.atomic, -1<<mcpuShift);
        if(atomic_mcpu(v) > 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);
}           

整體的邏輯與單線程排程器沒有太多差別，多線程排程器引入了 GOMAXPROCS 變量幫助我們控制程式中的最大線程數，這樣我們的程式中就可能同時存在多個活躍線程。

多線程排程器的主要問題是排程時的鎖競争，Scalable Go Scheduler Design Doc 中對排程器做的

性能測試

發現 14% 的時間都花費在 runtime.futex 函數上，目前的排程器實作有以下問題需要解決：

• 全局唯一的排程器和全局鎖，所有的排程狀态都是中心化存儲的，帶來了鎖競争；
• 線程需要經常互相傳遞可運作的 Goroutine，引入了大量的延遲和額外開銷；
• 每個線程都需要處理記憶體緩存，導緻大量的記憶體占用并影響資料局部性（Data locality）；
• 系統調用頻繁阻塞和解除阻塞正在運作的線程，增加了額外開銷。

這裡的全局鎖問題和 Linux 作業系統排程器在早期遇到的問題比較相似，解決方案也都大同小異。

任務竊取排程器

2012 年 Google 的工程師 Dmitry Vyukov 在 Scalable Go Scheduler Design Doc 中指出了現有多線程排程器的問題并在多線程排程器上提出了兩個改進的手段：

• 在目前的 G-M 模型中引入了處理器 P；
• 在處理器 P 的基礎上實作基于工作竊取的排程器。

基于任務竊取的 Go 語言排程器使用了沿用至今的 G-M-P 模型，我們能在 runtime: improved scheduler 送出中找到任務竊取排程器剛被實作時的源代碼，排程器的 schedule 函數到現在反而更簡單了：

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

• 如果目前運作時在等待垃圾回收，調用 gcstopm 函數；
• 調用 runqget 和 findrunnable 從本地的或者全局的運作隊列中擷取待執行的 Goroutine；
• 調用 execute 函數在目前線程 M 上運作 Goroutine。

目前處理器本地的運作隊列中不包含 Goroutine 時，調用 findrunnable 函數會觸發工作竊取，從其他的處理器的隊列中随機擷取一些 Goroutine。

運作時 G-M-P 模型中引入的處理器 P 是線程 M 和 Goroutine 之間的中間層，我們從它的結構體中就能看到 P 與 M 和 G 的關系：

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 持有一個運作隊列 runq，這是由可運作的 Goroutine 組成的數組，它還反向持有一個線程 M 的指針。排程器在排程時會從處理器的隊列中選擇隊列頭的 Goroutine 放到線程 M 上執行。如下所示的圖檔展示了 Go 語言中的線程 M、處理器 P 和 Goroutine 的關系。

圖 21 - G-M-P 模型

基于工作竊取的多線程排程器将每一個線程綁定到了獨立的 CPU 上并通過不同處理器分别管理，不同處理器中通過工作竊取對任務進行再配置設定，提升了排程器和 Go 語言程式的整體性能，今天所有的 Go 語言服務的高性能都受益于這一改動。

搶占式排程器

對 Go 語言并發模型的修改提升了排程器的性能，但是在 1.1 版本中的排程器仍然不支援搶占式排程，程式隻能依靠 Goroutine 主動讓出 CPU 資源。Go 語言的排程器在

1.2 版本

中引入了基于協作的搶占式排程解決下面的

問題

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

然而 1.2 版本中實作的搶占式排程是基于協作的，在很長的一段時間裡 Go 語言的排程器都包含一些無法被搶占的邊緣情況，直到 1.14 才實作了基于信号的真搶占式排程解決部分問題。

基于協作的搶占式排程

我們可以在 proc.c 檔案中找到引入搶占式排程後的排程器實作。Go 語言會在目前的分段棧機制上實作搶占式的排程，所有的 Goroutine 在函數調用時都有機會進入運作時檢查是否需要執行搶占。基于協作的搶占是通過以下的多個送出實作的：

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

從上述一系列的送出中，我們會發現 Go 語言運作時會在垃圾回收暫停程式、系統監控發現 Goroutine 運作超過 10ms 時提出搶占請求 StackPreempt；因為編譯器會在函數調用中插入 runtime.newstack，是以函數調用時會通過 runtime.newstack 檢查 Goroutine 的 stackguard0 是否為 StackPreempt 進而觸發搶占讓出目前線程。

這種做法沒有帶來運作時的過多額外開銷，實作也相對比較簡單，不過增加了運作時的複雜度，總體來看還是一種比較成功的實作。因為上述的搶占是通過編譯器在特定時機插入函數實作的，還是需要函數調用作為入口才能觸發搶占，是以這是一種協作式的搶占式排程。

基于信号的搶占式排程

協作的搶占式排程實作雖然巧妙，但是留下了很多的邊緣情況，我們能在 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 版本中實作了非協作的搶占式排程，在實作的過程中我們對已有的邏輯進行重構并為 Goroutine 增加新的狀态和字段來支援搶占。Go 團隊通過下面送出的實作了這一功能，我們可以順着送出的順序了解其實作原理：

• runtime: add general suspendG/resumeG。挂起 Goroutine 的過程是在棧掃描時完成的，我們通過 runtime.suspendG 和 runtime.resumeG 兩個函數重構棧掃描這一過程；調用 runtime.suspendG 函數時會将運作狀态的 Goroutine 的 preemptStop 标記成 true；調用 runtime.preemptPark 函數可以挂起目前 Goroutine、将其狀态更新成 _Gpreempted 并觸發排程器的重新排程，該函數能夠交出線程控制權；
• runtime: asynchronous preemption function for x86。在 x86 架構上增加異步搶占的函數 runtime.asyncPreempt 和 runtime.asyncPreempt2；
• runtime: use signals to preempt Gs for suspendG。支援通過向線程發送信号的方式暫停運作的 Goroutine；在 runtime.sighandler 函數中注冊了 SIGURG 信号的處理函數 runtime.doSigPreempt；runtime.preemptM 函數可以向線程發送搶占請求；
• runtime: implement async scheduler preemption。修改 runtime.preemptone 函數的實作，加入異步搶占的邏輯。

目前的搶占式排程也隻會在垃圾回收掃描任務時觸發，我們可以梳理一下觸發搶占式排程的過程：

• 程式啟動時，在 runtime.sighandler 函數中注冊了 SIGURG 信号的處理函數 runtime.doSigPreempt；
• 在觸發垃圾回收的棧掃描時會調用 runtime.suspendG 函數挂起 Goroutine。将 _Grunning 狀态的 Goroutine 标記成可以被搶占，即 preemptStop 設定成 true；調用 runtime.preemptM 函數觸發搶占；
• runtime.preemptM 函數會調用 runtime.signalM 向線程發送信号 SIGURG；
• 作業系統會中斷正在運作的線程并執行預先注冊的信号處理函數 runtime.doSigPreempt；
• runtime.doSigPreempt 函數會處理搶占信号，擷取目前的 SP 和 PC 寄存器并調用 runtime.sigctxt.pushCall；
• runtime.sigctxt.pushCall 會修改寄存器并在程式回到使用者态時從 runtime.asyncPreempt 開始執行；
• 彙編指令 runtime.asyncPreempt 會調用運作時函數 runtime.asyncPreempt2；
• runtime.asyncPreempt2 會調用 runtime.preemptPark 函數；
• runtime.preemptPark 會修改目前 Goroutine 的狀态到 _Gpreempted 并調用 runtime.schedule 讓目前函數陷入休眠并讓出線程，排程器會選擇其他的 Goroutine 繼續執行；

上述 9 個步驟展示了基于信号的搶占式排程的執行過程。我們還需要讨論一下該過程中信号的選擇，提案根據以下的四個原因選擇 SIGURG 作為觸發異步搶占的

信号

• 該信号需要被調試器透傳；
• 該信号不會被内部的 libc 庫使用并攔截；
• 該信号可以随意出現并且不觸發任何後果；
• 我們需要處理多個平台上的不同信号。

目前的搶占式排程也沒有解決所有潛在的問題，因為 STW 和棧掃描時更可能出現問題，也是一個可以搶占的安全點（Safe-points），是以我們會在這裡先加入

搶占功能

，在未來可能會加入更多搶占時間點。

非均勻記憶體通路排程器

非均勻記憶體通路（Non-uniform memory access，NUMA）排程器目前隻是 Go 語言的

提案

，因為該提案過于複雜，而目前的排程器的性能已經足夠優異，是以暫時沒有實作該提案。該提案的原理就是通過拆分全局資源，讓各個處理器能夠就近擷取本地資源，減少鎖競争并增加資料局部性。

在目前的運作時中，線程、處理器、網絡輪訓器、運作隊列、全局記憶體配置設定器狀态、記憶體配置設定緩存和垃圾收集器都是全局的資源。運作時沒有保證本地化，也不清楚系統的拓撲結構，部分結構可以提供一定的局部性，但是從全局來看沒有這種保證。

圖 22 - Go 語言 NUMA 排程器

如上圖所示，堆棧、全局運作隊列和線程池會按照 NUMA 節點進行分區，網絡輪訓器和計時器會由單獨的處理器持有。這種方式雖然能夠利用局部性提高排程器的性能，但是本身的實作過于複雜，是以 Go 語言團隊還沒有着手實作這一提案。

2. 小結

Go 語言的排程器在最初的幾個版本中迅速疊代，但是從 1.2 版本之後排程器就沒有太多的變化，直到 1.14 版本引入了真正的搶占式排程解決了自 1.2 以來一直存在的問題。在可預見的未來，Go 語言的排程器還會進一步演進，增加搶占式排程的時間點減少存在的邊緣情況。

本節内容選擇《Go 語言設計與實作》一書中的 Go 語言排程器實作原理，你可以點選連結了解更多與 Go 語言設計與實作原理相關的内容。

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 是生産級别的容器排程和管理系統，在過去的一段時間中，Kubernetes 迅速占領市場，成為容器編排領域的實施标準。

圖 23 - 容器編排系統演進

Kubernetes 是希臘語『舵手』的意思，它最開始由 Google 的幾位軟體工程師創立，深受公司内部

Borg 和 Omega 項目

的影響，很多設計都是從 Borg 中借鑒的，同時也對 Borg 的缺陷進行了改進，Kubernetes 目前是 Cloud Native Computing Foundation (CNCF) 的項目，也是很多公司管理分布式系統的

解決方案

。

排程器是 Kubernetes 的核心元件，它的主要功能是為待運作的工作負載 Pod 綁定運作的節點 Node。與其他排程場景不同，雖然資源使用率在 Kubernetes 中也非常重要，但是這隻是 Kubernetes 關注的一個因素，它需要在容器編排這個場景中支援非常多并且複雜的業務需求，除了考慮 CPU 和記憶體是否充足，還需要考慮其他的領域特定場景，例如：兩個服務不能占用同一台機器的相同端口、幾個服務要運作在同一台機器上，根據節點的類型排程資源等。

這些複雜的業務場景和排程需求使 Kubernetes 排程器的内部設計與其他排程器完全不同，但是作為使用者應用層的排程器，我們卻能從中學到很多有用的模式和設計。接下來，本節将介紹 Kubernetes 中排程器的設計以及演變。

Kubernetes 排程器的演變過程比較簡單，我們可以将它的演進過程分成以下的兩個階段：

• 基于謂詞和優先級的排程器 · v1.0.0 ~ v1.14.0
• 基于排程架構的排程器 · v1.15.0 ~ 至今

Kubernetes 從 v1.0.0 版本釋出到 v1.14.0，總共 15 個版本一直都在使用謂詞和優先級來管理不同的排程算法，知道 v1.15.0 開始引入排程架構（Alpha 功能）來重構現有的排程器。我們在這裡将以 v1.14.0 版本的謂詞和優先級和 v1.17.0 版本的排程架構分析排程器的演進過程。

謂詞和優先級算法

謂詞（Predicates）和優先級（Priorities）排程器是從 Kubernetes v1.0.0 釋出時就存在的模式，v1.14.0 的最後實作與最開始的設計也沒有太多差別。然而從 v1.0.0 到 v1.14.0 期間也引入了很多改進：

• 排程器擴充 · v1.2.0 - Scheduler extension。通過調用外部排程器擴充的方式改變排程器的決策；
• Map-Reduce 優先級算法 · v1.5.0 - MapReduce-like scheduler priority functions。為排程器的優先級算法支援 Map-Reduce 的計算方式，通過引入可并行的 Map 階段優化排程器的計算性能；
• 排程器遷移 · v1.10.0 - Move scheduler code out of plugin directory。從 plugin/pkg/scheduler 移到 pkg/scheduler；kube-scheduler 成為對外直接提供的可執行檔案；

謂詞和優先級都是 Kubernetes 在排程系統中提供的兩個抽象，謂詞算法使用 FitPredicate 類型，而優先級算法使用 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 開發的第一個版本，是以對當時的設計印象也非常深刻，v1.14.0 的 Kubernetes 排程器會使用 PriorityMapFunction 和 PriorityReduceFunction 這種 Map-Reduce 的方式計算所有節點的分數并從其中選擇分數最高的節點。下圖展示了，v1.14.0 版本中排程器的執行過程：

圖 24 - 謂詞和優先級算法

如上圖所示，我們假設排程器中存在一個謂詞算法和一個 Map-Reduce 優先級算法，當我們為一個 Pod 在 6 個節點中選擇最合适的一個時，6 個節點會先經過謂詞的篩選，圖中的謂詞算法會過濾掉一半的節點，剩餘的 3 個節點經過 Map 和 Reduce 兩個過程分别得到了 5、10 和 5 分，最終排程器就會選擇分數最高的 4 号節點。

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

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 中擷取目前系統中存在的全部節點；
• 調用 genericScheduler.findNodesThatFit 方法并行執行全部的謂詞算法過濾節點。謂詞算法會根據傳入的 Pod 和 Node 對節點進行過濾，這時會過濾掉端口号沖突、資源不足的節點；調用所有排程器擴充的 Filter 方法輔助過濾；
• 調用 PrioritizeNodes 函數為所有的節點打分。以 Pod 和 Node 作為參數并發執行同一優先級的 PriorityMapFunction；Pod 和優先級傳回的 Node 到分數的映射為參數調用 PriorityReduceFunction 函數；調用所有排程器擴充的 Prioritize 方法；将所有分數按照權重相加後傳回從 Node 到分數的映射；
• 調用 genericScheduler.selectHost 方法選擇得分最高的節點。

這就是使用謂詞和優先級算法時的排程過程，我們在這裡省略了排程器的優先隊列中的排序，出現排程錯誤時的搶占以及 Pod 持久存儲卷綁定到 Node 上的過程，隻保留了核心的排程邏輯。

排程架構

Kubernetes 排程架構是 Babak Salamat 和 Jonathan Basseri 2018 年提出的

最新排程器設計

，這個提案明确了 Kubernetes 中的各個排程階段，提供了設計良好的基于插件的接口。排程架構認為 Kubernetes 中目前存在排程（Scheduling）和綁定（Binding）兩個循環：

• 排程循環在多個 Node 中為 Pod 選擇最合适的 Node；
• 綁定循環将排程決策應用到叢集中，包括綁定 Pod 和 Node、綁定持久存儲等工作。

除了兩個大循環之外，排程架構中還包含 QueueSort、PreFilter、Filter、PostFilter、Score、Reserve、Permit、PreBind、Bind、PostBind 和 Unreserve 11 個擴充點（Extension Point），這些擴充點會在排程的過程中觸發，它們的運作順序如下：

圖 25 - Kubernetes 排程架構

我們可以将排程器中的 Scheduler.scheduleOne 方法作為入口分析基于排程架構的排程器實作，每次調用該方法都會完成一遍為 Pod 排程節點的全部流程，我們将該函數的執行過程分成排程和綁定兩個階段，首先是排程器的排程階段：

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
    }
    ...
}           

• 調用内部優先隊列的 MakeNextPodFunc 傳回的函數從隊列中擷取下一個等待排程的 Pod，用于維護等待 Pod 的隊列會執行 QueueSort 插件；
• 調用 genericScheduler.Schedule 函數選擇節點，該過程會執行 PreFilter、Filter、PostFilter、Score 四個擴充點的插件；
• 調用 framework.RunReservePlugins 函數運作 Reserve 插件用于保留資源并進入綁定階段（綁定階段運作時間較長，避免資源被搶占）。如果運作失敗執行，調用 framework.RunUnreservePlugins 函數運作 Unreserve 插件。

因為每一次排程決策都會改變上下文，是以該階段 Kubernetes 需要串行執行。而綁定階段就是實作排程的過程了，我們會建立一個新的 Goroutine 并行執行綁定循環：

func (sched *Scheduler) scheduleOne(ctx context.Context) {
    ...
    gofunc() {
        bindingCycleCtx, cancel := context.WithCancel(ctx)
        defer cancel()
        fwk.RunPermitPlugins(bindingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost)
        if !allBound {
             sched.bindVolumes(assumedPod)
        }
        fwk.RunPreBindPlugins(bindingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost)
        if err := sched.bind(bindingCycleCtx, assumedPod, scheduleResult.SuggestedHost, state); err != nil {
            fwk.RunUnreservePlugins(bindingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost)
        } else {
            fwk.RunPostBindPlugins(bindingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost)
        }
    }()
}           

• 啟動一個 Goroutine 并調用 framework.RunPermitPlugin 異步運作 Permit 插件，這個階段可以用來實作批排程器；
• 調用 Scheduler.bindVolumes 将卷先綁定到 Node 上；
• 調用 Scheduler.bind 函數将 Pod 綁定到 Node 上完成排程，綁定的過程會執行 PreBind、Bind 和 PostBind 三個擴充點的插件。

目前的排程架構在 Kubernetes v1.17.0 版本中還是 Alpha 階段，很多功能還不明确，為了支援更多、更豐富的場景，在接下來的幾個版本還可能會做出很多改進，不過排程架構在很長的一段時間中都會是排程器的核心。

本節介紹了 Kubernetes 排程器從 v1.0.0 到最新版本中的不同設計，Kubernetes 排程器中總共存在兩種不同的設計，一種是基于謂詞和優先級算法的排程器，另一種是基于排程架構的排程器。

很多的業務排程器也需要從多個選項中選出最優的選擇，無論是成本最低還是品質最優，我們可以考慮将排程的過程分成過濾和打分兩個階段為排程器建立合适的抽象，過濾階段會按照需求過濾掉不滿足需求的選項，打分階段可能會按照品質、成本和權重對多個選項進行排序，遵循這種設計思路可以解決很多類似問題。

目前的 Kubernetes 已經通過排程架構詳細地支援了多個階段的擴充方法，幾乎是排程器内部實作的最終形态了。不過随着排程器功能的逐漸複雜，未來可能還會遇到更複雜的排程場景，例如：多租戶的排程資源隔離、多排程器等功能，而 Kubernetes 社群也一直都在為建構高性能的排程器而努力。

• Scheduling Framework #624
• Create a custom Kubernetes scheduler
• Scheduler extender Document

總結

從作業系統、程式設計語言到應用程式，我們在這篇文章中分析了 Linux、Go 語言和 Kubernetes 排程器的設計與實作原理，這三個不同的排程器其實有互相依賴的關系：

圖 26 - 三層排程器

如上圖所示，Kubernetes 的排程器依賴于 Go 語言的運作時排程器，而 Go 語言的運作時排程器也依賴于 Linux 的程序排程器，從上到下離使用者越來越遠，從下到上越來越關注具體業務。我們在最後通過兩個比較分析一下這幾個排程器的異同：

• Linux 程序排程器與 Go 語言排程器；
• 系統級排程器（Linux 和 Go）與業務排程器（Kubernetes）。

這是兩種不同層面的比較，相信通過不同角度的比較能夠讓我們對排程器的設計有更深入的認識。

1. Linux 和 Go

首先是 Linux 和 Go 語言排程器，這兩個排程器的場景都非常相似，它們最終都是要充分利用機器上的 CPU 資源，是以在實作和演進上有很多相似之處：

• 排程器的初始版本都非常簡單，甚至很簡陋，隻能支援協作式的排程；
• 按照運作隊列進行分區，通過工作竊取的方式平衡不同 CPU 或者線程上的運作隊列；
• 最終都通過某些方式實作了基于信号的搶占式排程，不過 Go 語言的實作并不完善。

因為場景非常相似，是以它們的目的也非常相似，隻是它們排程的任務粒度會有不同，Linux 程序排程器的最小排程機關是線程，而 Go 語言是 Goroutine，與 Linux 程序排程器相比，Go 語言在使用者層建立新的模型，實作了另一個排程器，為使用者提供輕量級的排程機關來增強程式的性能，但是它也引入了很多元件來處理系統調用、網絡輪訓等線程相關的操作，同時組合多個不同粒度的任務導緻實作相對複雜。

Linux 排程器的最終設計引入了排程類的概念，讓不同任務的類型分别享受不同的排程政策以此來調和低延時和實時性這個在排程上兩難的問題。

Go 語言的排程器目前剛剛引入了基于信号的搶占式排程，還有很多功能都不完善。除了搶占式排程之外，複雜的 NUMA 排程器提案也可能是未來 Go 語言的發展方向。

2. 系統和業務

如果我們将系統排程器和業務排程器進行對比的話，你會發現兩者在設計差别非常大，畢竟它們處于系統的不同層級。系統排程器考慮的是極緻的性能，是以它通過分區的方式将運作隊列等資源分離，通過降低鎖的粒度來降低系統的延遲；而業務排程器關注的是完善的排程功能，排程的性能雖然十分重要，但是一定要建立在滿足特定排程需求之上，而因為業務上的排程需求往往都是比較複雜，是以隻能做出權衡和取舍。

正是因為需求的不同，我們會發現不同排程器的演進過程也完全不同。系統排程器都會先充分利用資源，降低系統延時，随後在性能無法優化時才考慮加入排程類等功能滿足不同場景下的排程，而 Kubernetes 排程器更關注内部不同排程算法的組織，如何同時維護多個複雜的排程算法，當設計了良好的抽象之後，它才會考慮更加複雜的多排程器、多租戶等場景。

3. 最後

這種研究曆史變化帶來的快樂是很不同的，當我們發現代碼發生變化的原因時也會感到欣喜，這讓我們站在今天重新見證了曆史上的決策，本文中的相應章節已經包含了對應源代碼的連結，各位讀者可以自行閱讀相應内容，也衷心希望各位讀者能夠有所收獲。

延伸閱讀

• Cooperative vs. Preemptive: a quest to maximize concurrency power
• Randomized Work Stealing versus Sharing in Large-scale Systems with Non-exponential Job Sizes
• Scalable work stealing

雲原生網絡研讨會邀您參加

“ 阿裡巴巴雲原生 關注微服務、Serverless、容器、Service Mesh 等技術領域、聚焦雲原生流行技術趨勢、雲原生大規模的落地實踐，做最懂雲原生開發者的技術圈。”