关于cpu:带你探索CPU调度的奥秘

摘要：本文将会从最根底的调度算法说起，一一剖析各种支流调度算法的原理，带大家一起摸索 CPU 调度的神秘。

本文分享自华为云社区《摸索 CPU 的调度原理》，作者：元闰子。

前言

软件工程师们总习惯把 OS（Operating System，操作系统）当成是一个十分值得信赖的管家，咱们只管把程序托管到 OS 上运行，却很少深刻理解操作系统的运行原理。的确，OS 作为一个通用的软件系统，在大多数的场景下都体现得足够的优良。但仍会有一些非凡的场景，须要咱们对 OS 进行各项调优，能力让业务零碎更高效地实现工作。这就要求咱们必须深刻理解 OS 的原理，不仅仅只会使唤这个管家，还能懂得如何让管家做得更好。

OS 是一个十分宏大的软件系统，本文次要摸索其中的冰山一角：CPU 的调度原理。

说起 CPU 的调度原理，很多人的第一反馈是基于工夫片的调度，也即每个过程都有占用 CPU 运行的工夫片，工夫片用完之后，就让出 CPU 给其余过程。至于 OS 是如何判断一个工夫片是否用完的、如何切换到另一个过程等等更深层的原理，理解的人仿佛并不多。

其实，基于工夫片的调度只是泛滥 CPU 的调度算法的一类，本文将会从最根底的调度算法说起，一一剖析各种支流调度算法的原理，带大家一起摸索 CPU 调度的神秘。

CPU 的上下文切换

在摸索 CPU 调度原理之前，咱们先理解一下 CPU 的上下文切换，它是 CPU 调度的根底。

现在的 OS 简直都反对 ” 同时 ” 运行远大于 CPU 数量的工作，OS 会将 CPU 轮流调配给它们应用。这就要求 OS 必须晓得从哪里加载工作，以及加载后从哪里开始运行，而这些信息都保留在 CPU 的 寄存器 中，其中行将执行的下一条指令的地址被保留在 程序计数器 （PC）这一非凡寄存器上。 咱们将寄存器的这些信息称为 CPU 的上下文，也叫硬件上下文。

OS 在切换运行工作时，将上一工作的上下文保留下来，并将行将运行的工作的上下文加载到 CPU 寄存器上的这一动作，被称为 CPU 上下文切换。

CPU 上下文属于过程上下文的一部分，咱们常说的过程上下文由如下两局部组成：

• 用户级上下文：蕴含过程的运行时堆栈、数据块、代码块等信息。
• 零碎级上下文：蕴含过程标识信息、过程现场信息（CPU 上下文）、过程管制信息等信息。

这波及到两个问题：（1）上一工作的 CPU 上下文如何保留下来？（2）什么时候执行上下文切换？

问题 1: 上一工作的 CPU 上下文如何保留下来？

CPU 上下文会被保留在过程的 内核空间（kernel space）上。OS 在给每个过程调配虚拟内存空间时，会调配一个内核空间，这部分内存只能由内核代码拜访。OS 在切换 CPU 上下文前，会先将以后 CPU 的通用寄存器、PC 等过程现场信息保留在过程的内核空间上，待下次切换时，再取出从新装载到 CPU 上，以复原工作的运行。

问题 2: 什么时候执行上下文切换？

OS 要想进行工作上下文切换，必须占用 CPU 来执行切换逻辑。然而，用户程序运行的过程中，CPU 曾经被用户程序所占用，也即 OS 在此刻并未处于运行状态，天然也无奈执行上下文切换。针对该问题，有两种解决策略，合作式策略与抢占式策略。

合作式策略 依赖用户程序被动让出 CPU，比方执行零碎调用（System Call）或者呈现除零等异样。但该策略并不靠谱，如果用户程序没有被动让出 CPU，甚至是歹意死循环，那么该程序将会始终占用 CPU，惟一的复原伎俩就是重启零碎了。

抢占式策略 则依赖硬件的定时中断机制（Timer Interrupt），OS 会在初始化时向硬件注册中断解决回调（Interrupt Handler）。当硬件产生中断时，硬件会将 CPU 的处理权交给来 OS，OS 就能够在中断回调上实现 CPU 上下文的切换。

调度的掂量指标

