- 先进先出(First In First Out)
- 最短工作优先(Shortest Job First)
- 最短完成时间优先(Shortest Time-to-Completion First)
- 轮转(Round-Robin)
这章介绍了一些基本的调度策略,从周转时间和响应时间两个指标分别讨论这些策略的优劣。
在进入正文之前首先了解周转时间、响应时间如何计算。
周转时间代表工作从到达和完成之间所花费时间,响应时间代表工作从到达和开始处理工作之间的时间花费。
介绍之前做出如下假设:
- 每个工作运行相同的时间
- 所有工作同时到达
- 一旦开始,每个工作都必须执行完成
- 所有工作都使用CPU,即没有IO操作
- 每个工作运行时间都是已知的。
先进先出(First In First Out)
假设:2 3 4 5
首先第一个基本调度策略是先进先出。它是按照工作压入顺序处理工作,早压入的工作总是比之后的工作先执行。但这种模式很依赖工作的压入顺序,工作处理的顺序不同会导致周转时间产生较大差异。例如:假设有两个同时到达的工作A、B,A的处理的所需时间远比B久。可以得出较短处理时间的工作B先处理远比先处理A的周转时间短。
最短工作优先(Shortest Job First)
假设:3 4 5
对于FIFO的按工作压入顺序处理工作,SJF在多个工作达到时总是会选择处理时间最短的工作处理,直到所有工作处理完毕。SJF能够解决了FIFO在工作选取上的不足。同FIFO,SJF也存在不足,假设长工作总比短工作先到达,那么SJF出现与FIFO类似的护航问题(参考书本p50)。
最短完成时间优先(Shortest Time-to-Completion First)
假设:4 5
为SJF添加抢占机制,称为STCF。与SJF不同的是STCF允许工作在没有执行完成可以切换到其他工作执行。每当一个工作到达时,总是检查剩余工作和新工作中谁的剩余工作处理时间最少,然后调度该工作。被抢占工作必须等待抢占工作处理完成之后才能被重新调度。
轮转(Round-Robin)
假设:4 5
上面介绍的三种调度只是针对周转时间进行处理,对于响应时间它们都存在着问题。轮转是一个很简单的思想:在统一时间片内运行一个工作,然后切换到运行队列中的下一个工作继续工作。简单一点就是工作都在交替执行一段时间。工作经过交替执行后响应时间远比前三种模式短,但是轮转的周转时间又因为轮转变得非常糟糕。
上述的几个调度模式非常侧重某一个维度,SJF、STCF侧重周转时间,RR侧重响应时间。所以需要一个对周转时间和响应时间都相对友好的调度模式,同时还需要放宽4、5条件。这些会在多级反馈队列得到解决。