# 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](https://640510796-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Me-3_JXLYv-4hrEXyDb%2Fuploads%2FWVFIlgGJNYzFyRrcLNAq%2Fcfs_rq.png?alt=media\&token=8f477c34-770d-4217-832d-065dc342a377)