对于一种 CPU 调度算法的好坏，个别都通过如下两个指标来进行掂量：

• 周转工夫（turnaround time），指从工作达到至工作实现之间的工夫，即 T_{turnaround}=T_{completiong}-T_{arrival}Tturnaround​=Tcompletiong​−Tarrival​
• 响应工夫（response time），指从工作达到至工作首次被调度的工夫，即 T_{response}=T_{firstrun}-T_{arrival}Tresponse​=Tfirstrun​−Tarrival​

两个指标从某种程度上是对抗的，要求高的均匀周转工夫，必然会升高均匀响应工夫。具体谋求哪种指标与工作类型无关，比方程序编译类的工作，要求周转工夫要小，尽可能快的实现编译；用户交互类的工作，则要求响应工夫要小，防止影响用户体验。

工作负载假如

OS 上的工作负载（也即各类工作运行的情况）总是变幻无穷的，为了更好的了解各类 CPU 调度算法原理，咱们先对工作负载进行来如下几种假如：

• 假如 1：所有工作都运行时长都雷同。
• 假如 2：所有工作的开始工夫都是雷同的
• 假如 3：一旦工作开始，就会始终运行，直至工作实现。
• 假如 4：所有工作只应用 CPU 资源（比方不产生 I / O 操作）。
• 假如 5：事后晓得所有工作的运行时长。

筹备工作曾经做好，上面咱们开始进入 CPU 调度算法的微妙世界。

FIFO：先进先出

FIFO（First In First Out，先进先出）调度算法以原理简略，容易实现著称，它先调度首先达到的工作直至完结，而后再调度下一个工作，以此类推。如果有多个工作同时达到，则随机选一个。

在咱们假如的工作负载情况下，FIFO 效率良好。比方有 A、B、C 三个工作满足上述所有负载假如，每个工作运行时长为 10s，在 t = 0 时刻达到，那么任务调度状况是这样的：

依据 FIFO 的调度原理，A、B、C 别离在 10、20、30 时刻实现工作，均匀周转工夫为 20s（\frac {10+20+30}{3}310+20+30​），成果很好。

然而事实总是残暴的，如果假如 1 被突破，比方 A 的运行工夫变成 100s，B 和 C 的还是 10s，那么调度状况是这样的：

依据 FIFO 的调度原理，因为 A 的运行工夫过长，B 和 C 长时间得不到调度，导致均匀周转工夫好转为 110（\frac {100+110+120}{3}3100+110+120​）。

因而，FIFO 调度策略在工作运行工夫差别较大的场景下，容易呈现工作饿死的问题！

针对这个问题，如果运行工夫较短的 B 和 C 先被调度，问题就能够解决了，这正是 SJF 调度算法的思维。

SJF：最短工作优先

SJF（Shortest Job First，最短工作优先）从雷同达到工夫的多个工作中选取运行时长最短的一个工作进行调度，接着再调度第二短的工作，以此类推。

针对上一节的工作负载，应用 SJF 进行调度的状况如下，周转工夫变成了 50s（\frac {10+20+120}{3}310+20+120​），相比 FIFO 的 110s，有了 2 倍多的晋升。

让咱们持续突破假如 2，A 在 t = 0 时刻，B 和 C 则在 t =10 时刻达到，那么调度状况会变成这样：

因为工作 B 和 C 比 A 后到，它们不得不始终期待 A 运行完结后才有机会调度，即便 A 须要长时间运行。周转工夫好转为 103.33s（\frac {100+(110-10)+(120-10)}{3}3100+(110−10)+(120−10)​），再次出现工作饿死的问题！

STCF：最短时间实现优先

为了解决 SJF 的工作饿死问题，咱们须要突破假如 3，也即工作在运行过程中是容许被打断的。如果 B 和 C 在达到时就立刻被调度，问题就解决了。这属于抢占式调度，原理就是 CPU 上下文切换一节提到的，在中断定时器达到之后，OS 实现工作 A 和 B 的上下文切换。

咱们在合作式调度的 SJF 算法的根底上，加上抢占式调度算法，就演变成了 STCF 算法（Shortest Time-to-Completion First，最短时间实现优先），调度原理是当运行时长较短的工作达到时，中断以后的工作，优先调度运行时长较短的工作。

