完全公平调度器

完全公平调度器(英语:Completely Fair Scheduler,缩写为CFS),Linux内核的一部分,负责进程调度。参考了澳大利亚麻醉师康恩·科里瓦斯提出的调度器原始码后,由匈牙利程序员英格·蒙内所提出。在Linux核心2.6.23之后采用,取代先前的O(1)调度器,成为系统默认的调度器。它负责将CPU资源,分配给正在执行中的进程,目标在于最大化程序交互性能与整体CPU的使用率。使用红黑树来实现,算法效率为

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

背景

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).