前言

早期的Linux调度器采用了简化的设计，显然并不针对具有许多处理器甚至超线程的大规模架构。Linux 1.2调度器使用循环队列对可运行任务进行管理，并采用循环调度策略。这个调度器对于添加和删除进程非常高效（使用锁来保护结构）。简而言之，这个调度器并不复杂，但简单且快速。

Linux 2.2版本引入了调度类的概念，允许为实时任务、非可抢占任务和非实时任务设置调度策略。2.2调度器还包括对对称多处理（SMP）的支持。

2.4内核包含了一个相对简单的调度器，它在O(N)时间内运行（因为它在每个调度事件中迭代所有任务）。2.4调度器将时间划分为时期，在每个时期内，每个任务都可以执行其时间片的时间。如果一个任务没有使用完其时间片，那么剩余时间片的一半将被添加到新的时间片中，以使其在下一个时期中执行时间更长。调度器只需要迭代任务，应用一个好度函数（度量）来确定下一个要执行的任务。尽管这种方法相对简单，但它相对低效，缺乏可扩展性，并且对于实时系统来说并不强大。它也缺乏利用新的硬件架构（如多核处理器）的功能。

早期的2.6调度器被称为O(1)调度器，旨在解决2.4调度器的许多问题。即调度器不需要迭代整个任务列表来确定下一个要调度的任务（因此得名O(1)，表示它更高效且可扩展性更好）。O(1)调度器通过在一个运行队列中跟踪可运行任务（实际上，对于每个优先级级别，有两个运行队列，一个用于活动任务，一个用于过期任务），这意味着为了确定下一个要执行的任务，调度器只需从特定的活动优先级运行队列中出队即可。O(1)调度器具有更好的可扩展性，并结合了交互性指标和许多启发式方法，以确定任务是I/O绑定还是处理器绑定。但是O(1)调度器在内核中变得臃肿。用于计算启发式方法的大量代码基本上难以管理，并且对于纯粹主义者来说，缺乏算法实质。

面对O(1)调度器及其他外部压力，需要进行一些改变。这种改变来自于Con Kolivas的内核补丁，其中包括他之前在阶梯调度器上的工作，引入了他的Rotating Staircase Deadline Scheduler (RSDL)。这项工作的结果是一个简单设计的调度器，将公平性与有界延迟相结合。Kolivas的调度器给很多人留下了深刻印象（有人呼吁将其纳入当前的2.6.21主线内核），因此可以明显看到调度器的改变正在途中。接着，O(1)调度器的创建者Ingo Molnar基于Kolivas的工作思想开发了CFS。

CFS（Completely Fair Scheduler）是Linux操作系统中的一种新的进程调度器，与其竞争对手RSDL相比，CFS的选择在某些圈子中引起了很大争议。为了澄清发生了什么以及CFS相对于旧调度器的作用，需要一些历史背景。

在Linux 2.5的开发过程中，来自Ingo Molnar的’O(1)'进程调度器（PS）被合并以取代从2.4继承的调度器。O(1) PS的设计旨在解决2.4调度器存在的可扩展性问题 - 性能改进非常显著，以至于O(1) PS成为商业Linux发行版中最常被反向移植到2.4的特性之一。然而，负责调度进程的算法并没有发生太大改变，因为它们被认为是“足够好”，或者至少没有被视为关键问题。但是，这些算法在用户所感知的“交互性”方面可能会产生巨大影响。例如，如果一个或多个进程开始执行无限循环，并且由于这些占用CPU的循环进程，调度器没有为已经存在的负责实现用户界面（如X.org、kicker、firefox、openoffice.org等）的非循环进程分配足够的CPU时间，用户会感觉这些程序对用户的操作反应不够流畅。更糟糕的是，在音乐播放器的情况下，你的音乐可能会出现跳跃。

