Linux 調(diào)度器對(duì)比

BFS vs CFS，設(shè)計(jì)上的不同 白天 Con Kolivas 在醫(yī)院里當(dāng)麻醉師，為人們解除痛苦，業(yè)余的時(shí)候借 Linux 解除自己的痛苦。額，Kolivas 學(xué)習(xí) Linux 并不是為了解決痛苦，我臆測(cè)而已。但據(jù) Kolivas 自述，他接觸 Linux 內(nèi)核時(shí)連 C 語(yǔ)言也沒(méi)有學(xué)習(xí)過(guò)。。。這個(gè)事實(shí)證明，語(yǔ)言只是一項(xiàng)工具，對(duì)問(wèn)題本質(zhì)的深入理解才是寫(xiě)程序的關(guān)鍵。可能還有執(zhí)著，CFS 和 RSDL 之爭(zhēng)導(dǎo)致 Kolivas 離開(kāi) Linux 社區(qū)，此去經(jīng)年，當(dāng) Kolivas 再次開(kāi)始看內(nèi)核代碼的時(shí)候，他立即發(fā)現(xiàn) CFS 存在以下幾個(gè)設(shè)計(jì)上的問(wèn)題:

CFS 的目標(biāo)是支持從桌面到高端服務(wù)器的所有應(yīng)用場(chǎng)景，這種大而全的設(shè)計(jì)思路導(dǎo)致其必須做一些實(shí)現(xiàn)上的折中，此外，那些只有在高端機(jī)器中才需要的特性將引入不必要的復(fù)雜代碼。

其次，為了維護(hù)多 CPU 上的公平性，CFS 采用了負(fù)載平衡機(jī)制，Kolivas 認(rèn)為，這些復(fù)雜代碼抵消了 per cpu queue 曾帶來(lái)的好處。

最后，主流內(nèi)核的 CFS 還是對(duì)睡眠進(jìn)程存在一些偏好，這意味著"不公平"。

在現(xiàn)實(shí)中，調(diào)度算法類(lèi)似一個(gè)處境尷尬的主婦，滿(mǎn)足孩子對(duì)晚餐的要求便有可能傷害到老人的食欲。Linux 內(nèi)核一直試圖做出一道讓全家老少都喜歡的菜，在這方面，CFS 已經(jīng)做的很好。但一道能被所有人接受的菜，或許就意味著稍許平淡。而 BFS 只打算滿(mǎn)足一種口味，以便將這種口味發(fā)展到極限。

根據(jù) Linux Magazine的說(shuō)法，Con Kolivas是看到了下面這則來(lái)自 xkcd 的漫畫(huà)而開(kāi)始思考 BFS 的。

事情源于一些 Linux 用戶(hù)，他們發(fā)現(xiàn) Linux 雖然號(hào)稱(chēng)能夠充分發(fā)揮 4096 顆 CPU 系統(tǒng)的計(jì)算能力，但在普通的 laptop 上卻無(wú)法流暢地播放 Youtube 視頻。

這讓人們開(kāi)始思考，對(duì)于 Desktop 環(huán)境來(lái)講，CFS 哪些復(fù)雜的特性究竟是否還有意義?人們是否有必要在自己的個(gè)人電腦中使用一個(gè)支持 4096 個(gè) CPU 的調(diào)度器?

BFS 正是對(duì)這種質(zhì)疑的自然反應(yīng)。它不打算支持 4096 個(gè) CPU 的龐然大物，BFS 的目標(biāo)是普通人使用的桌面電腦。此外，BFS 還刪除了那些只有在服務(wù)器上才需要的特性。比如，BFS 拋棄了 CFS 的組調(diào)度特性，類(lèi)似 CGROUP 這樣的特性對(duì)于普通的桌面用戶(hù)是多余的技術(shù)。

這很容易理解:在只有一個(gè) CPU 的系統(tǒng)中，誰(shuí)還會(huì)設(shè)計(jì)多個(gè) CGroup，哪里還能用到 NUMA domain等概念呢?

