詳細(xì)解讀Linux 2.6 完全公平調(diào)度算法CFS（Completely Fair Scheduler）

Linux 調(diào)度器簡(jiǎn)史

早期的 Linux 調(diào)度器使用了最低的設(shè)計(jì)，它顯然不關(guān)注具有很多處理器的大型架構(gòu)，更不用說(shuō)是超線程了。1.2 Linux 調(diào)度器使用了環(huán)形隊(duì)列用于可運(yùn)行的任務(wù)管理，使用循環(huán)調(diào)度策略。 此調(diào)度器添加和刪除進(jìn)程效率很高（具有保護(hù)結(jié)構(gòu)的鎖）。簡(jiǎn)而言之，該調(diào)度器并不復(fù)雜但是簡(jiǎn)單快捷。
Linux 版本 2.2 引入了調(diào)度類的概念，允許針對(duì)實(shí)時(shí)任務(wù)、非搶占式任務(wù)、非實(shí)時(shí)任務(wù)的調(diào)度策略。 2.2 調(diào)度器還包括對(duì)稱多處理 (SMP) 支持。
2.4 內(nèi)核包含了相對(duì)簡(jiǎn)單的調(diào)度器，按 O(N) 的時(shí)間間隔運(yùn)行（在調(diào)度事件期間它會(huì)迭代每個(gè)任務(wù)）。2.4 調(diào)度器將時(shí)間分割成 epoch，每個(gè) epoch 中，每個(gè)任務(wù)允許執(zhí)行到其時(shí)間切片用完。如果某個(gè)任務(wù)沒(méi)有使用其所有的時(shí)間切片，那么 剩余時(shí)間切片的一半將被添加到新時(shí)間切片使其在下個(gè) epoch 中可以執(zhí)行更長(zhǎng)時(shí)間。 調(diào)度器只是迭代任務(wù)，應(yīng)用 goodness 函數(shù)（指標(biāo)）決定下面執(zhí)行哪個(gè)任務(wù)。盡管這種方法比較簡(jiǎn)單，但是卻比較低效、缺乏可擴(kuò)展性而且不適合用在實(shí)時(shí)系統(tǒng)中。它還缺少利用新硬件架構(gòu)（比如多核處理器）的能力。
早期的 2.6 調(diào)度器，叫做 O(1) 調(diào)度器，它旨在解決 2.4 調(diào)度器存在的問(wèn)題 — 該調(diào)度器不需要迭代整個(gè)任務(wù)列表來(lái)確定要調(diào)度的下一個(gè)任務(wù)（因此得名 O(1)，這意味著它效率更高，擴(kuò)展性更好）。O(1) 調(diào)度器跟蹤運(yùn)行隊(duì)列中可運(yùn)行的任務(wù)（實(shí)際上，每個(gè)優(yōu)先級(jí)水平有兩個(gè)運(yùn)行隊(duì)列 — 一個(gè)用于活動(dòng)任務(wù)，一個(gè)用于過(guò)期任務(wù)）， 這意味著要確定接下來(lái)執(zhí)行的任務(wù)，調(diào)度器只需按優(yōu)先級(jí)將下一個(gè)任務(wù)從特定活動(dòng)的運(yùn)行隊(duì)列中取出即可）。 O(1) 調(diào)度器擴(kuò)展性更好而且包含交互性，提供了大量啟示用于確定任務(wù)是受 I/O 限制還是受處理器限制。 但是 O(1) 調(diào)度器在內(nèi)核中很笨拙。需要大量代碼計(jì)算啟示，難以管理并且對(duì)于純粹主義者而言未能體現(xiàn)算法的本質(zhì)。
?

為了解決 O(1) 調(diào)度器面臨的問(wèn)題以及應(yīng)對(duì)其他外部壓力， 需要改變某些東西。這種改變來(lái)自 Con Kolivas 的內(nèi)核補(bǔ)丁，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 這包含了他在 staircase 調(diào)度器方面的早期工作。這些工作的成果就是一個(gè)設(shè)計(jì)簡(jiǎn)單的調(diào)度器，包含了公平性和界限內(nèi)延遲。 Kolivas 的調(diào)度器吸引了很多人（并且很多人呼吁將其包含在目前的 2.6.21 主流內(nèi)核中），很顯然調(diào)度器的變革即將發(fā)生。 Ingo Molnar，O(1) 調(diào)度器的創(chuàng)造者，然后圍繞 Kolivas 的一些思想開(kāi)發(fā)了基于 CFS 的調(diào)度器。我們來(lái)剖析一下 CFS，從較高的層次上看看它是如何運(yùn)行的。

