最短作业优先(SJF)调度算法(详解版)
一个更为恰当的表示是最短下次CPU执行算法,这是因为调度取决于进程的下次 CPU 执行的长度,而不是其总的长度。我们使用 SJF 一词,主要由于大多数教科书和有关人员都这么称呼这种类型的调度策略。
举一个 SJF 调度的例子,假设有如下一组进程,CPU 执行长度以 ms 计:
进程 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 执行的进程来运行。
下次 CPU 执行通常预测为以前 CPU 执行的测量长度的指数平均。我们可以按下面的公式来计算指数平均。设 tn 为第 n 个 CPU 执行长度,设 n+1 为下次 CPU 执行预测值。因此,对于 , 0 1,定义:
n+1 = n + (1- ) n
值 tn 包括最近信息,而 n 存储了过去历史。参数 控制最近和过去历史在预测中的权重:
更为常见的是 = 1/2,这样最近历史和过去历史同样重要。初始值可作为常量或系统的总体平均值。
图 1 为一个指数平均的例子,其中 =1/2, 0=10。
图 1 下一个 CPU 执行长度的预测
为了理解指数平均行为,通过替换 n,可以展开 n+1,从而得到:
n+1 = tn + (1- ) tn-1 + + (l- )j tn-j + + (1- )n+1 0
通常,由于 和(1- )小于 1,所以后面项的权重比前面项的权重要小。
SJF 算法可以是抢占的或非抢占的。当一个新进程到达就绪队列而以前进程正在执行时,就需要选择了。新进程的下次 CPU 执行,与当前运行进程的尚未完成的 CPU 执行相比,可能还要小。抢占 SJF 算法会抢占当前运行进程,而非抢占 SJF 算法会允许当前运行进程以先完成 CPU 执行。抢占 SJF 调度有时称为最短剩余时间优先调度。
举个例子,假设有以下 4 个进程,其 CPU 执行时间以 ms 计:
如果进程按给定时间到达就绪队列,而且需要给定执行时间,那么产生的抢占 SJF 调度如以下 Gantt 图所示:
进程 P1 在时间 0 开始,因为这时只有进程 P1。进程 P2 在时间 1 到达。进程 P1 剩余时间(7ms)大于进程 P2 需要的时间(4ms),因此进程 P1 被抢占,而进程 P2 被调度。
对于这个例子,平均等待时间为 [(10-1) + (1-1) + (17-2) + (5-3)]/4 = 26/4 = 6.5ms。如果使用非抢占 SJF 调度,那么平均等待时间为 7.75ms。
21985.html
html相关文章
- 经典神经网络 | fast rcnn目标检测算法详解
- OHEM算法及Caffe代码详解
- 最短路径问题—Floyd算法详解[通俗易懂]
- CRC校验算法详解「建议收藏」
- 串的模式匹配算法(KMP算法,BF算法+算法详解+实现代码)
- Go 数据结构和算法篇(十七):二叉排序树
- 每日一个小算法之整数中每位上的数字进行反转 20190810
- 【计算理论】计算复杂性 ( 小 O 记号 | 严格渐进上界 | 分析算法的时间复杂度 )
- 非阻塞算法简介详解程序员
- 使用LRU算法缓存图片,android 3.0详解手机开发
- Nginx负载均衡算法详解程序员
- Java 对称加密几种算法分别实现详解编程语言
- 神经网络分类算法 数据挖掘详解大数据
- C语言按层次遍历二叉树算法详解编程语言
- 算法-最小的K个数详解编程语言
- 二叉树中和为某一值的路径算法详解编程语言
- 解数独算法详解编程语言
- C++ set_union(STL set_union)算法详解
- C++ stable_sort(STL stable_sort)排序算法详解
- C++ is_sorted(STL is_sorted)排序算法详解
- 磁盘调度算法详解
- Redis集群中的选举算法与机制研究(redis选举算法和机制)
- 海量数据库的查询优化及分页算法方案集合2/2