应用 STCF 算法对该工作负载进行调度的状况如下，周转工夫优化为 50s（\frac {120+(20-10)+(30-10)}{3}3120+(20−10)+(30−10)​），再次解决了工作饿死问题！

到目前为止，咱们只关怀了周转工夫这一掂量指标，那么 FIFO、SJF 和 STCF 调度算法的响应工夫又是多长呢？

无妨假如 A、B、C 三个工作都在 t = 0 时刻达到，运行时长都是 5s，那么这三个算法的调度状况如下，均匀响应时长为 5s（\frac {0+(5-0)+(10-0)}{3}30+(5−0)+(10−0)​）：

更蹩脚的是，随着工作运行时长的增长，均匀响应时长也随之增长，这对于交互类工作来说将会是灾难性的，重大影响用户体验。该问题的本源在于，当工作都同时达到且运行时长相同时，最初一个工作必须期待其余工作全副实现之后才开始调度。

为了优化响应工夫，咱们相熟的基于工夫片的调度呈现了。

RR：基于工夫片的轮询调度

RR（Round Robin，轮训）算法给每个任务分配一个工夫片，当工作的工夫片用完之后，调度器会中断当前任务，切换到下一个工作，以此类推。

须要留神的是，工夫片的长度设置必须是中断定时器的整数倍，比方中断定时器时长为 2ms，那么工作的工夫片能够设置为 2ms、4ms、6ms … 否则即便工作的工夫片用完之后，定时中断没产生，OS 也无奈切换工作。

当初，应用 RR 进行调度，给 A、B、C 调配一个 1s 的工夫片，那么调度状况如下，均匀响应时长为 1s（\frac {0+(1-0)+(2-0)}{3}30+(1−0)+(2−0)​）：

从 RR 的调度原理能够发现，把工夫片设置得越小，均匀响应工夫也越小。但随着工夫片的变小，工作切换的次数也随之回升，也就是上下文切换的耗费会变大。因而，工夫片大小的设置是一个 trade-off 的过程，不能一味谋求响应工夫而疏忽 CPU 上下文切换带来的耗费。

CPU 上下文切换的耗费，不只是保留和复原寄存器所带来的耗费。程序在运行过程中，会逐步在 CPU 各级缓存、TLB、分支预测器等硬件上建设属于本人的缓存数据。当工作被切换后，就意味着又得重来一遍缓存预热，这会带来微小的耗费。

另外，RR 调度算法的周转工夫为 14s（\frac {(13-0)+(14-0)+(15-0)}{3}3(13−0)+(14−0)+(15−0)​），相比于 FIFO、SJF 和 STCF 的 10s（\frac {(5-0)+(10-0)+(15-0)}{3}3(5−0)+(10−0)+(15−0)​）差了不少。这也验证了之前所说的，周转工夫和响应工夫在某种程度上是对抗的，如果想要优化周转工夫，倡议应用 SJF 和 STCF；如果想要优化响应工夫，则倡议应用 RR。

I/ O 操作对调度的影响

到目前为止，咱们并未思考任何的 I / O 操作。咱们晓得，当触发 I / O 操作时，过程并不会占用 CPU，而是阻塞期待 I / O 操作的实现。当初让咱们突破假如 4，思考工作 A 和 B 都在 t = 0 时刻达到，运行时长都是 50ms，但 A 每隔 10ms 执行一次阻塞 10ms 的 I / O 操作，而 B 没有 I /O。

如果应用 STCF 进行调度，调度的状况是这样的：

从上图看出，工作 A 和 B 的调度总时长达到了 140ms，比理论 A 和 B 运行时长总和 100ms 要大。而且 A 阻塞在 I / O 操作期间，调度器并没有切换到 B，导致了 CPU 的空转！

要解决该问题，只需应用 RR 的调度算法，给工作 A 和 B 调配 10ms 的工夫片，这样当 A 阻塞在 I / O 操作时，就能够调度 B，而 B 用完工夫片后，恰好 A 也从 I / O 阻塞中返回，以此类推，调度总时长优化至 100ms。

该调度计划是建设在假如 5 之上的，也即要求调度器事后晓得 A 和 B 的运行时长、I/ O 操作工夫长等信息，能力如此充沛地利用 CPU。然而，理论的状况远比这简单，I/ O 阻塞时长不会每次都一样，调度器也无奈精确晓得 A 和 B 的运行信息。当假如 5 也被突破时，调度器又该如何实现能力最大水平保障 CPU 利用率，以及调度的合理性呢？

