調(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è)備。

創(chuàng)新互聯(lián)是專業(yè)的白云網(wǎng)站建設(shè)公司，白云接單;提供成都網(wǎng)站建設(shè)、做網(wǎng)站,網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行白云網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊,希望更多企業(yè)前來合作!

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

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

協(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)致某些實例的負(fù)載過高。

工作分享與工作竊取

這一小節(jié)將繼續(xù)介紹在多個調(diào)度器間重新分配任務(wù)的兩個調(diào)度范式 — 工作分享（Work Sharing）和工作竊?。╓ork 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)度器的使用沒有那么廣泛，實際的應(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。由幾十行代碼實現(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ù)組實現(xiàn)  的時間復(fù)雜度；使用本地運(yùn)行隊列替代全局運(yùn)行隊列增強(qiáng)在對稱多處理器的擴(kuò)展性；引入工作竊取保證多個運(yùn)行隊列中任務(wù)的平衡；

• 完全公平調(diào)度器 · v2.6.23 ~ 至今。引入紅黑樹和運(yùn)行時間保證調(diào)度的公平性；引入調(diào)度類實現(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)用匯編語言的實現(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)度器的實現(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)度器替換該實現(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)度器的源代碼。因為實現(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)實現(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 實現(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)度類分別實現(xiàn)了 sched_class 中的函數(shù)以提供不同的調(diào)度行為。

本文標(biāo)題：調(diào)度系統(tǒng)的設(shè)計原理是什么
文章路徑：http://www.rwnh.cn/article46/jsdpeg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計公司、外貿(mào)建站、網(wǎng)站維護(hù)、響應(yīng)式網(wǎng)站、面包屑導(dǎo)航、網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)