526互联

CFS（一）设计理念与实现架构

发布时间 2023-10-11 11:37:57作者: ZouTaooo

前言

本文对CFS的基础的设计理念以及在内核实现上的基本代码架构进行了分析，从宏观上梳理调度和CFS的脉络。本文所有的代码基于Linux 4.19。

CFS的设计理念和目标

CFS（Completely Fair Scheduler）完全公平调度器，从字面上看定义的很清晰，首先CFS的本质是一个调度器，所谓调度就是决定CPU的执行权在每个时刻的归属，调度管理的对象就是CPU资源。所谓完全公平追求的是一种理想的多任务CPU模型，CPU资源能够平等分配给每一个任务，比如有两个任务，每个任务能够得到50%的CPU资源，但是这是一个不可能完成的任务，首先，对于CPU来说一个时刻只能有一个任务在执行，不存在并行执行；第二点，在执行的过程中不断地有任务的加入和退出。在这样的复杂场景下只能追求近似的完全公平。

设计中的关键点

CFS调度器在Linux 2.6中被引入，CFS在设计上有一些关键的点，提前了解可以有助于后续阅读源码：

  1. 虚拟时间（vruntime）：在CFS中使用vruntime来表示一个task在该CPU上的运行时间，vruntime累计值的计算与任务的优先级（权重）以及runq中的任务数量有关。CFS的调度逻辑也很简单，当一个调度时机出现时选择当前runq中vruntime最少的任务获得CPU。vruntime可以说是CFS调度器的灵魂，通过vruntimeCFS间接实现了任务优先级，高优先级能够得到更多的CPU时间。
  2. runq的实现基于红黑树实现，从逻辑上说任何能实现虚拟时间排序的数据结构都是可以作为runq的，但是红黑树在内存、性能的综合考虑下表现最好，在查找、删除、插入的这种场景下性能表现稳定。
  3. 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外都不重要，只是需要清楚存在这样一个概念，调度时会优先选择高优先级的调度器中的任务执行。

graph LR A[stop_sched_class] -.-> B[dl_sched_class] -.-> C[rt_sched_class] -.-> D[fair_sched_class] -.-> E[idle_sched_class]
调度类优先级

就绪队列

在调度类中只定义了了CFS的基本操作，这些函数的操作对象包括就绪队列和任务。在内核中就绪队列通过struct rq实现。struct rq是一个per-cpu的数据结构，可以看到struct rq下包含了cfs、rt、dl三个队列对应着三个不同的调度类。

NOTE：需要注意不同调度类的就绪队列实现是不同的，其次每一个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线程。因此这两个调度类不需要就绪队列。

graph TB subgraph CPUS C1[CPU0] Cx[....] C2[CPUn] end C1 -.-> rq subgraph rq cfs1[cfs_rq] rq1[rt_rq] dl1[dl_rq] end cfs1 -.->|tasks_timeline| rb_root_cached subgraph rb_root_cached rb_leftmost rb_root end rb_root -.-> 27 rb_leftmost -.-> 2 subgraph 27((27)) --> 19((19)) 19 --> 7((7)) --> 2((2)) 19 --> 25((25)) 27-->34 34--> 31((31)) 34((34)) --> 65((65)) --> 49((49)) 65 --> 98((98)) end subgraph task_struct se[sched_entity se] end se -.-> sched_entity subgraph sched_entity run_node[rb_node] vruntime[vruntime=98] end run_node -.-> 98
CFS数据组织结构

这里我们重点关注的是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;
};