完全公平排程器

完全公平排程器

原作者	英格·蒙內
開發者	Linux核心開發人員
编程语言	C語言
操作系统	Linux核心
类型	行程排程器
许可协议	GPL-2.0
网站	kernel.org

完全公平排程器（英語：Completely Fair Scheduler，縮寫為CFS），Linux內核的一部份，負責行程排程。參考了澳大利亞麻醉師康恩·科里瓦斯提出的排程器原始碼後，由匈牙利程式員英格·蒙內所提出。在Linux核心2.6.23之後採用，取代先前的O(1)排程器，成為系統預設的排程器。它負責將CPU資源，分配給正在執行中的行程，目標在於最大化程式互動效能與整體CPU的使用率。使用紅黑樹來實作，演算法效率為${\displaystyle O(\log n)}$。

背景

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，延斯·艾克斯博（英语：Jens Axboe）寫了一個名为 Latt.c 的程序進行比對，艾克斯博發現BFS確實稍稍優於 CFS^[4]，而且CFS的 sleeper fairness 在某些情況下會出現調度延遲。^[5]英格·蒙內不得不暫時關閉該特性，很快的在一周內提出新的 Gentle Fairness，徹底解決該問題。

參考資料

1. Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin (PDF). [2013-10-18]. （原始内容存档 (PDF)于2013-10-19）. 
2. Molnár, Ingo. [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]. linux-kernel (邮件列表). 2007-04-13 [2013-10-18]. （原始内容存档于2013-10-09）. 
3. Andrews, Jeremy. Linux: The Completely Fair Scheduler. KernelTrap. 2007-04-18 [2013-10-18]. （原始内容存档于2012-06-29）. 
4. 存档副本. [2013-10-22]. （原始内容存档于2017-03-31）. 
5. 存档副本. [2013-10-22]. （原始内容存档于2013-10-23）.