《【2017年整理】处理机调度算法的比较》由会员分享，可在线阅读，更多相关《【2017年整理】处理机调度算法的比较（5页珍藏版）》请在金锄头文库上搜索。
1、处理机调度算法的比较计算机科学学院 计算机科学与技术 2009摘要：处理机调度基本概念、调度算法优劣的评价准则、多种处理机调度算法的介绍引言操作系统是处理计算机硬件的一层软件和作为计算机用户与计算机硬件的中间的协调者。操作系统的 CPU 调度器负责给各个任务分发 CPU 带宽资源。调度算法负责管理当前执行任务等额顺序和性能 3 内容：3.1 处理机调度的基本概念高/中/低级调度1. 高级调度（作业调度）决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，准备执行。2. 低级调度（进程调度）决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程
2、的具体操作。非抢占方式和抢占方式3. 中级调度决定把又具备运行条件的挂起进程重新调入内存，挂到就绪队列上，准备执行。3.2 调度算法优劣的评价准则衡量和比较调度算法性能优劣主要有一下几个因素： （1）CPU 利用率。CPU 是计算机系统中最重要的资源，所以应尽可能使 CPU 保持忙，使这一资源利用率最高。 （2）吞吐量。CPU 运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的作业数目来描述的，这就叫吞吐量。 （3）周转时间。指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。 （4）等待时间。处理机调度算法实际
3、上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常简单的考察等待时间。 （5）响应时间。指从作业提交到系统作出相应所经过的时间。在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即相应时间。从用户观点看，响应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。（6）公平性确保每个用户每个进程获得合理的 CPU 份额或其他资源份额，不会出现饿死情况。 当然，这些目标本身就存在着矛盾之处，操作系统在设计时必须根据其类型的不同进行权衡，以达到较好的效果。下面着重看一下批处理系统的调度性能指标。批处理系统
4、的调度性能主要用作业周转时间和作业带权周转时间来衡量，此时间越短，则系统效率越高，作业吞吐能率越强。如果作业i 提交给系统的时刻是ts，完成时刻是tf，那么，作业的周转时间ti 为：ti =tf - ts实际上，它是作业在系统里的等待时间与运行时间之和。从操作系统来说，为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权作业周转时间最小。平均作业周转时间 T = （ti） / n如果作业i 的周转时间为ti，所需运行时间为tk，则称wi=ti /tk 为该作业的带权周转时间。因为，ti 是等待时间与运行时间之和，故带权周转时间总大于1。平均作业带权周转时间W = （wi） / n通常
5、，用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们呈现的调度性能；用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算法时，它们呈现的调度性能。这两个数值均越小越好。3.3 几种处理机调度算法详细介绍3.3.1 作业调度1、先来先服务算法先来先服务 FCFS（First Come，First Served ）算法是按照作业进入系统的作业后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选。这是一种非剥夺式算法，容易实现，但效率不高，只顾及到作业等候时间，而没考虑作业要求服务时间的长短。显然这不利于短作业而优待了长作业，或者说有利于 CPU 繁忙型作业而不利于 I/O
6、繁忙型作业。有时为了等待长作业的执行，而使短作业的周转时间变得很大。从而，平均周转时间也变大。2、最短作业优先算法最短作业优先 SJF（Shortest Job First ）算法是以进入系统的作业所要求的 CPU时间长短为标准，总是选取估计计算时间最短的作业投入运行。这是一种非剥夺式调度算法，它克服了 FCFS 偏爱长作业的缺点，易于实现，但效率也不高。它的主要弱点：一是需要预先知道作业所需的 CPU 时间，这个估计值很难精确，如果程序员估计过低，系统就可能提前终止该作业；二是忽视了作业等待时间，由于系统不断地接受新作业，而作业调度又总是选择计算时间短的作业投入运行，因此，使进入系统时间早但
7、计算时间长的作业等待时间过长，会出现饥饿现象；三是尽管减少了对长作业的偏爱，但由于缺少剥夺机制，对分时、实时处理仍然很不理想。3、响应比最高者优先（HRRF）算法先来先服务算法与最短作业优先算法都是比较片面的调度算法。先来先服务算法只考虑作业的等候时间而忽视了作业的计算时间，而最短作业优先算法恰好与之相反，它只考虑用户估计的作业计算时间而忽视了作业的等待时间。响应比最高者优先算法（Highest Response Ratio First）是介乎这两种算法之间的一种折衷的策略，既考虑作业等待时间，又考虑作业的运行时间，这样既照顾了短作业又不使长作业的等待时间过长，改进了调度性能。缺点是每次计算各
8、道作业的响应比会有一定的时间开销，需要估计期待的服务时间，性能要比 SJF 略差。这里把作业进入系统后的等待时间与估计计算时间之和称为作业的响应时间，作业的响应时间除以作业估计计算时间称作响应比，现定义：响应比作业响应时间/作业估计计算时间=1+作业等待时间/作业估计计算时间每当调度一个作业运行时，都要计算后备作业队列中每个作业的响应比，选择响应比最高者投入运行。显然，计算时间短的作业容易得到较高的响应比，因为，这时分母较小，使得 HRRF 较高，因此，本算法是优待短作业的。但是，如果一个长作业在系统中等待的时间足够长后，由于，它的年龄较大使得分子足够大，则 HRRF 较大，那么，它也将获得足
9、够高的响应比，从而，可以被选中执行，不至于长时间地等待下去，饥饿的现象不会发生。4、优先数法这种算法是根据确定的优先数来选取作业，每次总是选择优先数高的作业。规定用户作业优先数的方法是多种多样的。一种是由用户自己提出作业的优先数，称作外部优先数法。有的用户为了自己的作业尽快的被系统选中就设法提高自己作业的优先数，这时系统可以规定优先数越高则需付出的计算机使用费就越多，以作限制。另一种是由系统综合考虑有关因素来确定用户作业的优先数，称作内部优先数法。5、分类调度算法分类调度算法预先按一定的原则把作业划分成若干类，以达到均衡使用操作系统资源和兼顾大小作业的目的。分类原则包括：作业计算时间、对内存的
10、需求、对外围设备的需求等。作业调度时还可以为每类作业设置优先级，从而，照顾到同类作业中的轻重缓急。6、用磁带与不用磁带的作业搭配这种算法将需要使用磁带机的作业分开来。在作业调度时，把使用磁带机的作业和不使用磁带机的作业搭配挑选。在不使用磁带机的作业执行时，可预先通知操作员将下一批作业要用的磁带预先装上，这样可使要用磁带机的作业在执行时省去等待装磁带的时间。显然，这对缩短系统的平均周转时间是有益的。3.3.2 低级调度1、先来先服务算法先来先服务算法是按照进程进入就绪队列的先后次序来分配处理器。先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行下去直到运行结束或被阻塞，这是一种非剥
11、夺式调度。这种算法容易实现，但效率不高，显然，不利于 I/O频繁的进程。2、时间片轮转调度轮转法调度也称之为时间片调度，具体做法是调度程序每次把 CPU 分配给就绪队列首进程使用一个时间片，例如 100ms，就绪队列中的每个进程轮流地运行一个这样的时间片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，就表明该进程连续运行的时间已超过一个规定的时间片。此时，中断处理程序就通知处理器调度进行处理器的切换工作。这种调度策略可以防止那些很少使用外围设备的进
12、程过长的占用处理器，导致要使用外围设备的那些进程没有机会去启动外围设备。最常用的轮转法是基本轮转法。它要求每个进程轮流地运行相同的一个时间片。在分时系统中，这是一种较简单又有效的调度策略。个分时系统有许多终端设备，终端用户在各自的终端设备上同时使用计算机，如果某个终端用户的程序长时间的占用处理器，势必使其他终端用户的要求不能得到及时响应。一般说分时系统的终端用户提出要求后到计算机响应给出回答的时间只能是几秒钟，这样才能使终端用户感到满意。采用基本轮转的调度策略可以使系统及时响应。例如，一个分时系统有 10 个终端，如果每个终端用户进程的时间片为 100ms，那么，粗略地说，每个终端用户在每秒钟
13、内可以得到大约 100ms 的处理器时间，如果对于终端用户的每个要求，处理器花费 300ms 的时间就可以给出回答时，那么，终端响应的时间大致就在 3 秒左右，这样可算得上及时响应了。基本轮转法的策略可以略加修改。例如，对于不同的进程给以不同的时间片；时间片的长短可以动态地修改等等，这些做法主要是为了进一步提高效率。轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大，这个开销与时间片的大小很有关系。如果时间片取值太小，以致于大多数进程都不可能在一个时间片内运行完毕，切换就会频繁，系统开销显著增大，所以，从系统效率来看，时间片取大一点好。另一方面，时间片长度较大，那么，随着就绪队列里进
14、程数目的增加，轮转一次的总时间增大，亦即对每个进程的响应速度放慢了，甚至时间片大到让每个进程足以完成其所有任务，这一算法便退化成先来先服务算法。为了满足用户对响应时间的要求，要么限制就绪队列中的进程数量，要么采用动态时间片法，根据当前负载状况，及时调整时间片的大小。所以，时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等多方面考虑。3、优先数调度给每一个进程确定一个优先数，处理器调度每次选择就绪进程中优先数最大者，让它占用处理器运行称优先数调度。怎样确定优先数呢?可以有以下几种考虑，使用外围设备频繁者优先数大，这样有利于提高效率；重要算题进程的优先数大，这样有利于用户更早得到计算结果
15、；进入计算机时间长的进程优先数大，这样有利于缩短作业的周转时间；交互式用户的进程优先数大，这样有利于终端用户的响应时间等等，以上采用了静态优先数法。效率高性能好的低级调度可采用动态优先数法，在创建一个进程时，根括进程类型和资源使用情况确定一个优先数，而当进程耗尽时间片或重新被调度时，再次计算并调整所有进程的优先数。基本原则是：根据进程占有 CPU 时间多少来决定，当一个进程占有 CPU 时间愈长，那么，在它被阻塞之后再次获得调度的优先数就越低，反之，进程获得调度的可能性越大；根据进程等待 CPU 时间多少来决定，一个进程在队列中等待 CPU 的时间愈长，那么，在它再次获得调度时的优先数就越高，
16、反之，进程获得调度的可能性越小。基于优先数的低级调度算法可以按调度方式不同分为剥夺式和非剥夺式优先数调度算法。4、多级反馈队列调度多级反馈队列调度这种方法又称反馈循环队列或多队列策略。其主要思想是将就绪进程或线程分为两级或多级，系统相应建立两个或多个就绪队列，较高优先级的队列一般分配给较短的时间片。处理器调度每次先从高一级的就绪进程队列中选取可占有处理器的进程，同一队列中按先来先服务原则排队，只有在选不到时，才从较低一级的就绪进程队列中选取。5、保证调度算法一种完全不同的调度算法是向用户做出明确的性能保证，然后去实现它，称保证调度算法。一种很实际并很容易实现的保证是：当你工作时己有 n 个用户登录在系统，则你将获得 CPU 处理能力的 1/n。类似地，如果在一个有 n 个进程运行的用户系统中，每个进程将获得 CPU 处理能力的 1/n。为了实现所作的保证，系统必须跟踪各个进程自创建以来已经使用了多少 CPU 时间。然后，计算各个进程应获得的 CPU 时间，即自创建以来的时间除以 n。由于各个进程实际获得的 CPU 时间已知，所以，很容