接下来，咱们将介绍一个可能在所有工作负载假如被突破的状况下仍然体现良好，被许多古代操作系统采纳的 CPU 调度算法，MLFQ。

MLFQ：多级反馈队列

MLFQ（Multi-Level Feedback Queue，多级反馈队列）调度算法的指标如下：

1. 优化周转工夫。
2. 升高交互类工作的响应工夫，晋升用户体验。

从后面剖析咱们晓得，要优化周转工夫，能够优先调度运行时长短的工作（像 SJF 和 STCF 的做法）；要优化响应工夫，则采纳相似 RR 的基于工夫片的调度。然而，这两个指标看起来是矛盾的，要升高响应工夫，必然会减少周转工夫。

那么对 MLFQ 来说，就须要解决如下两个问题：

1. 在不事后分明工作的运行信息（包含运行时长、I/ O 操作等）的前提下，如何衡量周转工夫和响应工夫？
2. 如何从历史调度中学习，以便将来做出更好的决策？

划分工作的优先级

MLFQ 与前文介绍的几种调度算法最显著的特点就是新增了优先级队列寄存不同优先级的工作，并定下了如下两个规定：

• 规定 1：如果 Priority(A) > Priority(B)，则调度 A
• 规定 2：如果 Priority(A) = Priority(B)，则依照 RR 算法调度 A 和 B
  优先级的变动
  MLFQ 必须思考扭转工作的优先级，否则依据 规定 1 和 规定 2，对于上图中的工作 C，在 A 和 B 运行完结之前，C 都不会取得运行的机会，导致 C 的响应工夫很长。因而，能够定下了如下几个优先级变动规定：
• 规定 3：当一个新的工作达到时，将它放到最高优先级队列中
• 规定 4a：如果工作 A 运行了一个工夫片都没有被动让出 CPU（比方 I / O 操作），则优先级升高一级
• 规定 4b：如果工作 A 在工夫片用完之前，有被动让出 CPU，则优先级放弃不变

规定 3 次要思考到让新退出的工作都能失去调度机会，避免出现工作饿死的问题

规定 4a 和 4b 次要思考到，交互类工作大都是 short-running 的，并且会频繁让出 CPU，因而为了保障响应工夫，须要放弃现有的优先级；而 CPU 密集型工作，往往不会太关注响应工夫，因而能够升高优先级。

依照上述规定，当一个 long-running 工作 A 达到时，调度状况是这样的：

如果在工作 A 运行到 t =100 时，short-time 工作 B 达到，调度状况是这样的：

从上述调度状况能够看出，MLFQ 具备了 STCF 的长处，即能够优先实现 short-running 工作的调度，缩短了周转工夫。

如果工作 A 运行到 t =100 时，交互类工作 C 达到，那么调度状况是这样的：

MLFQ 会在工作处于阻塞时依照优先级抉择其余工作运行，防止 CPU 空转。因而，在上图中，当工作 C 处于 I / O 阻塞状态时，工作 A 失去了运行工夫片，当工作 C 从 I / O 阻塞上返回时，A 再次挂起，以此类推。另外，因为工作 C 在工夫片之内呈现被动让出 CPU 的行为，C 的优先级始终放弃不变，这对于交互类工作而言，无效晋升了用户体验。

CPU 密集型工作饿死问题

到目前为止，MLFQ 仿佛可能同时兼顾周转工夫，以及交互类工作的响应工夫，它真的完满了吗？

思考如下场景，工作 A 运行到 t =100 时，交互类工作 C 和 D 同时达到，那么调度状况会是这样的：

由此可见，如果以后零碎上存在很多交互类工作时，CPU 密集型工作将会存在饿死的可能！

为了解决该问题，能够设立了如下规定：

• 规定 5：零碎运行 S 时长之后，将所有工作放到最高优先级队列上 （Priority Boost）
  加上该规定之后，假如设置 S 为 50ms，那么调度状况是这样的，饿死问题失去解决！
  

歹意工作问题

思考如下一个歹意工作 E，为了长时间占用 CPU，工作 E 在工夫片还剩 1% 时成心执行 I / O 操作，并很快返回。依据规定 4b，E 将会维持在原来的最高优先级队列上，因而下次调度时

