調(diào)度系統(tǒng)設(shè)計(jì)精要-創(chuàng)新互聯(lián)

作者 |?Draveness

成都創(chuàng)新互聯(lián)公司堅(jiān)信：善待客戶，將會(huì)成為終身客戶。我們能堅(jiān)持多年，是因?yàn)槲覀円恢笨芍档眯刨?。我們從不忽悠初訪客戶，我們用心做好本職工作，不忘初心，方得始終。十年網(wǎng)站建設(shè)經(jīng)驗(yàn)成都創(chuàng)新互聯(lián)公司是成都老牌網(wǎng)站營(yíng)銷服務(wù)商,為您提供成都網(wǎng)站建設(shè)、成都做網(wǎng)站、網(wǎng)站設(shè)計(jì)、H5技術(shù)、網(wǎng)站制作、成都品牌網(wǎng)站建設(shè)、成都小程序開(kāi)發(fā)服務(wù),給眾多知名企業(yè)提供過(guò)好品質(zhì)的建站服務(wù)。

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

調(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ì)的核心原理。

設(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ì)。

1. 需求調(diào)研

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

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

應(yīng)用場(chǎng)景

調(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ù)的以下特征：

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

而用于執(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ù)和資源有以下特性：

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

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

調(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)度目的

在深入分析調(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)容：

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

這些都是偏理論的調(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ù)考慮的事情，不具有足夠的相似性。

2. 調(diào)度原理

性能優(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é)作式調(diào)度與搶占式調(diào)度；
• 單調(diào)度器與多調(diào)度器；
• 任務(wù)分享與任務(wù)竊??；

協(xié)作式與搶占式

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

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

圖 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)度。

單調(diào)度器與多調(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ǔ)言都選擇了工作竊取策略。

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

本節(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)度決策。

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

當(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)模塊

狀態(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)度合適的資源：

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

圖 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)度器外部

如果我們將調(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)度與并行調(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)度器

反調(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)景下使用。

操作系統(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)度器。

有一些讀者可能會(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ò)程。

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

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

長(zhǎng)期調(diào)度器

長(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ù)量：

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

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

中期調(diào)度器

中期調(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)度器

短期調(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í)行十分頻繁。

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

本節(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ù)的平衡；

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

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

初始調(diào)度器

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í)行不同的邏輯：

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

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)度。

O(n)調(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)題：

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

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

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

調(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)度器支持了??時(shí)間復(fù)雜度的調(diào)度；
• 調(diào)度器支持了對(duì)稱多處理（Symmetric multiprocessing，SMP）的擴(kuò)展性；
• 調(diào)度器優(yōu)化了對(duì)稱多處理的親和性。

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

調(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)度：

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

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

本地運(yùn)行隊(duì)列

全局的運(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ì)引入更多的鎖沖突。

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

調(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)度器

完全公平調(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è)文件組成：

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

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

調(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í)間單位。

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

雖然我們還是會(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)]有太多變化。

調(diào)度過(guò)程

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

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

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

調(diào)度類

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)度行為。

3. 小結(jié)

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

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

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

4. 延伸閱讀

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

Go 語(yǔ)言

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

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

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

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

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

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

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

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

單線程調(diào)度器

Go 語(yǔ)言在 0.x 版本調(diào)度器中只包含表示 Goroutine 的 G 和表示線程的 M 兩種結(jié)構(gòu)體，全局也只有一個(gè)線程。我們可以在 clean up scheduler 提交中找到單線程調(diào)度器的源代碼，在這時(shí) Go 語(yǔ)言的 調(diào)度器 還是由 C 語(yǔ)言實(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ù)會(huì)遵循如下所示的過(guò)程執(zhí)行：

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

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

多線程調(diào)度器

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

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

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

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

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

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

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

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

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

基于任務(wù)竊取的 Go 語(yǔ)言調(diào)度器使用了沿用至今的 G-M-P 模型，我們能在 runtime: improved scheduler 提交中找到任務(wù)竊取調(diào)度器剛被實(shí)現(xiàn)時(shí)的源代碼，調(diào)度器的 schedule 函數(shù)到現(xiàn)在反而更簡(jiǎ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)行時(shí)在等待垃圾回收，調(diào)用 gcstopm 函數(shù)；
• 調(diào)用 runqget 和 findrunnable 從本地的或者全局的運(yùn)行隊(duì)列中獲取待執(zhí)行的 Goroutine；
• 調(diào)用 execute 函數(shù)在當(dāng)前線程 M 上運(yùn)行 Goroutine。

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

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

圖 21 - G-M-P 模型

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

搶占式調(diào)度器

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

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

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

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

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

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

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

這種做法沒(méi)有帶來(lái)運(yùn)行時(shí)的過(guò)多額外開(kāi)銷，實(shí)現(xiàn)也相對(duì)比較簡(jiǎn)單，不過(guò)增加了運(yùn)行時(shí)的復(fù)雜度，總體來(lái)看還是一種比較成功的實(shí)現(xiàn)。因?yàn)樯鲜龅膿屨际峭ㄟ^(guò)編譯器在特定時(shí)機(jī)插入函數(shù)實(shí)現(xiàn)的，還是需要函數(shù)調(diào)用作為入口才能觸發(fā)搶占，所以這是一種協(xié)作式的搶占式調(diào)度。

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

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

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

