事实上，当 B 和 C 到达时，调度程序当然可以做其他事情：它可以抢占（preempt）工作 A，并决定运行另一个工作，或许稍后继续工作 A。那么，为了解决刚才遭遇的护航问题，我们可以向SJF添加抢占：称为最短完成时间优先（Shortest Time-to-Completion First，STCF）或抢占式最短作业优先（Preemptive Shortest Job First ，PSJF）调度程序。

他的做法是这样的：每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。

补充一点：几乎所有现代化的调度程序都是抢占式的（preemptive），非常愿意停止一个进程以运行另一个进程。这意味着调度程序采用了我们之前学习的机制。特别是调度程序可以进行上下文切换，临时停止一个运行进程，并恢复（或启动）另一个进程。

因此，在我们的例子中，STCF 将抢占 A 并运行 B 和 C 以完成。只有在它们完成后，才能调度 A 的剩余时间。平均周转时间为：

（120+10+20）/ 3 = 50 s

其实，考虑可抢占的假设，可以证明STCF为最优的调度算法。

那么，假如加入新的度量指标：响应时间呢？

还是使用刚才的例子：A 在时间 0 到达，B 和 C 在时间 10 达到，假如使用STCF，平均响应时间为：

（0 + 0 + 10）/ 3 = 3.33 s

而非抢占式的FIFO和SJF的响应时间都是0s，可以看出，STCF虽然有很好的周转时间，但对于响应时间和交互性上是糟糕的。就好像我们在终端按下回车，肯定不希望在10s之后才给我们显示内容。

为此，我们要引入一个新的调度算法。

1.4 轮转（RR）

轮转（RR）调度的基本思想很简单：RR 在一个时间片内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。

请注意：时间片长度必须是时钟中断周期的倍数。

为了更详细地理解 RR，我们来看一个例子：假设 3 个任务 A（5s）、B （5s）和 C（5s）在系统中同时到达。SJF 调度程序必须运行完当前任务才可运行下一个任务。相比之下，1s 时间片的 RR 可以快速地循环工作。

SJF的平均响应时间是：（0+5+10）/ 3 = 5 s

RR的平均响应时间是：（0+1+2）/ 3 = 1 s

如你所见，时间片长度对于 RR 是至关重要的。越短，RR 在响应时间上表现越好。然而，时间片太短是有问题的：突然上下文切换的成本将影响整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长，以便摊销（amortize）上下文切换成本，而又不会使系统不及时响应。

可是，如果再回过头来看周转时间，我们会发现，RR几乎是最差的。但这并不奇怪，如果周转时间是我们的指标，那么 RR 确实是最糟糕的策略之一。直观地说，这应该是有意义的：RR 所做的正是延伸每个工作，只运行每个工作一小段时间，就转向下一个工作。而因为周转时间只关心作业何时完成。

2、多考虑一些情况

2.1 结合I/O

交互式作业正在执行 I/O 时，其他 CPU 密集型作业将运行，从而更好地利用处理器。

2.2 工作长度未知

事实上，在一个通用的操作系统中，操作系统通常对每个作业的长度知之甚少。因此，我们如何建立一个没有这种先验知识的 SJF/STCF？更进一步，我们如何能够将已经看到的一些想法与 RR 调度程序结合起来，以便响应时间也变得很好？这就是我们接下来要讲的问题：多级反馈队列（MLFQ）调度方法 操作系统学习（二）：浅析多级反馈队列MLFQ

3、小结

按照我们介绍的顺序，几种调度算法可以这样串起来：

3.1 各自的优缺点

FIFO 优点：简单

缺点：平均周转时间长（护航问题）

SJF 优点：作业同时到达时，平均周转时间短

缺点：作业不同时到达时，同样面临护航问题

STCF 优点：作业不同时到达时，平均周转时间短

缺点：响应时间长

RR 优点：响应时间短

缺点：平均周转时间长

4、提到的其他技术

4.1 摊销（amortization）

摊销可以减少成本。

当系统某些操作有固定成本时，通常会使用摊销技术（amortization）。通过减少成本的频度（即执行较少次的操作），系统的总成本就会降低。例如，如果时间片设置为 10ms，并且上下文切换时间为 1ms，那么浪费大约 10%的时间用于上下文切换。如果要摊销这个成本，可以把时间片增加到 100ms。在这种情况下，不到 1%的时间用于上下文切换，因此时间片带来的成本就被摊销了。