BFS 是一個進程調度器，可以解釋為“腦殘調度器”。這古怪的名字有多重含義，比較容易被接受的一個說法為：它如此簡單，卻如此出色，這會讓人對自己的思維能力產生懷疑。

　　BFS 不會被合并進入 Linus 維護的 Linux mainline，BFS 本身也不打算這么做。但 BFS 擁有眾多的擁躉，這只有一個原因：BFS 非常出色，它讓用戶的桌面環境達到了前所未有的流暢。在硬件越來越先進，系統卻依然常顯得遲鈍的時代，這實在讓人興奮。

　　進入 2010 年，Android 使用 BFS 作為其操作系統的標準調度器，這也證明了 BFS 的價值。

一、BFS vs CFS，性能測試比拼

　　BFS 出現后得到了很多用戶的好評，得到了諸如“快，感覺的到的快”，“桌面的急速未來”等評價。這些詞讓人側目，于是我便開始四下尋找關于 BFS 的測試數據，希望能找到說明這一切的數字或者曲線。但結果卻頗令人失望。。。

1.Jens Axboe 的測試

　　BFS 發布后不久，即 2009 年 9 月，Ingo Molnar 發布了他的測評報告，比較了 CFS 和 BFS。作為 CFS 的作者 , 他所宣稱的測試結果并不讓人覺得意外：CFS 在各個方面優于 BFS。不過人們對他的測評結果有不同的反應，有人認同，也有人心存疑惑。Jens Axboe 就是心存懷疑的一位，他自己寫了一個名為 Latt.c 的程序，試圖測試調度器的兩個神秘屬性：”Interactivity”和 “Fluidness”。

　　他的測試結果剛好相反，表明 BFS 在交互性方面優于 CFS，而且其 CPU 利用率更高。不過 BFS 穩定性較差，并且在某些情況下也表現出了糟糕的交互性問題。

　　從 Jens 的測試數據來看，BFS 稍微優于 CFS，但優勢并非如同坊間流傳的那樣夸張。感興趣的讀者可以在 lkml 的郵件列表中找到 Jens 測試的詳細數據：http://thread.gmane.org/gmane.linux.kernel/886319/focus=887636

　　結果讓翹首以盼的我有些失望，并沒有看到 BFS 遙遙領先。反而有些類似奧運會男子百米的決賽，究竟誰是冠軍一時竟難以分辨。但值得注意的是，該測試意外地讓人們認識到了 CFS 本身的一個嚴重問題。

　　CFS 的 sleeper fairness 特性導致在一些情況下將出現嚴重的調度延遲，在 Jens 的 xmodmap測試中甚至出現了 10s 的延遲。并且圍繞 Jens 的測試，人們紛紛發表聲明，使用 CFS 時有很多交互性問題，比如編譯內核時，同時的音頻視頻會出現嚴重的停頓，而使用 BFS 則沒有這些問題。不過這些 CFS 的問題都在關閉了 sleeper fairness 特性后神秘地消失了。

　　這讓 CFS 調度器的開發者不得不暫時關閉了 sleeper fairness 特性，并一度曾號稱將在即將發布的 2.6.32 中正式關閉該特性，直到問題被解決為止。令人吃驚的是，Ingo 在一周之內就拋出了新的 patch，即 Gentle Fairness。使用這個 patch，10s 延遲消失了，其他的關于鼠標滯后，視頻停頓的關于 CFS 的負面報告也都消失了。。。

2.Phoronix 的測試

　　您可以在 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 對 BFS 的專業測試。該測試也是在 2009 年 9 月完成的，如前所述，此后 BFS 和 CFS 都有了一些更新，因此該測試也不能完全反映這兩款調度器最新的狀態。但作為權威的測評機構，該測評結果還是值得一看。

　　從 Phoronix 的測試結果來看，BFS 在多項測試中稍微領先，CFS 則在其余一些測試項目中反超。我不禁又有些黯然。

　　唯一能體現 BFS“急速”的測試項目來自針對網絡服務器吞吐量的測試，特在此處張貼這張最具有說服力和震撼力的直方圖。

　　圖 1. 網絡吞吐量測試

　　但除此一項之外，總的來講，Phoronix 的測試結果終究只是表明 BFS 和 CFS 旗鼓相當。

3.University of New Mexico 計算機系的測評

