2.6.2.1 调度逻辑 - 数据结构

不管是O(n)还是O(1), 调度器采用的都是列表来组织任务，O(n)将所有的任务都放在一个列表中，每次调度时都需要遍历所有节点；O(1)采用了多级列表，不同的列表通过优先级来划分，显著地提高了查找效率。由于CFS在调度时只需要选择vruntime最小的节点，因此CFS选择了红黑树（Red-Black Tree）这种更高效的数据结构来管理任务，红黑树的Key就是vruntime, 这样红黑树最左子节点永远都是下一个需要调度的任务。

红黑树是二叉查找树（BST - Bianry Search Tree）的一种，其特点是在对树节点进行增加、删除操作时能够尽可能地保持平衡，这样可以保证即使在最坏的情况下，总体的时间复杂度都保持在对数级别。这里我们不对红黑树做深入讨论，感兴趣的读者可以自行查阅资料。

Linux中黑红树的实现在文件 lib/rbtree.c 中，此处有详细介绍：https://lwn.net/Articles/184495/

CFS 使用调度实体 sched_entity 来封装调度时需要的各种属性，删除组调度与统计信息后代码如下：

/* file: include/linux/sched.h */
struct sched_entity {
/* 记录当前se的权重信息，由进程的nice值计算得到 */
struct load_weight load;
/* 指向该se在红黑树中的节点 */
struct rb_node run_node;
/* 是否在 runqueue 上，1 则表示在 rq 中 */
unsigned int on_rq;

/* 当该se被调度时，记录其开始执行的时间，以便后期用来计算该se此次调度的时长 */
u64 exec_start;
/* 记录总运行时间 */
u64 sum_exec_runtime;
/* 该进程的虚拟运行时间，该值是红黑树中的 key, CFS 依据该值来保证公平调度 */
u64 vruntime;
/* 截止该调度周期开始时，进程的总运行时间，在check_preempt_tick中会使用到 */
u64 prev_sum_exec_runtime;
}

struct load_weight {
/* nice 对应的权重数组sched_prio_to_weight中的值 */
unsigned long weight;

/* 记录 sched_prio_to_wmult 数组中的值 */
u32 inv_weight;
};

CFS 定义了自己的运行队列 cfs_rq, 同样删除额外字段后内容如下：

/* file: kernel/sched/sched.h */
struct cfs_rq {
/* 保存 CFS 整个运行队列的总权重，用于给每个调度实体计算 vruntime */
struct load_weight load;
/* 队列里面处于 runnable 状态的 se 的总数 */
unsigned int nr_running;
/* h 代表 hierarchy, 该字段会在组调度时讲解 */
unsigned int h_nr_running;

/* 记录该 cfs_rq 的总运行时间，用于统计 */
u64 exec_clock;
/* 记录队列中当前最小的 vruntime */
u64 min_vruntime;

/* 保存一个指向红黑树根节点与最左子节点的缓存 */
struct rb_root_cached tasks_timeline;

/* 指向当前正在运行的 se */
struct sched_entity *curr;
struct sched_entity *next;
struct sched_entity *last;
struct sched_entity *skip;
};

/* file: tools/include/linux/rbtree.h */
/* 指向红黑树根节点与最左子节点的缓存结构 */
struct rb_root_cached {
struct rb_root rb_root;
struct rb_node *rb_leftmost;
};

为什么需要保存 min_vruntime 呢？CFS 每次调度都选择 vruntime 最小的进程来运行，试想一下当系统创建一个新的进程时，如何给该进程初始化 vruntime 呢？正常来说该任务还没有运行过，所以该值应该为0, 但如果这样的话该进程的 vruntime 将远远小于队列中所有的任务，它将一直霸占 CPU 运行下去直到 vruntime 追上队列中其它任务，而这显然是不合理的。因此我们需要一个方法来对这些情况进行调节，该方法就是 min_vruntime, 后续我们将介绍详细的调节方式。

总体而言，CFS的核心数据结构关系如下：

CFS rq