Linux內(nèi)核完全剖析

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

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 語言也沒有學(xué)習(xí)過。。。這個(gè)事實(shí)證明，語言只是一項(xiàng)工具，對(duì)問題本質(zhì)的深入理解才是寫程序的關(guān)鍵。可能還有執(zhí)著，CFS 和 RSDL 之爭(zhēng)導(dǎo)致 Kolivas 離開 Linux 社區(qū)，此去經(jīng)年，當(dāng) Kolivas 再次開始看內(nèi)核代碼的時(shí)候，他立即發(fā)現(xiàn) CFS 存在以下幾個(gè)設(shè)計(jì)上的問題:

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 曾帶來的好處。

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

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

根據(jù) Linux Magazine的說法，Con Kolivas是看到了下面這則來自 xkcd 的漫畫而開始思考 BFS 的。

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

這讓人們開始思考，對(duì)于 Desktop 環(huán)境來講，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)度特性，類似 CGROUP 這樣的特性對(duì)于普通的桌面用戶是多余的技術(shù)。

這很容易理解:在只有一個(gè) CPU 的系統(tǒng)中，誰還會(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è)顯而易見的方面，更重要的是，這種理念的不同會(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 訪問 run queue 時(shí)，其他的 CPU 即使空閑也必須等待。當(dāng)使用 per CPU 的 run queue 之后，每個(gè) CPU 不必再使用大鎖，從而能夠并行地處理調(diào)度。

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

Kolivas 發(fā)現(xiàn)，采用 per cpu run queue 所帶來的好處會(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 的過程需要獲得其他 run queue 的鎖，這種操作降低了多運(yùn)行隊(duì)列帶來的并行性。

并且在復(fù)雜情況下，這種因 load balance 而引入的 footprint 將非常可觀。

當(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，而無需 CFS 那樣等待 load balance 代碼來決定，這減少了多 CPU 之間裁決的延遲，最終的結(jié)果是更小的調(diào)度延遲。

向前看還是向后看?

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

CFS 卻偏偏要考慮進(jìn)程的過去。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)程過去的睡眠時(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)過程。假如您花些時(shí)間回頭再看看，就會(huì)發(fā)現(xiàn) sleeper fairness 曾造成怎樣嚴(yán)重的延遲問題。雖然 Ingo 自稱 Gentle fairness 解決了延遲問題，但從代碼上看，Gentle Fairness 只是對(duì) sleeper 的獎(jiǎng)勵(lì)減半而已。因此我們可以說，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 來進(jìn)行選擇(關(guān)于 deadline 本文將在第 4 章中詳細(xì)描述)，其結(jié)果是，更早睡眠的進(jìn)程能更快地得到調(diào)度;CFS 的 sleeper fairness 則意味著要根據(jù) wakeup 的時(shí)間來選擇下一個(gè)被調(diào)度的進(jìn)程，更早 wakeup 的進(jìn)程會(huì)更快得到調(diào)度。

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

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

內(nèi)核是操作系統(tǒng)最內(nèi)核最基礎(chǔ)的構(gòu)件，因而，內(nèi)核結(jié)構(gòu)往往對(duì)操作系統(tǒng)的外部特性以及應(yīng)用領(lǐng)域有著一定程度的影響。盡管隨著理論和實(shí)踐的不斷演進(jìn)，操作系統(tǒng)高層特性與內(nèi)核結(jié)構(gòu)之間的耦合有日趨縮小之勢(shì)，但習(xí)慣上，內(nèi)核結(jié)構(gòu)仍然是操作系統(tǒng)分類之常用標(biāo)準(zhǔn)。

內(nèi)核的結(jié)構(gòu)可以分為單內(nèi)核、微內(nèi)核、混合內(nèi)核、外內(nèi)核等。

單內(nèi)核（Monolithic kernel），又稱為宏內(nèi)核。單內(nèi)核結(jié)構(gòu)是操作系統(tǒng)中各內(nèi)核部件雜然混居的形態(tài)，該結(jié)構(gòu)于1960年代（亦有1950年代初之說，尚存爭(zhēng)議），歷史最長(zhǎng)，是操作系統(tǒng)內(nèi)核與外圍分離時(shí)的最初形態(tài)。

微內(nèi)核（Microkernel），又稱為微核心。微內(nèi)核結(jié)構(gòu)是1980年代產(chǎn)生出來的較新的內(nèi)核結(jié)構(gòu)，強(qiáng)調(diào)結(jié)構(gòu)性部件與功能性部件的分離。20世紀(jì)末，基于微內(nèi)核結(jié)構(gòu)，理論界中又發(fā)展出了超微內(nèi)核與外內(nèi)核等多種結(jié)構(gòu)。盡管自1980年代起，大部分理論研究都集中在以微內(nèi)核為首的“新興”結(jié)構(gòu)之上，然而，在應(yīng)用領(lǐng)域之中，以單內(nèi)核結(jié)構(gòu)為基礎(chǔ)的操作系統(tǒng)卻一直占據(jù)著主導(dǎo)地位。

混合內(nèi)核（Hybrid kernel）像微內(nèi)核結(jié)構(gòu)，只不過它的組件更多的在核心態(tài)中運(yùn)行，以獲得更快的執(zhí)行速度。

外內(nèi)核（Exokernel）的設(shè)計(jì)理念是盡可能的減少軟件的抽象化，這使得開發(fā)者可以專注于硬件的抽象化。外核心的設(shè)計(jì)極為簡(jiǎn)化，它的目標(biāo)是在于同時(shí)簡(jiǎn)化傳統(tǒng)微內(nèi)核的訊息傳遞機(jī)制，以及整塊性核心的軟件抽象層。

在眾多常用操作系統(tǒng)之中，除了QNX和基于Mach的UNIX等個(gè)別系統(tǒng)外，幾乎全部采用單內(nèi)核結(jié)構(gòu)，例如大部分的Unix、Linux，以及Windows（微軟聲稱Windows NT是基于改良的微內(nèi)核架構(gòu)的，盡管理論界對(duì)此存有異議）。 微內(nèi)核和超微內(nèi)核結(jié)構(gòu)主要用于研究性操作系統(tǒng)，還有一些嵌入式系統(tǒng)使用外核。

基于單內(nèi)核的操作系統(tǒng)通常有著較長(zhǎng)的歷史淵源。例如，絕大部分UNIX的家族史都可上溯至1960年代。該類操作系統(tǒng)多數(shù)有著相對(duì)古老的設(shè)計(jì)和實(shí)現(xiàn)（例如某些UNIX中存在著大量1970年代、1980年代的代碼）。另外，往往在性能方面略優(yōu)于同一應(yīng)用領(lǐng)域中采用其他內(nèi)核結(jié)構(gòu)的操作系統(tǒng)（但通常認(rèn)為此種性能優(yōu)勢(shì)不能完全歸功于單內(nèi)核結(jié)構(gòu)）。