O(1)进程调度器PS和之前的调度器一样，试图改善这些情况，并且大多数时候表现良好。然而，许多用户报告了一些特殊情况和非特殊情况，新的调度器并没有按预期工作。其中一个用户是Con Kolivas，尽管他在内核编程领域没有经验，但他试图微调调度算法，而不是替换它们。他的工作取得了成功，他的补丁被纳入了主内核，其他人（Mike Galbraith、Davide Libenzi、Nick Piggin）也帮助调整了调度器。但并非所有特殊情况都消失了，当尝试修复其中一个问题时，可能会出现新问题。Con发现，“交互性估计器”——PS用来尝试判断哪些进程更具“交互性”，因此需要更多关注，以便用户感知其桌面更具“交互性”的一段代码，引发了比解决问题更多的问题。与其原始目的相反，交互性估计器无法解决PS中存在的所有“交互性”问题，而且尝试修复一个问题可能会导致另一个问题的出现。这是一个典型的算法使用统计数据和启发式方法来预测未来并在其上失败的案例。Con设计了一个名为RSDL的新的调度器，它取消了交互性估计代码。相反，他的调度器基于“公平性”的概念：进程被平等对待，并被分配相同的时间片（有关此调度器的更多细节，请参阅LWN文章：https://lwn.net/Articles/224865/）。这个调度器在这些特殊情况下改善了用户所感知的“交互性”。

这个PS原本打算合并，但Ingo Molnar（O(1)的创建者）创建了另一个名为CFS（完全公平调度器）的新的PS，其中一个基本设计元素是Con的PS证明了“公平调度”的优越性。CFS得到了一些黑客的好评，这帮助Ingo使CFS成为主线内核的一个很好的进程调度器替代方案。'公平性’是RSDL和CFS之间唯一共享的概念，这也是它们的相似之处终止的地方，甚至’公平性’的定义也非常不同：RSDL使用了’严格’的公平性定义。但是CFS将任务的睡眠时间包括在公平性指标中：这意味着在CFS中，睡眠任务（通常运行用户感觉为’交互式’的代码，如X.org、mp3播放器等）获得比运行任务更多的CPU时间（与RSDL的’严格公平性’不同，RSDL对它们采用严格的公平性处理），但这一切都受到公平性引擎的控制。这种设计兼顾了公平性和交互性，但没有使用交互性估计器。

CFS相对于旧的主线调度器和RSDL还有其他一些不同之处：它使用一个按时间顺序排列的红黑树（time-ordered rbtree）来构建未来任务执行的’时间轴’，以尝试避免常规调度器和RSDL调度器可能出现的’数组切换’问题。CFS还使用纳秒级粒度的计时，并且不依赖于任何滴答数或其他HZ细节；实际上，它没有传统的’timeslices’概念：切片决策是动态的，而不是静态的，并且切片没有持久性（即切片不是以传统意义上的方式’给予’任务并被任务’消耗’），因为CFS能够通过纳秒级计时准确追踪任务的完整执行历史。

最终，CFS被选择作为当前’O(1)'进程调度器的替代品，而不是RSDL。必须指出的是，无论是RSDL还是CFS，它们都是比主线内核中的调度器更好的调度器，而正是Con首创了使用’公平性’的概念而不是’交互性估计’的想法，但这并不意味着CFS不应该作为主线内核进程调度器的最终替代品被合并；这也不意味着RSDL不是一个很好的替代品。

可以看到CFS调度器是用来解决交互性进程响应快慢的问题，更适用于桌面操作系统；对于服务器来说，更注重吞吐性，CFS调度器和O1调度器没啥差别。

在一个混杂着大量计算型进程和IO交互进程的系统中，CFS调度器对待IO交互进程要比O(1)调度器更加友善和公平。

O(1)调度器直接将优先级线性映射到了时间片（进程的优先级和进程可运行的时间片进行了强映射），以表示差异化。
CFS调度器则直接将进程优先级映射到了CPU时间份额，以表示差异化。

优先级和时间片本来就是两个概念，二者中间还得有个变量沟通才可以。优先级高只是说明该进程能运行的久一些，但是到底久多少，并不是仅仅优先级就能决定的，还要综合考虑，换句话距离来说，如果只有一个进程，那么即便它优先级再低，它也可以永久运行，如果系统中有很多的进程，即便再高优先级的进程也要让出一些时间给其它进程。

CFS考虑到系统中总体的进程情况，将优先级转换为权重，将时间片转换为份额。最终的坐标系应该是 权重占比/时间片 坐标系而不是 权重(或者优先级)/时间片 。

CFS的时间片是动态的，是系统负载均衡以及其优先级的函数，这便可以把进程调度动态适应到系统最佳，以节省切换开销。

一、概要

