完全公平排程器
完全公平排程器(英語:Completely Fair Scheduler,縮寫為CFS),Linux內核的一部份,負責行程排程。參考了澳大利亞麻醉師康恩·科里瓦斯提出的排程器原始碼後,由匈牙利程式員英格·蒙內所提出。在Linux核心2.6.23之後採用,取代先前的O(1)排程器,成為系統預設的排程器。它負責將CPU資源,分配給正在執行中的行程,目標在於最大化程式互動效能與整體CPU的使用率。使用紅黑樹來實作,演算法效率為。
原作者 | 英格·蒙內 |
---|---|
開發者 | Linux核心開發人員 |
程式語言 | C語言 |
作業系統 | Linux核心 |
類型 | 行程排程器 |
許可協定 | GPL-2.0 |
網站 | kernel |
背景
編輯CFS 是首支以公平佇列(fair queuing)的排程器可應用於一般用途作業系統(general-purpose operating system).[1]
CFS排程器參考了康恩·科里瓦斯所開發的樓梯排程演算法(staircase scheduler)與RSDL(The Rotating Staircase Deadline Schedule)的經驗[2] ,選取花費CPU執行時間最少的行程來進行排程。CFS主要由sched_entity 內含的 vruntime所決定,不再跟蹤process的sleep time,並揚棄active/expire的概念,runqueue裏面所有的行程都平等對待,CFS使用「虛擬執行時」(virtual running time)來表示某個任務的時間量。
CFS改使用紅黑樹演算法,將執行時間越少的工作(即 sched_entity)排列在紅黑樹的左邊[3],時間複雜度是O(log N),節點(即rb_node)的安插工作則由dequeue_entity()和enqueue_entity()來完成。當前執行的task通過呼叫 put_prev_task 返回紅黑樹,下一個待執行的task則由pick_next_task來呼叫。蒙內表示,CFS在百分之八十時間都在確實模擬處理器的處理時間。
爭議
編輯因為在Linux 2.6.23將CFS合併到mainline。放棄了RSDL,引起科里瓦斯的不滿,一度宣佈脫離Linux開發團隊。數年後,科里瓦斯回歸,重新開發腦殘排程器來對決 CFS,延斯·艾克斯博寫了一個名為 Latt.c 的程式進行比對,艾克斯博發現BFS確實稍稍優於 CFS[4],而且CFS的 sleeper fairness 在某些情況下會出現調度延遲。[5]英格·蒙內不得不暫時關閉該特性,很快的在一周內提出新的 Gentle Fairness,徹底解決該問題。
參考資料
編輯- ^ Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin (PDF). [2013-10-18]. (原始內容存檔 (PDF)於2013-10-19).
- ^ Molnár, Ingo. [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]. linux-kernel (郵寄清單). 2007-04-13 [2013-10-18]. (原始內容存檔於2013-10-09).
- ^ Andrews, Jeremy. Linux: The Completely Fair Scheduler. KernelTrap. 2007-04-18 [2013-10-18]. (原始內容存檔於2012-06-29).
- ^ 存档副本. [2013-10-22]. (原始內容存檔於2017-03-31).
- ^ 存档副本. [2013-10-22]. (原始內容存檔於2013-10-23).