操作系统基础22-最短作业优先(SJF)调度算法

操作系统基础22-最短作业优先(SJF)调度算法

2020-11-28 17:16·重学IT的老猫

最短作业优先( Shortest Job First SJF)调度算法将每个进程与其下次CPU执行的长度关联起来。当CPU变为空闲时,它会被赋给具有最短CPU执行的进程。如果两个进程具有同样长度的CPU执行,那么可以由先到先服务(FCFS)调度算法来处理。

一个更为恰当的表示是最短下次CPU执行算法,这是因为调度取决于进程的下次CPU执行的长度,而不是其总的长度。使用SJF一词,主要由于大多数教科书和有关人员都这么称呼这种类型的调度策略。

算法思想:追求最少的平均等待时间,最少的平均周转时间、最少平均带权周转时间
算法规则:最短的作业/进程优先得到服务(所谓“最短”,服务时间最短)
用于作业/进程调度:即可用于作业调度,也可用于进程调度。用于进程调度时,称为“短进程优先(SPF,Shortest Process First)”

优缺点
  优点:“最短”平均等待时间、平均周转时间
  缺点:不公平。对短作业有利,对长作业不利。 可能产生饥饿现象。另外,作业/进程的运行时间是由用户提供的,并不一定真实,不一定能做到真正的短作业优先。

是否会导致饥饿。如果源源不断地由短作业/进程到来,可能使长作业/进程长时间得不到服务,产生饥饿现象。如果一直得不到服务,则称为饿死

举一个SJF调度的例子,假设有如下一组进程,CPU执行长度以ms计:

操作系统基础22-最短作业优先(SJF)调度算法

采用 SJF调度,就会根据如下 Gantt 图来调度这些进程:

操作系统基础22-最短作业优先(SJF)调度算法

进程 P1 的等待时间是3ms,进程 P2 的等待时间为16ms,进程P3的等待时间为9ms,进程 P4 的等待时间为0ms。因此,平均等待时间为(3 + 16 + 9 + 0)/4 = 7ms。相比之下,如果使用FCFS 调度方案,那么平均等待时间为10.25ms。
可以证明SJF调度算法是最优的。这是因为对于给定的一组进程,SJF算法的平均等待时间最小。通过将短进程移到长进程之前,短进程的等待时间减少大于长进程的等待时间增加。因而,平均等待时间减少。
SJF算法的真正困难是如何知道下次CPU执行的长度。对于批处理系统的长期(或作业)调度,可以将用户提交作业时指定的进程时限作为长度。在这种情况下,用户有意精确估计进程时间,因为低值可能意味着更快的响应(过小的值会引起时限超出错误,进而需要重新提交)。SJF调度经常用于长期调度。
虽然 SJF算法是最优的,但是它不能在短期CPU调度级别上加以实现,因为没有办法知道下次 CPU 执行的长度。一种方法是试图近似SJF调度。虽然不知道下一个CPU执行的长度,但是可以预测它。可以认为下一个CPU执行的长度与以前的相似。因此,通过计算下一个CPU执行长度的近似值,可以选择具有预测最短CPU执行的进程来运行。

实例(短作业优先非抢占式):

操作系统基础22-最短作业优先(SJF)调度算法

短作业优先非抢占式

实例(最短剩余时间优先算法抢占式):

操作系统基础22-最短作业优先(SJF)调度算法

-------------本文结束 感谢阅读-------------