处理机调度算法的比较.docVIP

处理机调度算法的比较 计算机科学学院 计算机科学与技术 2009 摘要：处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍 引言 操作系统是处理计算机硬件的一层软件和作为计算机用户与计算机硬件的中间的协调者。操作系统的CPU调度器负责给各个任务分发CPU带宽资源。调度算法负责管理当前执行任务等额顺序和性能 3 内容： 3.1 处理机调度的基本概念 高/中/低级调度 1. 高级调度（作业调度） 决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，准备执行。 2. 低级调度（进程调度） 决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。 非抢占方式和抢占方式 3. 中级调度 决定把又具备运行条件的挂起进程重新调入内存，挂到就绪队列上，准备执行。 衡量和比较调度算法性能优劣主要有一下几个因素： 　　（1）CPU利用率。CPU是计算机系统中最重要的资源，所以应尽可能使CPU保持忙，使这一资源利用率最高。 　　（2）吞吐量。CPU运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的作业数目来描述的，这就叫吞吐量。 　　（3）周转时间。指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。 　　（4）等待时间。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常简单的考察等待时间。 （5）响应时间。指从作业提交到系统作出相应所经过的时间。在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即相应时间。从用户观点看，响应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。 CPU 份额或其他资源份额，不会出现饿死情况。 当然，这些目标本身就存在着矛盾之处，操作系统在设计时必须根据其类型的不 同进行权衡，以达到较好的效果。下面着重看一下批处理系统的调度性能指标。 批处理系统的调度性能主要用作业周转时间和作业带权周转时间来衡量，此时间 越短，则系统效率越高，作业吞吐能率越强。如果作业i 提交给系统的时刻是ts，完成 时刻是tf，那么，作业的周转时间ti 为： ti =tf - ts 实际上，它是作业在系统里的等待时间与运行时间之和。从操作系统来说，为了 提高系统的性能，要让若干个用户的平均作业周转时间和平均带权作业周转时间最小。 平均作业周转时间 T = （Σti） / n 如果作业i 的周转时间为ti，所需运行时间为tk，则称wi=ti /tk 为该作业的带权周 转时间。因为，ti 是等待时间与运行时间之和，故带权周转时间总大于1。 平均作业带权周转时间W = （Σwi） / n 通常，用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们 呈现的调度性能；用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算 法时，它们呈现的调度性能。这两个数值均越小越好。 3.3几种处理机调度算法详细介绍 3.3.1作业调度 1、先来先服务算法 先来先服务FCFS（First Come，First Served）算法是按照作业进入系统的作业 后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选。这是一种非剥夺式 算法，容易实现，但效率不高，只顾及到作业等候时间，而没考虑作业要求服务时间 的长短。显然这不利于短作业而优待了长作业，或者说有利于CPU 繁忙型作业而不利 于I/O 繁忙型作业。有时为了等待长作业的执行，而使短作业的周转时间变得很大。 从而，平均周转时间也变大。 2、最短作业优先算法 最短作业优先SJF（Shortest Job First ）算法是以进入系统的作业所要求的CPU 时间长短为标准，总是选取估计计算时间最短的作业投入运行。这是一种非剥夺式调 度算法，它克服了FCFS 偏爱长作业的缺点，易于实现，但效率也不高。它的主要弱 点：一是需要预先知道作业所需的CPU 时间，这个估计值很难精确，如果程序员估计 过低，系统就可能提前终止该作业；二是忽视了作业等待时间，由于系统不断地接受 新作业，而作业调度又总是选择计算时间短的作业投入运行，因此，使进入系统时间 早但计算时间长的作业等待时间过长，会出现饥饿现象；三是尽管减少了对长作业的 偏爱，但由于缺少剥夺机制，对分时、实时处理仍然很不理想。 3、响应比最高者优先（HRRF）算法 先来先服务算法与最短作业优先算法都是比较片面的调度算法。先来先服务算法 只考虑作业的等候时间而忽视了作业的计算时间，而最短作业优先算法恰好与之相反， 它只考虑用户估计的作业计算时间而忽视了作业的等待时间。响应比