1. 调度指标

在进程调度过程中，我们需要一个东西，来衡量比较不同的调度策略。调度指标就是用来衡量不同调度策略好坏的。

周转时间：任务完成的时间减去任务到达操作系统的时间

响应时间：任务到达操作系统首次运行时间减去到达时间

2. 调度算法

2.1 先进先出（FIFO）

最基本的调度算法，被称为先进先出（First In Frist out或者FIFO）调度，有时候也称为先到先服务（Frist Come Frist Served 或者 FCFS）。

假设A、B和C在大致相同的时间（T到达时间=0）到达系统。因为FIFO必须将某个工作放在前面，我们假设A比B早一点点，B比C早一点点。每个工作运行10s。

从图可以看出，A在10s完成，B在20s完成，C在30s完成。这3个任务的平均周转时间就是（10 + 20 + 30）/ 3 = 20。

我没在看第二个例子，假设A运行完成需要100s，那么此时系统的平均周转时间就是（100 + 110 + 120） / 3 = 110. 一些耗时较少的潜在资源被排在后面，会拉慢整个系统的平均运转时间。

2.2 最短任务优先（SJF）

最短任务优先（Shortest Job Frist, SJF）调度策略，先运行最短的任务，然后运行次短的任务。

我没还是以上面的例子，但是以SJF调度策略。如图展示了在考虑平均周转的情况下，SJF调度策略要比FIFO更好。SJF平均周转时间为（10+20 + 120）/ 3 = 50

事实上，我没考虑到所有工作同时到达的假设，证明SJF确实是一个最优的调度算法。但是真实情况这种假设是不成立的，没法保证所有任务都同时到达。

假设 A 在t = 0到达，且需要运行100s。而B 和 C在t=10 到达，且各自需要运行10s,用纯SJF得到如下图的调度。从图中可以看出，即使B和C在A不久后达到，它们任然被迫等到A完成。这3项工作的平均周转时间为103.33s（100 + （110 - 10）+ （120 - 10））/ 3

2.3 最短完成时间优先（STCF）

为了解决这个问题。需要放宽调节（工作必须保持运行直到完成）。我们还需要调度程序本身的一些机制：

当B 和 C 到达时，调度程序当然可以做其他的事情：它可以抢占（preempt）工作A，并决定运行另一个工作。

那么，向SJF添加抢占，就称为最短完成时间优先（Shortest Time-to-Completion Frist, STCF）或者抢占式最短作业优先。

A先到达，运行10s后，B和C到达，STCF将抢占A，运行完B和C后，恢复A的运行。平均运行时间50s（（120 + 10 + 20）/ 3）

考虑到我们的新假设，STCF是最优的；考虑到所有任务都是同时到达，SJF是最优的。

2.4 轮转

到现在为止，我们唯一的衡量指标是周转时间。对于许多早期的批处理系统有一定的意义。然而引入分时系统改变了一切。用户坐在终端前。同时还要交互性好。因此一个新的衡量指标诞生了：响应时间。

响应时间定义为从任务首次运行和到达时间的差值。

STCF和相关方法在响应时间上不是很好。例如，如果3个工作同时到达，第三个工作必须等到前两个工作运行完成才能运行。这种方法虽然有很好的周转时间，但是对于响应和交互性是相当糟糕的。

为了解决这个问题，我们引入新的调度算法，通常被称为【轮转调度】（Round-Robin, RR）。

基本思想：RR在一个时间片（time slice, 有时又称为调度因子）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行直到任务结束。因此RR有时也被称作时间切片（时间片的长度必须是时钟中断周期的倍数）。

RR平均响应时间：（0+1+2）/ 3 = 1；SJF 平均响应时间（0+5+10）= 5. 时间片的长度对于RR是至关重要的。越短，RR在响应时间上表现越好。但是，时间片太短也是有问题的：突然上下文切换的成本也将影响整体性能。因此，系统设计者需要权衡时间片长度，使其足够长，以便摊销上下文切换成本，而又不会使系统不及时响应。

3. 总结

本文简单介绍了操作系统中进程调度的策略。有助于我们更好的理解程序运行的机制。显而易见，任何调度算法没法做到尽善尽美。

如果响应时间是我们唯一的标准，那么带有合理时间片的RR，就会是非常好的调度程序。但是其周转时间是相当糟糕的；如果周转时间是我们唯一的标准，那么显然（SJF，STCF），会是比较好的调度程序；

响应时间和周转时间是一个取舍的过程。