　　新墨西哥大學的 Taylor Groves, Je Knockel, Eric Schulte 在 2009 年 12 月也發布了一個 BFS vs. CFS 的評測報告。

　　他們的測評關注于三個方面：延遲 , Turnaround Time 還有交互性。下面摘錄他們的測試結果。

　　圖 2. 延遲

　　圖 3. Turnaround Time

　　圖 4. 交互性

　　這三張圖總算聊以安慰我四處找尋的辛苦，根據這個評測結果，終于可以得到這樣的結論：

　　在 turnaround time 方面，CFS 優于 BFS。但是 BFS 的調度延遲小于 CFS。這說明 BFS 更加適應于交互式應用環境。CFS 更加適合于批處理作業環境。這跟許多用戶的體驗相同。

　　小結

　　以上三個測評都是在 Linux2.6.32 發布前完成的。然而 CFS 在 Linux2.6.32 中引入了 GENTLE_FAIR_SLEEPERS 特性，正如 2.1 節中所說，這個 patch 據說是極大地提高了交互性。不幸的是，在那以后，卻似乎再也沒有人做關于 CFS 和 BFS 的比較測試了。因此在 Linux 已經進入 2.6.35 的時代，我們更無法輕易得出 BFS 和 CFS 孰優孰劣的結論。

　　從另一方面講，雖然專業評測沒有顯示出 BFS 的明顯優勢，但從 Internet 上能收集到的信息來看，大多數用戶都覺得 BFS 能夠顯著地提高交互式應用的體驗，這是一種個人的體驗，比如鼠標的移動是否流暢等等。在這類體驗中，兩款調度器的差異卻是相當大，這無法用前面的測試數據來加以說明。

　　因此我認為，目前人們并沒有理解影響交互性的真正原因，專業測試所關注的數據尚無法準確描述諸如“流暢”這類主觀的感覺。因此，對于 BFS，我們不妨相信感覺一次吧。

　　那么 BFS 究竟做了哪些改進，如果這些改進如此有效，為什么主流內核不愿意接納 BFS 呢?

二、BFS vs CFS

1.設計上的不同

　　白天 Con Kolivas 在醫院里當麻醉師，為人們解除痛苦，業余的時候借 Linux 解除自己的痛苦。額，Kolivas 學習 Linux 并不是為了解決痛苦，我臆測而已。但據 Kolivas 自述，他接觸 Linux 內核時連 C 語言也沒有學習過。。。這個事實證明，語言只是一項工具，對問題本質的深入理解才是寫程序的關鍵。可能還有執著，CFS 和 RSDL 之爭導致 Kolivas 離開 Linux 社區，此去經年，當 Kolivas 再次開始看內核代碼的時候，他立即發現 CFS 存在以下幾個設計上的問題：

　　CFS 的目標是支持從桌面到高端服務器的所有應用場景，這種大而全的設計思路導致其必須做一些實現上的折中，此外，那些只有在高端機器中才需要的特性將引入不必要的復雜代碼。

　　其次，為了維護多 CPU 上的公平性，CFS 采用了負載平衡機制，Kolivas 認為，這些復雜代碼抵消了 per cpu queue 曾帶來的好處。

　　最后，主流內核的 CFS 還是對睡眠進程存在一些偏好，這意味著“不公平”。

2.設計目標的不同

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

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

　　圖 5. 譏諷 Linux 調度器的 xkcd 漫畫

　　事情源于一些 Linux 用戶，他們發現 Linux 雖然號稱能夠充分發揮 4096 顆 CPU 系統的計算能力，但在普通的 laptop 上卻無法流暢地播放 Youtube 視頻。

　　這讓人們開始思考，對于 Desktop 環境來講，CFS 哪些復雜的特性究竟是否還有意義?人們是否有必要在自己的個人電腦中使用一個支持 4096 個 CPU 的調度器?

　　BFS 正是對這種質疑的自然反應。它不打算支持 4096 個 CPU 的龐然大物，BFS 的目標是普通人使用的桌面電腦。此外，BFS 還刪除了那些只有在服務器上才需要的特性。比如，BFS 拋棄了 CFS 的組調度特性，類似 CGROUP 這樣的特性對于普通的桌面用戶是多余的技術。

