我们在上一篇文章中已经讲过操作系统是如何虚拟化CPU的。今天再深入一点，说说进程调度。我们已经知道，CPU虚拟化的目的是为了能够同时运行多个进程（这不是唯一的目的），其实质是切换进程，即快速切换执行多个进程，所以那对于用户来说，所有的进程都是同时执行的，但是我们应该如何公平、合理、安全、高效的运行多个进程呢？因此，我们有很多进程调度算法。下面我们由浅入深，谈谈目前比较广泛的算法。第一种是最简单的先进先出（FIFO），也可以称为先到先得。该算法最大的优点是简单。没错，我们理解的进程先到，CPU会先处理哪一个，等待当前进程结束再处理下一个。我们假设有3个进程，每个进程需要10s来处理。此时无论哪个进程先来，最后一个进程的完成时间都是30s。也就是说，这种情况下的最大完成时间是所有进程所需时间的总和。但是如果也有3个进程，其中两个耗时10s，一个耗时100s，此时最大完成时间为120s。由于三个进程的完成时间不同，根据到达的先后顺序，最终的影响也会不同。也有很大的不同。假设三个进程A(10s)、B(10s)、C(100s)，如果它们按照A、B、C的顺序到达，那么执行过程和我们预期的一样，开始十秒，A执行结束，20秒后，B执行结束，120秒后，C执行结束。但是，如果它以相反的顺序到达怎么办？C、B、A，这样100秒后，C的执行结束，110秒后，B的执行结束，120秒后，A的执行结束。显然，在这种情况下，B和A都必须等待最长的C完成才能执行，所以这个算法的效率与到达的顺序有很大关系。显然，这不是我们想要的。这里我们计算流程的平均周转时间。当三个过程都用10s时，平均周转时间：(10+20+30)/3=20，因为A在10s内完成，B在20s内完成，C在20s内完成。完成于30年代。想一想，当进程A、B、C的时间分别为10s、10s、100s时？此时进程顺序为C、B、A，则平均周转时间为：(100+110+120)/3=110。这是我们不能接受的。这个问题通常被称为车队效应。这种情况在我们的生活中也很常见。比如我们去一个地方做一件事，一般人只需要一分钟就可以完成，但是他面前有一个人却需要30分钟才能完成。大家要一起等这三十分钟。针对以上问题，我们有了新的解决方案：ShortestTaskFirst(SJF)和ShortestTimetoCompletionFirst(STCF)。最短任务优先，顾名思义就是先执行需要占用CPU时间最短的进程，也就是上面的例子中（A需要10s，B需要20s，C需要100s），让A和B先到达，执行完c之后再执行。但是在这个算法中，我们仍然不能保证C一定是最后到达的。如果C还是先到，情况还是不好。下图中：SJF为了解决这个问题，我们的借贷条件是不需要保证所有的进程必须同时全部执行。现在我们假设最坏的情况，C先到，然后是A和B。当C的总执行时间需要100s时，B在开始执行时10s到达。这个时候我们不需要保证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岁完成，非常吓人。现在我们有两个指标不同的算法，一个是周转时间，一个是响应时间，但是大家都知道不能两者兼得，那怎么办呢？接下来的文章中，我们继续讲两个比较完善的算法，多级反馈队列和比例份额。这两个算法的内容比较多，所以单独拿出来。今天说的是一个比较基础的东西，可以说是进程调度思想的开端。有了这个基础，我们才能对后续的多级反馈队列算法和比例分享有更深入的理解。多说几句，为什么最近要写操作系统呢？因为我觉得这对生产有很大的帮助，尤其是在发现生产环境的问题，性能提升等方面，所以建议大家可以多多学习。这是我一直提倡的。语言只是工具，框架也是工具，只是千变万化。只有掌握了最核心最基础的，才能立于不败之地。
