調(diào)度是一個(gè)非常廣泛的概念，很多領(lǐng)域都會(huì)使用調(diào)度這個(gè)術(shù)語(yǔ)，在計(jì)算機(jī)科學(xué)中，調(diào)度就是一種將任務(wù)（Work）分配給資源的方法。任務(wù)可能是虛擬的計(jì)算任務(wù)，例如線程、進(jìn)程或者數(shù)據(jù)流，這些任務(wù)會(huì)被調(diào)度到硬件資源上執(zhí)行，例如：處理器 CPU 等設(shè)備。
圖 1 - 調(diào)度系統(tǒng)設(shè)計(jì)精要
本文會(huì)介紹調(diào)度系統(tǒng)的常見(jiàn)場(chǎng)景以及設(shè)計(jì)過(guò)程中的一些關(guān)鍵問(wèn)題，調(diào)度器的設(shè)計(jì)最終都會(huì)歸結(jié)到一個(gè)問(wèn)題上 — 如何對(duì)資源高效的分配和調(diào)度以達(dá)到我們的目的，可能包括對(duì)資源的合理利用、最小化成本、快速匹配供給和需求。
圖 2 - 文章脈絡(luò)和內(nèi)容
除了介紹調(diào)度系統(tǒng)設(shè)計(jì)時(shí)會(huì)遇到的常見(jiàn)問(wèn)題之外，本文還會(huì)深入分析幾種常見(jiàn)的調(diào)度器的設(shè)計(jì)、演進(jìn)與實(shí)現(xiàn)原理，包括操作系統(tǒng)的進(jìn)程調(diào)度器，Go 語(yǔ)言的運(yùn)行時(shí)調(diào)度器以及 Kubernetes 的工作負(fù)載調(diào)度器，幫助我們理解調(diào)度器設(shè)計(jì)的核心原理。
調(diào)度系統(tǒng)其實(shí)就是調(diào)度器（Scheduler），我們?cè)诤芏嘞到y(tǒng)中都能見(jiàn)到調(diào)度器的身影，就像我們?cè)谏厦嬲f(shuō)的，不止操作系統(tǒng)中存在調(diào)度器，編程語(yǔ)言、容器編排以及很多業(yè)務(wù)系統(tǒng)中都會(huì)存在調(diào)度系統(tǒng)或者調(diào)度模塊。
這些調(diào)度模塊的核心作用就是對(duì)有限的資源進(jìn)行分配，以實(shí)現(xiàn)大化資源的利用率或者降低系統(tǒng)的尾延遲，調(diào)度系統(tǒng)面對(duì)的就是資源的需求和供給不平衡的問(wèn)題。
圖 3 - 調(diào)度器的任務(wù)和資源
我們?cè)谶@一節(jié)中將從多個(gè)方面介紹調(diào)度系統(tǒng)設(shè)計(jì)時(shí)需要重點(diǎn)考慮的問(wèn)題，其中包括調(diào)度系統(tǒng)的需求調(diào)研、調(diào)度原理以及架構(gòu)設(shè)計(jì)。
在著手構(gòu)建調(diào)度系統(tǒng)之前，首要的工作就是進(jìn)行詳細(xì)的需求調(diào)研和分析，在這個(gè)過(guò)程中需要完成以下兩件事：
調(diào)度系統(tǒng)應(yīng)用的場(chǎng)景是我們首先需要考慮的問(wèn)題，對(duì)應(yīng)用場(chǎng)景的分析至關(guān)重要，我們需要深入了解當(dāng)前場(chǎng)景下待執(zhí)行任務(wù)和能用來(lái)執(zhí)行任務(wù)的資源的特點(diǎn)。我們需要分析待執(zhí)行任務(wù)的以下特征：
而用于執(zhí)行任務(wù)的資源也可能存在資源不平衡，不同資源處理任務(wù)的速度不一致的問(wèn)題。
資源和任務(wù)特點(diǎn)的多樣性決定了調(diào)度系統(tǒng)的設(shè)計(jì)，我們?cè)谶@里舉幾個(gè)簡(jiǎn)單的例子幫助各位讀者理解調(diào)度系統(tǒng)需求分析的過(guò)程。
圖 4 - Linux 操作系統(tǒng)
在操作系統(tǒng)的進(jìn)程調(diào)度器中，待調(diào)度的任務(wù)就是線程，這些任務(wù)一般只會(huì)處于正在執(zhí)行或者未執(zhí)行（等待或者終止）的狀態(tài)；而用于處理這些任務(wù)的 CPU 往往都是不可再分的，同一個(gè) CPU 在同一時(shí)間只能執(zhí)行一個(gè)任務(wù)，這是物理上的限制。簡(jiǎn)單總結(jié)一下，操作系統(tǒng)調(diào)度器的任務(wù)和資源有以下特性：
在上述場(chǎng)景中，待執(zhí)行的任務(wù)是操作系統(tǒng)調(diào)度的基本單位 —— 線程，而可分配的資源是 CPU 的時(shí)間。Go 語(yǔ)言的調(diào)度器與操作系統(tǒng)的調(diào)度器面對(duì)的是幾乎相同的場(chǎng)景，其中的任務(wù)是 Goroutine，可以分配的資源是在 CPU 上運(yùn)行的線程。
圖 5 - 容器編排系統(tǒng) Kubernetes
除了操作系統(tǒng)和編程語(yǔ)言這種較為底層的調(diào)度器之外，容器和計(jì)算任務(wù)調(diào)度在今天也很常見(jiàn)，Kubernetes 作為容器編排系統(tǒng)會(huì)負(fù)責(zé)調(diào)取集群中的容器，對(duì)它稍有了解的人都知道，Kubernetes 中調(diào)度的基本單元是 Pod，這些 Pod 會(huì)被調(diào)度到節(jié)點(diǎn) Node 上執(zhí)行：
任務(wù) —— Pod。優(yōu)先級(jí)不同：Pod 的優(yōu)先級(jí)可能不同，高優(yōu)先級(jí)的系統(tǒng) Pod 可以搶占低優(yōu)先級(jí) Pod 的資源；有狀態(tài)：Pod 可以分為無(wú)狀態(tài)和有狀態(tài)，有狀態(tài)的 Pod 需要依賴持久存儲(chǔ)卷；
調(diào)度系統(tǒng)在生活和工作中都很常見(jiàn)，除了上述的兩個(gè)場(chǎng)景之外，其他需要調(diào)度系統(tǒng)的場(chǎng)景包括 CDN 的資源調(diào)度、訂單調(diào)度以及離線任務(wù)調(diào)度系統(tǒng)等。在不同場(chǎng)景中，我們都需要深入思考任務(wù)和資源的特性，它們對(duì)系統(tǒng)的設(shè)計(jì)起者指導(dǎo)作用。
在深入分析調(diào)度場(chǎng)景后，我們需要理解調(diào)度的目的。我們可以將調(diào)度目的理解成機(jī)器學(xué)習(xí)中的成本函數(shù)（Cost function），確定調(diào)度目的就是確定成本函數(shù)的定義，調(diào)度理論一書(shū)中曾經(jīng)介紹過(guò)常見(jiàn)的調(diào)度目的，包含以下內(nèi)容：
這些都是偏理論的調(diào)度的目的，多數(shù)業(yè)務(wù)調(diào)度系統(tǒng)的調(diào)度目的都是優(yōu)化與業(yè)務(wù)聯(lián)系緊密的指標(biāo) — 成本和質(zhì)量。如何在成本和質(zhì)量之間達(dá)到平衡是需要仔細(xì)思考和設(shè)計(jì)的，由于篇幅所限以及業(yè)務(wù)場(chǎng)景的復(fù)雜，本文不會(huì)分析如何權(quán)衡成本和質(zhì)量，這往往都是需要結(jié)合業(yè)務(wù)考慮的事情，不具有足夠的相似性。
性能優(yōu)異的調(diào)度器是實(shí)現(xiàn)特定調(diào)度目的前提，我們?cè)谟懻撜{(diào)度場(chǎng)景和目的時(shí)往往都會(huì)忽略調(diào)度的額外開(kāi)銷，然而調(diào)度器執(zhí)行時(shí)的延時(shí)和吞吐量等指標(biāo)在調(diào)度負(fù)載較重時(shí)是不可忽視的。本節(jié)會(huì)分析與調(diào)度器實(shí)現(xiàn)相關(guān)的一些重要概念，這些概念能夠幫助我們實(shí)現(xiàn)高性能的調(diào)度器：
協(xié)作式（Cooperative）與搶占式（Preemptive）調(diào)度是操作系統(tǒng)中常見(jiàn)的多任務(wù)運(yùn)行策略。這兩種調(diào)度方法的定義完全不同：
圖 6 - 協(xié)作式調(diào)度與搶占式調(diào)度
任務(wù)的執(zhí)行時(shí)間和任務(wù)上下文切換的額外開(kāi)銷決定了哪種調(diào)度方式會(huì)帶來(lái)更好的性能。如下圖所示，圖 7 展示了一個(gè)協(xié)作式調(diào)度器調(diào)度任務(wù)的過(guò)程，調(diào)度器一旦為某個(gè)任務(wù)分配了資源，它就會(huì)等待該任務(wù)主動(dòng)釋放資源，圖中 4 個(gè)任務(wù)盡管執(zhí)行時(shí)間不同，但是它們都會(huì)在任務(wù)執(zhí)行完成后釋放資源，整個(gè)過(guò)程也只需要 4 次上下文的切換。
圖 7 - 協(xié)作式調(diào)度
圖 8 展示了搶占式調(diào)度的過(guò)程，由于調(diào)度器不知道所有任務(wù)的執(zhí)行時(shí)間，所以它為每一個(gè)任務(wù)分配了一段時(shí)間切片。任務(wù) 1 和任務(wù) 4 由于執(zhí)行時(shí)間較短，所以在第一次被調(diào)度時(shí)就完成了任務(wù)；但是任務(wù) 2 和任務(wù) 3 因?yàn)閳?zhí)行時(shí)間較長(zhǎng)，超過(guò)了調(diào)度器分配的上限，所以為了保證公平性會(huì)觸發(fā)搶占，等待隊(duì)列中的其他任務(wù)會(huì)獲得資源。在整個(gè)調(diào)度過(guò)程中，一共發(fā)生了 6 次上下文切換。
圖 8 - 搶占式調(diào)度
如果部分任務(wù)的執(zhí)行時(shí)間很長(zhǎng)，協(xié)作式的任務(wù)調(diào)度會(huì)使部分執(zhí)行時(shí)間長(zhǎng)的任務(wù)餓死其他任務(wù)；不過(guò)如果待執(zhí)行的任務(wù)執(zhí)行時(shí)間較短并且?guī)缀跸嗤?，那么使用協(xié)作式的任務(wù)調(diào)度能減少任務(wù)中斷帶來(lái)的額外開(kāi)銷，從而帶來(lái)更好的調(diào)度性能。
因?yàn)槎鄶?shù)情況下任務(wù)執(zhí)行的時(shí)間都不確定，在協(xié)作式調(diào)度中一旦任務(wù)沒(méi)有主動(dòng)讓出資源，那么就會(huì)導(dǎo)致其它任務(wù)等待和阻塞，所以調(diào)度系統(tǒng)一般都會(huì)以搶占式的任務(wù)調(diào)度為主，同時(shí)支持任務(wù)的協(xié)作式調(diào)度。
使用單個(gè)調(diào)度器還是多個(gè)調(diào)度器也是設(shè)計(jì)調(diào)度系統(tǒng)時(shí)需要仔細(xì)考慮的，多個(gè)調(diào)度器并不一定意味著多個(gè)進(jìn)程，也有可能是一個(gè)進(jìn)程中的多個(gè)調(diào)度線程，它們既可以選擇在多核上并行調(diào)度、在單核上并發(fā)調(diào)度，也可以同時(shí)利用并行和并發(fā)提高性能。
圖 9 - 單調(diào)度器調(diào)度任務(wù)和資源
不過(guò)對(duì)于調(diào)度系統(tǒng)來(lái)說(shuō)，因?yàn)樗龀龅臎Q策會(huì)改變資源的狀態(tài)和系統(tǒng)的上下文進(jìn)而影響后續(xù)的調(diào)度決策，所以單調(diào)度器的串行調(diào)度是能夠精準(zhǔn)調(diào)度資源的唯一方法。單個(gè)調(diào)度器利用不同渠道收集調(diào)度需要的上下文，并在收到調(diào)度請(qǐng)求后會(huì)根據(jù)任務(wù)和資源情況做出當(dāng)下最優(yōu)的決策。
隨著調(diào)度器的不斷演變，單調(diào)度器的性能和吞吐量可能會(huì)受到限制，我們還是需要引入并行或者并發(fā)調(diào)度來(lái)解決性能上的瓶頸，這時(shí)我們需要將待調(diào)度的資源分區(qū)，讓多個(gè)調(diào)度器分別負(fù)責(zé)調(diào)度不同區(qū)域中的資源。
圖 10 - 多調(diào)度器與資源分區(qū)
多調(diào)度器的并發(fā)調(diào)度能夠極大提升調(diào)度器的整體性能，例如 Go 語(yǔ)言的調(diào)度器。Go 語(yǔ)言運(yùn)行時(shí)會(huì)將多個(gè) CPU 交給不同的處理器分別調(diào)度，這樣通過(guò)并行調(diào)度能夠提升調(diào)度器的性能。
上面介紹的兩種調(diào)度方法都建立在需要精準(zhǔn)調(diào)度的前提下，多調(diào)度器中的每一個(gè)調(diào)度器都會(huì)面對(duì)無(wú)關(guān)的資源，所以對(duì)于同一個(gè)分區(qū)的資源，調(diào)度還是串行的。
圖 11 - 多調(diào)度器粗粒度調(diào)度
使用多個(gè)調(diào)度器同時(shí)調(diào)度多個(gè)資源也是可行的，只是可能需要犧牲調(diào)度的精確性 — 不同的調(diào)度器可能會(huì)在不同時(shí)間接收到狀態(tài)的更新，這就會(huì)導(dǎo)致不同調(diào)度器做出不同的決策。負(fù)載均衡就可以看做是多線程和多進(jìn)程的調(diào)度器，因?yàn)閷?duì)任務(wù)和資源掌控的信息有限，這種粗粒度調(diào)度的結(jié)果很可能就是不同機(jī)器的負(fù)載會(huì)有較大差異，所以無(wú)論是小規(guī)模集群還是大規(guī)模集群都很有可能導(dǎo)致某些實(shí)例的負(fù)載過(guò)高。
這一小節(jié)將繼續(xù)介紹在多個(gè)調(diào)度器間重新分配任務(wù)的兩個(gè)調(diào)度范式 — 工作分享（Work Sharing）和工作竊?。╓ork Stealing）。獨(dú)立的調(diào)度器可以同時(shí)處理所有的任務(wù)和資源，所以它不會(huì)遇到多調(diào)度器的任務(wù)和資源的不平衡問(wèn)題。在多數(shù)的調(diào)度場(chǎng)景中，任務(wù)的執(zhí)行時(shí)間都是不確定的，假設(shè)多個(gè)調(diào)度器分別調(diào)度相同的資源，由于任務(wù)的執(zhí)行時(shí)間不確定，多個(gè)調(diào)度器中等待調(diào)度的任務(wù)隊(duì)列最終會(huì)發(fā)生差異 — 部分隊(duì)列中包含大量任務(wù)，而另外一些隊(duì)列不包含任務(wù)，這時(shí)就需要引入任務(wù)再分配策略。
工作分享和工作竊取是完全不同的兩種再分配策略。在工作分享中，當(dāng)調(diào)度器創(chuàng)建了新任務(wù)時(shí)，它會(huì)將一部分任務(wù)分給其他調(diào)度器；而在工作竊取中，當(dāng)調(diào)度器的資源沒(méi)有被充分利用時(shí)，它會(huì)從其他調(diào)度器中竊取一些待分配的任務(wù)，如下圖所示：
圖 12 - 工作竊取調(diào)度器
這兩種任務(wù)再分配的策略都為系統(tǒng)增加了額外的開(kāi)銷，與工作分享相比，工作竊取只會(huì)在當(dāng)前調(diào)度器的資源沒(méi)有被充分利用時(shí)才會(huì)觸發(fā)，所以工作竊取引入的額外開(kāi)銷更小。工作竊取在生產(chǎn)環(huán)境中更加常用，Linux 操作系統(tǒng)和 Go 語(yǔ)言都選擇了工作竊取策略。
本節(jié)將從調(diào)度器內(nèi)部和外部?jī)蓚€(gè)角度分析調(diào)度器的架構(gòu)設(shè)計(jì)，前者分析調(diào)度器內(nèi)部多個(gè)組件的關(guān)系和做出調(diào)度決策的過(guò)程；后者分析多個(gè)調(diào)度器應(yīng)該如何協(xié)作，是否有其他的外部服務(wù)可以輔助調(diào)度器做出更合理的調(diào)度決策。
當(dāng)調(diào)度器收到待調(diào)度任務(wù)時(shí)，會(huì)根據(jù)采集到的狀態(tài)和待調(diào)度任務(wù)的規(guī)格（Spec）做出合理的調(diào)度決策，我們可以從下圖中了解常見(jiàn)調(diào)度系統(tǒng)的內(nèi)部邏輯。
圖 13 - 調(diào)度器做出調(diào)度決策
常見(jiàn)的調(diào)度器一般由兩部分組成 — 用于收集狀態(tài)的狀態(tài)模塊和負(fù)責(zé)做決策的決策模塊。
狀態(tài)模塊會(huì)從不同途徑收集盡可能多的信息為調(diào)度提供豐富的上下文，其中可能包括資源的屬性、利用率和可用性等信息。根據(jù)場(chǎng)景的不同，上下文可能需要存儲(chǔ)在 MySQL 等持久存儲(chǔ)中，一般也會(huì)在內(nèi)存中緩存一份以減少調(diào)度器訪問(wèn)上下文的開(kāi)銷。
決策模塊會(huì)根據(jù)狀態(tài)模塊收集的上下文和任務(wù)的規(guī)格做出調(diào)度決策，需要注意的是做出的調(diào)度決策只是在當(dāng)下有效，在未來(lái)某個(gè)時(shí)間點(diǎn)，狀態(tài)的改變可能會(huì)導(dǎo)致之前做的決策不符合任務(wù)的需求，例如：當(dāng)我們使用 Kubernetes 調(diào)度器將工作負(fù)載調(diào)度到某些節(jié)點(diǎn)上，這些節(jié)點(diǎn)可能由于網(wǎng)絡(luò)問(wèn)題突然不可用，該節(jié)點(diǎn)上的工作負(fù)載也就不能正常工作，即調(diào)度決策失效。
調(diào)度器在調(diào)度時(shí)都會(huì)通過(guò)以下的三個(gè)步驟為任務(wù)調(diào)度合適的資源：
圖 14 - 調(diào)度框架
上圖展示了常見(jiàn)調(diào)度器決策模塊執(zhí)行的幾個(gè)步驟，確定優(yōu)先級(jí)、對(duì)閑置資源進(jìn)行打分、確定搶占資源的犧牲者，上述三個(gè)步驟中的最后一個(gè)往往都是可選的，部分調(diào)度系統(tǒng)不需要支持搶占式調(diào)度的功能。
如果我們將調(diào)度器看成一個(gè)整體，從調(diào)度器外部看架構(gòu)設(shè)計(jì)就會(huì)得到完全不同的角度 — 如何利用外部系統(tǒng)增強(qiáng)調(diào)度器的功能。在這里我們將介紹兩種調(diào)度器外部的設(shè)計(jì)，分別是多調(diào)度器和反調(diào)度器（Descheduler）。
串行調(diào)度與并行調(diào)度一節(jié)已經(jīng)分析了多調(diào)度器的設(shè)計(jì)，我們可以將待調(diào)度的資源進(jìn)行分區(qū)，讓多個(gè)調(diào)度器線程或者進(jìn)程分別負(fù)責(zé)各個(gè)區(qū)域中資源的調(diào)度，充分利用多和 CPU 的并行能力。
反調(diào)度器是一個(gè)比較有趣的概念，它能夠移除決策不再正確的調(diào)度，降低系統(tǒng)中的熵，讓調(diào)度器根據(jù)當(dāng)前的狀態(tài)重新決策。
圖 15 - 調(diào)度器與反調(diào)度器
反調(diào)度器的引入使得整個(gè)調(diào)度系統(tǒng)變得更加健壯。調(diào)度器負(fù)責(zé)根據(jù)當(dāng)前的狀態(tài)做出正確的調(diào)度決策，反調(diào)度器根據(jù)當(dāng)前的狀態(tài)移除錯(cuò)誤的調(diào)度決策，它們的作用看起來(lái)相反，但是目的都是為任務(wù)調(diào)度更合適的資源。
反調(diào)度器的使用沒(méi)有那么廣泛，實(shí)際的應(yīng)用場(chǎng)景也比較有限。作者第一次發(fā)現(xiàn)這個(gè)概念是在 Kubernetes 孵化的descheduler 項(xiàng)目中，不過(guò)因?yàn)榉凑{(diào)度器移除調(diào)度關(guān)系可能會(huì)影響正在運(yùn)行的線上服務(wù)，所以 Kubernetes 也只會(huì)在特定場(chǎ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)度器。
有一些讀者可能會(huì)感到困惑，操作系統(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)度器會(huì)將進(jìn)程和線程都看成任務(wù)，我們?cè)谶@里先說(shuō)明這一問(wèn)題，避免讀者感到困惑。我們會(huì)使用進(jìn)程調(diào)度器這個(gè)術(shù)語(yǔ)，但是一定要注意 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).
接下來(lái)，本節(jié)會(huì)研究操作系統(tǒng)中調(diào)度系統(tǒng)的類型以及 Linux 進(jìn)程調(diào)度器的演進(jìn)過(guò)程。
操作系統(tǒng)會(huì)將進(jìn)程調(diào)度器分成三種不同的類型，即長(zhǎng)期調(diào)度器、中期調(diào)度器和短期調(diào)度器。這三種不同類型的調(diào)度器分別提供了不同的功能，我們將在這一節(jié)中依次介紹它們。
長(zhǎng)期調(diào)度器（Long-Term Scheduler）也被稱作任務(wù)調(diào)度器（Job Scheduler），它能夠決定哪些任務(wù)會(huì)進(jìn)入調(diào)度器的準(zhǔn)備隊(duì)列。當(dāng)我們嘗試執(zhí)行新的程序時(shí)，長(zhǎng)期調(diào)度器會(huì)負(fù)責(zé)授權(quán)或者延遲該程序的執(zhí)行。長(zhǎng)期調(diào)度器的作用是平衡同時(shí)正在運(yùn)行的 I/O 密集型或者 CPU 密集型進(jìn)程的任務(wù)數(shù)量：
長(zhǎng)期調(diào)度器能平衡同時(shí)正在運(yùn)行的 I/O 密集型和 CPU 密集型任務(wù)，大化的利用操作系統(tǒng)的 I/O 和 CPU 資源。
中期調(diào)度器會(huì)將不活躍的、低優(yōu)先級(jí)的、發(fā)生大量頁(yè)錯(cuò)誤的或者占用大量?jī)?nèi)存的進(jìn)程從內(nèi)存中移除，為其他的進(jìn)程釋放資源。
圖 16 - 中期調(diào)度器
當(dāng)正在運(yùn)行的進(jìn)程陷入 I/O 操作時(shí)，該進(jìn)程只會(huì)占用計(jì)算資源，在這種情況下，中期調(diào)度器就會(huì)將它從內(nèi)存中移除等待 I/O 操作完成后，該進(jìn)程會(huì)重新加入就緒隊(duì)列并等待短期調(diào)度器的調(diào)度。
短期調(diào)度器應(yīng)該是我們最熟悉的調(diào)度器，它會(huì)從就緒隊(duì)列中選出一個(gè)進(jìn)程執(zhí)行。進(jìn)程的選擇會(huì)使用特定的調(diào)度算法，它會(huì)同時(shí)考慮進(jìn)程的優(yōu)先級(jí)、入隊(duì)時(shí)間等特征。因?yàn)槊總€(gè)進(jìn)程能夠得到的執(zhí)行時(shí)間有限，所以短期調(diào)度器的執(zhí)行十分頻繁。
本節(jié)將重點(diǎn)介紹 Linux 的 CPU 調(diào)度器，也就是短期調(diào)度器。Linux 的 CPU 調(diào)度器并不是從設(shè)計(jì)之初就是像今天這樣復(fù)雜的，在很長(zhǎng)的一段時(shí)間里（v0.01 ~ v2.4），Linux 的進(jìn)程調(diào)度都由幾十行的簡(jiǎn)單函數(shù)負(fù)責(zé)，我們先了解一下不同版本調(diào)度器的歷史：
初始調(diào)度器 · v0.01 ~ v2.4。由幾十行代碼實(shí)現(xiàn)，功能非常簡(jiǎn)陋；同時(shí)最多處理 64 個(gè)任務(wù)；
調(diào)度器 · v2.4 ~ v2.6。調(diào)度時(shí)需要遍歷全部任務(wù)當(dāng)待執(zhí)行的任務(wù)較多時(shí)，同一個(gè)任務(wù)兩次執(zhí)行的間隔很長(zhǎng)，會(huì)有比較嚴(yán)重的饑餓問(wèn)題；
調(diào)度器 · v2.6.0 ~ v2.6.22。通過(guò)引入運(yùn)行隊(duì)列和優(yōu)先數(shù)組實(shí)現(xiàn) 的時(shí)間復(fù)雜度；使用本地運(yùn)行隊(duì)列替代全局運(yùn)行隊(duì)列增強(qiáng)在對(duì)稱多處理器的擴(kuò)展性；引入工作竊取保證多個(gè)運(yùn)行隊(duì)列中任務(wù)的平衡；
這里會(huì)詳細(xì)介紹從最初的調(diào)度器到今天復(fù)雜的完全公平調(diào)度器（Completely Fair Scheduler，CFS）的演變過(guò)程。
Linux 最初的進(jìn)程調(diào)度器僅由 sched.h 和 sched.c 兩個(gè)文件構(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);
}無(wú)論是進(jìn)程還是線程，在 Linux 中都被看做是 task_struct 結(jié)構(gòu)體，所有的調(diào)度進(jìn)程都存儲(chǔ)在上限僅為 64 的數(shù)組中，調(diào)度器能夠處理的進(jìn)程上限也只有 64 個(gè)。
圖 17 - 最初的進(jìn)程調(diào)度器
上述函數(shù)會(huì)先喚醒獲得信號(hào)的可中斷進(jìn)程，然后從隊(duì)列倒序查找計(jì)數(shù)器 counter 大的可執(zhí)行進(jìn)程，counter 是進(jìn)程能夠占用的時(shí)間切片數(shù)量，該函數(shù)會(huì)根據(jù)時(shí)間切片的值執(zhí)行不同的邏輯：
Linux 操作系統(tǒng)的計(jì)時(shí)器會(huì)每隔 10ms 觸發(fā)一次 do_timer 將當(dāng)前正在運(yùn)行進(jìn)程的 counter 減一，當(dāng)前進(jìn)程的計(jì)數(shù)器歸零時(shí)就會(huì)重新觸發(fā)調(diào)度。
調(diào)度器是 Linux 在 v2.4 ~ v2.6 版本使用的調(diào)度器，由于該調(diào)取器在最壞的情況下會(huì)遍歷所有的任務(wù)，所以它調(diào)度任務(wù)的時(shí)間復(fù)雜度就是 。Linux 調(diào)度算法將 CPU 時(shí)間分割成了不同的時(shí)期（Epoch），也就是每個(gè)任務(wù)能夠使用的時(shí)間切片。
我們可以在 sched.h 和 sched.c 兩個(gè)文件中找到調(diào)度器的源代碼。與上一個(gè)版本的調(diào)度器相比， 調(diào)度器的實(shí)現(xiàn)復(fù)雜了很多，該調(diào)度器會(huì)在 schedule 函數(shù)中遍歷運(yùn)行隊(duì)列中的所有任務(wù)并調(diào)用 goodness 函數(shù)分別計(jì)算它們的權(quán)重獲得下一個(gè)運(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;
}
}
...
}在每個(gè)時(shí)期開(kāi)始時(shí)，上述代碼都會(huì)為所有的任務(wù)計(jì)算時(shí)間切片，因?yàn)樾枰獔?zhí)行 n 次，所以調(diào)度器被稱作 調(diào)度器。在默認(rèn)情況下，每個(gè)任務(wù)在一個(gè)周期都會(huì)分配到 200ms 左右的時(shí)間切片，然而這種調(diào)度和分配方式是 調(diào)度器的大問(wèn)題：
正是因?yàn)檎{(diào)度器存在了上述的問(wèn)題，所以 Linux 內(nèi)核在兩個(gè)版本后使用新的 調(diào)度器替換該實(shí)現(xiàn)。
調(diào)度器在 v2.6.0 到 v2.6.22 的 Linux 內(nèi)核中使用了四年的時(shí)間，它能夠在常數(shù)時(shí)間內(nèi)完成進(jìn)程調(diào)度，你可以在sched.h 和 sched.c 中查看 調(diào)度器的源代碼。因?yàn)閷?shí)現(xiàn)和功能復(fù)雜性的增加，調(diào)度器的代碼行數(shù)從 的 2100 行增加到 5000 行，它在調(diào)度器的基礎(chǔ)上進(jìn)行了如下的改進(jìn)：
調(diào)度器通過(guò)運(yùn)行隊(duì)列 runqueue 和優(yōu)先數(shù)組 prio_array 兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了 的時(shí)間復(fù)雜度。每一個(gè)運(yùn)行隊(duì)列都持有兩個(gè)優(yōu)先數(shù)組，分別存儲(chǔ)活躍的和過(guò)期的進(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 位，每一位都表示對(duì)應(yīng)優(yōu)先級(jí)的進(jìn)程是否存在。圖 17 中的優(yōu)先數(shù)組包含 3 個(gè)優(yōu)先級(jí)為 2 的進(jìn)程和 1 個(gè)優(yōu)先級(jí)為 5 的進(jìn)程。每一個(gè)優(yōu)先級(jí)的標(biāo)志位都對(duì)應(yīng)一個(gè) list_head 數(shù)組中的鏈表。 調(diào)度器使用上述的數(shù)據(jù)結(jié)構(gòu)進(jìn)行如下所示的調(diào)度：
上述的這些規(guī)則是 調(diào)度器運(yùn)行遵守的主要規(guī)則，除了上述規(guī)則之外，調(diào)度器還需要支持搶占、CPU 親和等功能，不過(guò)在這里就不展開(kāi)介紹了。
全局的運(yùn)行隊(duì)列是 調(diào)度器難以在對(duì)稱多處理器架構(gòu)上擴(kuò)展的主要原因。為了保證運(yùn)行隊(duì)列的一致性，調(diào)度器在調(diào)度時(shí)需要獲取運(yùn)行隊(duì)列的全局鎖，隨著處理器數(shù)量的增加，多個(gè)處理器在調(diào)度時(shí)會(huì)導(dǎo)致更多的鎖競(jìng)爭(zhēng)，嚴(yán)重影響調(diào)度性能。 調(diào)度器通過(guò)引入本地運(yùn)行隊(duì)列解決這個(gè)問(wèn)題，不同的 CPU 可以通過(guò) this_rq 獲取綁定在當(dāng)前 CPU 上的運(yùn)行隊(duì)列，降低了鎖的粒度和沖突的可能性。
#define this_rq() (&__get_cpu_var(runqueues))
圖 19 - 全局運(yùn)行隊(duì)列和本地運(yùn)行隊(duì)列
多個(gè)處理器由于不再需要共享全局的運(yùn)行隊(duì)列，所以增強(qiáng)了在對(duì)稱對(duì)處理器架構(gòu)上的擴(kuò)展性，當(dāng)我們?cè)黾有碌奶幚砥鲿r(shí)，只需要增加新的運(yùn)行隊(duì)列，這種方式不會(huì)引入更多的鎖沖突。
調(diào)度器中包含兩種不同的優(yōu)先級(jí)計(jì)算方式，一種是靜態(tài)任務(wù)優(yōu)先級(jí)，另一種是動(dòng)態(tài)任務(wù)優(yōu)先級(jí)。在默認(rèn)情況下，任務(wù)的靜態(tài)任務(wù)優(yōu)先級(jí)都是 0，不過(guò)我們可以通過(guò)系統(tǒng)調(diào)用 nice 改變?nèi)蝿?wù)的優(yōu)先級(jí)； 調(diào)度器會(huì)獎(jiǎng)勵(lì) I/O 密集型任務(wù)并懲罰 CPU 密集型任務(wù)，它會(huì)通過(guò)改變?nèi)蝿?wù)的靜態(tài)優(yōu)先級(jí)來(lái)完成優(yōu)先級(jí)的動(dòng)態(tài)調(diào)整，因?yàn)榕c用戶交互的進(jìn)程時(shí) I/O 密集型的進(jìn)程，這些進(jìn)程由于調(diào)度器的動(dòng)態(tài)策略會(huì)提高自身的優(yōu)先級(jí)，從而提升用戶體驗(yàn)。
完全公平調(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 由以下的多個(gè)文件組成：
通過(guò) CFS 的名字我們就能發(fā)現(xiàn)，該調(diào)度器的能為不同的進(jìn)程提供完全公平性。一旦某些進(jìn)程受到了不公平的待遇，調(diào)度器就會(huì)運(yùn)行這些進(jìn)程，從而維持所有進(jìn)程運(yùn)行時(shí)間的公平性。這種保證公平性的方式與『水多了加面，面多了加水』有一些相似：
調(diào)度器算法不斷計(jì)算各個(gè)進(jìn)程的運(yùn)行時(shí)間并依次調(diào)度隊(duì)列中的受到最不公平對(duì)待的進(jìn)程，保證各個(gè)進(jìn)程的運(yùn)行時(shí)間差不會(huì)大于最小運(yùn)行的時(shí)間單位。
雖然我們還是會(huì)延用運(yùn)行隊(duì)列這一術(shù)語(yǔ)，但是 CFS 的內(nèi)部已經(jīng)不再使用隊(duì)列來(lái)存儲(chǔ)進(jìn)程了，cfs_rq 是用來(lái)管理待運(yùn)行進(jìn)程的新結(jié)構(gòu)體，該結(jié)構(gòu)體會(huì)使用紅黑樹(shù)（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;
};紅黑樹(shù)（Red-black tree）是平衡的二叉搜索樹(shù)，紅黑樹(shù)的增刪改查操作的最壞時(shí)間復(fù)雜度為 ，也就是樹(shù)的高度，樹(shù)中最左側(cè)的節(jié)點(diǎn) rb_leftmost 運(yùn)行的時(shí)間最短，也是下一個(gè)待運(yùn)行的進(jìn)程。
注：在最新版本的 CFS 實(shí)現(xiàn)中，內(nèi)核使用虛擬運(yùn)行時(shí)間 vruntime 替代了等待時(shí)間，但是基本的調(diào)度原理和排序方式?jīng)]有太多變化。
CFS 的調(diào)度過(guò)程還是由 schedule 函數(shù)完成的，該函數(shù)的執(zhí)行過(guò)程可以分成以下幾個(gè)步驟：
CFS 的調(diào)度過(guò)程與 調(diào)度器十分類似，當(dāng)前調(diào)度器與前者的區(qū)別只是增加了可選的工作竊取機(jī)制并改變了底層的數(shù)據(jù)結(jié)構(gòu)。
CFS 中的調(diào)度類是比較有趣的概念，調(diào)度類可以決定進(jìn)程的調(diào)度策略。每個(gè)調(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ù)的初始化、入隊(duì)和出隊(duì)等函數(shù)，這里的設(shè)計(jì)與面向?qū)ο笾械脑O(shè)計(jì)稍微有些相似。內(nèi)核中包含 SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE、SCHED_FIFO 和 SCHED_RR 調(diào)度類，這些不同的調(diào)度類分別實(shí)現(xiàn)了 sched_class 中的函數(shù)以提供不同的調(diào)度行為。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
