秒懂算法 | 调度算法
介绍典型的调度算法以及算法应用。
01、作业（进程）优先调度算法
短作业优先调度（Shortest Job First,SJF）算法或短进程调度（Shortest Process First,SPF）算法是指对短作业或短进程优先调度的算法。这里，作业或进程的长短是以作业或进程要求运行时间的长短来衡量的。在把短作业优先调度算法作为作业调度算法时，系统将从外存后备作业队列中选择估计运行时间最短的作业，优先将它调入内存执行。这种算法适合作业调度和进程调度。
例1 采用SJF算法对它们的开始执行时间、运行结束时间、周转时间和带权周转时间进行讨论。对于相同长度的作业，通常按照FCFS算法执行。通过计算，可得如表1所示的结果。
表1 SJF算法示例
表1列出了各进程的开始执行时间、完成时间、周转时间和带权周转时间。比较表3-3（b）和表3-4可以看出，SJF算法给短作业带来明显的改善，同时降低了作业的平均周转时间，提高了整个系统的性能。
SJ(P)F算法也存在一些不容忽视的缺点。
（1） 该算法对长作业不利。若系统不断有短作业进入，将造成长作业无限期延迟而得不到调度。
（2） 该算法未考虑作业的紧迫度，因而不能保证紧迫作业的及时处理。
（3） 由于作业或进程的长短只是由用户估计的，而用户又可能有意无意地缩短作业的估计运行时间，因此不一定保证做到真正意义上的短作业优先调度，因此该调度算法经常作为其他调度算法的比较算法。
02、高响应比优先调度算法
该算法通常用于作业调度。
高响应比优先调度（Highest Response First，HRF），也称为HRN（Highest Response Next）算法。FCFS算法只考虑作业等待时间长短而忽略作业的长度，而SJF算法的主要不足是长作业的运行得不到保证，两者都具有片面性。为了克服这两种算法的缺点，可以采用一种折中的方法，既让短作业优先，又考虑系统内等待时间过长的作业，这就是HRF算法。该调度策略在考虑每个作业等待时间的长短的同时估计所需的执行时间长短，从中选出响应比最高的作业投入运行。响应比R可定义为
所谓响应比R高者优先调度，是指每次挑选一个作业投入执行时，先计算此时后备作业队列中每个作业的响应比R值，选择一个R值最高者投入执行。注意公式中的“已等待时间”为一个动态数据，它随着作业等待时间的增长而增加，因此作业等待时间越长，响应比越大。因此，一个长期未被调度的作业，只要等待足够长的时间，总有机会成为响应比高者，从而得以执行；同样长度的作业，其R值可以从其等待调度的时间长短来区分；同样等待时间的作业，要求执行时间少的作业R值高。因此，该算法既照顾了短作业，又考虑了作业的等待时间。当然，利用该算法时，每次进行调度之前，都要先计算响应比，因此增加了系统的开销。
例2 系统的作业调度采用高响应比优先调度算法，有四个作业先后进入后备状态队列，到达系统时间和所需运行时间如表2所示，说明各作业的运行顺序，计算各作业的周转时间、带权周转时间，及平均周转时间、平均带权周转时间。
表2 HRF算法示例
这四个作业的调度采用 HRF 算法，过程如下:
■ 图 2 执行过程图
t=0时，只有作业J1到达，J1执行，直到t=20，作业J1执行结束。
t=20时，作业J1运行结束。作业J2、J3、J4都已到达后备队列，需要计算各作业的响应比。
R2=1+J2已等待时间/J2需运行时间＝1+15/15=2。
R3=1+J3已等待时间/J3需运行时间＝1+10/5=3。
R4=1+J4已等待时间/J4需运行时间＝1+5/10=1.5。
根据高响应比优先作业调度算法，作业J3的响应比R3最大，所以选择J3运行。
t=25时，作业J3运行结束。作业J2、J4的响应比如下：
R2=1+J2已等待时间/J2需运行时间＝1+(25-5)/15=2.3。
R4=1+J4已等待时间/J4需运行时间＝1+(25-15)/10=2。
根据高响应比优先作业调度算法，作业J2的响应比R3最大，所以选择J2运行。
t=40时，作业J2运行结束。作业J4开始运行，直到t=50作业J4运行结束。
因此，这四个作业的运行顺序为：J1→J3→J2→J4。
周转时间和带权周转时间分别为：
平均周转时间=(T1+T2+T3+T4)/4=(20+35+15+35)ms/4=26.25ms
平均带权周转时间=(W1+W2+W3+W4)/4=(1+2.33+3+3.5)=2.46
- 点赞
- 收藏
- 关注作者
评论（0）