为了解决该问题，咱们须要将规定 4 调整为如下规定：

• 规定 4：给每个优先级调配一个工夫片，当工作用完该优先级的工夫片后，优先级降一级
  利用新的规定 4 后，雷同的工作负载，调度状况变成了如下所述，不再呈现歹意工作 E 占用大量 CPU 的问题。
  

到目前为止，MLFQ 的基本原理曾经介绍完，最初，咱们总结下 MLFQ 最要害的 5 项规定：

• 规定 1：如果 Priority(A) > Priority(B)，则调度 A
• 规定 2：如果 Priority(A) = Priority(B)，则依照 RR 算法调度 A 和 B
• 规定 3：当一个新的工作达到时，将它放到最高优先级队列中
• 规定 4：给每个优先级调配一个工夫片，当工作用完该优先级的工夫片后，优先级降一级
• 规定 5：零碎运行 S 时长之后，将所有工作放到最高优先级队列上（Priority Boost）

当初，再回到本节开始时提出的两个问题：

1、在不事后分明工作的运行信息（包含运行时长、I/ O 操作等）的前提下，MLFQ 如何衡量周转工夫和响应工夫？

在事后不分明工作到底是 long-running 或 short-running 的状况下，MLFQ 会先假如工作属于 shrot-running 工作，如果假如正确，工作就会很快实现，周转工夫和响应工夫都失去优化；即便假如谬误，工作的优先级也能逐步升高，把更多的调度机会让给其余 short-running 工作。

2、MLFQ 如何从历史调度中学习，以便将来做出更好的决策？

MLFQ 次要依据工作是否有被动让出 CPU 的行为来判断其是否是交互类工作，如果是，则维持在以后的优先级，保障该工作的调度优先权，晋升交互类工作的响应性。

当然，MLFQ 并非完满的调度算法，它也存在着各种问题，其中最让人困扰的就是 MLFQ 各项参数的设定，比方优先级队列的数量，工夫片的长度、Priority Boost 的距离等。这些参数并没有完满的参考值，只能依据不同的工作负载来进行设置。

比方，咱们能够将低优先级队列上工作的工夫片设置长一些，因为低优先级的工作往往是 CPU 密集型工作，它们不太关怀响应工夫，较长的工夫片长可能缩小上下文切换带来的耗费。

CFS：Linux 的齐全偏心调度

本节咱们将介绍一个平时打交道最多的调度算法，Linux 零碎下的 CFS（Completely Fair Scheduler，齐全偏心调度）。与上一节介绍的 MLFQ 不同，CFS 并非以优化周转工夫和响应工夫为指标，而是心愿将 CPU 偏心地均分给每个工作。

当然，CFS 也提供了给过程设置优先级的性能，让用户 / 管理员决定哪些过程须要取得更多的调度工夫。

基本原理

大部分调度算法都是基于固定工夫片来进行调度，而 CFS 另辟蹊径，采纳基于计数的调度办法，该技术被称为virtual runtime。

CFS 给每个工作都保护一个 vruntime 值，每当工作被调度之后，就累加它的 vruntime。比方，当工作 A 运行了 5ms 的工夫片之后，则更新为 vruntime += 5ms。CFS 在下次调度时，抉择 vruntime 值最小的工作来调度，比方：

那 CFS 应该什么时候进行工作切换呢？切换得频繁些，工作的调度会更加的偏心，然而上下文切换带来的耗费也越大。因而，CFS 给用户提供了个可配参数 sched_latency，让用户来决定切换的机会。CFS 将每个工作分到的工夫片设置为 time_slice = sched_latency / n（n 为以后的工作数），以确保在 sched_latency 周期内，各工作可能均分 CPU，保障公平性。

比方将 sched_latency 设置为 48ms，以后有 4 个工作 A、B、C 和 D，那么每个工作分到的工夫片为 12ms；前面 C 和 D 完结之后，A 和 B 分到的工夫片也更新为 24ms：

从上述原理上看，在 sched_latency 不变的状况下，随着零碎工作数的减少，每个工作分到的工夫片也随之缩小，工作切换所带来的耗费也会增大。为了防止过多的工作切换耗费，CFS 提供了可配参数 min_granularity 来设置工作的最小工夫片。比方 sched_latency 设置为 48ms，min_granularity 设置为 6ms，那么即便当前任务数有 12，每个工作数分到的工夫片也是 6ms，而不是 4ms。

