不管是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/
/* 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;
};
/* 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;
};
