摘要：本文将会从最根底的调度算法说起，一一剖析各种支流调度算法的原理，带大家一起摸索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. 计算机系统根底(三)：异样、中断和输出/输入,

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