此外 BFS 使用單一的 run queue，不再需要復(fù)雜的負(fù)載均衡機(jī)制。由于不再有 CGROUP 概念，也不再需要 Group 間的負(fù)載均衡。

這些簡(jiǎn)單的裁剪使得 BFS 的代碼極大地簡(jiǎn)化，簡(jiǎn)化的代碼意味著執(zhí)行一次調(diào)度所需要的指令數(shù)減少了，相應(yīng)的 footprint 自然也減少了。

當(dāng)然簡(jiǎn)化代碼只是一個(gè)顯而易見(jiàn)的方面，更重要的是，這種理念的不同會(huì)對(duì)最終的調(diào)度器實(shí)現(xiàn)產(chǎn)生更加深遠(yuǎn)的影響，這實(shí)在是難以盡述。

多隊(duì)列 vs 單一隊(duì)列

?在 Linux 內(nèi)核進(jìn)入 2.6 時(shí)，調(diào)度器采用 per cpu run queue 從而克服了單一 run queue 的局限。在多 CPU 系統(tǒng)中，單一 run queue 意味著 run queue 成為了系統(tǒng)的瓶頸，因?yàn)樵谕粫r(shí)刻，一個(gè) CPU 訪(fǎng)問(wèn) run queue 時(shí)，其他的 CPU 即使空閑也必須等待。當(dāng)使用 per CPU 的 run queue 之后，每個(gè) CPU 不必再使用大鎖，從而能夠并行地處理調(diào)度。

但很多事情都不像第一眼看上去那樣簡(jiǎn)單。

Kolivas 發(fā)現(xiàn)，采用 per cpu run queue 所帶來(lái)的好處會(huì)被追求公平性的 load balance 代碼所抵消。在目前的 CFS 調(diào)度器中，每顆 CPU 只維護(hù)本地 run queue 中所有進(jìn)程的公平性，為了實(shí)現(xiàn)跨 CPU 的調(diào)度公平性，CFS 必須定時(shí)進(jìn)行 load balance，將一些進(jìn)程從繁忙的 CPU 的 run queue 中移到其他空閑的 run queue 中。

這個(gè) load balance 的過(guò)程需要獲得其他 run queue 的鎖，這種操作降低了多運(yùn)行隊(duì)列帶來(lái)的并行性。

并且在復(fù)雜情況下，這種因 load balance 而引入的 footprint 將非?？捎^(guān)。

當(dāng)然，load balance 引入的加鎖操作依然比全局鎖的代價(jià)要低，這種代價(jià)差異隨著 CPU 個(gè)數(shù)的增加而更加顯著。但請(qǐng)您注意，BFS 并不打算為那些擁有 1024 個(gè) CPU 的系統(tǒng)工作，假若系統(tǒng)中的 CPU 個(gè)數(shù)有限時(shí)，多 run queue 的優(yōu)勢(shì)便不明顯了。

而 BFS 采用單一隊(duì)列之后，每一個(gè)需要調(diào)度的新進(jìn)程都可以在全局范圍內(nèi)查找最合適的 CPU，而無(wú)需 CFS 那樣等待 load balance 代碼來(lái)決定，這減少了多 CPU 之間裁決的延遲，最終的結(jié)果是更小的調(diào)度延遲。

向前看還是向后看?

多年來(lái) Kolivas 一直關(guān)注著 Linux 在 desktop 上的表現(xiàn)。對(duì)于 desktop 的用戶(hù)，最注重的不是系統(tǒng)的吞吐量，而是交互性程序的流暢體驗(yàn)。從 SD 開(kāi)始，Kolivas 就告訴內(nèi)核黑客們，完全公平能夠從根本上保證交互性。他始終堅(jiān)持一個(gè)基本觀(guān)點(diǎn):調(diào)度器應(yīng)該 forward look only。決不要去考慮一個(gè)進(jìn)程的過(guò)去。

