操作系统的进程调度算法（CPU虚拟化）

作者：Go语言之美 2020-03-10 19:34:08

云计算

虚拟化

算法 关于操作系统是如何虚拟化 CPU 的我们上一篇文章已经聊过了，今天再深入一下，聊一聊进程调度那些事。

关于操作系统是如何虚拟化 CPU 的我们上一篇文章已经聊过了，今天再深入一下，聊一聊进程调度那些事。

[[318073]]

我们已经知道，对 CPU 虚拟化的目的就是能够同时运行多个进程(这不是唯一目的)，而实质就是对进程的切换，也就是快速的切换执行多个进程，这样对于用户而言，所有的进程都是同时进行的，但是我们应该如何对多个进程来公平合理并安全高效的运行呢?所以，我们就出现了很多的进程调度算法。这里我们由浅入深，来讲一下目前比较广泛的算法。

第一个就是最简单的先进先出(FIFO)，也可以叫做先到先服务。这个算法的最大优点就是简单。没错，就是我们理解的那个进程先来了，CPU 就先处理哪个，等当前的处理结束，在处理下一个。

我们假设有三个进程，每一个进程处理需要10s，这时，无论哪个进程先来，最后一个进程的完成时间都是30s，也就是说这种情况下最大完成时间是所有进程需要时间之和。但是如果同样有三个进程，其中两个进程需要10s，另外一个进程需要100s，这种情况，最大完成时间就是120s，由于三个进程的各自完成时间不同，所以根据他们到达的顺序不同最终的影响也有很大差异。假设三个进程 A(10s)、B(10s)、C(100s)，如果按照 A、B、C 的顺序到达，那么执行的过和我们预想的是一样的，开始十秒钟，A 执行结束，二十秒后，B 执行结束，一百二十秒后，C执行结束。但是如果是按照相反的顺序到达的呢?C、B、A，这样开始一百秒后，C 执行结束，一百一十秒后，B 执行结束，一百二十秒后，A 执行结束。很显然，这种情况下，B 和 A 都要等待时间最长的 C 结束才可以执行，所以这个算法的效率根据到达的顺序有很大关系。显然，这并不是我们想要的。在这里我们计算一下进程的平均周转时间，当三个进程都需要10s的时候平均周转时间：

(10+20+30)/3=20，因为 A 在第10s完成，B 在第20s完成，C 在第30s完成。大家想一下当进程 A、B、C 时间分别为 10s、10s、100s呢?此时进程的顺序是 C、B、A，那么平均周转时间就是：(100+110+120)/3=110。这是我们不能接受的。这个问题通常被称为护航效应(convoy effect)。这种情况在我们生活中也是非常常见的，例如我们去一个地方办一件事，大多数人只需要一分钟就可以办完，但是前面有一个人需要三十分钟才可以办完，那么后面的人都要一起等待这三十分钟。

针对上面的问题，我们有新的解决方案：最短任务优先(SJF)与最短完成时间优先(STCF)。

最短任务优先顾名思义，就是需要占用 CPU 时间短的进程先执行，也就是在上面的例子中(A需要10s、B需要20s、C需要100s)，先让A和B先到达，执行结束后在执行C。但是这种算法中，我们依然不能保证C一定最后到达，如果C依然是最先到达，情况依然糟糕，情况下图：

SJF

为了解决这个问题，我们放款条件，就是我们不需要保证所有的进程必须一次都执行完。现在我们在假设最坏的情况，C先到达，之后才是A和B。当C总执行时间需要100s时，刚开始执行到了10s的时候，B到达，此时我们不需要保证C执行全部完成，发现B的时间只需要10s就可以结束，此时就暂停C同时开始执行B，当B执行结束后，A又到达，此时我们同样不执行C而是执行A，当A结束后，我们再回到C，这样性能又上升了一个台阶。如下图：

STCF

上面的算法中主要考量的是平均周转时间，但是现实中如果用这样的算法依然是不可靠的，试想我们打开一个软件，某一个功能需要等待100s后才反应，那我们岂不是要疯掉?此时新的度量指标出现了：响应时间(响应时间=首次运行-到达时间)。

我们再介绍新的算法，轮转(Round-Robin，RR)。顾名思义，就是轮训执行进程。在一个时间片内运行一个工作，然后切换到运行队列中的下一个任务。重复执行，直到所有结束。这里我们有一点需要注意，就是时间片需要是时钟中断周期的倍数，时钟中断部分这里不再细讲，上一篇文章我们已经聊过了。假如时钟中断周期是10ms，那么时间片可以是10ms、20ms、30ms或者10ms的任何倍数。三个进程A、B、C，所需时间都是5，如果使用RR这种算法，执行过程就是如下图：

RR

但是这种算法还要付出另外的代价，就是上下文切换的成本。所以说需要找一个合理的时间片。但是最主要的问题是，这种算法与之前的最短任务优先与最短完成时间优先是有些相反的，也就是说，这种算法导致了周转时间变得更长。如图例子，A程序在13完成，B在14，C在15，这是非常可怕的。

现在我们有了两种算法，各自的度量标准不同，一个是周转时间，另一个是响应时间，但是鱼与熊掌不可兼得的道理大家都知道，那么我们具体应该怎么做呢?下一篇文章我们继续聊更加完善的两个算法多级反馈队列与比例份额。​这两个算法内容较多，所以再单独拿出来。

今天说的是比较基础的东西，可以说的进程调度思想的一个起步，有了这个基础我们就可以更加深入的理解后面的多级反馈队列算法与比例份额。再啰嗦几句，最近为什么要写操作系统相关的内容呢?因为我觉得这对生产是有很大帮助的，尤其在生产环境中找问题，性能提升等，所以建议大家可以了解一些。这也是我一直所提倡的，语言只是工具，框架也是工具，但是百变不离其宗，只有掌握了最核心，最基础的才能所向披靡。