CFS（Completely Fair Scheduler）是由Ingo Molnar实现并在Linux 2.6.23中合并的新的“桌面”进程调度器。它是对以前的普通调度器（vanilla scheduler）的SCHED_OTHER互动性代码的替代。

CFS的设计中，80%可以用一句话总结：CFS基本上在真实硬件上模拟了一个“理想的、精确的多任务CPU”。

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

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

CFS（完全公平调度器）的主要思想是在为任务提供处理器时间时保持平衡（公平性）。这意味着进程应该被给予公平的处理器时间。当任务的时间不平衡（意味着一个或多个任务与其他任务相比没有得到公平的时间）时，那些不平衡的任务应该被给予执行的时间。

为了确定平衡，CFS维护了所谓的虚拟运行时间，即为给定任务提供的时间量。任务的虚拟运行时间越小（意味着任务被允许访问处理器的时间越少），它对处理器的需求就越高。CFS还包括了“睡眠公平性”的概念，以确保当前不可运行的任务（例如，等待I/O的任务）在它们最终需要处理器时能够获得相当的份额。

但与以前的Linux调度器在运行队列中维护任务不同，CFS维护一个按时间排序的红黑树（如下图所示）。红黑树是一种具有一些有趣和有用属性的树。首先，它是自平衡的，这意味着树中的任意路径长度都不会超过其他路径长度的两倍。其次，对树的操作在O(log n)的时间内完成（其中n是树中节点的数量）。这意味着您可以快速高效地插入或删除一个任务。

在按时间排序的红黑树中存储任务（表示为sched_entity对象），具有最迫切需要处理器的任务（虚拟运行时间最低）存储在树的左侧，而对处理器需求最小的任务（虚拟运行时间最高）存储在树的右侧。为了保持公平性，调度器选择红黑树的最左边的节点作为下一个要调度的任务，以保持公平性。任务通过将其执行时间添加到虚拟运行时间来记录其在CPU上的时间，如果可运行，则重新插入到树中。通过这种方式，树的左侧的任务被给予执行时间，并且树的内容从右侧向左侧迁移，以保持公平性。因此，每个可运行的任务都会追逐其他任务，以在可运行任务集合中保持执行的平衡。

二、实现

2.1 简介

CFS有一些有趣的方面。首先，它完全取消了运行队列数组的使用。相反，CFS使用单个红黑树来跟踪所有处于可运行状态的进程。在树的最左节点出现的进程是在任何给定时间最有资格运行的进程。因此，理解这个调度器的关键是了解它如何计算用于将进程插入树中的键值。

这个计算相当简单。当一个任务进入运行队列时，记录下当前时间。当进程等待CPU时，调度器跟踪它本应获得的处理器时间量；这个权益简单地是等待时间除以运行进程数（根据不同优先级值进行修正）。在实际情况下，键值是进程应获得的CPU时间量，而较高优先级的进程会稍微获得提升。因此，进程的短期优先级将根据它是否获得了公平的处理器份额而变化。

只是略微简化地说，上述讨论涵盖了CFS调度器的全部内容。它没有跟踪睡眠时间，也没有尝试识别交互式进程等等。从某种意义上说，CFS调度器甚至取消了时间片的概念；一切都取决于给定进程是否获得了根据试图运行的进程数而应得的CPU份额。CFS调度器提供了一个可调整的参数："granularity"值，用于描述调度器为了保持公平性而切换进程的速度。较低的granularity值会导致更频繁的切换；这个设置会降低交互响应的延迟，但可能会稍微降低吞吐量。服务器系统可能会在较高的granularity值下运行得更好。

2.2 算法实现

在CFS中，虚拟运行时间通过每个任务的p->se.vruntime（纳秒单位）值来表示和跟踪。通过这种方式，可以准确地记录和测量任务应该获得的“预期CPU时间”。

一个小细节是，在“理想”的硬件上，任何时候所有任务的p->se.vruntime值都相同，也就是说，任务会同时执行，没有任务会从“理想”的CPU时间份额中“失衡”。

CFS的任务选择逻辑基于p->se.vruntime值，因此非常简单：它总是尝试运行具有最小p->se.vruntime值的任务（即到目前为止执行最少的任务）。CFS始终尽可能地将CPU时间在可运行的任务之间分配得接近“理想的多任务硬件”。

CFS的大部分设计都是基于这个非常简单的概念。

