Linux内核CFS调度器：多任务处理的魔法
在当今数字化时代，操作系统如同复杂交响乐的指挥家，高效协调着计算机系统的各项资源。而多任务处理，无疑是这场交响乐中最激昂的乐章。想象一下，你的电脑在同一时刻流畅运行着办公软件、浏览器、音乐播放器等多个程序，这背后便是多任务处理的神奇魔力。
在 Linux 操作系统的内核中，有一位默默奉献的 “幕后英雄”——CFS 调度器。它宛如一位精明的管家，精心管理着 CPU 时间这一宝贵资源，将其合理分配给各个运行的进程。从诞生之初，CFS 调度器便承载着实现公平、高效多任务调度的使命，在 Linux 内核的发展历程中留下了浓墨重彩的一笔。接下来，让我们一同揭开 Linux 内核 CFS 调度器的神秘面纱，探寻它在多任务处理中创造奇迹的奥秘。
一、CFS调度器简介
1. 什么是CFS调度器在 Linux 内核的庞大体系中，CFS 调度器(Completely Fair Scheduler，完全公平调度器)占据着举足轻重的地位，是 Linux 默认的调度类 ，负责普通用户任务(SCHED_OTHER 和 SCHED_BATCH)的调度，自 Linux 2.6.23 版本引入以来，一直是 Linux 内核中的默认调度器。
CFS 调度器的核心使命是为所有运行的任务提供公平的 CPU 时间分配，它就像是一位公正无私的 “时间管家”，精心管理着系统中各个任务对 CPU 时间的使用。在多任务处理的场景下，不同的任务都在竞争 CPU 资源，而 CFS 调度器的存在，确保了每个任务都能在这场资源竞争中获得合理的时间份额，不会出现某些任务长时间霸占 CPU，而其他任务却苦苦等待的不公平现象。
2. CFS调度器诞生背景在 CFS 调度器出现之前，Linux 内核使用的调度器在多任务处理方面存在一些明显的不足。早期的调度器往往难以在不同类型的任务之间实现精准的平衡，比如在面对交互式任务和计算密集型任务时，就容易顾此失彼。对于交互式任务而言，它们对响应时间极为敏感，用户期望在进行操作后能立即得到系统反馈，像我们日常使用的图形界面应用程序，每一次鼠标点击、键盘输入都希望能即时在屏幕上呈现出结果。而计算密集型任务则更侧重于长时间占用 CPU 资源，以高效完成复杂的计算任务，例如科学计算程序、大数据分析任务等 。
在早期调度器的管理下，计算密集型任务可能会凭借其对 CPU 资源的持续需求，长时间霸占 CPU，使得交互式任务的响应时间大幅增加，用户在操作时会明显感觉到卡顿、延迟，极大地影响了使用体验。这种资源分配的不公平性，就像一场比赛中，有的选手被过度偏袒，而有的选手则被严重忽视，整个比赛失去了公平竞争的基础。
为了解决这些问题，CFS 调度器应运而生。它的出现，就像是为多任务处理的赛场引入了一位公正的裁判，致力于打破资源分配的不公平局面，为每个任务提供公平竞争 CPU 资源的机会，确保系统在各种任务混合的场景下，都能高效、稳定地运行，满足不同类型任务的需求，提升整个系统的性能和用户体验。
二、CFS调度器实现方式
1. 虚拟运行时间(vruntime)：公平的基石在 CFS 调度器的公平调度体系中，虚拟运行时间(vruntime)是最为核心的概念，它就像是一把精准的 “公平标尺”，用来衡量每个任务在 CPU 资源竞争中的 “进度”。
CFS 调度器的设计目标是模拟一个理想的多任务 CPU 环境，在这个环境中，所有任务都能以相同的速率并行运行。但在现实中，CPU 资源是有限的，多个任务必须分时复用 CPU。为了实现这种理想的公平状态，CFS 引入了 vruntime 。它并不是真实的物理时间，而是一个抽象的虚拟时间概念。当一个任务开始执行时，它的 vruntime 会随着实际执行时间的增加而增长，增长的速度与任务的权重相关。
例如，系统中有两个任务 A 和 B，任务 A 的权重较高，任务 B 的权重较低。假设任务 A 的权重是任务 B 的两倍，那么在相同的实际执行时间内，任务 B 的 vruntime 增长速度将是任务 A 的两倍。这意味着，即使任务 A 和 B 在不同的时间段内执行，但只要它们获得的 CPU 时间与各自的权重成正比，它们的 vruntime 增长就会保持一种相对的公平性。
当任务执行完毕或者被抢占时，它的 vruntime 就会保持不变，等待下一次被调度执行。在调度决策时，CFS 调度器会从所有就绪任务中，挑选出 vruntime 最小的任务来运行，因为这个任务的 vruntime 最小，说明它之前获得的 CPU 时间相对较少，受到了 “不公平” 对待，理应在下一轮调度中优先获得 CPU 资源 。通过这种方式，CFS 调度器不断地让各个任务的 vruntime 相互追赶，从而实现了 CPU 时间在不同任务之间的公平分配，确保每个任务都能在合理的时间内得到执行。
在CFS调度器中，虚拟运行时间(virtual runtime)通过每个任务的p->se.vruntime(以纳秒单位)来表示和跟踪，这样，就可以准确地标记时间戳并测量任务应该获得的预期 CPU 时间。其中，p指向一个struct task_struct结构体。
<p data-pid="qy7bviVo">在理想的 虚拟 CPU 上，在任何时刻，所有任务 虚拟运行时间值 p->se.vruntime 都保持相同的值；CFS 调度器，其任务选择逻辑基于 p->se.vruntime 值：CFS 始终尝试运行具有最小 p->se.vruntime 值的任务（即到目前为止虚拟执行时间(virtual runtime)最小的任务）。
CFS 始终尝试在可运行任务之间平均分配 虚拟 CPU时间 ，尽可能接近理想的多任务 虚拟 CPU。CFS 设计的其余部分大部分都脱离了这个非常简单的概念，有一些其它附加修饰，如任务的 nice 值，各种识别睡眠任务的算法等等。
2. 权重(Weight)：优先级的体现在 CFS 调度器中，任务的权重是决定其优先级的关键因素，而权重又与任务的 nice 值紧密相关。nice 值是 Linux 系统中用于调整进程优先级的一个参数，它的取值范围通常是 -20 到 19 ，数值越小，表示任务的优先级越高 。通过 nice 值与权重的映射关系，CFS 调度器能够为不同优先级的任务分配不同的权重。
具体来说，低 nice 值的任务具有较高的优先级，相应地，它们也会被赋予较大的权重。这就好比一场比赛中，实力更强(优先级更高)的选手会得到更多的资源支持(更大的权重)。当一个任务具有较大的权重时，在相同的实际执行时间内，它的 vruntime 增长速度会相对较慢。例如，有任务 C 和任务 D，任务 C 的 nice 值较低，权重较大，任务 D 的 nice 值较高，权重较小。在同样运行 10 毫秒的情况下，任务 D 的 vruntime 增加量会大于任务 C，这使得任务 C 在调度竞争中更具优势，能够获得更多的 CPU 执行时间。
这种通过权重调整 vruntime 增长速度的机制，不仅保证了高优先级任务能够优先获得 CPU 资源，同时也兼顾了低优先级任务的执行机会，避免了低优先级任务长时间得不到调度而 “饿死” 的情况。CFS 调度器就像一位经验丰富的资源分配者，在高优先级任务和低优先级任务之间找到了一个平衡点，让系统中的所有任务都能在这个公平的调度框架下有序运行。
3. 红黑树(Red - Black Tree)：高效的任务管理为了高效地管理就绪队列中的任务，CFS 调度器采用了红黑树这种数据结构。红黑树是一种自平衡的二叉查找树，它具有高效的插入、删除和查找操作特性，这使得 CFS 调度器能够快速地对任务进行管理和调度决策。
在 CFS 调度器中，红黑树的每个节点都对应一个任务，节点中的关键值就是任务的 vruntime 。当一个新任务进入就绪队列时，它会根据自己的 vruntime 被插入到红黑树的合适位置;当任务执行完毕或者被抢占时，它会从红黑树中删除。红黑树的自平衡特性保证了树的高度始终保持在一个较低的水平，从而确保了插入、删除和查找操作的时间复杂度始终保持在 O (log n)，这里的 n 是红黑树中节点的数量 。
由于红黑树是按照 vruntime 从小到大的顺序排列节点的，CFS 调度器可以通过简单地访问红黑树的最左节点(即 vruntime 最小的节点)，快速地找到下一个应该执行的任务。这种高效的查找方式，使得 CFS 调度器能够在众多就绪任务中迅速做出调度决策，大大提高了调度效率。与传统的线性链表结构相比，红黑树在处理大量任务时的优势更加明显，它能够显著减少查找下一个执行任务所需的时间，从而提升整个系统的多任务处理能力。
CFS 需要高效的数据结构来跟踪任务信息，需要高性能的代码来产生调度。让我们从调度中的一个中心术语开始，即运行队列(runqueue)。运行队列(runqueue)是一个数据结构，表示被调度任务的时间线。尽管有这个名字，但运行队列不需要以传统方式实现，如实现为一个 FIFO 列表。CFS 打破了传统，它不使用运行队列以往的旧数据结构，而是使用按时间排序的红黑树(red-black tree)作为可运行任务队列，来构建未来任务执行的时间线。
红黑树非常适合这项工作，因为它是一个自平衡的二叉搜索树，具有高效的插入和删除操作，在 O(log N) 时间内执行，其中 N 是树中的节点数。此外，树是一种出色的数据结构，用于根据特定属性(在 CFS 中为 vruntime)将实体组织到层次结构中。
在 CFS 中，树的内部节点表示要调度的任务，而树作为一个整体(与任何运行队列一样)表示任务执行的时间线。红黑树被广泛使用，还用于任务调度之外，例如，Java 使用此数据结构来实现其树状图。
在 CFS 下，每个处理器都有一个自己特定的任务运行队列，同一任务某一时刻只会位于某个运行队列中。每个运行队列都是一棵红黑树。树的内部节点表示任务或任务组，这些节点按其 vruntime 值索引，因此(在整个树或任何子树中)左侧内部节点的 vruntime 值低于右侧节点：
总之，具有最低 vruntime 的任务(因此对处理器的需求最大)位于左侧子树的某个位置;具有相对较高的 vruntimes 的任务聚集在右侧子树中。抢占的任务将进入右侧子树，从而使其他任务有机会在树中向左移动。具有最小 vruntime 的任务最终出现在树的最左侧(内部)节点中，因此该节点位于运行队列的前面。
红黑树的每个内部节点都有指向父节点和两个子节点的指针，叶节点的值为NULL：
CFS 调度器用 task_struct 来描述一个任务，task_struct 用于跟踪有关要调度的每个任务的详细信息。此结构嵌入了一个 sched_entity 结构，该结构又具有特定于调度的信息，特别是每个任务或任务组的 vruntime，即 rq->cfs.min_vruntime 值，该值是一个单调递增值，用于跟踪运行队列中所有任务中的最小 vruntime。该值用于尽可能将新激活的调度实体(struct sched_entity，即任务)放置在红黑树的左侧。由于该值一直使用 min_vruntime 单调递增累加，所以也可用来跟踪系统完成的工作总量。
运行队列的权重通过rq->cfs.load值进行统计，该值是运行队列上排队的任务权重的总和：
CFS 维护一个按时间排序的 红黑树(rbtree)，即所有可运行的任务都按 p->se.vruntime 键排序，然后CFS 从这棵树中挑选最左边(即 p->se.vruntime 最小)的任务执行。随着时间往后推移，执行的任务越来越多地被放入树中，执行时间更少的任务逐渐往红黑树左边移动，执行时间更多的任务往红黑树右边移动，如此循环往复。
创建新任务时，将它们插入红黑树，初始 vruntime 值赋为 min_vruntime，使得它们尽可能快的得到执行：vruntime 越小，越快得到执行。
使用红黑树还有一个优点，那就是如果一个进程是 I/O 密集型的，那么它的虚拟时间将非常少，并且它显示为红黑树中最左边的节点，因此首先执行。因此，CFS 很容易找出哪些是 I/O 密集型的进程，哪些是 CPU 密集型的进程，并且它让 I/O 密集型的进程具有更高的优先级，从而避免了饥饿。
4. 负载均衡(Load Balancing)：资源的合理分配在多核处理器系统中，为了充分发挥多核的性能优势，CFS 调度器需要进行负载均衡操作，确保任务能够在各个 CPU 核心之间均匀分布，避免出现某些 CPU 核心负载过重，而其他 CPU 核心闲置的情况。CFS 调度器通过调度域(scheduling domains)和调度组(sched_groups)来实现负载均衡。
调度域是一种层次结构，它将相关的 CPU 核心组合在一起，形成一个调度范围。调度域可以嵌套，形成多层的树状结构，最顶层的是根域(Root Domain)，代表整个系统的所有任务;最底层的是叶域(Leaf Domains)，直接包含具体的任务。调度组则是调度域的一部分，它将 CPU 核心进一步分组，以便在组内进行更精细的任务调度。例如，在一个具有多个 CPU 核心的服务器系统中，可能会根据 CPU 的物理位置、性能特点等因素，将不同的 CPU 核心划分到不同的调度组中。
CFS 调度器会周期性地执行负载均衡操作，监控各个调度组和 CPU 核心的负载情况。当发现某个调度组或 CPU 核心的负载过高时，调度器会将部分任务从高负载的调度组或 CPU 核心迁移到低负载的调度组或 CPU 核心上，实现负载的均衡分布。在进行任务迁移时，CFS 调度器还会考虑任务的 CPU 亲和性(CPU Affinity)，尽量将任务分配到它们偏好的 CPU 核心上，同时仍然保持整体的负载均衡。
这就好比在一个工厂中，管理人员会根据各个生产线的工作量，合理地调配工人(任务)，让每个生产线(CPU 核心)都能高效地运转，同时又考虑到每个工人(任务)对不同生产线(CPU 核心)的熟悉程度(CPU 亲和性)，从而提高整个工厂(系统)的生产效率 。通过这种负载均衡机制，CFS 调度器能够充分利用多核处理器的资源，提高系统的整体性能和响应速度，让多任务处理在多核环境下更加高效、稳定地运行。
三、CFS调度器的调度策略
CFS 调度器针对不同类型的任务，提供了多种调度策略，以满足多样化的系统需求。这些调度策略就像是为不同类型的 “选手” 量身定制的比赛规则，确保每个任务都能在最合适的规则下参与 CPU 资源的竞争。
1. SCHED_NORMAL(SCHED_OTHER)SCHED_NORMAL，也被称为 SCHED_OTHER ，是 CFS 调度器中最为常用的调度策略，适用于大多数普通的用户级交互式任务 。像我们日常使用的图形界面应用程序、办公软件、浏览器等，这些需要与用户频繁交互的任务，都采用了这种调度策略。
在 SCHED_NORMAL 策略下，任务的执行优先级主要由其 nice 值决定。nice 值的取值范围是 -20 到 19 ，数值越小，任务的优先级越高。系统会根据任务的 nice 值，为其分配相应的 CPU 时间份额。例如，当我们在电脑上同时打开浏览器浏览网页，又运行一个文本编辑软件进行文字处理时，由于这两个任务都属于交互式任务，它们的 nice 值默认可能都是 0 。在这种情况下，CFS 调度器会按照公平的原则，为它们分配大致相等的 CPU 时间，使得我们在操作浏览器切换页面时，不会感觉到文本编辑软件的响应受到明显影响，反之亦然，从而保证了用户在使用这些交互式应用时，能够获得流畅、及时的体验 。
2. SCHED_BATCHSCHED_BATCH 调度策略主要适用于那些非交互式的批处理任务 ，这类任务通常不需要与用户进行实时交互，它们更注重任务的整体运行效率，而不是对用户输入的即时响应。比如一些长时间运行的计算任务，如大数据分析、科学计算程序等。这些任务往往需要大量的 CPU 计算资源，如果它们与交互式任务采用相同的调度策略，可能会因为频繁的上下文切换，导致 CPU 缓存命中率降低，从而影响整体的计算效率。
在 SCHED_BATCH 策略下，任务会被调度器安排在系统资源相对空闲的时候执行，并且尽量减少任务的上下文切换次数。这就好比工厂里的大型生产设备，在原材料准备充足、其他辅助工作都安排妥当后，集中一段时间进行高效生产，避免频繁地启动和停止设备，以提高生产效率。由于批处理任务不需要像交互式任务那样对用户操作做出即时响应，它们可以在后台默默地运行，充分利用 CPU 的空闲时间，同时又不会对前台的交互式任务造成干扰，确保系统在处理批处理任务的，用户仍然能够正常、流畅地使用其他交互式应用。
3. SCHED_IDLESCHED_IDLE 是 CFS 调度器中优先级最低的调度策略，它仅在系统处于空闲状态时才会运行 。这类任务通常是一些对系统性能影响极小，且不需要及时执行的后台服务，比如系统的一些定期清理任务、日志统计任务等。这些任务的特点是即使延迟执行，也不会对系统的正常运行和用户体验产生明显的影响。
SCHED_IDLE 任务的权重非常低，这使得它们在与其他任务竞争 CPU 资源时，几乎没有优势。当系统中存在其他优先级较高的任务时，SCHED_IDLE 任务会被调度器 “冷落”，几乎得不到 CPU 的执行时间。只有当系统中所有其他任务都处于等待状态，CPU 资源完全空闲时，SCHED_IDLE 任务才会有机会被调度执行 。例如，当我们的电脑在一段时间内没有任何用户操作，系统处于空闲状态时，那些采用 SCHED_IDLE 调度策略的后台清理任务就会开始运行，对系统中的临时文件、缓存数据等进行清理，为系统的下一次高效运行做好准备，而在系统忙碌时，这些任务则会自动 “让路”，避免占用宝贵的 CPU 资源，确保其他重要任务的顺利执行。
四、CFS调度器常见问题
问题一：请简述对进程调度器的理解，早起Linux内核调度器(包括O(N)和O(1))调度器是如何工作的?调度器是按一定的方式对进程进行调度的一种机制，需要为各个普通进程尽可能公平地共享CPU时间。
O(N)调度器发布与1992年，从就绪队列中比较所有进程的优先级，然后选择一个最高优先级的进程作为下一个调度进程。每一个进程有一个固定时间片，当进程时间片使用完之后，调度器会选择下一个调度进程，当所有进程都运行一遍后再重新分配时间片。这个调度器选择下一个调度进程前需要遍历整个就绪队列，花费O(N)时间。
O(1)调度器用于Linux2.6.23内核之前，它为每个CPU维护一组进程优先级队列，每个优先级一个队列，这样在选择下一个进程时，只要查询优先级队列相应的位图即可知道哪个队列中有就绪进程，查询时间常数为O(1)。
问题二：请简述进程优先级、nice和权重之间的关系。内核使用0~139的数值表示进程的优先级，数值越低优先级越高。优先级0~99给实时进程使用，100~139给普通进程使用。在用户空间由一个传统的变量nice值映射到普通进程的优先级(100~139)。
nice值从-20~19，进程默认的nice值为0。这可以理解为40个等级，nice值越高，则优先级越低，反之亦然。(nice每变化1，则相应的进程获得CPU的时间就改变10%)。
权重信息即为调度实体的权重，为了计算方便，内核约定nice值为0的权重值为1024，其他的nice值对应相应的权重值可以通过查表的方式来获取，表即为prio_to_weight。
问题三：请简述CFS调度器是如何工作的。CFS调度器抛弃以前固定时间片和固定调度周期的算法，采用进程权重值的比重来量化和计算实际运行时间。引入虚拟时钟的概念，每个进程的虚拟时间是实际运行时间相对nice值为0的权重的比例值。进程按照各自不同的速率比在物理时钟节拍内前进。nice值小的进程，优先级高且权重大，其虚拟时钟比真实时钟跑得慢，但是可以获得比较多的运行时间;
反之，nice值大的进程，优先级低，权重也低，其虚拟时钟比真实时钟跑得快，获得比较少的运行时间。CFS调度器总是选择虚拟时钟跑得慢的进程，类似一个多级变速箱，nice值为0的进程是基准齿轮，其他各个进程在不同变速比下相互追赶，从而达到公正公平。
问题四：CFS调度器中的vruntime是如何计算的?vruntime=(delta_exec*nice_0_weight)/weight。其中，delta_exec为实际运行时间，nice_0_weight为nice为0的权重值，weight表示该进程的权重值。在update_curr()函数中，完成了该值的计算，此时，为了计算高效，将计算方式变成了乘法和移位vruntime=(delta_exec*nice_0_weight*inv_weight)>>shift，其中inv_weight=2^32/weight，是预先计算好存放在prio_to_wmult中的。
问题五：vruntime是何时更新的?创建新进程，加入就绪队列，调度tick等都会更新当前vruntime值。
问题六：CFS调度器中的min_vruntime有什么作用?min_vruntime在CFS就绪队列数据结构中，单步递增，用于跟踪该就绪队列红黑树中最小的vruntime。
问题七：CFS调度器对新创建的进程和刚唤醒的进程有何关照?对于睡眠进程，其vruntime在睡眠期间不增长，在唤醒后如果还用原来的vruntime值，会进行报复性满载运行，所以要修正vruntime，具体在enqueue_entity()函数中，计算公式为vruntime+=min_vruntime，vruntime=MAX(vruntime, min_vruntime-sysctl_sched_lantency/2)。
对于新创建的进程，需要加上一个调度周期的虚拟是时间(sched_vslice())。首先在task_fork_fair()函数中，place_entity()增加了调度周期的虚拟时间，相当于惩罚，se->vruntime=sched_vslice()。
接着新进程在添加到就绪队列时，wake_up_new_task()->activate_task()->enqueue_entity()函数里，se->vruntime+=cfs_rq->min_vruntime。
问题八：如何计算普通进程的平均负载load_avg_contrib?runnable_avg_sum和runnable_avg_period分别表示了什么含义?load_avg_contrib=runnable_avg_sum*weight/runnable_avg_period。runnable_avg_sum为调度实体的可运行状态下总衰减累加时间。runnable_avg_period记录的是上一次更新时的总周期数(一个周期是1024us)，即调度实体在调度器中的总衰减累加时间。runnable_avg_sum越接近runnable_avg_period，则平均负载越大，表示该调度实体一直在占用CPU。问题九：内核代码中定义了若干个表，请分别说出它们的含义，比如prio_to_weight、prio_to_wmult、runnable_avg_yN_inv、runnable_avg_yN_sum。prio_to_weight表记录的是nice值对应的权重值。prio_to_wmult表记录的是nice值对应的权重值倒转后的值inv_weight=2^32/weight。runnable_avg_yN_inv表是为了避免CPU做浮点计算，提前计算了公式2^32*实际衰减因子(第32ms约为0.5)的值，有32个下标，对应过去0~32ms的负载贡献的衰减因子。runnable_avg_yN_sum表为1024*(y+y^2+…+y^n)，y为实际衰减因子，n取1~32。问题十：如果一个普通进程在就绪队列里等待了很长时间才被调度，那么它的平均负载该如何计算?一个进程等待很长时间之后(过了很多个period)，原来的runnable_avg_sum和runable_ave_period值衰减后可能变成0，相当于之前的统计值被清0。
