本文主要介绍一些基础的调度策略。

调度指标

以下算法的性能指标只考虑周转时间。

周转时间 = 完成时间 - 到达时间

先进先出（FIFO）

这个算法的思路很简单，先来的先执行，并且易于实现。就好比有三个任务A，B，C，他们到来的顺序是B，A，C，那么就按照他们到来的顺序进行执行。

存在的问题：如果先来的任务执行了很长时间，会导致后边的任务等待很久才可以执行，这样会导致系统的周转时间变的很长。

最短任务优先（SJF）

该算法会先运行短任务，然后运行次短任务，依次下去。如果任务同时到达，该算法较FIFO算法可以很好的解决平均周转时间长的问题。

但是如果任务不同时到达，那么执行时间长的任务比短时任务先到达，还是会导致短任务需要等待。

最短完成时间优先（STCF）

上面两种算法都是非抢占式的。

而最短完成时间优先可以理解为一种抢占式的最短任务优先算法。

该算法下，没当有任务进入系统，会判断当前正在执行任务的剩余时间和新任务的时间，哪个短就执行哪个。

新的性能指标

从现在开始，性能不仅考虑周转时间，还要考虑响应时间。

响应时间 = 首次运行 - 到达时间。

轮转

在加入新的性能指标后，上述算法就会出现问题，因为会导致长任务的响应时间特别长。

轮转的思想是，每一个任务执行一个时间片，然后切换到队列中的下一个任务，而不是一个任务一直执行，直到完毕。

该算法需要考虑时间片长短的问题，太短会导致频繁切换而导致性能下降，而太长，则会导致周转时间和响应时间太长，所以需要权衡考虑。

结合I/O

现在假设任务都需要进行I/O操作，那么轮转这种设计方法就会体现出它的优势。

如果不进行轮转，先到来的任务占用处理器资源，然后又进行了I/O操作，那么会导致一个任务占用处理器资源却不使用，而是进行I/O操作，导致其他任务也无法执行，这是对处理器的浪费。

而轮转却能很好的解决该问题，因为任务在执行I/O操作时，可以让出处理器，让其他任务使用。

无法预知

上面的讨论都是建立在操作系统知道任务需要处理多长时间，而事实情况是，执行时间是无法估计的，所以像SJF或者STCF这种算法，几乎无法实现。

参考

《操作系统导论》