基本信息
linux調度器（BFS ）是一款專門為 Linux 桌面環境所設計的核心調度器，它基於 Staircase Deadline和 EEVDF 算法，支持 Linux 2.6.31之後的核心。它提供了前所未有的流暢桌面性能，不僅得到了用戶的認可，也為一些商業系統所採用。
BFS 是一個進程調度器，可以解釋為“腦殘調度器”。這古怪的名字有多重含義，比較容易被接受的一個說法為：它如此簡單，卻如此出色，這會讓人對自己的思維能力產生懷疑。
BFS 不會被合併進入 Linus 維護的 Linux mainline，BFS 本身也不打算這么做。但 BFS 擁有眾多的擁躉，這隻有一個原因：BFS 非常出色，它讓用戶的桌面環境達到了前所未有的流暢。在硬體越來越先進，系統卻依然常顯得遲鈍的時代，這實在讓人興奮。
進入 2010 年，Android 開發一個分支使用 BFS 作為其作業系統的標準調度器，這也證明了 BFS 的價值。後來放棄 。
作者信息
Linux 調度器作者名字： CK，Con Kolivas
性別：男
國籍：澳大利亞
職業：資深核心 hacker
眾所周知，Linux Kernel 是聚集了一幫天才蠢才和暴君怪胎的地方，CK 貌似最適合這種地方的人。是真的貌似，一張電影裡面典型高智商通緝犯的臉。
幾年前編譯 Linux kernel，ck 補丁集就是系統提速的代名詞。當時編譯核心的三部曲是下 kernel 源碼，打上 ck 補丁集，編譯安裝。後來上游代碼將 ck 補丁集穩定的部分不斷吸收，它的影響力也漸漸消失。
CK 本身對任務調度有很深的造詣，他聰明而經典地實現了 fair scheduling，而實現模式被 Igor 借鑑改進最終寫出了現在 kernel 用的進程調度管理器 CFS (Completely Fair Scheduler)。不得不順便介紹一下任務調度。Kernel 的進程調度主要是將 CPU 資源分配給各種驅動、進程等等。你可能聽說過，一般人的大腦使用率不足 20% 這種科學或者偽科學言論。但事實是，你電腦上的CPU從來就沒有真正被 100% 的利用過（別跟我說你在資源管理器裡面看到過 CPU 100%，我還見過 101% 呢）。如何將各種運算任務一刻不停又有條不紊的塞給 CPU 處理是一門嚴肅的科學，絕不是電視購物導購能解決的問題。一次塞的運算量少了，CPU 閒著，運算時間增長，電腦慢了；而一次塞的運算多了，CPU 忙不過來，運算又要在門口排隊，電腦也慢了。進程調度主要是用算法解決這個問題，而現在 Linux Kernel 用的 CFS 據說非常經典，在不同情況下都可達到相當高的 CPU 利用率。而現用 CFS 也是在 2.6.23 才加入的，取代原來 O(1)，直接將 Linux 桌面速度從 XX 時代帶入了 XX+N 時代。
兩年前，CK 淡出了核心開發，忽然從江湖中蒸發。幾周前，CK 重出江湖，兩年磨一劍，帶來了 BFS ，全稱 Brain F u c k Scheduler （只認識中間那個單詞的請參考谷歌翻譯），聲稱專為低端硬體設計（我的理解是不超過 10 個 CPU 的電腦電視手機遊戲機都算低端機），說白了就是比 Kernel 默認要更加山崩地裂海枯石爛房價上漲油價飛升的快。BFS 為什麼叫這個名字？為了中文用戶，不能三個詞讓他們一個也不懂吧？ 好吧，這名字有點不雅，不過算是直爽。對了，據說 CK 也是看到上面我提到的漫畫才開始劍走偏鋒。真正有幾個人用有上千 CPU 的電腦呢？為什麼要為這種擴展性犧牲桌面性能。BFS 就在其間做了取捨，僅僅支持最多 16 個 CPU ，把問題外沿做小，讓算法更簡單精悍高效。作為原理來講，這足夠解釋速度的來源。對於其它廢問題， CK 專門寫了一個 FAQ。在可以預見的將來，BFS 也不會進入 mainline kernel，說白了是取向問題。
對比
譏諷 Linux 調度器的 xkcd 漫畫BFS vs CFS，設計上的不同 白天 Con Kolivas 在醫院裡當麻醉師，為人們解除痛苦，業餘的時候借 Linux 解除自己的痛苦。額，Kolivas 學習 Linux 並不是為了解決痛苦，我臆測而已。但據 Kolivas 自述，他接觸 Linux 核心時連 C 語言也沒有學習過。這個事實證明，語言只是一項工具，對問題本質的深入理解才是寫程式的關鍵。可能還有執著，CFS 和 RSDL 之爭導致 Kolivas 離開 Linux 社區，此去經年，當 Kolivas 再次開始看核心代碼的時候，他立即發現 CFS 存在以下幾個設計上的問題：
CFS 的目標是支持從桌面到高端伺服器的所有套用場景，這種大而全的設計思路導致其必須做一些實現上的折中，此外，那些只有在高端機器中才需要的特性將引入不必要的複雜代碼。
其次，為了維護多 CPU 上的公平性，CFS 採用了負載平衡機制，Kolivas 認為，這些複雜代碼抵消了 per cpu queue 曾帶來的好處。
最後，主流核心的 CFS 還是對睡眠進程存在一些偏好，這意味著“不公平”。
設計目標的不同
在現實中，調度算法類似一個處境尷尬的主婦，滿足孩子對晚餐的要求便有可能傷害到老人的食慾。Linux 核心一直試圖做出一道讓全家老少都喜歡的菜，在這方面，CFS 已經做的很好。但一道能被所有人接受的菜，或許就意味著稍許平淡。而 BFS 只打算滿足一種口味，以便將這種口味發展到極限。
根據 Linux Magazine的說法，Con Kolivas是看到了下面這則來自 xkcd 的漫畫而開始思考 BFS 的。
事情源於一些 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 的實現細節吧。然後或許您會理解我，有些詞還是不翻譯更好。
實現原理
調度器是非常複雜的話題，尤其是 CFS 調度器，想要描述清楚，需要一支非凡的筆，我還沒有找到。但 BFS 非常簡單，所以我才有勇氣在這裡寫點兒 BFS 的實現原理什麼的。首先介紹幾個關鍵概念。
虛擬 Deadline ( Virtual Deadline )
當一個進程被創建時，它被賦予一個固定的時間片，和一個虛擬 Deadline。該虛擬 deadline 的計算公式非常簡單：
| Virtual Deadline = jiffies + (user_priority * rr_interval) 公式一 |
其中 jiffies 是當前時間 , user_priority 是進程的優先權，rr_interval 代表 round-robin interval，近似於一個進程必須被調度的最後期限，所謂 Deadline 么。不過在這個 Deadline 之前還有一個形容詞為 Virtual，因此這個 Deadline 只是表達一種願望而已，並非很多領導們常說的那種 deadline。
虛擬 Deadline 將用於調度器的 picknext 決策，這將在後續章節詳細描述。
進程佇列的表示方法和調度策略
在作業系統內部，所有的 Ready 進程都被存放在進程佇列中，調度器從進程佇列中選取下一個被調度的進程。因此如何設計進程佇列是我們研究調度器的一個重要話題。BFS 採用了非常傳統的進程佇列表示方法，即 bitmap 加 queue。
BFS 將所有進程分成 4 類，分別表示不同的調度策略 :
Realtime，實時進程 SCHED_ISO，isochronous 進程，用於互動式任務 SCHED_NORMAL，普通進程 SCHED_IDELPRO，低優先權任務 實時進程總能獲得 CPU，採用 Round Robin 或者 FIFO 的方法來選擇同樣優先權的實時進程。他們需要 superuser 的許可權，通常限於那些占用 CPU 時間不多卻非常在乎 Latency 的進程。
SCHED_ISO 在主流核心中至今仍未實現，Con 早在 2003 年就提出了這個 patch，但一直無法進入主流核心，這種調度策略是為了那些 near-realtime 的進程設計的。如前所述，實時進程需要用戶有 superuser 的許可權，這類進程能夠獨占 CPU，因此只有很少的進程可以被配置為實時進程。對於那些對互動性要求比較高的，又無法成為實時進程的進程，BFS 將採用 SCHED_ISO，這些進程能夠搶占 SCHED_NORMAL 進程。他們的優先權比 SCHED_NORMAL 高，但又低於實時進程。此外當 SCHED_ISO 進程占用 CPU 時間達到一定限度後，會被降級為 SCHED_NORMAL，防止其獨占整個系統資源。
SCHED_NORMAL 類似於主流調度器 CFS 中的 SCHED_OTHER，是基本的分時調度策略。
SCHED_IDELPRO 類似於 CFS 中的 SCHED_IDLE，即只有當 CPU 即將處於 IDLE 狀態時才被調度的進程。
經常調度策略示意圖在這些不同的調度策略中，實時進程分成 100 個不同的優先權，加上其他三個調度策略，一共有 103 個不同的進程類型。對於每個進程類型，系統中都有可能有多個進程同時 Ready，比如很可能有兩個優先權為 10 的 RT 進程同時 Ready，所以對於每個類型，還需要一個佇列來存儲屬於該類型的 ready 進程。
BFS 用 103 個 bitmap 來表示是否有相應類型的進程準備進行調度。如圖所示：
當任何一種類型的進程佇列非空時，即存在 Ready 進程時，相應的 bitmap 位被設定為 1。
調度器如何在這樣一個 bitmap 加 queue 的複雜結構中選擇下一個被調度的進程的問題被稱為 Task Selection 或者 pick next。
Task Selection i.e. Pick Next
當調度器決定進行進程調度的時候，BFS 將按照下面的原則來進行任務的選擇：
首先查看 bitmap 是否有置位的比特。比如上圖，對應於 SCHED_NORMAL 的 bit 被置位，表明有類型為 SCHED_NORMAL 的進程 ready。如果有 SCHED_ISO 或者 RT task 的比特被置位，則優先處理他們。
選定了相應的 bit 位之後，便需要遍歷其相應的子佇列。假如是一個 RT 進程的子佇列，則選取其中的第一個進程。如果是其他的佇列，那么就採用 EEVDF 算法來選取合適的進程。
EEVDF，即 earliest eligible virtual deadline first。BFS 將遍歷該子佇列，一個雙向列表，比較佇列中的每一個進程的 Virtual Deadline 值，找到最小的那個。最壞情況下，這是一個 O(n) 的算法，即需要遍歷整個雙向列表，假如其中有 n 個進程，就需要進行 n 此讀取和比較。
但實際上，往往不需要遍歷整個 n 個進程，這是因為 BFS 還有這樣一個搜尋條件：
當某個進程的 Virtual Deadline 小於當前的 jiffies 值時，直接返回該進程。並將其從就緒佇列中刪除，下次再 insert 時會放到佇列的尾部，從而保證每個進程都有可能被選中，而不會出現飢餓現象。
這條規則對應於這樣一種情況，即進程已經睡眠了比較長的時間，以至於已經睡過了它的 Virtual Deadline，
T1 本來的 virtual deadline 為 t1，它 sleep 之後，其他的進程比如 T2 開始運行，等到 T1 再次 wakeup 的時候，當時的 jiffies 已經大於 t1，在這種情況下，T1 無需和其他進程的 virtual deadline 相比較，而直接被 BFS 調度器選取。
基本的調度場景
三個基本的 scenario 可以概括多數的調度情景。系統中發生的每一次調度都屬於以下三種情景之一。
進程wakeup：TaskInsertion
睡眠進程 wakeup 時，調度器需要執行 task insertion 的操作，將該進程插入到 run queue 中。BFS 將進程插入相應佇列的操作就是執行一個雙向佇列的插入操作，計算機常用算法結構告訴我們，這個操作是 O(1) 的。不過，BFS 在執行插入操作之前需要首先查看當前進程是否可以搶占當前正在系統中運行的進程。因此它會用新進程的 virtual deadline 值和當前在每個 CPU 上正在運行的進程的 virtual deadline 值進行比較，如果新進程的值小，則直接搶占該 CPU 上正在運行的進程。這個算法是 O(m) 的，其中 m 是 CPU 的個數，假如系統中有 16 個 CPU，那么每次都需要進行 16 次比較。但這個設計卻保證了非常好的 low-latency 特性。
進程 Sleep
當前正在運行的進程有可能主動睡眠，此時，調度器需要將該進程從 run queue 中移除，並選擇另外一個進程運行。但該進程的 virtual deadline 的值保持不變。
這樣該進程 wakeup 時，其 virtual deadline 將相對較小，因為 jiffies 隨著時間流逝而不斷增加。較小的 Virtual Deadline 可以保證該進程能更快得到調度。
仍然以圖 8 為例，系統中有兩個進程，T1 和 T2，T1 進入 sleep 狀態後其 virtual deadline 仍然為 t1。T2 此時被調度，根據公式一，計算得出其 virtual deadline 為 t2。此後，T1 進程 wakeup 了，此時雖然 T2 的時間片尚未用完，但由於 T1 的 virtual deadline 小於 T2 的，（t1<t2），因此 T1 立即得到調度。
進程用完自己的時間片
每個進程都擁有自己的時間片，即使不被其他進程搶占，假如屬於自己的時間片用完時，當前進程也一定會被剝奪 CPU 時間，以便讓別的進程有機會執行。
當前進程的時間片用完後就必須讓出 CPU, 此時將它的 virtual deadline 按照公式一重新計算。
這保證了一個特性：只有其他就緒進程都獲得 CPU 之後，用完當前時間片的進程才可以再次得到運行，這避免了飢餓。
