
_START_ARTICLE_
完全公平排程器
_START_PARAGRAPH_
完全公平调度器（英语：Completely Fair Scheduler，缩写为CFS），Linux内核的一部分，负责进程调度。参考了康恩·科里瓦斯（Con Kolivas）提出的调度器源代码后，由匈牙利程式员英格·蒙内（Ingo Molnar）所提出。在Linux kernel 2.6.23之后采用，取代先前的O(1)调度器，成为系统预设的调度器。它负责将CPU资源，分配给正在执行中的进程，目标在于最大化程式互动效能的同时，最小化整体CPU的运用。使用红黑树来实作，算法效率为O(log(n))。
_START_SECTION_
背景
_START_PARAGRAPH_
CFS 是首支以公平伫列（fair queuing）的调度器可应用于一般用途操作系统（general-purpose operating system）._NEWLINE_CFS调度器参考了康恩·科里瓦斯（Con Kolivas）所开发的楼梯调度算法（staircase scheduler）与RSDL（The Rotating Staircase Deadline Schedule）的经验_NEWLINE_，选取花费CPU执行时间最少的进程来进行调度。CFS主要由sched_entity 内含的vruntime所决定，不再跟踪process的sleep time，并扬弃active/expire的概念, runqueue里面所有的进程都平等对待，CFS使用“虚拟运行时”（virtual running time）来表示某个任务的时间量。_NEWLINE_CFS改使用红黑树算法，将执行时间越少的工作（即 sched_entity）排列在红黑树的左边，时间复杂度是O(log N)，节点（即rb_node）的安插工作则由dequeue_entity()和enqueue_entity（）来完成。当前执行的task通过呼叫put_prev_task 返回红黑树，下一个待执行的task则由pick_next_task来呼叫。蒙内表示, CFS在百分之八十时间都在确实模拟处理器的处理时间。
_START_SECTION_
争议
_START_PARAGRAPH_
因为在Linux 2.6.23 将CFS 合并到mainline。放弃了RSDL，引起康恩·科里瓦斯的不满，一度宣布脱离Linux开发团队。数年后, Con Kolivas 卷土重来, 重新开发脑残调度器来对决CFS, Jens Axboe 写了一个名为Latt.c 的程序进行比对，Jens 发现BFS 确实稍稍优于CFS，而且CFS 的 sleeper fairness 在某些情况下会出现调度延迟。Ingo不得不暂时关闭该特性，很快的在一周内提出新的Gentle Fairness，彻底解决该问题。