详细解读Linux 2.6 完全公平调度算法CFS（Completely Fair Scheduler）
linux 调度器简史
早期的 linux 调度器使用了最低的设计，它显然不关注具有很多处理器的大型架构，更不用说是超线程了。1.2 linux 调度器使用了环形队列用于可运行的任务管理，使用循环调度策略。 此调度器添加和删除进程效率很高（具有保护结构的锁）。简而言之，该调度器并不复杂但是简单快捷。
linux 版本 2.2 引入了调度类的概念，允许针对实时任务、非抢占式任务、非实时任务的调度策略。 2.2 调度器还包括对称多处理 (smp) 支持。
2.4 内核包含了相对简单的调度器，按 o(n) 的时间间隔运行（在调度事件期间它会迭代每个任务）。2.4 调度器将时间分割成 epoch，每个 epoch 中，每个任务允许执行到其时间切片用完。如果某个任务没有使用其所有的时间切片，那么 剩余时间切片的一半将被添加到新时间切片使其在下个 epoch 中可以执行更长时间。 调度器只是迭代任务，应用 goodness 函数（指标）决定下面执行哪个任务。尽管这种方法比较简单，但是却比较低效、缺乏可扩展性而且不适合用在实时系统中。它还缺少利用新硬件架构（比如多核处理器）的能力。
早期的 2.6 调度器，叫做 o(1) 调度器，它旨在解决 2.4 调度器存在的问题 — 该调度器不需要迭代整个任务列表来确定要调度的下一个任务（因此得名 o(1)，这意味着它效率更高，扩展性更好）。o(1) 调度器跟踪运行队列中可运行的任务（实际上，每个优先级水平有两个运行队列 — 一个用于活动任务，一个用于过期任务）， 这意味着要确定接下来执行的任务，调度器只需按优先级将下一个任务从特定活动的运行队列中取出即可）。 o(1) 调度器扩展性更好而且包含交互性，提供了大量启示用于确定任务是受 i/o 限制还是受处理器限制。 但是 o(1) 调度器在内核中很笨拙。需要大量代码计算启示，难以管理并且对于纯粹主义者而言未能体现算法的本质。
为了解决 o(1) 调度器面临的问题以及应对其他外部压力， 需要改变某些东西。这种改变来自 con kolivas 的内核补丁，其中包括他的 rotating staircase deadline scheduler (rsdl)， 这包含了他在 staircase 调度器方面的早期工作。这些工作的成果就是一个设计简单的调度器，包含了公平性和界限内延迟。 kolivas 的调度器吸引了很多人（并且很多人呼吁将其包含在目前的 2.6.21 主流内核中），很显然调度器的变革即将发生。 ingo molnar，o(1) 调度器的创造者，然后围绕 kolivas 的一些思想开发了基于 cfs 的调度器。我们来剖析一下 cfs，从较高的层次上看看它是如何运行的。
cfs 概述
cfs 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。这意味着应给进程分配相当数量的处理器。分给某个任务的时间失去平衡时（意味着一个或多个任务相对于其他任务而言未被给予相当数量的时间），应给失去平衡的任务分配时间，让其执行。
要实现平衡，cfs 在叫做虚拟运行时的地方维持提供给某个任务的时间量。任务的虚拟运行时越小， 意味着任务被允许访问服务器的时间越短 — 其对处理器的需求越高。cfs 还包含睡眠公平概念以便确保那些目前没有运行的 任务（例如，等待 i/o）在其最终需要时获得相当份额的处理器。
但是与之前的 linux 调度器不同，它没有将任务维护在运行队列中，cfs 维护了一个以时间为顺序的红黑树（参见图 1）。红黑树是一个树，具有很多有趣、有用的属性。首先，它是自平衡的，这意味着树上没有路径比任何其他路径长两倍以上。 第二，树上的运行按 o(logn) 时间发生（其中n是树中节点的数量）。这意味着您可以快速高效地插入或删除任务。
图 1. 红黑树示例
任务存储在以时间为顺序的红黑树中（由sched_entity对象表示），对处理器需求最多的任务 （最低虚拟运行时）存储在树的左侧，处理器需求最少的任务（最高虚拟运行时）存储在树的右侧。 为了公平，调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。任务通过将其运行时间添加到虚拟运行时， 说明其占用 cpu 的时间，然后如果可运行，再插回到树中。这样，树左侧的任务就被给予时间运行了，树的内容从右侧迁移到左侧以保持公平。 因此，每个可运行的任务都会追赶其他任务以维持整个可运行任务集合的执行平衡。
------------------------------------------------------------------------------------------------------------------------------
cfs 内部原理
linux 内的所有任务都由称为task_struct的任务结构表示。该结构（以及其他相关内容）完整地描述了任务并包括了任务的当前状态、其堆栈、进程标识、优先级（静态和动态）等等。您可以在 ./linux/include/linux/sched.h 中找到这些内容以及相关结构。 但是因为不是所有任务都是可运行的，您在task_struct中不会发现任何与 cfs 相关的字段。 相反，会创建一个名为sched_entity的新结构来跟踪调度信息（参见图 2）。
图 2. 任务和红黑树的结构层次
各种结构的关系如图 2所示。树的根通过rb_root元素通过cfs_rq结构（在 ./kernel/sched.c 中）引用。红黑树的叶子不包含信息，但是内部节点代表一个或多个可运行的任务。红黑树的每个节点都由rb_node表示，它只包含子引用和父对象的颜色。rb_node包含在sched_entity结构中，该结构包含rb_node引用、负载权重以及各种统计数据。最重要的是，sched_entity包含vruntime（64 位字段），它表示任务运行的时间量，并作为红黑树的索引。 最后，task_struct位于顶端，它完整地描述任务并包含sched_entity结构。
就 cfs 部分而言，调度函数非常简单。 在 ./kernel/sched.c 中，您会看到通用schedule()函数，它会先抢占当前运行任务（除非它通过yield()代码先抢占自己）。注意 cfs 没有真正的时间切片概念用于抢占，因为抢占时间是可变的。 当前运行任务（现在被抢占的任务）通过对put_prev_task调用（通过调度类）返回到红黑树。 当schedule函数开始确定下一个要调度的任务时，它会调用pick_next_task函数。此函数也是通用的（在 ./kernel/sched.c 中），但它会通过调度器类调用 cfs 调度器。 cfs 中的pick_next_task函数可以在 ./kernel/sched_fair.c（称为pick_next_task_fair()）中找到。 此函数只是从红黑树中获取最左端的任务并返回相关sched_entity。通过此引用，一个简单的task_of()调用确定返回的task_struct引用。通用调度器最后为此任务提供处理器。
------------------------------------------------------------------------------------------------------------------------------
优先级和 cfs
cfs 不直接使用优先级而是将其用作允许任务执行的时间的衰减系数。 低优先级任务具有更高的衰减系数，而高优先级任务具有较低的衰减系数。 这意味着与高优先级任务相比，低优先级任务允许任务执行的时间消耗得更快。 这是一个绝妙的解决方案，可以避免维护按优先级调度的运行队列。
cfs 组调度
cfs 另一个有趣的地方是组调度概念（在 2.6.24 内核中引入）。组调度是另一种为调度带来公平性的方式，尤其是在处理产生很多其他任务的任务时。 假设一个产生了很多任务的服务器要并行化进入的连接（http 服务器的典型架构）。不是所有任务都会被统一公平对待， cfs 引入了组来处理这种行为。产生任务的服务器进程在整个组中（在一个层次结构中）共享它们的虚拟运行时，而单个任务维持其自己独立的虚拟运行时。这样单个任务会收到与组大致相同的调度时间。您会发现 /proc 接口用于管理进程层次结构，让您对组的形成方式有完全的控制。使用此配置，您可以跨用户、跨进程或其变体分配公平性。
调度类和域
与 cfs 一起引入的是调度类概念（可以回顾图 2）。每个任务都属于一个调度类，这决定了任务将如何调度。 调度类定义一个通用函数集（通过sched_class），函数集定义调度器的行为。例如，每个调度器提供一种方式， 添加要调度的任务、调出要运行的下一个任务、提供给调度器等等。每个调度器类都在一对一连接的列表中彼此相连，使类可以迭代（例如， 要启用给定处理器的禁用）。一般结构如图 3 所示。注意，将任务函数加入队列或脱离队列只需从特定调度结构中加入或移除任务。 函数pick_next_task选择要执行的下一个任务（取决于调度类的具体策略）。
图 3. 调度类图形视图
但是不要忘了调度类是任务结构本身的一部分（参见图 2）。这一点简化了任务的操作，无论其调度类如何。例如， 以下函数用 ./kernel/sched.c 中的新任务抢占当前运行任务（其中curr定义了当前运行任务，rq代表 cfs 红黑树而p是下一个要调度的任务）：
static inline void check_preempt( struct rq *rq, struct task_struct *p ){ rq->curr->sched_class->check_preempt_curr( rq, p );}
如果此任务正使用公平调度类，则check_preempt_curr()将解析为check_preempt_wakeup()。 您可以在 ./kernel/sched_rt.c, ./kernel/sched_fair.c 和 ./kernel/sched_idle.c 中查看这些关系。
调度类是调度发生变化的另一个有趣的地方，但是随着调度域的增加，功能也在增加。 这些域允许您出于负载平衡和隔离的目的将一个或多个处理器按层次关系分组。 一个或多个处理器能够共享调度策略（并在其之间保持负载平衡）或实现独立的调度策略从而故意隔离任务。
其他调度器
继续研究调度，您将发现正在开发中的调度器将会突破性能和扩展性的界限。con kolivas 没有被他的 linux 经验羁绊，他开发出了另一个 linux 调度器，其缩写为：bfs。该调度器据说在 numa 系统以及移动设备上具有更好的性能， 并且被引入了android操作系统的一款衍生产品中。
Eureka的集群搭建方法-保证高可用
关于MOSFET驱动电阻的选择
SCSI 技术详细资料
便携式气象站的应用可推动智慧农业的发展
MOR分子筛羰基化反应的乙酰基中间体转移和电荷分离机理
详细解读Linux 2.6 完全公平调度算法CFS（Completely Fair Scheduler）
主键不用随机字符串用什么？主键自增？
iPhone XR升级版的试产，国行售价或6499元起
IOT物联网—让城市、家庭更加安全
台积电张忠谋谈论美国芯片产业发展
昕诺飞宣布将与美国国家冰球联盟达成合作
基于H桥级联型逆变器PWM控制设计方案
智能电网未来 借助大数据重塑能源系统
安路科技发布ELF3 FPGA产品：努力改变国际FPGA格局
华为将在不久后发布全新的华为nova8系列产品
2018年广东番禺VR设备出货规模达1450多万元
大普微与迈普完成兼容性互认证
该用哪款导热材料解决充电桩散热的难题呢？
马英九：不排除开放12寸晶圆厂至大陆投资
交通运输部：进一步推进公路工程建设标准化
早期的 linux 调度器使用了最低的设计，它显然不关注具有很多处理器的大型架构，更不用说是超线程了。1.2 linux 调度器使用了环形队列用于可运行的任务管理，使用循环调度策略。 此调度器添加和删除进程效率很高（具有保护结构的锁）。简而言之，该调度器并不复杂但是简单快捷。
linux 版本 2.2 引入了调度类的概念，允许针对实时任务、非抢占式任务、非实时任务的调度策略。 2.2 调度器还包括对称多处理 (smp) 支持。
2.4 内核包含了相对简单的调度器，按 o(n) 的时间间隔运行（在调度事件期间它会迭代每个任务）。2.4 调度器将时间分割成 epoch，每个 epoch 中，每个任务允许执行到其时间切片用完。如果某个任务没有使用其所有的时间切片，那么 剩余时间切片的一半将被添加到新时间切片使其在下个 epoch 中可以执行更长时间。 调度器只是迭代任务，应用 goodness 函数（指标）决定下面执行哪个任务。尽管这种方法比较简单，但是却比较低效、缺乏可扩展性而且不适合用在实时系统中。它还缺少利用新硬件架构（比如多核处理器）的能力。
早期的 2.6 调度器，叫做 o(1) 调度器，它旨在解决 2.4 调度器存在的问题 — 该调度器不需要迭代整个任务列表来确定要调度的下一个任务（因此得名 o(1)，这意味着它效率更高，扩展性更好）。o(1) 调度器跟踪运行队列中可运行的任务（实际上，每个优先级水平有两个运行队列 — 一个用于活动任务，一个用于过期任务）， 这意味着要确定接下来执行的任务，调度器只需按优先级将下一个任务从特定活动的运行队列中取出即可）。 o(1) 调度器扩展性更好而且包含交互性，提供了大量启示用于确定任务是受 i/o 限制还是受处理器限制。 但是 o(1) 调度器在内核中很笨拙。需要大量代码计算启示，难以管理并且对于纯粹主义者而言未能体现算法的本质。
为了解决 o(1) 调度器面临的问题以及应对其他外部压力， 需要改变某些东西。这种改变来自 con kolivas 的内核补丁，其中包括他的 rotating staircase deadline scheduler (rsdl)， 这包含了他在 staircase 调度器方面的早期工作。这些工作的成果就是一个设计简单的调度器，包含了公平性和界限内延迟。 kolivas 的调度器吸引了很多人（并且很多人呼吁将其包含在目前的 2.6.21 主流内核中），很显然调度器的变革即将发生。 ingo molnar，o(1) 调度器的创造者，然后围绕 kolivas 的一些思想开发了基于 cfs 的调度器。我们来剖析一下 cfs，从较高的层次上看看它是如何运行的。
cfs 概述
cfs 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。这意味着应给进程分配相当数量的处理器。分给某个任务的时间失去平衡时（意味着一个或多个任务相对于其他任务而言未被给予相当数量的时间），应给失去平衡的任务分配时间，让其执行。
要实现平衡，cfs 在叫做虚拟运行时的地方维持提供给某个任务的时间量。任务的虚拟运行时越小， 意味着任务被允许访问服务器的时间越短 — 其对处理器的需求越高。cfs 还包含睡眠公平概念以便确保那些目前没有运行的 任务（例如，等待 i/o）在其最终需要时获得相当份额的处理器。
但是与之前的 linux 调度器不同，它没有将任务维护在运行队列中，cfs 维护了一个以时间为顺序的红黑树（参见图 1）。红黑树是一个树，具有很多有趣、有用的属性。首先，它是自平衡的，这意味着树上没有路径比任何其他路径长两倍以上。 第二，树上的运行按 o(logn) 时间发生（其中n是树中节点的数量）。这意味着您可以快速高效地插入或删除任务。
图 1. 红黑树示例
任务存储在以时间为顺序的红黑树中（由sched_entity对象表示），对处理器需求最多的任务 （最低虚拟运行时）存储在树的左侧，处理器需求最少的任务（最高虚拟运行时）存储在树的右侧。 为了公平，调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。任务通过将其运行时间添加到虚拟运行时， 说明其占用 cpu 的时间，然后如果可运行，再插回到树中。这样，树左侧的任务就被给予时间运行了，树的内容从右侧迁移到左侧以保持公平。 因此，每个可运行的任务都会追赶其他任务以维持整个可运行任务集合的执行平衡。
------------------------------------------------------------------------------------------------------------------------------
cfs 内部原理
linux 内的所有任务都由称为task_struct的任务结构表示。该结构（以及其他相关内容）完整地描述了任务并包括了任务的当前状态、其堆栈、进程标识、优先级（静态和动态）等等。您可以在 ./linux/include/linux/sched.h 中找到这些内容以及相关结构。 但是因为不是所有任务都是可运行的，您在task_struct中不会发现任何与 cfs 相关的字段。 相反，会创建一个名为sched_entity的新结构来跟踪调度信息（参见图 2）。
图 2. 任务和红黑树的结构层次
各种结构的关系如图 2所示。树的根通过rb_root元素通过cfs_rq结构（在 ./kernel/sched.c 中）引用。红黑树的叶子不包含信息，但是内部节点代表一个或多个可运行的任务。红黑树的每个节点都由rb_node表示，它只包含子引用和父对象的颜色。rb_node包含在sched_entity结构中，该结构包含rb_node引用、负载权重以及各种统计数据。最重要的是，sched_entity包含vruntime（64 位字段），它表示任务运行的时间量，并作为红黑树的索引。 最后，task_struct位于顶端，它完整地描述任务并包含sched_entity结构。
就 cfs 部分而言，调度函数非常简单。 在 ./kernel/sched.c 中，您会看到通用schedule()函数，它会先抢占当前运行任务（除非它通过yield()代码先抢占自己）。注意 cfs 没有真正的时间切片概念用于抢占，因为抢占时间是可变的。 当前运行任务（现在被抢占的任务）通过对put_prev_task调用（通过调度类）返回到红黑树。 当schedule函数开始确定下一个要调度的任务时，它会调用pick_next_task函数。此函数也是通用的（在 ./kernel/sched.c 中），但它会通过调度器类调用 cfs 调度器。 cfs 中的pick_next_task函数可以在 ./kernel/sched_fair.c（称为pick_next_task_fair()）中找到。 此函数只是从红黑树中获取最左端的任务并返回相关sched_entity。通过此引用，一个简单的task_of()调用确定返回的task_struct引用。通用调度器最后为此任务提供处理器。
------------------------------------------------------------------------------------------------------------------------------
优先级和 cfs
cfs 不直接使用优先级而是将其用作允许任务执行的时间的衰减系数。 低优先级任务具有更高的衰减系数，而高优先级任务具有较低的衰减系数。 这意味着与高优先级任务相比，低优先级任务允许任务执行的时间消耗得更快。 这是一个绝妙的解决方案，可以避免维护按优先级调度的运行队列。
cfs 组调度
cfs 另一个有趣的地方是组调度概念（在 2.6.24 内核中引入）。组调度是另一种为调度带来公平性的方式，尤其是在处理产生很多其他任务的任务时。 假设一个产生了很多任务的服务器要并行化进入的连接（http 服务器的典型架构）。不是所有任务都会被统一公平对待， cfs 引入了组来处理这种行为。产生任务的服务器进程在整个组中（在一个层次结构中）共享它们的虚拟运行时，而单个任务维持其自己独立的虚拟运行时。这样单个任务会收到与组大致相同的调度时间。您会发现 /proc 接口用于管理进程层次结构，让您对组的形成方式有完全的控制。使用此配置，您可以跨用户、跨进程或其变体分配公平性。
调度类和域
与 cfs 一起引入的是调度类概念（可以回顾图 2）。每个任务都属于一个调度类，这决定了任务将如何调度。 调度类定义一个通用函数集（通过sched_class），函数集定义调度器的行为。例如，每个调度器提供一种方式， 添加要调度的任务、调出要运行的下一个任务、提供给调度器等等。每个调度器类都在一对一连接的列表中彼此相连，使类可以迭代（例如， 要启用给定处理器的禁用）。一般结构如图 3 所示。注意，将任务函数加入队列或脱离队列只需从特定调度结构中加入或移除任务。 函数pick_next_task选择要执行的下一个任务（取决于调度类的具体策略）。
图 3. 调度类图形视图
但是不要忘了调度类是任务结构本身的一部分（参见图 2）。这一点简化了任务的操作，无论其调度类如何。例如， 以下函数用 ./kernel/sched.c 中的新任务抢占当前运行任务（其中curr定义了当前运行任务，rq代表 cfs 红黑树而p是下一个要调度的任务）：
static inline void check_preempt( struct rq *rq, struct task_struct *p ){ rq->curr->sched_class->check_preempt_curr( rq, p );}
如果此任务正使用公平调度类，则check_preempt_curr()将解析为check_preempt_wakeup()。 您可以在 ./kernel/sched_rt.c, ./kernel/sched_fair.c 和 ./kernel/sched_idle.c 中查看这些关系。
调度类是调度发生变化的另一个有趣的地方，但是随着调度域的增加，功能也在增加。 这些域允许您出于负载平衡和隔离的目的将一个或多个处理器按层次关系分组。 一个或多个处理器能够共享调度策略（并在其之间保持负载平衡）或实现独立的调度策略从而故意隔离任务。
其他调度器
继续研究调度，您将发现正在开发中的调度器将会突破性能和扩展性的界限。con kolivas 没有被他的 linux 经验羁绊，他开发出了另一个 linux 调度器，其缩写为：bfs。该调度器据说在 numa 系统以及移动设备上具有更好的性能， 并且被引入了android操作系统的一款衍生产品中。
Eureka的集群搭建方法-保证高可用
关于MOSFET驱动电阻的选择
SCSI 技术详细资料
便携式气象站的应用可推动智慧农业的发展
MOR分子筛羰基化反应的乙酰基中间体转移和电荷分离机理
详细解读Linux 2.6 完全公平调度算法CFS（Completely Fair Scheduler）
主键不用随机字符串用什么？主键自增？
iPhone XR升级版的试产，国行售价或6499元起
IOT物联网—让城市、家庭更加安全
台积电张忠谋谈论美国芯片产业发展
昕诺飞宣布将与美国国家冰球联盟达成合作
基于H桥级联型逆变器PWM控制设计方案
智能电网未来 借助大数据重塑能源系统
安路科技发布ELF3 FPGA产品：努力改变国际FPGA格局
华为将在不久后发布全新的华为nova8系列产品
2018年广东番禺VR设备出货规模达1450多万元
大普微与迈普完成兼容性互认证
该用哪款导热材料解决充电桩散热的难题呢？
马英九：不排除开放12寸晶圆厂至大陆投资
交通运输部：进一步推进公路工程建设标准化