溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
調度是一個非常廣泛的概念，很多領域都會使用調度這個術語，在計算機科學中，調度就是一種將任務（Work）分配給資源的方法。任務可能是虛擬的計算任務，例如線程、進程或者數據流，這些任務會被調度到硬件資源上執行，例如：處理器 CPU 等設備。
圖 1 - 調度系統設計精要
本文會介紹調度系統的常見場景以及設計過程中的一些關鍵問題，調度器的設計最終都會歸結到一個問題上 — 如何對資源高效的分配和調度以達到我們的目的，可能包括對資源的合理利用、最小化成本、快速匹配供給和需求。
圖 2 - 文章脈絡和內容
除了介紹調度系統設計時會遇到的常見問題之外，本文還會深入分析幾種常見的調度器的設計、演進與實現原理，包括操作系統的進程調度器，Go 語言的運行時調度器以及 Kubernetes 的工作負載調度器，幫助我們理解調度器設計的核心原理。
調度系統其實就是調度器（Scheduler），我們在很多系統中都能見到調度器的身影，就像我們在上面說的，不止操作系統中存在調度器，編程語言、容器編排以及很多業務系統中都會存在調度系統或者調度模塊。
這些調度模塊的核心作用就是對有限的資源進行分配，以實現最大化資源的利用率或者降低系統的尾延遲，調度系統面對的就是資源的需求和供給不平衡的問題。
圖 3 - 調度器的任務和資源
我們在這一節中將從多個方面介紹調度系統設計時需要重點考慮的問題，其中包括調度系統的需求調研、調度原理以及架構設計。
在著手構建調度系統之前，首要的工作就是進行詳細的需求調研和分析，在這個過程中需要完成以下兩件事：
調度系統應用的場景是我們首先需要考慮的問題，對應用場景的分析至關重要，我們需要深入了解當前場景下待執行任務和能用來執行任務的資源的特點。我們需要分析待執行任務的以下特征：
而用于執行任務的資源也可能存在資源不平衡，不同資源處理任務的速度不一致的問題。
資源和任務特點的多樣性決定了調度系統的設計，我們在這里舉幾個簡單的例子幫助各位讀者理解調度系統需求分析的過程。
圖 4 - Linux 操作系統
在操作系統的進程調度器中，待調度的任務就是線程，這些任務一般只會處于正在執行或者未執行（等待或者終止）的狀態；而用于處理這些任務的 CPU 往往都是不可再分的，同一個 CPU 在同一時間只能執行一個任務，這是物理上的限制。簡單總結一下，操作系統調度器的任務和資源有以下特性：
在上述場景中，待執行的任務是操作系統調度的基本單位 —— 線程，而可分配的資源是 CPU 的時間。Go 語言的調度器與操作系統的調度器面對的是幾乎相同的場景，其中的任務是 Goroutine，可以分配的資源是在 CPU 上運行的線程。
圖 5 - 容器編排系統 Kubernetes
除了操作系統和編程語言這種較為底層的調度器之外，容器和計算任務調度在今天也很常見，Kubernetes 作為容器編排系統會負責調取集群中的容器，對它稍有了解的人都知道，Kubernetes 中調度的基本單元是 Pod，這些 Pod 會被調度到節點 Node 上執行：
任務 —— Pod。優先級不同：Pod 的優先級可能不同，高優先級的系統 Pod 可以搶占低優先級 Pod 的資源；有狀態：Pod 可以分為無狀態和有狀態，有狀態的 Pod 需要依賴持久存儲卷；
調度系統在生活和工作中都很常見，除了上述的兩個場景之外，其他需要調度系統的場景包括 CDN 的資源調度、訂單調度以及離線任務調度系統等。在不同場景中，我們都需要深入思考任務和資源的特性，它們對系統的設計起者指導作用。
在深入分析調度場景后，我們需要理解調度的目的。我們可以將調度目的理解成機器學習中的成本函數（Cost function），確定調度目的就是確定成本函數的定義，調度理論一書中曾經介紹過常見的調度目的，包含以下內容：
這些都是偏理論的調度的目的，多數業務調度系統的調度目的都是優化與業務聯系緊密的指標 — 成本和質量。如何在成本和質量之間達到平衡是需要仔細思考和設計的，由于篇幅所限以及業務場景的復雜，本文不會分析如何權衡成本和質量，這往往都是需要結合業務考慮的事情，不具有足夠的相似性。
性能優異的調度器是實現特定調度目的前提，我們在討論調度場景和目的時往往都會忽略調度的額外開銷，然而調度器執行時的延時和吞吐量等指標在調度負載較重時是不可忽視的。本節會分析與調度器實現相關的一些重要概念，這些概念能夠幫助我們實現高性能的調度器：
協作式（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 語言都選擇了工作竊取策略。
本節將從調度器內部和外部兩個角度分析調度器的架構設計，前者分析調度器內部多個組件的關系和做出調度決策的過程；后者分析多個調度器應該如何協作，是否有其他的外部服務可以輔助調度器做出更合理的調度決策。
當調度器收到待調度任務時，會根據采集到的狀態和待調度任務的規格（Spec）做出合理的調度決策，我們可以從下圖中了解常見調度系統的內部邏輯。
圖 13 - 調度器做出調度決策
常見的調度器一般由兩部分組成 — 用于收集狀態的狀態模塊和負責做決策的決策模塊。
狀態模塊會從不同途徑收集盡可能多的信息為調度提供豐富的上下文，其中可能包括資源的屬性、利用率和可用性等信息。根據場景的不同，上下文可能需要存儲在 MySQL 等持久存儲中，一般也會在內存中緩存一份以減少調度器訪問上下文的開銷。
決策模塊會根據狀態模塊收集的上下文和任務的規格做出調度決策，需要注意的是做出的調度決策只是在當下有效，在未來某個時間點，狀態的改變可能會導致之前做的決策不符合任務的需求，例如：當我們使用 Kubernetes 調度器將工作負載調度到某些節點上，這些節點可能由于網絡問題突然不可用，該節點上的工作負載也就不能正常工作，即調度決策失效。
調度器在調度時都會通過以下的三個步驟為任務調度合適的資源：
圖 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 進程調度器的演進過程。
操作系統會將進程調度器分成三種不同的類型，即長期調度器、中期調度器和短期調度器。這三種不同類型的調度器分別提供了不同的功能，我們將在這一節中依次介紹它們。
長期調度器（Long-Term Scheduler）也被稱作任務調度器（Job Scheduler），它能夠決定哪些任務會進入調度器的準備隊列。當我們嘗試執行新的程序時，長期調度器會負責授權或者延遲該程序的執行。長期調度器的作用是平衡同時正在運行的 I/O 密集型或者 CPU 密集型進程的任務數量：
長期調度器能平衡同時正在運行的 I/O 密集型和 CPU 密集型任務，最大化的利用操作系統的 I/O 和 CPU 資源。
中期調度器會將不活躍的、低優先級的、發生大量頁錯誤的或者占用大量內存的進程從內存中移除，為其他的進程釋放資源。
圖 16 - 中期調度器
當正在運行的進程陷入 I/O 操作時，該進程只會占用計算資源，在這種情況下，中期調度器就會將它從內存中移除等待 I/O 操作完成后，該進程會重新加入就緒隊列并等待短期調度器的調度。
短期調度器應該是我們最熟悉的調度器，它會從就緒隊列中選出一個進程執行。進程的選擇會使用特定的調度算法，它會同時考慮進程的優先級、入隊時間等特征。因為每個進程能夠得到的執行時間有限，所以短期調度器的執行十分頻繁。
本節將重點介紹 Linux 的 CPU 調度器，也就是短期調度器。Linux 的 CPU 調度器并不是從設計之初就是像今天這樣復雜的，在很長的一段時間里（v0.01 ~ v2.4），Linux 的進程調度都由幾十行的簡單函數負責，我們先了解一下不同版本調度器的歷史：
初始調度器 · v0.01 ~ v2.4。由幾十行代碼實現，功能非常簡陋；同時最多處理 64 個任務；
調度器 · v2.4 ~ v2.6。調度時需要遍歷全部任務當待執行的任務較多時，同一個任務兩次執行的間隔很長，會有比較嚴重的饑餓問題；
調度器 · v2.6.0 ~ v2.6.22。通過引入運行隊列和優先數組實現 的時間復雜度；使用本地運行隊列替代全局運行隊列增強在對稱多處理器的擴展性；引入工作竊取保證多個運行隊列中任務的平衡；
這里會詳細介紹從最初的調度器到今天復雜的完全公平調度器（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 是進程能夠占用的時間切片數量，該函數會根據時間切片的值執行不同的邏輯：
Linux 操作系統的計時器會每隔 10ms 觸發一次 do_timer 將當前正在運行進程的 counter 減一，當前進程的計數器歸零時就會重新觸發調度。
調度器是 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 左右的時間切片，然而這種調度和分配方式是 調度器的最大問題：
正是因為調度器存在了上述的問題，所以 Linux 內核在兩個版本后使用新的 調度器替換該實現。
調度器在 v2.6.0 到 v2.6.22 的 Linux 內核中使用了四年的時間，它能夠在常數時間內完成進程調度，你可以在sched.h 和 sched.c 中查看 調度器的源代碼。因為實現和功能復雜性的增加，調度器的代碼行數從 的 2100 行增加到 5000 行，它在調度器的基礎上進行了如下的改進：
調度器通過運行隊列 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 數組中的鏈表。 調度器使用上述的數據結構進行如下所示的調度：
上述的這些規則是 調度器運行遵守的主要規則，除了上述規則之外，調度器還需要支持搶占、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 由以下的多個文件組成：
通過 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 函數完成的，該函數的執行過程可以分成以下幾個步驟：
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 中的函數以提供不同的調度行為。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
