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 語(yǔ)言也沒(méi)有學(xué)習(xí)過(guò)。。。這個(gè)事實(shí)證明，語(yǔ)言只是一項(xiàng)工具，對(duì)問(wèn)題本質(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ì)上的問(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)度算法類似一個(gè)處境尷尬的主婦，滿足孩子對(duì)晚餐的要求便有可能傷害到老人的食欲。Linux 內(nèi)核一直試圖做出一道讓全家老少都喜歡的菜，在這方面，CFS 已經(jīng)做的很好。但一道能被所有人接受的菜，或許就意味著稍許平淡。而 BFS 只打算滿足一種口味，以便將這種口味發(fā)展到極限。

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

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

這讓人們開始思考，對(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)度特性，類似 CGROUP 這樣的特性對(duì)于普通的桌面用戶是多余的技術(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è)顯而易見的方面，更重要的是，這種理念的不同會(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 訪問(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 將非?？捎^。

當(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 的用戶，最注重的不是系統(tǒng)的吞吐量，而是交互性程序的流暢體驗(yàn)。從 SD 開始，Kolivas 就告訴內(nèi)核黑客們，完全公平能夠從根本上保證交互性。他始終堅(jiān)持一個(gè)基本觀點(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 自稱 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ì)理解我，有些詞還是不翻譯更好。

內(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年代初之說(shuō)，尚存爭(zhēng)議），歷史最長(zhǎng)，是操作系統(tǒng)內(nèi)核與外圍分離時(shí)的最初形態(tài)。

微內(nèi)核（Microkernel），又稱為微核心。微內(nèi)核結(jié)構(gòu)是1980年代產(chǎn)生出來(lái)的較新的內(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)，只不過(guò)它的組件更多的在核心態(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)）。