调度指标
周转时间
T周转时间=T完成时间-T到达时间
如果所有任务在同一时间到达，那么 T完成时间 = 0，T周转时间 = T完成时间
先进先出(FIFO)
(1) 假设有 3 个工作 A，B和C在大致在同一时间到达，A 比 B 早一点，B 比 C 早一点，假设每个工作的运行 10s，计算周转时间？
(10+20+30)/3=20
(2) 同(1)，不过这次 A 运行 100s，B和C运行10秒，计算周转时间？
(100+110+120)/3=110
在 (2) 中，周转时间显著增长，这种问题称为护航效应(convoy effect)，一些耗时较少的潜在资源消费者被排在耗时较长的重量级资源消费者之后。
最短任务优先(SJF)
先运行最短的任务，然后是次短的任务。
(1) 假设有 3 个工作 A，B和C在大致在同一时间到达，A 比 B 早一点，B 比 C 早一点，假设每个工作的运行 10s，计算周转时间？
(10+20+120)/3=50s
(2) 还是(1)中例子，不过此时A先到达，B和C在 t=10 到达。
(100+(110-10)+(120-10))/3= 103.33
这里还是会遭遇护航问题。
最短完成时间优先(STCF)
将 SJF 添加抢占特性，成为最短完成时间优先(Shortest Time-to-Completion First, STCF)或抢占式最短作业优先(Preemptive Shortest Job First, PSJF)。这种调度程序称为抢占式调度程序。
3.1 假设有 3 个工作 A，B和C在大致在同一时间到达，A先到达，B和C在 t=10 到达，计算周转时间？
((20-10)+(30-10)+120)/3=50s，可见平均周转时间大大提高了。
假设工作必须保持运行直到完成，这时STCF是最优的，如果考虑所有工作同时到达，SJF 是最优的。
新度量指标：响应时间
自从引入了分时系统，现在，用户将会坐在终端前面，这时要求系统的交互性好，即能在最短时间内获得响应。因此，一个新的度量标准诞生了：响应时间(response time)
T响应时间=T首次运行时间-T到达时间
例如： 使用 3.1 的作业，A 在时间 0 到达，B 和 C 在时间 10 到达。每个作业的响应时间如下：作业 A 为 0，作业 B 为 0，作业 C 为10(平均: 3.33)
STCF 和相关方法在响应时间上并不是很好，例如，如果 3 个工作同时到达，第 3 个工做必须等待前两个工作全部运行后才能运行。
轮转
通常称为轮转(Round-Robin，RR)调度。其基本思想是：RR 在一个时间片(time slice)内运行一个工作，然后切换到运行队列的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。RR 有时被称为时间片(time-slicing)。时间片长度必须是时钟中断周期的倍数。如果时钟中断是每 10ms 中断一次，则时间片可以是 10ms，20ms或者 10ms。
例如：现有 3 个任务 A，B和C在系统中同时到达，并且它们都希望运行 5s。SJF 调度程序必须完成当前任务才可以运行下一个任务。1s 时间片的 RR 可以快速地循环工作。
RR 的平均响应时间：(0+1+2)/3=1
SJF 的平均响应时间：(0+5+10)/3=5
时间片越短，RR 在响应时间上表现越好，然后短也会造成上下文切换的成本过大。
摊销可以减少成本，时间片越大，上下文切换的成本就越低。
如果响应是唯一指标，那么带有合理时间片的 RR 就会使非常好的调度程序。
如果考虑周转时间，那么 RR 会是糟糕的策略。
结合 I/O
假设两项工作 A 和 B，每项工作都需要 50 ms的 CPU 时间，A 运行 10 ms，然后发出 I/O 请求，假设每个 I/O 请求都需要 10 ms，而 B 只使用 CPU 50 ms，不执行 I/O。调度程序先运行 A，然后运行B。
一种常见的方法是将 A 的每个 10ms 的子工作视为一项独立工作。因此，当系统启动时，它的选择是调度 10ms 的A，还是 50ms 的B。使用STCF，选择是明确的。
无法预知
前面的讨论都基于这样一个假设，就是作业的运行时间已知。但实际情况是操作系统对每个作业的运行时间知之甚少。因此，我们如何建立一个没有这种先验知识的 SJF/STCF？更进一步，我们如何将已经看到的一些想法与 RR 调度程序结合起来，以便响应时间也变得相当不错。
小结
我们介绍了调度的基本思想，并开发了两类方法。第一类是运行最短的工作，从而优化周转时间。第二类是交替运行所有工作，从而优化响应时间。很难做到“鱼和熊掌兼得”，这是系统中常见的，固有的折中。我们也看到了如何将 I/O 结合到场景中，但仍未解决操作系统根本无法看到未来的问题。稍后，我们将看到如何通过构建一个调度程序，利用最近的历史预测未来，从而解决这个问题。这个调度程序称为多级反馈队列。
