操作系统的CPU虚拟化

谭清宽

对CPU虚拟化的目的之一就是能够同时运行多个进程，实质就是对进程的切换，也就是快速的切换执行多个进程，这样对于用户而言，所有的进程都是同时进行的，但是应该如何让多个进程公平合理并安全高效的运行呢？所以，就出现了很多进程调度算法。

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

假设有3个进程，每1个进程处理需要10 s，这时，无论哪个进程先来，最后一个进程的完成时间都是30s，也就是说这种情况下最大完成时间是所有进程需要时间之和。但是如果同样有3个进程，其中2个进程需要10s，另外1个进程需要100 s，这种情况，最大完成时间就是120 s，由于3个进程的各自完成时间不同，所以根据他们到达的顺序不同最终的影响也有很大差异。假设3个进程A（10s）、B（10s）、C（100s），如果按照A、B、C的顺序到达，那么执行的过和我们预想的是一样的，开始10 s，A执行结束，20 s后，B执行结束，120 s，C执行结束。但是如果是按照相反的顺序到达的呢？C、B、A，这样开始100 s后，C执行结束，110s，B执行结束，120 s后，A执行结束。很显然，这种情况下，B和A都要等待时间最长的C结束才可以执行，所以这个算法的效率根据到达的顺序有很大关系。显然，这并不是我们想要的。

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

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

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

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

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

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

但是这种算法还要付出另外的代价，就是上下文切换的成本。所以说需要找一个合理的时间片。但是最主要的问题是，这种算法与之前的最短任务优先与最短完成时间优先是有些相反的，也就是说，这种算法导致了周转时间变得更长。

其实2种算法，各自的度量标准不同，一个是周转时间，另一个是响应时间，毕竟魚与熊掌不可兼得的道理大家都知道。