完全公平排程器

完全公平排程器

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

完全公平排程器（英语：Completely Fair Scheduler，缩写为CFS），Linux内核的一部份，负责行程排程。参考了澳大利亚麻醉师康恩·科里瓦斯提出的排程器原始码后，由匈牙利程式员英格·蒙内所提出。在Linux核心2.6.23之后采用，取代先前的O(1)排程器，成为系统预设的排程器。它负责将CPU资源，分配给正在执行中的行程，目标在于最大化程式互动效能与整体CPU的使用率。使用红黑树来实作，演算法效率为$O(\log n)$。

背景

CFS 是首支以公平伫列（fair queuing）的排程器可应用于一般用途作业系统（general-purpose operating system）.

CFS排程器参考了康恩·科里瓦斯所开发的楼梯调度算法（staircase scheduler）与RSDL（The Rotating Staircase Deadline Schedule）的经验 ，选取花费CPU执行时间最少的行程来进行排程。CFS主要由sched_entity 内含的 vruntime所决定，不再跟踪process的sleep time，并扬弃active/expire的概念，runqueue里面所有的进程都平等对待，CFS使用“虚拟运行时”（virtual running time）来表示某个任务的时间量。

CFS改使用红黑树演算法，将执行时间越少的工作（即 sched_entity）排列在红黑树的左边，时间复杂度是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，而且CFS的 sleeper fairness 在某些情况下会出现调度延迟。英格·蒙内不得不暂时关闭该特性，很快的在一周内提出新的 Gentle Fairness，彻底解决该问题。