前言
本文对CFS的基础的设计理念以及在内核实现上的基本代码架构进行了分析，从宏观上梳理调度和CFS的脉络。本文所有的代码基于Linux 4.19。
CFS的设计理念和目标
CFS（Completely Fair Scheduler）完全公平调度器，从字面上看定义的很清晰，首先CFS的本质是一个调度器，所谓调度就是决定CPU的执行权在每个时刻的归属，调度管理的对象就是CPU资源。所谓完全公平追求的是一种理想的多任务CPU模型，CPU资源能够平等分配给每一个任务，比如有两个任务，每个任务能够得到50%的CPU资源，但是这是一个不可能完成的任务，首先，对于CPU来说一个时刻只能有一个任务在执行，不存在并行执行；第二点，在执行的过程中不断地有任务的加入和退出。在这样的复杂场景下只能追求近似的完全公平。
设计中的关键点
CFS调度器在Linux 2.6中被引入，CFS在设计上有一些关键的点，提前了解可以有助于后续阅读源码：
- 虚拟时间（
vruntime）：在CFS中使用vruntime来表示一个task在该CPU上的运行时间，vruntime累计值的计算与任务的优先级（权重）以及runq中的任务数量有关。CFS的调度逻辑也很简单，当一个调度时机出现时选择当前runq中vruntime最少的任务获得CPU。vruntime可以说是CFS调度器的灵魂，通过vruntimeCFS间接实现了任务优先级，高优先级能够得到更多的CPU时间。 - runq的实现基于红黑树实现，从逻辑上说任何能实现虚拟时间排序的数据结构都是可以作为runq的，但是红黑树在内存、性能的综合考虑下表现最好，在查找、删除、插入等场景下性能表现稳定。
- cgroup：支持按group来分配时间片，以组为单位划分CPU资源。
CFS内核实现的相关数据结构
调度类
任何机制都是对数据的操作，在理解或者了解一项技术前需要先纵览它的设计架构。首先，在内核中CFS只是调度器中的一种，还有针对于实时系统的实时调度器，同时为了满足调度器的可拓展性，调度器被抽象为调度类（Scheduling Class），类似于C++中的虚基类，只定义了函数的类型具体的实现交给具体的子类，CFS就是其子类之一。
sched_class定义了一个调度器应该具备的基本操作，CFS调度器的实现在fair.c中，fair_sched_class变量就是CFS的调度类对象，初始化了所有的函数指针。
const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
....
.update_curr = update_curr_fair,
};
在sched_class中的next指针指向下一个调度类，所有的调度类按照优先级从高到低存放在单链表中。优先级从高到底依次是stop_sched_class、dl_sched_class、rt_sched_class、fair_sched_class以及idle_sched_class。不同的调度类实现了不同的调度策略，在本文中只需要关注fair_sched_class，但是需要清楚存在这样一个逻辑，调度时会优先选择高优先级调度器中的任务获取CPU执行权。
就绪队列
在调度类中只定义了CFS的基本操作，这些函数的操作对象包括就绪队列和任务。在内核中就绪队列通过struct rq实现。struct rq是一个per-cpu的数据结构，可以看到struct rq下包含了cfs、rt、dl三个队列对应着三个不同的调度类。
NOTE：1. 不同调度类的就绪队列实现是不同的，与其策略相关。2. 每一个CPU上的就绪队列是独立的。
struct rq {
struct cfs_rq cfs;
struct rt_rq rt;
struct dl_rq dl;
....
struct task_struct *curr; // 当前在运行的task
struct task_struct *idle; // idle task
struct task_struct *stop; // stop task
};
这里存在一个问题，为什么调度类有五个只有三个就绪队列，因为stop和idle两个调度类只执行固定的进程，stop调度类用于stop_machine.c，停机线程的优先级高于所有的task，这也是stop调度类的优先级最高的原因。idle调度类执行的是固定的idle线程。因此这两个调度类不需要就绪队列。
这里我们重点关注的是CFS的就绪队列cfs_rq。cfs_rq中最关键的就是存放调度实体的队列，也就是上述的红黑树的数据结构。但是内核中使用的红黑树还存在一点优化，在rb_root_cached中不仅存放了红黑树的根节点，还缓存最小元素的节点指针，将访问最小元素的操作简化到O(1)。除此之外，内核中的红黑树实现是一个通用的数据结构，具体的实现细节这里不详细说明，只需要明确通过rb_leftmost这个struct rb_node指针我们可以找到其对应的调度实体即可，中间的转化会涉及一些编译器与指针的trick。
struct cfs_rq {
struct rb_root_cached tasks_timeline;
...
}
struct rb_root_cached {
struct rb_root rb_root;
struct rb_node *rb_leftmost;
};