进程调度：介绍（原书第七章）

问题：如何开发调度策略？

工作负载假设

在具体给出一个目标调度程序之前，先逐步分析，先给出一些列约束，这些约束看上去都非常理想化，不切实际，不过随着后面分析的深入，会逐步放开这些约束，这样最终的方案就是想要的一个比较理想的调度策略了。

假设如下：

1. 每个工作运行时间相同
2. 所有工作同时到达
3. 任务一旦开始，每个任务必须保持运行，直到运行结束，中间不会被打断
4. 所有的工作只涉及CPU
5. 每个工作所需的时间是已知的

调度指标

这里给出一个概念：周转时间

T(周转时间) = T(完成时间) - T(到达时间)

结合前面的五个假设中的第二个假设，所有工作同时达到，所以这里的T(到达时间) = 0；因此 ： T(周转时间) = T(完成时间)

先进先出（FIFO）

假设一个场景：现在有A、B、C三个任务同时到达，但是稍微一丢丢的时间差异，比如A比B先到一点点，同理B比C也先到一点点，每个任务的执行时间是10s，那么这三个任务此时的平均周转时间是多少？

A的周转时间：10s，B：20s，C：30s，因此平均周转时间就是（10s + 20s + 30s）/ 3 = 20s。

此时放宽前面五个假设中的第一个假设，比如此时A任务需要100s结束，B和C都需要10s，那么此时的平均周转时间就变成了：（100s + 110s + 120s） / 3 = 110s

此时这种情况就是所谓的护航效应，一些潜在耗时较少的资源消费者被排到了重量级的资源消费者之后。

最短任务优先（SJF：Shortest Job First）

前面的例子中，可以将A放到B和C后面运行，这时候就可以将平均周转时间降下来：（10s + 20s + 120s）/ 3 = 50s

这个方案看似是一个不错的调度方案，但是要知道，现在我们是基于一些不切实际的假设之上的，现在再尝试放开前面五个假设中的第2个假设，即：此时的假设生效只有3、4、5三条了。

现在假设A任务在t = 0到达，而B和C在t = 10到达，此时如果采用SJF策略，可以算出平均周转时间：(100s + (110 - 10)s + (120 - 10)s) / 3 = 103.3s

最短完成时间优先（STCF：Shortest Time-to-Completion First）

它也叫作：抢占式最短作业优先（ Preemptive Shortest Job First ， PSJF）调度程序。

这种策略下，受限需要放开前面五个假设中的第3个假设，就是任务运行之后不一定会一直运行到结束，而是可以被抢占的，那么依旧是前面这个例子，A最开始运行，然后t = 10s的时候B和C到达，此时按照STCF策略，B和C肯定就会抢占A的资源先运行，B和C运行结束后再切回到A运行，整个过程平均周转时间：(120s + (20 -10)s + (30 - 20)s) / 3 = 46.7s。

可以看到，这个策略是最符合直觉的，但是它也有一个非常不切实际的假设前提，那就是直到任务的运行时间，所以该策略是好的，不过不实用，因为下面会再引入一个度量指标。

新度量指标：响应时间

响应时间定义为：从任务到达系统到首次运行的时间：

T(响应时间) = T(首次运行) - T(到达时间)

因此对于前面的A、B、C任务的场景，A的相应时间为0，B的响应时间为0（10 -10）， C的响应时间为10（20 - 10），所以平均响应时间为3.33，可以看到这种调度响应时间很长。

基于这种响应时间的度量标准，提出了一个新的问题：如果构建一个对响应时间敏感的调度程序。

轮转（RR）

轮转调度（RR：Round Robin）：在一个时间片内运行一个工作，然后切换到队列中的下一个任务，反复执行直到任务结束。

注意：时间片长度必须是时钟周期的倍数，比如时钟周期为10ms，那么时间片长度可以是10ms、20ms等这种整数倍的时间。

此时假设场景：A、B、C同时到达，并且都希望运行5s，那么如果对于前面的SJF策略，此时的平均响应时间就是：(0 + 5 + 10) / 3 = 5。

而如果采用轮转，假设时间片选择为1s，那么此时平均响应时间就是(0 + 1 + 2) / 3 = 1，同时这里可以感觉到，如果选择的时间片越短，则平均响应时间就越高。

但实际中，不可能将时间片设定的太小，否则频繁的切换上下文带来的损耗就会陡增从而影响整体性能。因此这里需要做一个权衡，既要在保证不错的响应时间指标基础上，也要摊销掉一部分因为切换上下文带来的性能损耗。

轮转策略确实降低了平均响应时间，但是回头再看一下前面提到的平均周转时间呢？可以发现RR策略的平均周转时间：A在13s完成，B在14s完成，C在15s完成，所以平均是14s。

因此这里是一个鱼和熊掌不可兼得的问题，如果选择了公平策略（如RR），那就没法保证很好的平均周转时间，如果选择不公平，某个任务可以一直运行到结束，那就要以响应时间为代价。

结合I/O

现在打破第4个假设，引入I/O，这里假设两个任务A和B，它们都需要50ms运行结束，不过A任务每隔10ms都需要进行一次10ms的I/O操作，B就是一个单纯的50ms的纯CPU任务。

假如现在逐个运行，比如先运行A，然后再运行B，那么两个任务运行结束，需要140ms。

如果此时我们采取STCF调度方案，那么可以将A看成是五个10ms的子任务，每个子任务之间需要10ms的I/O操作，那么如果此时将A的每个子任务视为一项独立的工作，子A和B此时肯定先调度子A，然后子A结束，进入IO，CPU调度B并运行，然后提交另一个子A任务，抢占CPU，等它结束就再次调度B，如此反复直至结束。

这样可以看到整个任务执行过程中可以实现重叠的效果！A在等待IO的时候可以运行B，这样CPU可以最大化利用。

无法预知

在真实的场景中，操作系统对任务的具体情况所知甚少，根本就无法具体确定任务的执行时长！这里就留下了一个思考：如何在没有这种先验知识的前提下建立一个比较合适的调度方案，前面介绍到的SJF/STCF可能需要进行一些调整！也可以结合一些已经看到的想法配合着RR调度，以实现降低响应时间。