Linux 調(diào)度器 BFS
BFS 是一個(gè)進(jìn)程調(diào)度器，可以解釋為“腦殘調(diào)度器”。這古怪的名字有多重含義，比較容易被接受的一個(gè)說法為：它如此簡(jiǎn)單，卻如此出色，這會(huì)讓人對(duì)自己的思維能力產(chǎn)生懷疑。
BFS 不會(huì)被合并進(jìn)入 Linus 維護(hù)的 Linux mainline，BFS 本身也不打算這么做。但 BFS 擁有眾多的擁躉，這只有一個(gè)原因：BFS 非常出色，它讓用戶的桌面環(huán)境達(dá)到了前所未有的流暢。在硬件越來越先進(jìn)，系統(tǒng)卻依然常顯得遲鈍的時(shí)代，這實(shí)在讓人興奮。
進(jìn)入 2010 年，Android 使用 BFS 作為其操作系統(tǒng)的標(biāo)準(zhǔn)調(diào)度器，這也證明了 BFS 的價(jià)值。
BFS vs CFS，性能測(cè)試比拼
BFS 出現(xiàn)后得到了很多用戶的好評(píng)，得到了諸如“快，感覺的到的快”，“桌面的急速未來”等評(píng)價(jià)。這些詞讓人側(cè)目，于是我便開始四下尋找關(guān)于 BFS 的測(cè)試數(shù)據(jù)，希望能找到說明這一切的數(shù)字或者曲線。但結(jié)果卻頗令人失望。。。
Jens Axboe 的測(cè)試
BFS 發(fā)布后不久，即 2009 年 9 月，Ingo Molnar 發(fā)布了他的測(cè)評(píng)報(bào)告，比較了 CFS 和 BFS。作為 CFS 的作者 , 他所宣稱的測(cè)試結(jié)果并不讓人覺得意外：CFS 在各個(gè)方面優(yōu)于 BFS。不過人們對(duì)他的測(cè)評(píng)結(jié)果有不同的反應(yīng)，有人認(rèn)同，也有人心存疑惑。Jens Axboe 就是心存懷疑的一位，他自己寫了一個(gè)名為 Latt.c 的程序，試圖測(cè)試調(diào)度器的兩個(gè)神秘屬性：”Interactivity”和 “Fluidness”。
他的測(cè)試結(jié)果剛好相反，表明 BFS 在交互性方面優(yōu)于 CFS，而且其 CPU 利用率更高。不過 BFS 穩(wěn)定性較差，并且在某些情況下也表現(xiàn)出了糟糕的交互性問題。
從 Jens 的測(cè)試數(shù)據(jù)來看，BFS 稍微優(yōu)于 CFS，但優(yōu)勢(shì)并非如同坊間流傳的那樣夸張。感興趣的讀者可以在 lkml 的郵件列表中找到 Jens 測(cè)試的詳細(xì)數(shù)據(jù)：http://thread.gmane.org/gmane.linux.kernel/886319/focus=887636
結(jié)果讓翹首以盼的我有些失望，并沒有看到 BFS 遙遙領(lǐng)先。反而有些類似奧運(yùn)會(huì)男子百米的決賽，究竟誰是冠軍一時(shí)竟難以分辨。但值得注意的是，該測(cè)試意外地讓人們認(rèn)識(shí)到了 CFS 本身的一個(gè)嚴(yán)重問題。
CFS 的 sleeper fairness 特性導(dǎo)致在一些情況下將出現(xiàn)嚴(yán)重的調(diào)度延遲，在 Jens 的 xmodmap測(cè)試中甚至出現(xiàn)了 10s 的延遲。并且圍繞 Jens 的測(cè)試，人們紛紛發(fā)表聲明，使用 CFS 時(shí)有很多交互性問題，比如編譯內(nèi)核時(shí)，同時(shí)的音頻視頻會(huì)出現(xiàn)嚴(yán)重的停頓，而使用 BFS 則沒有這些問題。不過這些 CFS 的問題都在關(guān)閉了 sleeper fairness 特性后神秘地消失了。
這讓 CFS 調(diào)度器的開發(fā)者不得不暫時(shí)關(guān)閉了 sleeper fairness 特性，并一度曾號(hào)稱將在即將發(fā)布的 2.6.32 中正式關(guān)閉該特性，直到問題被解決為止。令人吃驚的是，Ingo 在一周之內(nèi)就拋出了新的 patch，即 Gentle Fairness。使用這個(gè) patch，10s 延遲消失了，其他的關(guān)于鼠標(biāo)滯后，視頻停頓的關(guān)于 CFS 的負(fù)面報(bào)告也都消失了。。。
Phoronix 的測(cè)試
您可以在 http://www.phoronix.com/scan.php?page=article&item=bfs_scheduler_benchmarks&num=1和 http://global.phoronix-test-suite.com/?k=profile&u=zero-9274-28890-6247看到 Phoronix 對(duì) BFS 的專業(yè)測(cè)試。該測(cè)試也是在 2009 年 9 月完成的，如前所述，此后 BFS 和 CFS 都有了一些更新，因此該測(cè)試也不能完全反映這兩款調(diào)度器最新的狀態(tài)。但作為權(quán)威的測(cè)評(píng)機(jī)構(gòu)，該測(cè)評(píng)結(jié)果還是值得一看。
從 Phoronix 的測(cè)試結(jié)果來看，BFS 在多項(xiàng)測(cè)試中稍微領(lǐng)先，CFS 則在其余一些測(cè)試項(xiàng)目中反超。我不禁又有些黯然。
唯一能體現(xiàn) BFS“急速”的測(cè)試項(xiàng)目來自針對(duì)網(wǎng)絡(luò)服務(wù)器吞吐量的測(cè)試，特在此處張貼這張最具有說服力和震撼力的直方圖。
圖 1. 網(wǎng)絡(luò)吞吐量測(cè)試
但除此一項(xiàng)之外，總的來講，Phoronix 的測(cè)試結(jié)果終究只是表明 BFS 和 CFS 旗鼓相當(dāng)。
University of New Mexico 計(jì)算機(jī)系的測(cè)評(píng)
新墨西哥大學(xué)的 Taylor Groves, Je Knockel, Eric Schulte 在 2009 年 12 月也發(fā)布了一個(gè) BFS vs. CFS 的評(píng)測(cè)報(bào)告。
他們的測(cè)評(píng)關(guān)注于三個(gè)方面：延遲 , Turnaround Time 還有交互性。下面摘錄他們的測(cè)試結(jié)果。
圖 2. 延遲
圖 3. Turnaround Time
圖 4. 交互性
這三張圖總算聊以安慰我四處找尋的辛苦，根據(jù)這個(gè)評(píng)測(cè)結(jié)果，終于可以得到這樣的結(jié)論：
在 turnaround time 方面，CFS 優(yōu)于 BFS。但是 BFS 的調(diào)度延遲小于 CFS。這說明 BFS 更加適應(yīng)于交互式應(yīng)用環(huán)境。CFS 更加適合于批處理作業(yè)環(huán)境。這跟許多用戶的體驗(yàn)相同。
小結(jié)
以上三個(gè)測(cè)評(píng)都是在 Linux2.6.32 發(fā)布前完成的。然而 CFS 在 Linux2.6.32 中引入了 GENTLE_FAIR_SLEEPERS 特性，正如 2.1 節(jié)中所說，這個(gè) patch 據(jù)說是極大地提高了交互性。不幸的是，在那以后，卻似乎再也沒有人做關(guān)于 CFS 和 BFS 的比較測(cè)試了。因此在 Linux 已經(jīng)進(jìn)入 2.6.35 的時(shí)代，我們更無法輕易得出 BFS 和 CFS 孰優(yōu)孰劣的結(jié)論。
從另一方面講，雖然專業(yè)評(píng)測(cè)沒有顯示出 BFS 的明顯優(yōu)勢(shì)，但從 Internet 上能收集到的信息來看，大多數(shù)用戶都覺得 BFS 能夠顯著地提高交互式應(yīng)用的體驗(yàn)，這是一種個(gè)人的體驗(yàn)，比如鼠標(biāo)的移動(dòng)是否流暢等等。在這類體驗(yàn)中，兩款調(diào)度器的差異卻是相當(dāng)大，這無法用前面的測(cè)試數(shù)據(jù)來加以說明。
因此我認(rèn)為，目前人們并沒有理解影響交互性的真正原因，專業(yè)測(cè)試所關(guān)注的數(shù)據(jù)尚無法準(zhǔn)確描述諸如“流暢”這類主觀的感覺。因此，對(duì)于 BFS，我們不妨相信感覺一次吧。
那么 BFS 究竟做了哪些改進(jìn)，如果這些改進(jìn)如此有效，為什么主流內(nèi)核不愿意接納 BFS 呢?
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)程存在一些偏好，這意味著“不公平”。
設(shè)計(jì)目標(biāo)的不同
在現(xiàn)實(shí)中，調(diào)度算法類似一個(gè)處境尷尬的主婦，滿足孩子對(duì)晚餐的要求便有可能傷害到老人的食欲。Linux 內(nèi)核一直試圖做出一道讓全家老少都喜歡的菜，在這方面，CFS 已經(jīng)做的很好。但一道能被所有人接受的菜，或許就意味著稍許平淡。而 BFS 只打算滿足一種口味，以便將這種口味發(fā)展到極限。
根據(jù) Linux Magazine 的說法，Con Kolivas 是看到了下面這則來自 xkcd 的漫畫而開始思考 BFS 的。
圖 5. 譏諷 Linux 調(diào)度器的 xkcd 漫畫
事情源于一些 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)度延遲。#p#
向前看還是向后看?
多年來 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ì)理解我，有些詞還是不翻譯更好。
BFS 實(shí)現(xiàn)原理
調(diào)度器是非常復(fù)雜的話題，尤其是 CFS 調(diào)度器，想要描述清楚，需要一支非凡的筆，我還沒有找到。但 BFS 非常簡(jiǎn)單，所以我才有勇氣在這里寫點(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)單：
Virtual Deadline = jiffies + (user_priority * rr_interval) 公式一
其中 jiffies 是當(dāng)前時(shí)間 , user_priority 是進(jìn)程的優(yōu)先級(jí)，rr_interval 代表 round-robin interval，近似于一個(gè)進(jìn)程必須被調(diào)度的最后期限，所謂 Deadline 么。不過在這個(gè) Deadline 之前還有一個(gè)形容詞為 Virtual，因此這個(gè) Deadline 只是表達(dá)一種愿望而已，并非很多領(lǐng)導(dǎo)們常說的那種 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è)重要話題。BFS 采用了非常傳統(tǒng)的進(jìn)程隊(duì)列表示方法，即 bitmap 加 queue。
BFS 將所有進(jìn)程分成 4 類，分別表示不同的調(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 的方法來選擇同樣優(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，但一直無法進(jìn)入主流內(nèi)核，這種調(diào)度策略是為了那些 near-realtime 的進(jìn)程設(shè)計(jì)的。如前所述，實(shí)時(shí)進(jìn)程需要用戶有 superuser 的權(quán)限，這類進(jìn)程能夠獨(dú)占 CPU，因此只有很少的進(jìn)程可以被配置為實(shí)時(shí)進(jìn)程。對(duì)于那些對(duì)交互性要求比較高的，又無法成為實(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 類似于主流調(diào)度器 CFS 中的 SCHED_OTHER，是基本的分時(shí)調(diào)度策略。
SCHED_IDELPRO 類似于 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)程類型。對(duì)于每個(gè)進(jìn)程類型，系統(tǒng)中都有可能有多個(gè)進(jìn)程同時(shí) Ready，比如很可能有兩個(gè)優(yōu)先級(jí)為 10 的 RT 進(jìn)程同時(shí) Ready，所以對(duì)于每個(gè)類型，還需要一個(gè)隊(duì)列來存儲(chǔ)屬于該類型的 ready 進(jìn)程。
BFS 用 103 個(gè) bitmap 來表示是否有相應(yīng)類型的進(jìn)程準(zhǔn)備進(jìn)行調(diào)度。如下圖所示：
圖 6. BFS 進(jìn)程隊(duì)列
當(dāng)任何一種類型的進(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)程的問題被稱為 Task Selection 或者 pick next。
Task Selection i.e. Pick Next
當(dāng)調(diào)度器決定進(jìn)行進(jìn)程調(diào)度的時(shí)候，BFS 將按照下面的原則來進(jìn)行任務(wù)的選擇：
圖 7. Task Selection
首先查看 bitmap 是否有置位的比特。比如上圖，對(duì)應(yīng)于 SCHED_NORMAL 的 bit 被置位，表明有類型為 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 算法來選取合適的進(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)睡過了它的 Virtual Deadline，如下圖所示：
圖 8. 睡眠和喚醒
T1 本來的 virtual deadline 為 t1，它 sleep 之后，其他的進(jìn)程比如 T2 開始運(yùn)行，等到 T1 再次 wakeup 的時(shí)候，當(dāng)時(shí)的 jiffies 已經(jīng)大于 t1，在這種情況下，T1 無需和其他進(jìn)程的 virtual deadline 相比較，而直接被 BFS 調(diào)度器選取。
基本的調(diào)度場(chǎng)景
三個(gè)基本的 scenario 可以概括多數(shù)的調(diào)度情景。系統(tǒng)中發(fā)生的每一次調(diào)度都屬于以下三種情景之一。
進(jìn)程 wakeup：Task Insertion
睡眠進(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) 的。不過，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
進(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)行，這避免了饑餓。
此時(shí)此刻我有一種力不從心之感，介紹似乎不該在此處就戛然截止，但我的確已經(jīng)講完了我想要講的。唯一能做的，便是想在這里抓住最后一個(gè)機(jī)會(huì)進(jìn)行一個(gè)小小的總結(jié)。
BFS 專注于單一的目標(biāo)，因此能夠?qū)⒋a精簡(jiǎn)到極致。它采用單一 Queue，從而免除了 load balance 的需要，雖然并發(fā)性減低，但對(duì)于少量 CPU 的桌面系統(tǒng)而言，其快速切換 CPU 的能力應(yīng)該能夠補(bǔ)償并發(fā)的損失，說不定還有盈余。
BFS 只關(guān)注未來，它完全公平，一個(gè)進(jìn)程的睡眠習(xí)慣以及其過去的種種都不能影響它下一次調(diào)度的時(shí)機(jī)。在 BFS 世界中，調(diào)度器嚴(yán)格按照每個(gè)進(jìn)程的 Deadline 進(jìn)行公平調(diào)度，簡(jiǎn)單，嚴(yán)肅甚至有些單調(diào)。
嗯，我必須承認(rèn)，無法從這些描述中看出什么先進(jìn)的思想或者特性，但廣大用戶的真實(shí)體驗(yàn)說明了那一切。我想，這或許也正說明用于描述桌面交互性的理論基礎(chǔ)還極其缺乏，我只能通過感性而非理性來總結(jié)它了。想說的是，我的使用體驗(yàn)是“快，真的很快”。
或許我并不客觀，人的感受往往受到感情的影響。我認(rèn)為 Kovalis 得到了不公正的對(duì)待，直到我寫這篇文章的今天，主流的內(nèi)核黑客們還是依然指責(zé) Kovalis，Kovalis 不合群。我想在人群擁擠的咖啡館里，Kovalis 應(yīng)該是那個(gè)不想也不知道如何表達(dá)自己，只能在某個(gè)角落里獨(dú)自寫點(diǎn)兒什么的人吧。這種同情讓我覺得 BFS 更加流暢了?
無論如何，我還是希望能有更多的人關(guān)注 BFS，也希望能有更專業(yè)的分析和評(píng)測(cè)。
【編輯推薦】