CFS 卻偏偏要考慮進(jìn)程的過(guò)去。2.6.23 的時(shí)候，CFS 記錄并使用 sleep time。之后不久，在 2.6.24 發(fā)布的時(shí)候，CFS 合并了"Real Fair Scheduler"，刪除了 sleep time。因此在 2.6.24 之后的內(nèi)核中，CFS 終于也不再考慮進(jìn)程過(guò)去的睡眠時(shí)間。

但 CFS 還是保留了 sleeper fairness 的思想，當(dāng)進(jìn)程 wakeup 的時(shí)候，在 place_entity() 函數(shù)中，CFS 將對(duì) sleeper 進(jìn)行獎(jiǎng)勵(lì)，以便其能盡快得到 CPU。這個(gè)策略是非常微妙的，我們?cè)?2.1 節(jié)中詳細(xì)介紹了 sleeper fairness 的演進(jìn)過(guò)程。假如您花些時(shí)間回頭再看看，就會(huì)發(fā)現(xiàn) sleeper fairness 曾造成怎樣嚴(yán)重的延遲問(wèn)題。雖然 Ingo 自稱(chēng) Gentle fairness 解決了延遲問(wèn)題，但從代碼上看，Gentle Fairness 只是對(duì) sleeper 的獎(jiǎng)勵(lì)減半而已。因此我們可以說(shuō)，CFS 依然對(duì) Sleeper 進(jìn)程進(jìn)行獎(jiǎng)勵(lì)，這代表著一種偏好，一種"不公平"。而這，正是 BFS 所反對(duì)的。

BFS 中，當(dāng)一個(gè)進(jìn)程 wakeup 時(shí)，調(diào)度器將根據(jù)進(jìn)程的 deadline 來(lái)進(jìn)行選擇(關(guān)于 deadline 本文將在第 4 章中詳細(xì)描述)，其結(jié)果是，更早睡眠的進(jìn)程能更快地得到調(diào)度;CFS 的 sleeper fairness 則意味著要根據(jù) wakeup 的時(shí)間來(lái)選擇下一個(gè)被調(diào)度的進(jìn)程，更早 wakeup 的進(jìn)程會(huì)更快得到調(diào)度。

這種不同究竟會(huì)對(duì)桌面應(yīng)用造成何種影響尚沒(méi)有理論依據(jù)可以參考。但我個(gè)人認(rèn)為，BFS 的策略更加合理。

您現(xiàn)在可能已經(jīng)讀得有些煩躁了 ( 這些英文加中文的說(shuō)些啥啊 )，所以我還是盡快介紹一下 BFS 的實(shí)現(xiàn)細(xì)節(jié)吧。然后或許您會(huì)理解我，有些詞還是不翻譯更好。

BFS 是一個(gè)進(jìn)程調(diào)度器，可以解釋為"腦殘調(diào)度器"。這古怪的名字有多重含義，比較容易被接受的一個(gè)說(shuō)法為:它如此簡(jiǎn)單，卻如此出色，這會(huì)讓人對(duì)自己的思維能力產(chǎn)生懷疑。

BFS 不會(huì)被合并進(jìn)入 Linus 維護(hù)的 Linux mainline，BFS 本身也不打算這么做。但 BFS 擁有眾多的擁躉，這只有一個(gè)原因:BFS 非常出色，它讓用戶(hù)的桌面環(huán)境達(dá)到了前所未有的流暢。在硬件越來(lái)越先進(jìn)，系統(tǒng)卻依然常顯得遲鈍的時(shí)代，這實(shí)在讓人興奮。

進(jìn)入 2010 年，Android 開(kāi)發(fā)一個(gè)分支使用 BFS 作為其操作系統(tǒng)的標(biāo)準(zhǔn)調(diào)度器，這也證明了 BFS 的價(jià)值。后來(lái)放棄。

linux調(diào)度器(BFS )是一款專(zhuān)門(mén)為 Linux 桌面環(huán)境所設(shè)計(jì)的內(nèi)核調(diào)度器，它基于 Staircase Deadline和 EEVDF 算法，支持 Linux 2.6.31之后的內(nèi)核。它提供了前所未有的流暢桌面性能，不僅得到了用戶(hù)的認(rèn)可，也為一些商業(yè)系統(tǒng)所采用。

