操作系统基础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计：
采用 SJF调度，就会根据如下 Gantt 图来调度这些进程：
进程 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执行的进程来运行。
实例(短作业优先非抢占式)：
短作业优先非抢占式