CFS的设计非常激进：它不使用旧的运行队列数据结构，而是使用一个按时间排序的红黑树来构建未来任务执行的“时间线”，因此没有“数组切换”现象（这会影响到以前的普通调度器和RSDL/SD）。

CFS还维护了rq->cfs.min_vruntime值，它是一个单调递增的值，跟踪运行队列中所有任务中最小的vruntime。系统完成的总工作量通过min_vruntime来跟踪；该值被用于尽可能将新激活的实体放在树的左侧。

运行队列中正在运行的任务总数通过rq->cfs.load值来统计，该值是排队在运行队列上的任务权重的总和。

CFS维护了一个按时间排序的红黑树，其中所有可运行的任务按照p->se.vruntime键进行排序。CFS从这棵树中选择“最左边”的任务并坚持执行。随着系统的前进，执行的任务被逐渐放置到树的右侧，以便给每个任务一个机会成为“最左边的任务”，从而在确定的时间内获得CPU时间。

总结起来，CFS的工作方式如下：它运行一个任务一小段时间，当任务调度（或发生调度器时钟中断）时，任务的CPU使用情况被“记账”：刚刚使用物理CPU的时间被添加到p->se.vruntime中。一旦p->se.vruntime变得足够高，以至于另一个任务成为它维护的按时间排序的红黑树的“最左边的任务”（加上一小段与最左边任务的“粒度”距离，以避免过度调度任务和缓存垃圾），则选择新的最左边任务并抢占当前任务。

2.3 内核源码

在Linux中，所有任务都由一个名为task_struct的任务结构表示。该结构（以及与之相关的其他结构）完整描述了任务，包括任务的当前状态、堆栈、进程标志、优先级（静态和动态）等等。但是，由于并非所有任务都是可运行的，因此在task_struct中找不到与CFS相关的字段。相反，创建了一个名为sched_entity的新结构来跟踪调度信息。

// linux-4.10.1/include/linux/sched.hstruct sched_entity {struct load_weight	load;		/* for load-balancing */struct rb_node		run_node;struct list_head	group_node;unsigned int		on_rq;......u64			vruntime;	
}struct task_struct {......struct sched_entity se;	......
}

sched_entity结构用于存储任务的调度信息，包括任务的虚拟运行时间、调度实体的优先级以及其他与CFS调度器相关的字段。通过sched_entity结构，CFS可以跟踪每个任务的运行时间和调度状态，并根据任务的需求进行公平调度。

各种结构之间的关系如上图所示。树的根节点通过cfs_rq结构中的rb_root元素进行引用。红黑树中的叶子节点不包含任何信息，但内部节点表示一个或多个可运行的任务。红黑树中的每个节点都由一个rb_node表示，其中只包含子节点的引用和父节点的颜色信息。rb_node包含在sched_entity结构中，该结构包括rb_node引用、负载权重和各种统计数据。最重要的是，sched_entity包含一个64位的vruntime字段，用于表示任务运行的时间量，并作为红黑树的索引。最后，task_struct位于顶部，完整描述了任务，并包含sched_entity结构。

三、特点

CFS的设计非常激进：它不使用运行队列，而是使用一个按时间排序的rbtree来构建未来任务执行的“时间轴”，因此没有“数组切换”现象（这是原始调度器和RSDL/SD所受影响的）。

CFS使用纳秒级的精确度进行计算，不依赖于任何jiffies或其他HZ细节。因此，CFS调度器没有像以前的调度器那样关于“时间片”的概念，并且没有任何启发式规则。中心可调参数为"/proc/sys/kernel/sched_granularity_ns"，可以用来根据不同的工作负载从"桌面"（低延迟）到"服务器"（良好批处理）进行调整。默认设置适用于桌面工作负载，并且还处理SCHED_BATCH工作负载。

CFS保证的是每时每刻的公平，cfs依据的是进程的执行时间，利用的是补偿原理，cfs让进程先超前运 行，然后补偿别的进程，这样很合理。另外cfs不用任何启发算法，只是一个虚拟时钟就够了，因为当进程睡眠的时候，其虚拟时钟就不走了，这样当然落后于别 的进程的虚拟时钟，理应得到补偿。

可以用来调整调度器以适应“桌面”（即低延迟）到“服务器”（即良好批处理）负载。它的默认设置适用于桌面工作负载。CFS调度器模块也处理SCHED_BATCH。

