CFS调度器(一)

微信公众号：deepcoder
微信号：deepcoder_001
关注可了解操作系统知识。问题或建议，请公众号留言;
如果你觉得文章对你有帮助，欢迎转发^[1]

目录

1，概述2，少许实现细节3，红黑树4，CFS的一些特性5，调度策略6，调度类7，对CFS进行组调度器扩展

1，概述

CFS代表“完全公平调度器”，是Ingo Molnar实现的新的“桌面”进程调度器，并合并到Linux 2.6.23中。它取代了之前的普通调度器的SCHED_OTHER交互代码。

CFS 80%的设计可以用一句话概括:CFS基本上是在真实硬件上模拟一个“理想的、精确的多任务CPU”。

“理想的多任务CPU”是一个(不存在:-))CPU，具有100%的物理能力，可以以精确相等的速度并行运行每个任务，每个任务的运行速度为1/nr_running。例如:如果有两个任务正在运行，那么每个任务都以50%的物理能力运行——也就是说，实际上是并行的。

在真实的硬件上，我们一次只能运行一个任务，因此我们必须引入“虚拟运行时”的概念。任务的虚拟运行时指定了它的下一个时间片在上面描述的理想的多任务CPU上开始执行的时间。在实践中，任务的虚拟运行时是其规范化为运行任务总数的实际运行时。

2，少许实现细节

在CFS中，虚拟运行时是通过每个任务的p→se.vruntime(纳秒单位)值表示和跟踪的。通过这种方式，可以准确地进行时间戳，并测量任务应该获得的“预期CPU时间”。

[小细节:在“理想”硬件上，任何时候所有任务都具有相同的p→se.vruntime值——即，任务将同时执行，并且没有任务会从“理想”CPU时间共享中“失去平衡”。］

CFS的任务选择逻辑基于这个p→se.vruntime值，因此非常简单:它总是尝试运行具有最小p→se.vruntime值的任务(即到目前为止执行最少的任务)。CFS总是尝试在可运行的任务之间分配CPU时间，尽可能接近“理想的多任务硬件”。

CFS剩下的大部分设计都是基于这个简单的概念，并添加了一些额外的修饰，如nice level，多处理器和各种识别休眠者的算法变体。

3，红黑树

CFS的设计非常彻底:它不使用运行队列的旧数据结构，而是使用时间顺序的rbtree来构建未来任务执行的“时间轴”，因此没有“数组切换”的古老机制(该机制之前的vanilla调度器和RSDL/SD都受到影响)。

CFS还维护rq→cfs.min_vruntime值，这是一个单调递增的值，跟踪运行队列中所有任务中最小的vruntime。使用min_vruntime跟踪系统完成的工作总量;该值用于将新激活的实体尽可能地放置在树的左侧。

运行队列中运行任务的总数通过rq→cfs. load值计算，它是运行队列上排队的任务的权重之和。

CFS维护一个按时间顺序排列的rbtree，其中所有可运行的任务都按p→se.vruntime键排序。CFS从这个树中选择“最左边”的任务并坚持使用它。随着系统向前发展，执行的任务被越来越多地放到树的右边——缓慢但肯定地让每个任务都有机会成为“最左边的任务”，从而在确定的时间内进入CPU。

综上所述，CFS的工作方式是这样的:它稍微运行一个任务，当任务调度(或调度程序计时发生)时，任务的CPU使用量被“计入”:它刚刚使用物理CPU的时间被添加到p→se.vruntime中。一旦p→se.vruntime足够高，使得另一个任务成为它所维护的时间顺序rbtree的“最左边的任务”(加上相对于最左边的任务的少量“粒度”距离，这样我们就不会过度调度任务并丢弃缓存)，那么新的最左边的任务将被选中，当前任务将被抢占。

原文始发于微信公众号（deepcoder）：CFS调度器(一)