調(diào)度器是非常復(fù)雜的話(huà)題，尤其是 CFS 調(diào)度器，想要描述清楚，需要一支非凡的筆，我還沒(méi)有找到。但 BFS 非常簡(jiǎn)單，所以我才有勇氣在這里寫(xiě)點(diǎn)兒 BFS 的實(shí)現(xiàn)原理什么的。首先介紹幾個(gè)關(guān)鍵概念。

虛擬 Deadline ( Virtual Deadline )

當(dāng)一個(gè)進(jìn)程被創(chuàng)建時(shí)，它被賦予一個(gè)固定的時(shí)間片，和一個(gè)虛擬 Deadline。該虛擬 deadline 的計(jì)算公式非常簡(jiǎn)單:

其中 jiffies 是當(dāng)前時(shí)間 , user_priority 是進(jìn)程的優(yōu)先級(jí)，rr_interval 代表 round-robin interval，近似于一個(gè)進(jìn)程必須被調(diào)度的最后期限，所謂 Deadline 么。不過(guò)在這個(gè) Deadline 之前還有一個(gè)形容詞為 Virtual，因此這個(gè) Deadline 只是表達(dá)一種愿望而已，并非很多領(lǐng)導(dǎo)們常說(shuō)的那種 deadline。

虛擬 Deadline 將用于調(diào)度器的 picknext 決策，這將在后續(xù)章節(jié)詳細(xì)描述。

進(jìn)程隊(duì)列的表示方法和調(diào)度策略

在操作系統(tǒng)內(nèi)部，所有的 Ready 進(jìn)程都被存放在進(jìn)程隊(duì)列中，調(diào)度器從進(jìn)程隊(duì)列中選取下一個(gè)被調(diào)度的進(jìn)程。因此如何設(shè)計(jì)進(jìn)程隊(duì)列是我們研究調(diào)度器的一個(gè)重要話(huà)題。BFS 采用了非常傳統(tǒng)的進(jìn)程隊(duì)列表示方法，即 bitmap 加 queue。

BFS 將所有進(jìn)程分成 4 類(lèi)，分別表示不同的調(diào)度策略 :

Realtime，實(shí)時(shí)進(jìn)程 SCHED_ISO，isochronous 進(jìn)程，用于交互式任務(wù) SCHED_NORMAL，普通進(jìn)程 SCHED_IDELPRO，低優(yōu)先級(jí)任務(wù) 實(shí)時(shí)進(jìn)程總能獲得 CPU，采用 Round Robin 或者 FIFO 的方法來(lái)選擇同樣優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程。他們需要 superuser 的權(quán)限，通常限于那些占用 CPU 時(shí)間不多卻非常在乎 Latency 的進(jìn)程。

SCHED_ISO 在主流內(nèi)核中至今仍未實(shí)現(xiàn)，Con 早在 2003 年就提出了這個(gè) patch，但一直無(wú)法進(jìn)入主流內(nèi)核，這種調(diào)度策略是為了那些 near-realtime 的進(jìn)程設(shè)計(jì)的。如前所述，實(shí)時(shí)進(jìn)程需要用戶(hù)有 superuser 的權(quán)限，這類(lèi)進(jìn)程能夠獨(dú)占 CPU，因此只有很少的進(jìn)程可以被配置為實(shí)時(shí)進(jìn)程。對(duì)于那些對(duì)交互性要求比較高的，又無(wú)法成為實(shí)時(shí)進(jìn)程的進(jìn)程，BFS 將采用 SCHED_ISO，這些進(jìn)程能夠搶占 SCHED_NORMAL 進(jìn)程。他們的優(yōu)先級(jí)比 SCHED_NORMAL 高，但又低于實(shí)時(shí)進(jìn)程。此外當(dāng) SCHED_ISO 進(jìn)程占用 CPU 時(shí)間達(dá)到一定限度后，會(huì)被降級(jí)為 SCHED_NORMAL，防止其獨(dú)占整個(gè)系統(tǒng)資源。

