常用作业调度算法的分析与评价

《常用作业调度算法的分析与评价》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第23卷第12期乐山师范学院学报Vol．23,No．122008年12月JournalofLeshanTeachersCollegeDec．2008常用作业调度算法的分析与评价12江志华齐文静（乐山师范学院1.数学系；2.计算机科学与信息工程系，四川乐山614004）摘要：调度算法是指根据系统的资源分配策略所规定的资源分配算法.本文详细地讨论了先来先服务调度算法、短作业优先调度算法、高优先级优先调度算法和高响应比优先调度算法等四种常用作业调度算法的基本思想，并结合实例对其进行了分析和评价.关键词

2、：作业调度算法；FCFS；SJF；HPF；HRN；平均周转时间中图分类号：TP202.7文献标识码：A文章编号：1009-8666（2008）12-0057-031．1.1周转时间T=T-T[1]0引言iciɑ周转时间指作业从提交到完成的时间所需的时间，具作业调度又称为高级调度或长程调度（long-term体包括驻外存等待调度时间、驻内存等待调度时间、执行scheduling），用于决定把外存上处于后备队列中的哪一个时间和阻塞时间.上试中Tic是作业的完成时间，Tiɑ是作业或者几个作业调入内存，

3、投入运行.因此有时也把作业调度的到达时间.就整个系统而言，主要是考虑其平均周转时称为接纳调度（AdmissionScheduling）.作业调度的策略通间，带权周转时间和平均带权周转时间.常有先来先服务（FCFS）、短作业优先（SJF）、高优先级优先n1（1）平均周转时间T=ΣΣTiΣ（HPF）、响应比高者优先算法（HRN）等.衡量和评价作业调ni=1度的性能可以从多个方面考虑.在文献[1]中，作者以系统是（2）带权周转时间W=Ti面向用户设计还是面向系统设计的准则衡量和评价调度Tsin算法的性

4、能.文献[4]中，作者利用泊松过程的基本理论，根（3）平均带权周转时间W=1ΣΣTiΣ据M/M/1排队模型对单道批处理系统作业调度模型加以ni=1Tsi分析，给出确定系统性能参数的计算方法，研究系统的处对于单个用户来说，都希望自己作业的周转时间最理能力和作业队列长度之间的关系，确定了一个批处理系短，但是作为计算机系统的管理者则希望平均周转时间最统的CPU主频.本文从用户、系统、作业响应时间、作业平短.平均周转时间越短，系统的效率就越高，这能使多数用均周转时间、系统吞吐量以及系统资源的使用率等方面

5、，户感到满意.分析与评价了四种作业调度算法的性能，详细阐述了各种1.1.2响应时间调度策略的优缺点，对在具体系统中调度策略的选择有一所谓响应时间，是指用户从键盘提交一个请求开始到定的指导意义.系统首次产生响应为止的时间.从用户的角度看，每个用户都希望自己的作业响应时间短，作业能够得到及时处理.1衡量算法的准则1.1．3截止时间的保证以及优先权准则.1.1面向用户的准则1.2面向系统的准则收稿日期：2008-06-12作者简介：江志华（1981-），男，湖北黄梅人，乐山师范学院数学系助教，电子科技

6、大学在读硕士研究生，研究方向：操作系统教学与研究，软件工程.571.2．1系统的吞吐量即单位时间完成的作业数，吞吐量越于饥饿状态，最终有可能被饿死.该算法完全未考虑作业的大系统的效率越高.紧迫程度和系统的实时性，不能保证紧迫性作业能够及时1.2．2处理机利用率Up.得到处理.另外一个不利的因素是由于作业的长短只是根Up=CPU有效工作时间/CPU总的运行时间据用户所提供的估计执行时间而定的，而用户又可能会有1.2.3各类资源的平衡利用.意或无意的缩短其作业的估计运行时间，致使该算法不一系统的吞吐

7、量越高，系统单位时间内完成的作业数就定能真正保证短作业优先得到调度.越多，说明系统中采用的作业调度算法效率高，系统效率2．3高响应比优先（HighestResponse-ratioNext）调度算法高；对于系统来说，好的是调度算法能提高处理机的利用2.3.1算法思想率，能够平衡使用系统的各类资源.先给出计算响应比Rp的方法：上述要求往往是互相矛盾的，例如，为了提高吞吐量，R=1+等待时间/需要服务时间[2]p应优先考虑运行短作业，这样有利于提高单位时间内完成HRN是在调度作业时选择后备队列中那些

8、Rp最高的的作业个数；而为了提高CPU的使用率则优先考虑长作作业投入运行.当一个作业执行完成，需要从后备队列中调业，因为频繁的作业交替会增加CPU的无效开销.因此，作入作业进内存的时候，后备队列中作业的Rp需要重新计业调度算法的选择要从不同系统的设计目标出发，对上述算.要求有所侧重.2.3.2算法的分析与评价2四种常用作业调度算法的分析与由响应比Rp的计算公式可以看出，一个作业的Rp会随着它的等待时间的增加而增加.因此一个作业只要它的评价等待时间足够长，它总会由于响应比的提高而获得运行的2.1先