CFS 概述

CFS 背后的主要想法是維護(hù)為任務(wù)提供處理器時(shí)間方面的平衡（公平性）。這意味著應(yīng)給進(jìn)程分配相當(dāng)數(shù)量的處理器。分給某個(gè)任務(wù)的時(shí)間失去平衡時(shí)（意味著一個(gè)或多個(gè)任務(wù)相對(duì)于其他任務(wù)而言未被給予相當(dāng)數(shù)量的時(shí)間），應(yīng)給失去平衡的任務(wù)分配時(shí)間，讓其執(zhí)行。

要實(shí)現(xiàn)平衡，CFS 在叫做虛擬運(yùn)行時(shí)?的地方維持提供給某個(gè)任務(wù)的時(shí)間量。任務(wù)的虛擬運(yùn)行時(shí)越小， 意味著任務(wù)被允許訪問(wèn)服務(wù)器的時(shí)間越短 — 其對(duì)處理器的需求越高。CFS 還包含睡眠公平概念以便確保那些目前沒(méi)有運(yùn)行的 任務(wù)（例如，等待 I/O）在其最終需要時(shí)獲得相當(dāng)份額的處理器。

但是與之前的 Linux 調(diào)度器不同，它沒(méi)有將任務(wù)維護(hù)在運(yùn)行隊(duì)列中，CFS 維護(hù)了一個(gè)以時(shí)間為順序的紅黑樹(shù)（參見(jiàn)圖 1）。?紅黑樹(shù)?是一個(gè)樹(shù)，具有很多有趣、有用的屬性。首先，它是自平衡的，這意味著樹(shù)上沒(méi)有路徑比任何其他路徑長(zhǎng)兩倍以上。 第二，樹(shù)上的運(yùn)行按 O(log?n) 時(shí)間發(fā)生（其中?n?是樹(shù)中節(jié)點(diǎn)的數(shù)量）。這意味著您可以快速高效地插入或刪除任務(wù)。

圖 1. 紅黑樹(shù)示例

任務(wù)存儲(chǔ)在以時(shí)間為順序的紅黑樹(shù)中（由?sched_entity?對(duì)象表示），對(duì)處理器需求最多的任務(wù) （最低虛擬運(yùn)行時(shí)）存儲(chǔ)在樹(shù)的左側(cè)，處理器需求最少的任務(wù)（最高虛擬運(yùn)行時(shí)）存儲(chǔ)在樹(shù)的右側(cè)。 為了公平，調(diào)度器然后選取紅黑樹(shù)最左端的節(jié)點(diǎn)調(diào)度為下一個(gè)以便保持公平性。任務(wù)通過(guò)將其運(yùn)行時(shí)間添加到虛擬運(yùn)行時(shí)， 說(shuō)明其占用 CPU 的時(shí)間，然后如果可運(yùn)行，再插回到樹(shù)中。這樣，樹(shù)左側(cè)的任務(wù)就被給予時(shí)間運(yùn)行了，樹(shù)的內(nèi)容從右側(cè)遷移到左側(cè)以保持公平。 因此，每個(gè)可運(yùn)行的任務(wù)都會(huì)追趕其他任務(wù)以維持整個(gè)可運(yùn)行任務(wù)集合的執(zhí)行平衡。

------------------------------------------------------------------------------------------------------------------------------

CFS 內(nèi)部原理

Linux 內(nèi)的所有任務(wù)都由稱為?task_struct?的任務(wù)結(jié)構(gòu)表示。該結(jié)構(gòu)（以及其他相關(guān)內(nèi)容）完整地描述了任務(wù)并包括了任務(wù)的當(dāng)前狀態(tài)、其堆棧、進(jìn)程標(biāo)識(shí)、優(yōu)先級(jí)（靜態(tài)和動(dòng)態(tài)）等等。您可以在 ./linux/include/linux/sched.h 中找到這些內(nèi)容以及相關(guān)結(jié)構(gòu)。 但是因?yàn)椴皇撬腥蝿?wù)都是可運(yùn)行的，您在?task_struct?中不會(huì)發(fā)現(xiàn)任何與 CFS 相關(guān)的字段。 相反，會(huì)創(chuàng)建一個(gè)名為?sched_entity?的新結(jié)構(gòu)來(lái)跟蹤調(diào)度信息（參見(jiàn)圖 2）。

