# 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` 中，此处有详细介绍：
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的核心数据结构关系如下：
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://s3.shizhz.me/linux-sched/cfs-sched/logic-data-structure.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.