0、前置知识
0.1 调度性能指标
周转时间：周转时间 = 完成时间 - 到达时间
响应时间：响应时间 = 首次运行时间 - 到达时间
0.2 上下文切换
当一个进程停止时，他的寄存器将被保存在这个内存位置。通过恢复这些寄存器（将他们的值放回实际的物理寄存器中），操作系统可以恢复运行该进程。这种技术叫做上下文切换。
1、进程调度算法简单介绍
1.1 先进先出（FIFO）
先进先出（First In First Out）调度是我们可以实现的最基本的算法，有时也被称为先到先服务（First Come First Served或FCFS）。
优点：简单，易于实现。
举个例子看看为什么FIFO不好：假设A（100s）、B（10s）、C（10s）三个工作几乎同时来到系统，A稍微比B早一点，B稍微比C早一点，那么，一定要等到A完成后，B才有机会运行。所以系统平均周转时间为：
（100+110+120）/ 3 = 110 s
这个问题通常被称作护航效应，简单来说，就是一些耗时较少的潜在资源消费者被排在重量级资源消费者之后。
那么如何解决这个问题呢？咱们接着往下看：
1.2 最短任务优先（SJF）
最短任务优先（Shortest Job First）很好地解决了这个问题。它的策略为：先运行最短的任务，然后运行次短的任务。
当在只考虑平均周转时间的情况下，SJF显然比FIFO要好的多，同样是上面的例子，平均周转时间为：
10+20+100）/ 3 = 50 s
事实上，考虑到所有工作同时到达的假设，我们几乎可以证明SJF确实是最优的调度算法。然而，当我们考虑实际：工作可以随时到达，这又会出现什么情况呢？
我们再用一个例子来说明：假设 A 在 t = 0 时到达，且需要运行 100s。而 B 和 C 在 t = 10 到达，且各需要运行 10s。用SJF，平均周转时间为：
（100 + （90+10）+ （100+10））/ 3 = 103.33
可以看到，SJF遭遇了同样的护航问题。
1.3 最短完成时间优先（STCF）
事实上，当 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%的时间用于上下文切换，因此时间片带来的成本就被摊销了。
4.2 重叠（overlap）
如有可能，重叠（overlap）操作可以最大限度地提高系统的利用率。重叠在许多不同的领域很有用，包括执行磁盘 I/O 或将消息发送到远程机器时。在任何一种情况下，开始操作然后切换到其他工作都是一个好主意，这也提高了系统的整体利用率和效率。