　　這很容易理解：在只有一個 CPU 的系統中，誰還會設計多個 CGroup，哪里還能用到 NUMA domain 等概念呢?

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

　　這些簡單的裁剪使得 BFS 的代碼極大地簡化，簡化的代碼意味著執行一次調度所需要的指令數減少了，相應的 footprint 自然也減少了。

　　當然簡化代碼只是一個顯而易見的方面，更重要的是，這種理念的不同會對最終的調度器實現產生更加深遠的影響，這實在是難以盡述。

　　多隊列 vs 單一隊列

　　在 Linux 內核進入 2.6 時，調度器采用 per cpu run queue 從而克服了單一 run queue 的局限。在多 CPU 系統中，單一 run queue 意味著 run queue 成為了系統的瓶頸，因為在同一時刻，一個 CPU 訪問 run queue 時，其他的 CPU 即使空閑也必須等待。當使用 per CPU 的 run queue 之后，每個 CPU 不必再使用大鎖，從而能夠并行地處理調度。

　　但很多事情都不像第一眼看上去那樣簡單。

　　Kolivas 發現，采用 per cpu run queue 所帶來的好處會被追求公平性的 load balance 代碼所抵消。在目前的 CFS 調度器中，每顆 CPU 只維護本地 run queue 中所有進程的公平性，為了實現跨 CPU 的調度公平性，CFS 必須定時進行 load balance，將一些進程從繁忙的 CPU 的 run queue 中移到其他空閑的 run queue 中。

　　這個 load balance 的過程需要獲得其他 run queue 的鎖，這種操作降低了多運行隊列帶來的并行性。

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

　　當然，load balance 引入的加鎖操作依然比全局鎖的代價要低，這種代價差異隨著 CPU 個數的增加而更加顯著。但請您注意，BFS 并不打算為那些擁有 1024 個 CPU 的系統工作，假若系統中的 CPU 個數有限時，多 run queue 的優勢便不明顯了。

　　而 BFS 采用單一隊列之后，每一個需要調度的新進程都可以在全局范圍內查找最合適的 CPU，而無需 CFS 那樣等待 load balance 代碼來決定，這減少了多 CPU 之間裁決的延遲，最終的結果是更小的調度延遲。

　　向前看還是向后看?

　　多年來 Kolivas 一直關注著 Linux 在 desktop 上的表現。對于 desktop 的用戶，最注重的不是系統的吞吐量，而是交互性程序的流暢體驗。從 SD 開始，Kolivas 就告訴內核黑客們，完全公平能夠從根本上保證交互性。他始終堅持一個基本觀點：調度器應該 forward look only。決不要去考慮一個進程的過去。

　　CFS 卻偏偏要考慮進程的過去。2.6.23 的時候，CFS 記錄并使用 sleep time。之后不久，在 2.6.24 發布的時候，CFS 合并了“Real Fair Scheduler”，刪除了 sleep time。因此在 2.6.24 之后的內核中，CFS 終于也不再考慮進程過去的睡眠時間。

　　但 CFS 還是保留了 sleeper fairness 的思想，當進程 wakeup 的時候，在 place_entity() 函數中，CFS 將對 sleeper 進行獎勵，以便其能盡快得到 CPU。這個策略是非常微妙的，我們在 2.1 節中詳細介紹了 sleeper fairness 的演進過程。假如您花些時間回頭再看看，就會發現 sleeper fairness 曾造成怎樣嚴重的延遲問題。雖然 Ingo 自稱 Gentle fairness 解決了延遲問題，但從代碼上看，Gentle Fairness 只是對 sleeper 的獎勵減半而已。因此我們可以說，CFS 依然對 Sleeper 進程進行獎勵，這代表著一種偏好，一種“不公平”。而這，正是 BFS 所反對的。

　　BFS 中，當一個進程 wakeup 時，調度器將根據進程的 deadline 來進行選擇(關于 deadline 本文將在第 4 章中詳細描述)，其結果是，更早睡眠的進程能更快地得到調度;CFS 的 sleeper fairness 則意味著要根據 wakeup 的時間來選擇下一個被調度的進程，更早 wakeup 的進程會更快得到調度。

　　這種不同究竟會對桌面應用造成何種影響尚沒有理論依據可以參考。但我個人認為，BFS 的策略更加合理。

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

望能有更專業的分析和評測。