圖 2. 任務(wù)和紅黑樹(shù)的結(jié)構(gòu)層次

各種結(jié)構(gòu)的關(guān)系如?圖 2?所示。樹(shù)的根通過(guò)?rb_root?元素通過(guò)?cfs_rq?結(jié)構(gòu)（在 ./kernel/sched.c 中）引用。紅黑樹(shù)的葉子不包含信息，但是內(nèi)部節(jié)點(diǎn)代表一個(gè)或多個(gè)可運(yùn)行的任務(wù)。紅黑樹(shù)的每個(gè)節(jié)點(diǎn)都由?rb_node?表示，它只包含子引用和父對(duì)象的顏色。?rb_node?包含在sched_entity?結(jié)構(gòu)中，該結(jié)構(gòu)包含?rb_node?引用、負(fù)載權(quán)重以及各種統(tǒng)計(jì)數(shù)據(jù)。最重要的是，?sched_entity?包含?vruntime（64 位字段），它表示任務(wù)運(yùn)行的時(shí)間量，并作為紅黑樹(shù)的索引。 最后，task_struct?位于頂端，它完整地描述任務(wù)并包含?sched_entity?結(jié)構(gòu)。

就 CFS 部分而言，調(diào)度函數(shù)非常簡(jiǎn)單。 在 ./kernel/sched.c 中，您會(huì)看到通用?schedule()?函數(shù)，它會(huì)先搶占當(dāng)前運(yùn)行任務(wù)（除非它通過(guò)yield()?代碼先搶占自己）。注意 CFS 沒(méi)有真正的時(shí)間切片概念用于搶占，因?yàn)閾屨紩r(shí)間是可變的。 當(dāng)前運(yùn)行任務(wù)（現(xiàn)在被搶占的任務(wù)）通過(guò)對(duì)?put_prev_task?調(diào)用（通過(guò)調(diào)度類）返回到紅黑樹(shù)。 當(dāng)?schedule?函數(shù)開(kāi)始確定下一個(gè)要調(diào)度的任務(wù)時(shí)，它會(huì)調(diào)用?pick_next_task函數(shù)。此函數(shù)也是通用的（在 ./kernel/sched.c 中），但它會(huì)通過(guò)調(diào)度器類調(diào)用 CFS 調(diào)度器。 CFS 中的?pick_next_task?函數(shù)可以在 ./kernel/sched_fair.c（稱為?pick_next_task_fair()）中找到。 此函數(shù)只是從紅黑樹(shù)中獲取最左端的任務(wù)并返回相關(guān)?sched_entity。通過(guò)此引用，一個(gè)簡(jiǎn)單的?task_of()?調(diào)用確定返回的?task_struct?引用。通用調(diào)度器最后為此任務(wù)提供處理器。

------------------------------------------------------------------------------------------------------------------------------

優(yōu)先級(jí)和 CFS

CFS 不直接使用優(yōu)先級(jí)而是將其用作允許任務(wù)執(zhí)行的時(shí)間的衰減系數(shù)。 低優(yōu)先級(jí)任務(wù)具有更高的衰減系數(shù)，而高優(yōu)先級(jí)任務(wù)具有較低的衰減系數(shù)。 這意味著與高優(yōu)先級(jí)任務(wù)相比，低優(yōu)先級(jí)任務(wù)允許任務(wù)執(zhí)行的時(shí)間消耗得更快。 這是一個(gè)絕妙的解決方案，可以避免維護(hù)按優(yōu)先級(jí)調(diào)度的運(yùn)行隊(duì)列。

CFS 組調(diào)度