给任务分配权重

有时候，咱们心愿给零碎中某个重要的业务过程多调配些工夫片，而其余不重要的过程则少调配些工夫片。但依照上一节介绍的基本原理，应用 CFS 调度时，每个工作都是均分 CPU 的，有没有方法能够做到这一点呢？

能够给任务分配权重，让权重高的工作更多的 CPU！

加上权重机制后，工作工夫片的计算形式变成了这样：

比方，sched_latency 还是设置为 48ms，现有 A 和 B 两个工作，A 的权重设置为 1024，B 的权重设置为 3072，依照上述的公式，A 的工夫片是 12ms，B 的工夫片是 36ms。

从上一节可知，CFS 每次选取 vruntime 值最小的工作来调度，而每次调度实现后，vruntime 的计算规定为 vruntime += runtime，因而仅仅扭转工夫片的计算规定不会失效，还需将 vruntime 的计算规定调整为：

还是后面的例子，假如 A 和 B 都没有 I / O 操作，更新 vruntime 计算规定后，调度状况如下，工作 B 比工作 A 可能分得更多的 CPU 了。

应用红黑树晋升 vruntime 查找效率

CFS 每次切换工作时，都会选取 vruntime 值最小的工作来调度，因而须要它有个数据结构来存储各个工作及其 vruntime 信息。

最直观的当然就是选取一个有序列表来存储这些信息，列表依照 vruntime 排序。这样在切换工作时，CFS 只需获取列表头的工作即可，工夫复杂度为 O(1)。比方以后有 10 个工作，vruntime 保留为有序链表[1, 5, 9, 10, 14, 18, 17, 21, 22, 24]，然而每次插入或删除工作时，工夫复杂度会是 O(N)，而且耗时随着工作数的增多而线性增长！

为了兼顾查问、插入、删除的效率，CFS 应用红黑树来保留工作和 vruntime 信息，这样，查问、插入、删除操作的复杂度变成了 log(N)，并不会随着工作数的增多而线性增长，极大晋升了效率。

另外，为了晋升存储效率，CFS 在红黑树中只保留了处于 Running 状态的工作的信息。

应答 I / O 与休眠

每次都选取 vruntime 值最小的工作来调度这种策略，也会存在工作饿死的问题。思考有 A 和 B 两个工作，工夫片为 1s，起初 A 和 B 均分 CPU 轮流运行，在某次调度后，B 进入了休眠，假如休眠了 10s。等 B 醒来后，vruntime_{B}vruntimeB​就会比 vruntime_{A}vruntimeA​小 10s，在接下来的 10s 中，B 将会始终被调度，从而工作 A 呈现了饿死景象。

为了解决该问题，CFS 规定当工作从休眠或 I / O 中返回时，该工作的 vruntime 会被设置为以后红黑树中的最小 vruntime 值。上述例子，B 从休眠中醒来后，vruntime_{B}vruntimeB​会被设置为 11，因而也就不会饿死工作 A 了。

这种做法其实也存在瑕疵，如果工作的休眠工夫很短，那么它醒来后仍旧是优先调度，这对于其余工作来说是不偏心的。

写在最初

本文花了很长的篇幅解说了几种常见 CPU 调度算法的原理，每种算法都有各自的优缺点，并不存在一种完满的调度策略。在利用中，咱们须要依据理论的工作负载，选取适合的调度算法，配置正当的调度参数，衡量周转工夫和响应工夫、工作偏心和切换耗费。这些都应验了《Fundamentals of Software Architecture》中的那句名言：Everything in software architecture is a trade-off.

本文中形容的调度算法都是基于单核处理器进行剖析的，而多核处理器上的调度算法要比这简单很多，比方须要思考处理器之间 共享数据同步、缓存亲和性 等，但实质原理仍然离不开本文所形容的几种根底调度算法。

参考

1. Operating Systems: Three Easy Pieces, Remzi H Arpaci-Dusseau / Andrea C Arpaci-Dusseau
2. 计算机系统根底(三)：异样、中断和输出 / 输入,

点击关注，第一工夫理解华为云陈腐技术~