• runtime: add general suspendG/resumeG。掛起 Goroutine 的過(guò)程是在棧掃描時(shí)完成的，我們通過(guò) runtime.suspendG 和 runtime.resumeG 兩個(gè)函數(shù)重構(gòu)棧掃描這一過(guò)程；調(diào)用 runtime.suspendG 函數(shù)時(shí)會(huì)將運(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。支持通過(guò)向線程發(fā)送信號(hào)的方式暫停運(yùn)行的 Goroutine；在 runtime.sighandler 函數(shù)中注冊(cè)了 SIGURG 信號(hào)的處理函數(shù) runtime.doSigPreempt；runtime.preemptM 函數(shù)可以向線程發(fā)送搶占請(qǐng)求；
• runtime: implement async scheduler preemption。修改 runtime.preemptone 函數(shù)的實(shí)現(xiàn)，加入異步搶占的邏輯。

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

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

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

• 該信號(hào)需要被調(diào)試器透?jìng)鳎?/li>
• 該信號(hào)不會(huì)被內(nèi)部的 libc 庫(kù)使用并攔截；
• 該信號(hào)可以隨意出現(xiàn)并且不觸發(fā)任何后果；
• 我們需要處理多個(gè)平臺(tái)上的不同信號(hào)。

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

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

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

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

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

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

2. 小結(jié)

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

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

3. 延伸閱讀

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

Kubernetes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如上圖所示，我們假設(shè)調(diào)度器中存在一個(gè)謂詞算法和一個(gè) Map-Reduce 優(yōu)先級(jí)算法，當(dāng)我們?yōu)橐粋€(gè) Pod 在 6 個(gè)節(jié)點(diǎn)中選擇最合適的一個(gè)時(shí)，6 個(gè)節(jié)點(diǎn)會(huì)先經(jīng)過(guò)謂詞的篩選，圖中的謂詞算法會(huì)過(guò)濾掉一半的節(jié)點(diǎn)，剩余的 3 個(gè)節(jié)點(diǎn)經(jīng)過(guò) Map 和 Reduce 兩個(gè)過(guò)程分別得到了 5、10 和 5 分，最終調(diào)度器就會(huì)選擇分?jǐn)?shù)最高的 4 號(hào)節(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í)行全部的謂詞算法過(guò)濾節(jié)點(diǎn)。謂詞算法會(huì)根據(jù)傳入的 Pod 和 Node 對(duì)節(jié)點(diǎn)進(jìn)行過(guò)濾，這時(shí)會(huì)過(guò)濾掉端口號(hào)沖突、資源不足的節(jié)點(diǎn)；調(diào)用所有調(diào)度器擴(kuò)展的 Filter 方法輔助過(guò)濾；
• 調(diào)用 PrioritizeNodes 函數(shù)為所有的節(jié)點(diǎn)打分。以 Pod 和 Node 作為參數(shù)并發(fā)執(zhí)行同一優(yōu)先級(jí)的 PriorityMapFunction；Pod 和優(yōu)先級(jí)返回的 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)先級(jí)算法時(shí)的調(diào)度過(guò)程，我們?cè)谶@里省略了調(diào)度器的優(yōu)先隊(duì)列中的排序，出現(xiàn)調(diào)度錯(cuò)誤時(shí)的搶占以及 Pod 持久存儲(chǔ)卷綁定到 Node 上的過(guò)程，只保留了核心的調(diào)度邏輯。

調(diào)度框架

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

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

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

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

我們可以將調(diào)度器中的 Scheduler.scheduleOne 方法作為入口分析基于調(diào)度框架的調(diào)度器實(shí)現(xiàn)，每次調(diào)用該方法都會(huì)完成一遍為 Pod 調(diào)度節(jié)點(diǎn)的全部流程，我們將該函數(shù)的執(zhí)行過(guò)程分成調(diào)度和綁定兩個(gè)階段，首先是調(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)部?jī)?yōu)先隊(duì)列的 MakeNextPodFunc 返回的函數(shù)從隊(duì)列中獲取下一個(gè)等待調(diào)度的 Pod，用于維護(hù)等待 Pod 的隊(duì)列會(huì)執(zhí)行 QueueSort 插件；
• 調(diào)用 genericScheduler.Schedule 函數(shù)選擇節(jié)點(diǎn)，該過(guò)程會(huì)執(zhí)行 PreFilter、Filter、PostFilter、Score 四個(gè)擴(kuò)展點(diǎn)的插件；
• 調(diào)用 framework.RunReservePlugins 函數(shù)運(yùn)行 Reserve 插件用于保留資源并進(jìn)入綁定階段（綁定階段運(yùn)行時(shí)間較長(zhǎng)，避免資源被搶占）。如果運(yùn)行失敗執(zhí)行，調(diào)用 framework.RunUnreservePlugins 函數(shù)運(yùn)行 Unreserve 插件。

因?yàn)槊恳淮握{(diào)度決策都會(huì)改變上下文，所以該階段 Kubernetes 需要串行執(zhí)行。而綁定階段就是實(shí)現(xiàn)調(diào)度的過(guò)程了，我們會(huì)創(chuàng)建一個(gè)新的 Goroutine 并行執(zhí)行綁定循環(huán)：

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

                標(biāo)題名稱：調(diào)度系統(tǒng)設(shè)計(jì)精要-創(chuàng)新互聯(lián)
                

                分享地址：http://muchs.cn/article32/djggsc.html
            
            

                成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、Google、網(wǎng)站內(nèi)鏈、品牌網(wǎng)站設(shè)計(jì)、外貿(mào)建站、網(wǎng)站設(shè)計(jì)公司            
            

                廣告
                
            
            

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