CFS 另一個(gè)有趣的地方是組調(diào)度?概念（在 2.6.24 內(nèi)核中引入）。組調(diào)度是另一種為調(diào)度帶來(lái)公平性的方式，尤其是在處理產(chǎn)生很多其他任務(wù)的任務(wù)時(shí)。 假設(shè)一個(gè)產(chǎn)生了很多任務(wù)的服務(wù)器要并行化進(jìn)入的連接（HTTP 服務(wù)器的典型架構(gòu)）。不是所有任務(wù)都會(huì)被統(tǒng)一公平對(duì)待， CFS 引入了組來(lái)處理這種行為。產(chǎn)生任務(wù)的服務(wù)器進(jìn)程在整個(gè)組中（在一個(gè)層次結(jié)構(gòu)中）共享它們的虛擬運(yùn)行時(shí)，而單個(gè)任務(wù)維持其自己獨(dú)立的虛擬運(yùn)行時(shí)。這樣單個(gè)任務(wù)會(huì)收到與組大致相同的調(diào)度時(shí)間。您會(huì)發(fā)現(xiàn) /proc 接口用于管理進(jìn)程層次結(jié)構(gòu)，讓您對(duì)組的形成方式有完全的控制。使用此配置，您可以跨用戶、跨進(jìn)程或其變體分配公平性。

調(diào)度類和域

與 CFS 一起引入的是調(diào)度類概念（可以回顧?圖 2）。每個(gè)任務(wù)都屬于一個(gè)調(diào)度類，這決定了任務(wù)將如何調(diào)度。 調(diào)度類定義一個(gè)通用函數(shù)集（通過(guò)?sched_class），函數(shù)集定義調(diào)度器的行為。例如，每個(gè)調(diào)度器提供一種方式， 添加要調(diào)度的任務(wù)、調(diào)出要運(yùn)行的下一個(gè)任務(wù)、提供給調(diào)度器等等。每個(gè)調(diào)度器類都在一對(duì)一連接的列表中彼此相連，使類可以迭代（例如， 要啟用給定處理器的禁用）。一般結(jié)構(gòu)如圖 3 所示。注意，將任務(wù)函數(shù)加入隊(duì)列或脫離隊(duì)列只需從特定調(diào)度結(jié)構(gòu)中加入或移除任務(wù)。 函數(shù)?pick_next_task?選擇要執(zhí)行的下一個(gè)任務(wù)（取決于調(diào)度類的具體策略）。

圖 3. 調(diào)度類圖形視圖

但是不要忘了調(diào)度類是任務(wù)結(jié)構(gòu)本身的一部分（參見(jiàn)?圖 2）。這一點(diǎn)簡(jiǎn)化了任務(wù)的操作，無(wú)論其調(diào)度類如何。例如， 以下函數(shù)用 ./kernel/sched.c 中的新任務(wù)搶占當(dāng)前運(yùn)行任務(wù)（其中?curr?定義了當(dāng)前運(yùn)行任務(wù)，?rq?代表 CFS 紅黑樹(shù)而?p?是下一個(gè)要調(diào)度的任務(wù)）：

static inline void check_preempt( struct rq *rq, struct task_struct *p ){ rq->curr->sched_class->check_preempt_curr( rq, p );}

如果此任務(wù)正使用公平調(diào)度類，則?check_preempt_curr()?將解析為?check_preempt_wakeup()。 您可以在 ./kernel/sched_rt.c, ./kernel/sched_fair.c 和 ./kernel/sched_idle.c 中查看這些關(guān)系。

調(diào)度類是調(diào)度發(fā)生變化的另一個(gè)有趣的地方，但是隨著調(diào)度域的增加，功能也在增加。 這些域允許您出于負(fù)載平衡和隔離的目的將一個(gè)或多個(gè)處理器按層次關(guān)系分組。 一個(gè)或多個(gè)處理器能夠共享調(diào)度策略（并在其之間保持負(fù)載平衡）或?qū)崿F(xiàn)獨(dú)立的調(diào)度策略從而故意隔離任務(wù)。

其他調(diào)度器

繼續(xù)研究調(diào)度，您將發(fā)現(xiàn)正在開(kāi)發(fā)中的調(diào)度器將會(huì)突破性能和擴(kuò)展性的界限。Con Kolivas 沒(méi)有被他的 Linux 經(jīng)驗(yàn)羈絆，他開(kāi)發(fā)出了另一個(gè) Linux 調(diào)度器，其縮寫(xiě)為：BFS。該調(diào)度器據(jù)說(shuō)在 NUMA 系統(tǒng)以及移動(dòng)設(shè)備上具有更好的性能， 并且被引入了?Android?操作系統(tǒng)的一款衍生產(chǎn)品中。

?