SCHED_NORMAL 類(lèi)似于主流調(diào)度器 CFS 中的 SCHED_OTHER，是基本的分時(shí)調(diào)度策略。

SCHED_IDELPRO 類(lèi)似于 CFS 中的 SCHED_IDLE，即只有當(dāng) CPU 即將處于 IDLE 狀態(tài)時(shí)才被調(diào)度的進(jìn)程。

在這些不同的調(diào)度策略中，實(shí)時(shí)進(jìn)程分成 100 個(gè)不同的優(yōu)先級(jí)，加上其他三個(gè)調(diào)度策略，一共有 103 個(gè)不 同的進(jìn)程類(lèi)型。對(duì)于每個(gè)進(jìn)程類(lèi)型，系統(tǒng)中都有可能有多個(gè)進(jìn)程同時(shí) Ready，比如很可能有兩個(gè)優(yōu)先級(jí)為 10 的 RT 進(jìn)程同時(shí) Ready，所以對(duì)于每個(gè)類(lèi)型，還需要一個(gè)隊(duì)列來(lái)存儲(chǔ)屬于該類(lèi)型的 ready 進(jìn)程。

BFS 用 103 個(gè) bitmap 來(lái)表示是否有相應(yīng)類(lèi)型的進(jìn)程準(zhǔn)備進(jìn)行調(diào)度。如圖所示:

當(dāng)任何一種類(lèi)型的進(jìn)程隊(duì)列非空時(shí)，即存在 Ready 進(jìn)程時(shí)，相應(yīng)的 bitmap 位被設(shè)置為 1。

調(diào)度器如何在這樣一個(gè) bitmap 加 queue 的復(fù)雜結(jié)構(gòu)中選擇下一個(gè)被調(diào)度的進(jìn)程的問(wèn)題被稱(chēng)為 Task Selection 或者 pick next。

Task Selection i.e. Pick Next

當(dāng)調(diào)度器決定進(jìn)行進(jìn)程調(diào)度的時(shí)候，BFS 將按照下面的原則來(lái)進(jìn)行任務(wù)的選擇:

首先查看 bitmap 是否有置位的比特。比如上圖，對(duì)應(yīng)于 SCHED_NORMAL 的 bit 被置位，表明有類(lèi)型為 SCHED_NORMAL 的進(jìn)程 ready。如果有 SCHED_ISO 或者 RT task 的比特被置位，則優(yōu)先處理他們。

選定了相應(yīng)的 bit 位之后，便需要遍歷其相應(yīng)的子隊(duì)列。假如是一個(gè) RT 進(jìn)程的子隊(duì)列，則選取其中的第一個(gè)進(jìn)程。如果是其他的隊(duì)列，那么就采用 EEVDF 算法來(lái)選取合適的進(jìn)程。

EEVDF，即 earliest eligible virtual deadline first。BFS 將遍歷該子隊(duì)列，一個(gè)雙向列表，比較隊(duì)列中的每一個(gè)進(jìn)程的 Virtual Deadline 值，找到最小的那個(gè)。最壞情況下，這是一個(gè) O(n) 的算法，即需要遍歷整個(gè)雙向列表，假如其中有 n 個(gè)進(jìn)程，就需要進(jìn)行 n 此讀取和比較。

但實(shí)際上，往往不需要遍歷整個(gè) n 個(gè)進(jìn)程，這是因?yàn)?BFS 還有這樣一個(gè)搜索條件:

當(dāng)某個(gè)進(jìn)程的 Virtual Deadline 小于當(dāng)前的 jiffies 值時(shí)，直接返回該進(jìn)程。并將其從就緒隊(duì)列中刪除，下次再 insert 時(shí)會(huì)放到隊(duì)列的尾部，從而保證每個(gè)進(jìn)程都有可能被選中，而不會(huì)出現(xiàn)饑餓現(xiàn)象。

這條規(guī)則對(duì)應(yīng)于這樣一種情況，即進(jìn)程已經(jīng)睡眠了比較長(zhǎng)的時(shí)間，以至于已經(jīng)睡過(guò)了它的 Virtual Deadline，