CFS调度器对于nice级别和SCHED_BATCH的处理比以前的普通调度器更强大：这两种类型的工作负载被更积极地隔离。

负载平衡代码在对称多处理（SMP）系统中进行了重新设计和清理。代码不再依赖于运行队列遍历的假设，而是使用来自调度模块的迭代器。这个改变简化了负载平衡代码。

引入了调度类（Scheduling Classes）：这是一个可扩展的调度程序模块层次结构。这些模块封装了调度策略的细节，并由调度器核心处理，而核心代码对它们的假设不过多。

该模块以比原始调度器更简单的方式实现了SCHED_FIFO和SCHED_RR的语义。它使用100个运行队列来处理所有100个实时（RT）优先级级别，而不是原始调度器的140个运行队列。它也不需要一个过期数组。

四、调度策略

CFS（完全公平调度器）实现了三种调度策略：
（1）SCHED_NORMAL（传统上称为SCHED_OTHER）：这是用于常规任务的调度策略。它用于普通任务的默认调度策略。

（2）SCHED_BATCH：相比于常规任务，该策略不会频繁地进行抢占，从而允许任务运行更长时间并更好地利用缓存，但代价是降低了交互性。这非常适合批处理作业。

（3）SCHED_IDLE：该策略比nice 19的任务优先级还要低，但它不是一个真正的空闲定时器调度器，以避免陷入优先级反转问题，这可能导致系统死锁。

五、调度类

CFS发布还带来了一个意外的特性，几乎让所有关注内核开发领域的人感到惊讶：一个模块化调度器框架。Ingo将其描述为"一个可扩展的调度器模块层次结构"，但是，如果是这样的话，它是一个没有分支的层次结构。它是一个按优先级顺序排列的模块简单链表；第一个能够提供可运行任务的调度器模块将决定下一个运行的进程。

新的CFS调度器的设计引入了“调度类（Scheduling Classes）”，这是一种可扩展的调度器模块层次结构。这些模块封装了调度策略的细节，并由调度器核心处理，核心代码不会对它们做过多的假设。

调度类通过sched_class结构来实现，该结构包含了在发生事件时必须调用的函数钩子。

// kernel/sched/sched.hstruct sched_class {const struct sched_class *next;void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);void (*yield_task) (struct rq *rq);bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);/** It is the responsibility of the pick_next_task() method that will* return the next task to call put_prev_task() on the @prev task or* something equivalent.** May return RETRY_TASK when it finds a higher prio class has runnable* tasks.*/struct task_struct * (*pick_next_task) (struct rq *rq,struct task_struct *prev,struct pin_cookie cookie);void (*put_prev_task) (struct rq *rq, struct task_struct *p);......
}

● Stop○ No policy
● Deadline○ SCHED_DEADLINE
● Real Time○ SCHED_FIFO○ SCHED_RR
● Fair○ SCHED_NORMAL○ SCHED_BATCH○ SCHED_IDLE
● Idle○ No policy

以下是这些函数钩子的（部分）列表：

enqueue_task(…)

当任务进入可运行状态时调用。它将调度实体（任务）放入红黑树中，并增加nr_running变量。

dequeue_task(…)

当任务不再可运行时，调用此函数将相应的调度实体从红黑树中移除。它减少nr_running变量。

yield_task(…)

除非启用了compat_yield sysctl，否则此函数基本上只是一个dequeue，然后是一个enqueue操作；在这种情况下，它将调度实体放置在红黑树的最右端。

wakeup_preempt(…)

此函数检查进入可运行状态的任务是否应该抢占当前正在运行的任务。

pick_next_task(…)

此函数选择下一个合适的可运行任务。

set_next_task(…)

当任务更改其调度类、更改其任务组或被调度时，调用此函数。

task_tick(…)

此函数主要从时间滴答函数中调用；它可能导致进程切换。它驱动运行抢占。

参考资料

Linux 4.10.0
https://www.kernel.org/doc/html/latest/scheduler/sched-design-CFS.html
https://kernelnewbies.org/Linux_2_6_23#The_CFS_process_scheduler
https://lwn.net/Articles/230574/
https://developer.ibm.com/tutorials/l-completely-fair-scheduler/

https://blog.csdn.net/dog250/article/details/95729830
https://blog.csdn.net/dog250/article/details/96500186
https://zhuanlan.zhihu.com/p/659215677