T1 本來(lái)的 virtual deadline 為 t1，它 sleep 之后，其他的進(jìn)程比如 T2 開(kāi)始運(yùn)行，等到 T1 再次 wakeup 的時(shí)候，當(dāng)時(shí)的 jiffies 已經(jīng)大于 t1，在這種情況下，T1 無(wú)需和其他進(jìn)程的 virtual deadline 相比較，而直接被 BFS 調(diào)度器選取。

三個(gè)基本的 scenario 可以概括多數(shù)的調(diào)度情景。系統(tǒng)中發(fā)生的每一次調(diào)度都屬于以下三種情景之一。

進(jìn)程wakeup:TaskInsertion

睡眠進(jìn)程 wakeup 時(shí)，調(diào)度器需要執(zhí)行 task insertion 的操作，將該進(jìn)程插入到 run queue 中。BFS 將進(jìn)程插入相應(yīng)隊(duì)列的操作就是執(zhí)行一個(gè)雙向隊(duì)列的插入操作，計(jì)算機(jī)常用算法結(jié)構(gòu)告訴我們，這個(gè)操作是 O(1) 的。不過(guò)，BFS 在執(zhí)行插入操作之前需要首先查看當(dāng)前進(jìn)程是否可以搶占當(dāng)前正在系統(tǒng)中運(yùn)行的進(jìn)程。因此它會(huì)用新進(jìn)程的 virtual deadline 值和當(dāng)前在每個(gè) CPU 上正在運(yùn)行的進(jìn)程的 virtual deadline 值進(jìn)行比較，如果新進(jìn)程的值小，則直接搶占該 CPU 上正在運(yùn)行的進(jìn)程。這個(gè)算法是 O(m) 的，其中 m 是 CPU 的個(gè)數(shù)，假如系統(tǒng)中有 16 個(gè) CPU，那么每次都需要進(jìn)行 16 次比較。但這個(gè)設(shè)計(jì)卻保證了非常好的 low-latency 特性。

進(jìn)程Sleep

當(dāng)前正在運(yùn)行的進(jìn)程有可能主動(dòng)睡眠，此時(shí)，調(diào)度器需要將該進(jìn)程從 run queue 中移除，并選擇另外一個(gè)進(jìn)程運(yùn)行。但該進(jìn)程的 virtual deadline 的值保持不變。

這樣該進(jìn)程 wakeup 時(shí)，其 virtual deadline 將相對(duì)較小，因?yàn)?jiffies 隨著時(shí)間流逝而不斷增加。較小的 Virtual Deadline 可以保證該進(jìn)程能更快得到調(diào)度。

仍然以圖 8 為例，系統(tǒng)中有兩個(gè)進(jìn)程，T1 和 T2，T1 進(jìn)入 sleep 狀態(tài)后其 virtual deadline 仍然為 t1。T2 此時(shí)被調(diào)度，根據(jù)公式一，計(jì)算得出其 virtual deadline 為 t2。此后，T1 進(jìn)程 wakeup 了，此時(shí)雖然 T2 的時(shí)間片尚未用完，但由于 T1 的 virtual deadline 小于 T2 的，(t1<t2)，因此 T1 立即得到調(diào)度。

進(jìn)程用完自己的時(shí)間片

每個(gè)進(jìn)程都擁有自己的時(shí)間片，即使不被其他進(jìn)程搶占，假如屬于自己的時(shí)間片用完時(shí)，當(dāng)前進(jìn)程也一定會(huì)被剝奪 CPU 時(shí)間，以便讓別的進(jìn)程有機(jī)會(huì)執(zhí)行。

當(dāng)前進(jìn)程的時(shí)間片用完后就必須讓出 CPU, 此時(shí)將它的 virtual deadline 按照公式一重新計(jì)算。

這保證了一個(gè)特性:只有其他就緒進(jìn)程都獲得 CPU 之后，用完當(dāng)前時(shí)間片的進(jìn)程才可以再次得到運(yùn)行，這避免了饑餓。