《第4章调度.ppt》由会员分享，可在线阅读，更多相关《第4章调度.ppt（75页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 4 4 处理机调度处理机调度 在多道程序系统中，进程数目往往多在多道程序系统中，进程数目往往多于处理机数目。要求系统能按某种算法，于处理机数目。要求系统能按某种算法，动态地把处理机分配给就绪队列中的进程，动态地把处理机分配给就绪队列中的进程，使之执行。而系统的运行性能，如吞吐量使之执行。而系统的运行性能，如吞吐量地大小、周转时间的长短、响应的及时性地大小、周转时间的长短、响应的及时性等，在很大程度上都取决于处理机调度。等，在很大程度上都取决于处理机调度。1本章的主要内容本章的主要内容本章的主要内容本章的主要内容:w作业调度作业调度作业调度作业调度;w进程调度进程调度进程调度进程调度;w调度算
2、法调度算法调度算法调度算法;2 3.1 3.1 处理机调度的基本概念处理机调度的基本概念高级调度高级调度高级调度高级调度中级调度中级调度低级调度低级调度多处理机调度多处理机调度3作业的状态及其转换作业的状态及其转换如图所示，一个作业从提交给计算机系统到执行结束如图所示，一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成等退出系统，一般都要经历提交、收容、执行和完成等4个状态。个状态。4图图4.1作业的状态及其转换作业的状态及其转换5 3.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度1 1 作业调度作业调度 又称为又称为高级调度高级调度或长程调度或长
3、程调度(long-term(long-term scheduling),scheduling),用于决定把外存上处于后备队列中的用于决定把外存上处于后备队列中的作业调入内存，并为他们创建进程、分配必要的资作业调入内存，并为他们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准源，然后，再将新创建的进程排在就绪队列上，准备执行。备执行。作业作业:用户提交给系统处理的一个任务用户提交给系统处理的一个任务.包括用包括用户程序户程序数据数据对程序运行进行控制和处理有关的对程序运行进行控制和处理有关的信息信息.分为批处理作业和终端型作业分为批处理作业和终端型作业.6 每次执行作业调度时，
4、都需作出以下两个每次执行作业调度时，都需作出以下两个决定：决定：接纳多少个作业接纳多少个作业:取决于系统的多道程序取决于系统的多道程序度度.接纳哪些作业接纳哪些作业:取决于系统调度算法：先取决于系统调度算法：先来先服务来先服务,优先级优先级,响应比等响应比等.72 2进程调度进程调度 又称为又称为低级调度低级调度（low level Schedulinglow level Scheduling）或或短程调度短程调度.它决定就绪队列中的哪个进程将获得处它决定就绪队列中的哪个进程将获得处理机，然后分派程序执行把处理机分派给该进程的理机，然后分派程序执行把处理机分派给该进程的操作。可分为两种方式：操
5、作。可分为两种方式：非抢占方式（非抢占方式（Non-Non-preemaptivepreemaptive Mode Mode）:一旦把处理机分配给进程后便让该进程一直执一旦把处理机分配给进程后便让该进程一直执行行,直至完成或发生事件而被阻塞时直至完成或发生事件而被阻塞时,才再把处理机才再把处理机分配给其它进程分配给其它进程,不允许某进程抢占已经分配出去不允许某进程抢占已经分配出去的处理机的处理机.优点优点:简单简单,系统开销小系统开销小,适合在批处理系统环境适合在批处理系统环境.缺点缺点:实时性差实时性差.8抢占方式（抢占方式（Preemptive ModePreemptive Mode）:允
6、许调度程序根据某种原则去停止某个正允许调度程序根据某种原则去停止某个正在执行的进程，将已分配的处理机重新分配给在执行的进程，将已分配的处理机重新分配给另一进程另一进程.抢占原则抢占原则:a.a.优先权原则优先权原则.b.b.短作业（进程）优先原则短作业（进程）优先原则.c.c.时间片原则时间片原则.9 3 3 交换调度交换调度 又称为又称为中级调度中级调度（Intermediate-Level Intermediate-Level Scheduling Scheduling）。目的是提高内存的利用率和系。目的是提高内存的利用率和系统吞吐量。统吞吐量。操作是将暂时不能运行的进程从内存中调到操作是
7、将暂时不能运行的进程从内存中调到外存上去，该进程为外存就绪或外存挂起状态。外存上去，该进程为外存就绪或外存挂起状态。当这些进程重又具备运行条件、且内存又有空闲当这些进程重又具备运行条件、且内存又有空闲时，时，由中级调度来决定将外存上具备运行的就绪由中级调度来决定将外存上具备运行的就绪进程重新从外存调入到内存，修改状态为就绪，进程重新从外存调入到内存，修改状态为就绪，等待进程调度。等待进程调度。10在多道批处理系统中，存在着作业调度和在多道批处理系统中，存在着作业调度和进程调度。但是，一般来说，在进程调度。但是，一般来说，在纯粹的分时系纯粹的分时系统和实时系统统和实时系统中，一般中，一般不存在作
8、业调度不存在作业调度，而只，而只有进程调度、交换调度。这是因为在分时系统有进程调度、交换调度。这是因为在分时系统和实时系统中，为了缩短响应时间或为了满足和实时系统中，为了缩短响应时间或为了满足用户需求的截止时间，作业不是建立在外存，用户需求的截止时间，作业不是建立在外存，而是直接建立在内存中。在这些系统中，一旦而是直接建立在内存中。在这些系统中，一旦用户和系统的交互开始，用户马上要进行控制。用户和系统的交互开始，用户马上要进行控制。因而，这些系统中没有作业提交状态和后备状因而，这些系统中没有作业提交状态和后备状态。它们的输入信息经过终端缓冲区为系统所态。它们的输入信息经过终端缓冲区为系统所接收
9、，或者立即处理或者经交换调度暂存外存接收，或者立即处理或者经交换调度暂存外存中。中。但也不是绝对的，取决于设备的运行速度但也不是绝对的，取决于设备的运行速度!11在这三种调度方式中：在这三种调度方式中：进程调度的运行频率最高：分时系统中进程调度的运行频率最高：分时系统中10-10010-100msms进行一次进程调度，所以进程调度算法不能太复进行一次进程调度，所以进程调度算法不能太复杂，不能占用太多杂，不能占用太多CPUCPU时间。时间。作业调度往往发生在一个批处理作业运行完毕，作业调度往往发生在一个批处理作业运行完毕，作业调度的周期较长，大约几分钟。作业调度的周期较长，大约几分钟。中级调度介
10、于以上两者之间。中级调度介于以上两者之间。12同时具有三种调度方式的调度队列模型同时具有三种调度方式的调度队列模型133.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则可分为面向用户和面向系统的准则：可分为面向用户和面向系统的准则：1 1 面向用户准则：面向用户准则：（1 1）具有公平性。）具有公平性。（2 2）周转时间短周转时间短(周转时间与平均周转时间概念周转时间与平均周转时间概念).).带权周转时间带权周转时间:作业的周转时间与系统为它实作业的周转时间与系统为它实 际服务时间之比际服务时间之比.(.(大于等于大于等于1,1,越小越好越小越好)（3 3）响应时间快
11、）响应时间快(响应时间概念响应时间概念).).（4 4）截止时间的保证）截止时间的保证(截止时间概念截止时间概念).).（5 5）优先权准则）优先权准则.14 2 2 面向系统准则：面向系统准则：(1)(1)系统吞吐量系统吞吐量.(2)(2)处理机利用率好处理机利用率好.(3)(3)各类资源的平衡利用各类资源的平衡利用.由于这些目标的相互冲突，任一调由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不度算法要想同时满足上述目标是不可能的。可能的。15必须指出，如果考虑的因素过多，调度算法就会变得必须指出，如果考虑的因素过多，调度算法就会变得非常复杂。其结果是系统开销增加，资源利用率下降
12、。非常复杂。其结果是系统开销增加，资源利用率下降。因此，大多数操作系统都根据用户需要，采用兼顾某因此，大多数操作系统都根据用户需要，采用兼顾某些目标的简单调度算法。些目标的简单调度算法。那么，怎样来衡量一个作业调度算法是否满足系统设那么，怎样来衡量一个作业调度算法是否满足系统设计的要求呢？对于批处理系统，由于主要用于计算，计的要求呢？对于批处理系统，由于主要用于计算，对于作业的周转时间要求较高。因此，对于作业的周转时间要求较高。因此，作业的平均周作业的平均周转时间或平均带权周转时间，被作为衡量调度算法优转时间或平均带权周转时间，被作为衡量调度算法优劣的标准。但是，对于分时系统和实时系统来说，外
13、劣的标准。但是，对于分时系统和实时系统来说，外加平均响应时间被作为衡量调度策略优劣的标准。加平均响应时间被作为衡量调度策略优劣的标准。161.1.周转时间周转时间：作业作业i的周转时间的周转时间Ti为为Ti=Tei-Tsi其中其中Tei为作业为作业i的完成时间，的完成时间，Tsi为作业的提交时间。为作业的提交时间。对于被测定作业流所含有的对于被测定作业流所含有的n（n=1）个作业来说，个作业来说，其平均周转时间为：其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留的时一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间；执行时间，即：间，包含两部分：等待时间；执行时
14、间，即：Ti=TwiTri这里，这里，Twi主要指作业主要指作业i由后备状态到执行状态的等待由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。时间，它不包括作业进入执行状态后的等待时间。172.2.带权周转时间带权周转时间作业的周转时间包含了两个部分，即等待时间和执行作业的周转时间包含了两个部分，即等待时间和执行时间。为了更进一步反映调度性能，使用带权周转时时间。为了更进一步反映调度性能，使用带权周转时间的概念。带权周转时间是作业周转时间与作业执行间的概念。带权周转时间是作业周转时间与作业执行时间的比：时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平均
15、带对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：权周转时间为：对于分时系统，除了要保证系统吞吐量大、资源利用对于分时系统，除了要保证系统吞吐量大、资源利用率高之外，还应保证有用户能够容忍的响应时间。因率高之外，还应保证有用户能够容忍的响应时间。因此，在分时系统中，仅仅用周转时间或带权周转时间此，在分时系统中，仅仅用周转时间或带权周转时间来衡量调度性能是不够的。来衡量调度性能是不够的。184.4调调度度算算法法本节讨论各种常用的进程调度算法和作业调度算法。本节讨论各种常用的进程调度算法和作业调度算法。1.先来先服务（先来先服务（FCFS）调度算法调度算法它根据进程进入就绪队列的先后
16、次序来分配处它根据进程进入就绪队列的先后次序来分配处理机，实现的是理机，实现的是非剥夺调度方式非剥夺调度方式。当一个进程获得处。当一个进程获得处理机并运行后，它将一直占用处理机，直到该进程完理机并运行后，它将一直占用处理机，直到该进程完成其任务，或因等待某个事件或资源而不能继续运行成其任务，或因等待某个事件或资源而不能继续运行时才释放处理机。时才释放处理机。直观看，该算法在一般意义下是公平的。即每直观看，该算法在一般意义下是公平的。即每个作业或进程都按照它们在队列中等待时间长短来决个作业或进程都按照它们在队列中等待时间长短来决定它们是否优先享受服务。定它们是否优先享受服务。不过对于那些执行时间
17、较不过对于那些执行时间较短的作业或进程来说，如果它们在某些执行时间很长短的作业或进程来说，如果它们在某些执行时间很长的作业或进程之后到达，则它们将等待很长时间的作业或进程之后到达，则它们将等待很长时间。19在实际操作系统中，尽管很少单独使用在实际操作系统中，尽管很少单独使用FCFS算法，算法，但和其他一些算法配合起来，但和其他一些算法配合起来，FCFS算法还是使用得算法还是使用得相当多的。例如基于优先级的调度算法就是对具有同相当多的。例如基于优先级的调度算法就是对具有同样优先级的作业或进程采用的样优先级的作业或进程采用的FCFS方式。方式。2.轮转法（轮转法（roundrobin）轮转法的基本
18、思路是让每个进程在就绪队列中的等待轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。轮转法的基本概念是时间与享受服务的时间成比例。轮转法的基本概念是将将CPU的处理时间分成固定大小的时间片。如果一个的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。同时而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进，进程调度程序又去调度当前
19、就绪队列中的第一个进程或作业。轮转法的原理见图程或作业。轮转法的原理见图4.4。20图图4.4轮转法调度轮转法调度显然，轮转法只能用来显然，轮转法只能用来调度分配那些可以抢占的资源调度分配那些可以抢占的资源。将它们随时剥夺再分配给别的进程。将它们随时剥夺再分配给别的进程。CPU是可抢占资是可抢占资源的一种。但如打印机等资源是不可抢占的。由于作源的一种。但如打印机等资源是不可抢占的。由于作业调度是对除了业调度是对除了CPU之外的所有系统硬件资源的分配之外的所有系统硬件资源的分配，其中包含有不可抢占资源，所以，其中包含有不可抢占资源，所以作业调度不使用轮作业调度不使用轮转法。转法。21在轮转法中，
20、在轮转法中，时间片长度的选取非常重要时间片长度的选取非常重要。首先，时。首先，时间片长度的选择会直接影响系统开销和响应时间。如间片长度的选择会直接影响系统开销和响应时间。如果时间片长度过短，则调度程序剥夺处理机的次数增果时间片长度过短，则调度程序剥夺处理机的次数增多。这将使进程上下文切换次数也大大增加，从而加多。这将使进程上下文切换次数也大大增加，从而加重系统开销。反过来，如果时间片长度选择过长，比重系统开销。反过来，如果时间片长度选择过长，比方说一个时间片能保证就绪队列中所需执行时间最长方说一个时间片能保证就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务法。的进程能执行完
21、毕，则轮转法变成了先来先服务法。时间片长度时间片长度q的选择是根据系统对响应时间的要求的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数和就绪队列中所允许的最大进程数Nmax确定的。它确定的。它可表示为：可表示为：q=R/Nmax22在在q为常数的情况下，如果就绪队列中的进程数发生为常数的情况下，如果就绪队列中的进程数发生远小于远小于Nmax的变化，则响应时间的变化，则响应时间R看上去会大大减看上去会大大减小。但是，就系统开销来说，由于小。但是，就系统开销来说，由于q值固定，从而进值固定，从而进程上下文切换的时机不变，系统开销也不变。通常，程上下文切换的时机不变，系统开销也不变。
22、通常，系统开销也是处理机执行时间的一部分。系统开销也是处理机执行时间的一部分。CPU的整个的整个执行时间等于各进程执行时间加上系统开销。在进程执行时间等于各进程执行时间加上系统开销。在进程执行时间大幅度减少的情况下，如果系统开销也随之执行时间大幅度减少的情况下，如果系统开销也随之减少的话，系统的响应时间有可能更好一点。例如，减少的话，系统的响应时间有可能更好一点。例如，在一个用户进程的情况下，如果在一个用户进程的情况下，如果q值增大到足够该进值增大到足够该进程执行完毕的话，则进程调度所引起的系统开销就没程执行完毕的话，则进程调度所引起的系统开销就没有了。有了。一种可行的办法是，每当一轮调度开始
23、时，系一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次统便根据就绪队列中已有进程数目计算一次q值，作值，作为新一轮调度的时间片。这种方法得到的时间片随就为新一轮调度的时间片。这种方法得到的时间片随就绪队列中的进程数变化。绪队列中的进程数变化。23 在实际的计算机系统中在实际的计算机系统中,不少都配置了几种不少都配置了几种类型的操作系统类型的操作系统,既有批处理型作业既有批处理型作业,又有处理又有处理交互型作业的分时操作系统交互型作业的分时操作系统,前台交互型进程采前台交互型进程采用时间片轮转调度算法用时间片轮转调度算法,后台批处理型作业的进后台批处理型作业的进程会
24、采用优先权高者优先的算法程会采用优先权高者优先的算法.根据作业的性质或类型的不同根据作业的性质或类型的不同,将就绪进程将就绪进程队列再分为若干个独立子队列队列再分为若干个独立子队列,每个队列采用一每个队列采用一种算法种算法,不同的队列采用不同的调度算法不同的队列采用不同的调度算法.3 3 多级反馈轮转算法多级反馈轮转算法24256-263多级反馈轮转算法多级反馈轮转算法实施过程实施过程：（1）在系统中设置多个就绪进程队列，每个队）在系统中设置多个就绪进程队列，每个队列对应一个调度级别或优先级，第一个队列的优列对应一个调度级别或优先级，第一个队列的优先级最高，以下各个队列的优先级逐次降低。先级最
25、高，以下各个队列的优先级逐次降低。（2）赋予各个就绪队列中的进程以不同的时间）赋予各个就绪队列中的进程以不同的时间片。优先级越高的就绪队列中的进程所分得的时片。优先级越高的就绪队列中的进程所分得的时间片越小，优先级越低的进程所分得的时间片越间片越小，优先级越低的进程所分得的时间片越大，通常优先级每低一级，队列中进程所分得的大，通常优先级每低一级，队列中进程所分得的时间片就增加一倍，如第时间片就增加一倍，如第k+1队列中的进程所分队列中的进程所分得的时间片是第得的时间片是第k队列中进程的两倍。所以，进程队列中进程的两倍。所以，进程的优先级降低了，但其获得的时间片却增加了。的优先级降低了，但其获得
26、的时间片却增加了。进程调度算法6-27多级反馈队列调度算法多级反馈队列调度算法（3）每个队列按先来先服务的原则排序。）每个队列按先来先服务的原则排序。（4）当一个新进程进入内存后，首先将它排在第）当一个新进程进入内存后，首先将它排在第一个队列的尾部等候调度。该队列中的进程按先一个队列的尾部等候调度。该队列中的进程按先来先服务的原则分配处理机，并在规定的时间片来先服务的原则分配处理机，并在规定的时间片内运行。如一个进程被调度、并在规定的时间片内运行。如一个进程被调度、并在规定的时间片内执行完毕，该进程就可准备撤离系统；如该进内执行完毕，该进程就可准备撤离系统；如该进程尚未执行完毕，但需要等待某事
27、件的发生而主程尚未执行完毕，但需要等待某事件的发生而主动让出处理机，则该进程移入相应的等待队列；动让出处理机，则该进程移入相应的等待队列；如进程用完给定的时间片后仍未执行完毕，则进如进程用完给定的时间片后仍未执行完毕，则进程调度程序将该进程移入下一级队列的尾部去等程调度程序将该进程移入下一级队列的尾部去等待，而将处理机分配给同队列中的下一个就绪进待，而将处理机分配给同队列中的下一个就绪进程。程。进程调度算法6-28多级反馈队列调度算法多级反馈队列调度算法（5）只有当第一个就绪队列为空时，调度程序才）只有当第一个就绪队列为空时，调度程序才去调度第二个队列中的就绪进程，依次类推，只去调度第二个队列
28、中的就绪进程，依次类推，只有当第有当第1队列到第队列到第k队列为空时，调度程序才去调队列为空时，调度程序才去调度第度第k+1队列中的就绪进程。队列中的就绪进程。（6）当第）当第k队列中的一个进程正在运行时，如果队列中的一个进程正在运行时，如果出现了一个优先级更高的就绪进程，则调度程序出现了一个优先级更高的就绪进程，则调度程序将暂停正在运行的进程，并将它移入到第将暂停正在运行的进程，并将它移入到第k队列的队列的尾部去等待，同时把处理机分配给新出现的更高尾部去等待，同时把处理机分配给新出现的更高优先级的进程去运行。优先级的进程去运行。进程调度算法6-29(2)(2)调度性能调度性能:能够满足各种类
29、型用户的需要能够满足各种类型用户的需要:终端型作业终端型作业:交互作业交互作业,作业通常较短小作业通常较短小,系统只系统只要能估计适合的时间片大小使作业要能估计适合的时间片大小使作业(进程进程)在第一在第一队列所规定的时间片完成队列所规定的时间片完成,便能满足用户便能满足用户.短批处理作业用户短批处理作业用户:通常会在第一或第二队列完通常会在第一或第二队列完成成,其周转时间仍然较短其周转时间仍然较短.长批处理作业长批处理作业:依次按不同的队列和不同的时间依次按不同的队列和不同的时间片直到完成片直到完成,用户不必担心其作业得不到处理用户不必担心其作业得不到处理.6-30 UNIXUNIX和和OS
30、/2OS/2操作系统采用了该调度算法操作系统采用了该调度算法.该调度算法是目前公认得较好的一种调度算该调度算法是目前公认得较好的一种调度算法法.4.优先级法优先级法优先级法可被用作作业或进程的调度策略。首先，系优先级法可被用作作业或进程的调度策略。首先，系统或用户按某种原则为作业或进程指定一个优先级来统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。该算法的核表示该作业或进程所享有的调度优先权。该算法的核心是确定进程或作业的优先级。心是确定进程或作业的优先级。31确定优先级的方法可分为静态法和动态法。静态法根确定优先级的方法可分为静态法和动态法。静态法根据作业或
31、进程的静态特性，在作业或进程开始执行之据作业或进程的静态特性，在作业或进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改前就确定它们的优先级，一旦开始执行之后就不能改变。动态法则不然，它把作业或进程的静态特性和动变。动态法则不然，它把作业或进程的静态特性和动态特性结合起来确定作业或进程的优先级，随着作业态特性结合起来确定作业或进程的优先级，随着作业或进程的执行过程，其优先级不断变化。或进程的执行过程，其优先级不断变化。静态优先级静态优先级作业调度中的静态优先级大多按以下原则确定：作业调度中的静态优先级大多按以下原则确定：(1)由用户自己根据作业的紧急程度输入一个适当的由用户自己根据作
32、业的紧急程度输入一个适当的优先级。为防止各用户都将自己的作业冠以高优先级，优先级。为防止各用户都将自己的作业冠以高优先级，系统应对高优先级用户收取较高的费用。系统应对高优先级用户收取较高的费用。(2)由系统或操作员根据作业类型指定优先级。作业由系统或操作员根据作业类型指定优先级。作业类型一般由用户约定或由操作员指定。例如：可将作类型一般由用户约定或由操作员指定。例如：可将作业分为：业分为：32IO繁忙的作业，繁忙的作业，CPU繁忙的作业，繁忙的作业，IO与与CPU均衡的作业，均衡的作业，一般作业，等等。一般作业，等等。系统或操作员可以给每类作业指定不同的优先级。系统或操作员可以给每类作业指定不
33、同的优先级。(3)系统根据作业要求资源情况确定优先级。例如根系统根据作业要求资源情况确定优先级。例如根据估计所需处理机时间、内存量大小、据估计所需处理机时间、内存量大小、IO设备类设备类型及数量等，确定作业的优先级。型及数量等，确定作业的优先级。进程的静态优先级确定原则可以是：进程的静态优先级确定原则可以是：(1)按进程的类型给予不同的优先级。例如，在有些按进程的类型给予不同的优先级。例如，在有些系统中，进程被划分为系统进程和用户进程。系统进系统中，进程被划分为系统进程和用户进程。系统进程享有比用户进程高的优先级。对于用户进程来说，程享有比用户进程高的优先级。对于用户进程来说，则可以分为：则可
34、以分为：33IO繁忙的进程，繁忙的进程，CPU繁忙的进程，繁忙的进程，IO与与CPU均衡的进程，均衡的进程，其他进程。其他进程。对系统进程，也可以根据其所要完成的功能划分为不对系统进程，也可以根据其所要完成的功能划分为不同的类型，例如，调度进程、同的类型，例如，调度进程、IO进程、中断处理进程、中断处理进程、存储管理进程等。这些进程还可进一步划分为进程、存储管理进程等。这些进程还可进一步划分为不同类型和赋予不同的优先级。例如，在操作系统中，不同类型和赋予不同的优先级。例如，在操作系统中，对于键盘中断的处理优先级和对于电源掉电中断的处对于键盘中断的处理优先级和对于电源掉电中断的处理优先级是不相同
35、的。理优先级是不相同的。(2)将作业的静态优先级作为它所属进程的优先级。将作业的静态优先级作为它所属进程的优先级。34优先级的类型优先级的类型静态优先级静态优先级优缺点：优缺点：算法实现简单，系统开销小，但不够灵活，算法实现简单，系统开销小，但不够灵活，不能根据实际情况进行调整，可能造成低优先不能根据实际情况进行调整，可能造成低优先级的进程长期不能被调度、运行级的进程长期不能被调度、运行动态优先级动态优先级优缺点：优缺点：为了能动态计算进程的优先级，一般操作系为了能动态计算进程的优先级，一般操作系统内核中都提供有改变进程优先级原语统内核中都提供有改变进程优先级原语,但是每但是每次调度都需要实时
36、计算进程的优先级，消耗大次调度都需要实时计算进程的优先级，消耗大量的量的cpu计算时间。计算时间。35动态优先级动态优先级基于静态优先级的调度算法实现简单，系统开销小，基于静态优先级的调度算法实现简单，系统开销小，但由于静态优先级一旦确定之后，直到执行结束为止但由于静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。始终保持不变，从而系统效率较低，调度性能不高。现在的操作系统中，如果使用优先级调度的话，则大现在的操作系统中，如果使用优先级调度的话，则大多采用动态优先级的调度策略。多采用动态优先级的调度策略。进程的动态优先级一般根据以下原则确定：进程的动态优先级
37、一般根据以下原则确定：(1)根据进程占有根据进程占有CPU时间的长短来决定。一个进程时间的长短来决定。一个进程占有处理机的时间愈长，则在被阻塞之后再次获得调占有处理机的时间愈长，则在被阻塞之后再次获得调度的优先级就越低，反之，其获得调度的可能性就会度的优先级就越低，反之，其获得调度的可能性就会越大。越大。(2)根据就绪进程等待根据就绪进程等待CPU的时间长短来决定。一个的时间长短来决定。一个就绪进程在就绪队列中等待的时间越长，则它获得调就绪进程在就绪队列中等待的时间越长，则它获得调度选中的优先级就越高。度选中的优先级就越高。36由于动态优先级随时间的推移而变化，系统要经常计由于动态优先级随时间
38、的推移而变化，系统要经常计算各进程的优先级，因此，系统要为此付出一定的开算各进程的优先级，因此，系统要为此付出一定的开销。销。例如：线性优先级调度策略（例如：线性优先级调度策略（selfishroundrobin）使用轮转法调度进程时，新创建的进程也放入就绪队使用轮转法调度进程时，新创建的进程也放入就绪队列末尾享受平等的处理机时间片。这对于执行时间长列末尾享受平等的处理机时间片。这对于执行时间长的进程来说是有点不公平的，因为它们需要多个时间的进程来说是有点不公平的，因为它们需要多个时间片才能完成。因此，线性优先级调度策略采用如下方片才能完成。因此，线性优先级调度策略采用如下方式，即新创建的进程
39、按式，即新创建的进程按FCFS方式排成就绪队列，而方式排成就绪队列，而其他已得到过时间片服务的进程也按其他已得到过时间片服务的进程也按FCFS方式排成方式排成另一个就绪队列或称享受服务队列另一个就绪队列或称享受服务队列(图图4.5）。）。375.最短作业优先法（最短作业优先法（shortestjobfirst）最短作业优先法（最短作业优先法（SJF）就是选择那些估计需要执行就是选择那些估计需要执行时间最短的作业投入执行，为它们创建进程和分配资时间最短的作业投入执行，为它们创建进程和分配资源。直观上来说，采用最短作业优先的调度算法，可源。直观上来说，采用最短作业优先的调度算法，可使得系统在同一时
40、间内处理的作业个数最多，从而吞使得系统在同一时间内处理的作业个数最多，从而吞吐量也就大于其他调度方式。但是，对于一个不断有吐量也就大于其他调度方式。但是，对于一个不断有作业进入的批处理系统来说，最短作业优先法有可能作业进入的批处理系统来说，最短作业优先法有可能使得那些长作业永远得不到调度执行的机会。使得那些长作业永远得不到调度执行的机会。6.最高响应比优先法（最高响应比优先法（highestresponserationext）最高响应比优先法（最高响应比优先法（HRN）是对是对FCFS方式和方式和SJF方方式的一种综合平衡。式的一种综合平衡。HRN调度策略同时考虑每个作调度策略同时考虑每个作业
41、的等待时间长短和估计需要的执行时间长短，从中业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。选出响应比最高的作业投入执行。38响应比响应比R定义如下：定义如下：R=(W+T)/T=1+W/T其中其中T为该作业估计需要的执行时间，为该作业估计需要的执行时间，W为作业在后为作业在后备状态队列中的等待时间。备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，每当要进行作业调度时，系统计算每个作业的响应比，选择其中选择其中R最大者投入执行。这样，即使是长作业，最大者投入执行。这样，即使是长作业，随着它等待时间的增加，随着它等待时间的增加，W/T也就随着增
42、加，也就也就随着增加，也就有机会获得调度执行。这种算法是介于有机会获得调度执行。这种算法是介于FCFS和和SJF之间的一种折中算法。由于长作业也有机会投入运行，之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于在同一时间内处理的作业数显然要少于SJF法，从而法，从而采用采用HRN方式时其吞吐量将小于采用方式时其吞吐量将小于采用SJF法时的吞法时的吞吐量。另外，由于每次调度前要计算响应比，系统开吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。销也要相应增加。39 4.2 4.2 调度算法举例调度算法举例4.2.14.2.1先来先服务和短作业（进程）优
43、先调度先来先服务和短作业（进程）优先调度算法算法 1 1 先来先服务（先来先服务（FCFS)FCFS)调度算法调度算法 作业调度：作业调度：每次调度是从后备作业队列中，选择每次调度是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内一个或多个最先进入该队列的作业，将它们调入内存，并分配资源、创建进程，然后放入就绪队列。存，并分配资源、创建进程，然后放入就绪队列。进程调度：进程调度：每次调度是从就绪队列中，选择一个最每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投先进入该队列的进程，把处理机分配给它，使之投入运行。入运行。40进程进程名名到达到达时间
44、时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A01B1100C21D3100 FCFSFCFS算法比较有利于长作业（进程），而算法比较有利于长作业（进程），而不利于短作业（进程）。在应用中也就是利于不利于短作业（进程）。在应用中也就是利于CPUCPU繁忙型作业（进程），而不利于繁忙型作业（进程），而不利于I/OI/O繁忙型繁忙型作业（进程）。如下例子，求平均周转时间和作业（进程）。如下例子，求平均周转时间和平均平均带权周转时间带权周转时间41进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时
45、间带权周带权周转时间转时间A010111B110011011001C21101102100100D31001022021991.99 FCFSFCFS算法比较有利于长作业（进程），而算法比较有利于长作业（进程），而不利于短作业（进程）。在应用中也就是利于不利于短作业（进程）。在应用中也就是利于CPUCPU繁忙型作业（进程），而不利于繁忙型作业（进程），而不利于I/OI/O繁忙型繁忙型作业（进程）。作业（进程）。422 2 2 2 短作业（进程）优先调度算法短作业（进程）优先调度算法短作业（进程）优先调度算法短作业（进程）优先调度算法 SJ(P)FSJ(P)FSJ(P)FSJ(P)F SJ(P)
46、FSJ(P)F是指对短作业或短进程优先调度的算法。是指对短作业或短进程优先调度的算法。短作业短作业(SJF)SJF)的调度算法可以照顾实际上占很的调度算法可以照顾实际上占很大比例的短作业大比例的短作业,使其能比长作业优先执行使其能比长作业优先执行.从作从作业的后备队列中选则一个或若干个短作业到内存业的后备队列中选则一个或若干个短作业到内存就绪队列就绪队列.短进程短进程(SPF)SPF)的调度算法从内存就绪队列中选的调度算法从内存就绪队列中选则一个运行时间最短的进程到处理机中执行则一个运行时间最短的进程到处理机中执行.43 作业情作业情况况调度算法调度算法进程名进程名A AB BC CD DE
47、E平均平均到达时间到达时间0 01 12 23 34 4服务时间服务时间4 43 35 52 24 4FCFSFCFS完成时间完成时间周转时间周转时间带权周转时带权周转时间间SJFSJF完成时间完成时间周转时间周转时间带权周转时带权周转时间间44 作业情作业情况况调度算法调度算法进程名进程名A AB BC CD DE E平均平均到达时间到达时间0 01 12 23 34 4服务时间服务时间4 43 35 52 24 4FCFSFCFS完成时间完成时间4 47 7121214141818周转时间周转时间4 46 61010111114149 9带权周转时带权周转时间间1 12 22 25.55.
48、53.53.52.82.8SJFSJF完成时间完成时间4 49 918186 61313周转时间周转时间4 48 816163 39 98 8带权周转时带权周转时间间1 12.62.67 73.13.1 1.51.52.22.25 52.12.145SJ(P)FSJ(P)F调度算法存在的问题调度算法存在的问题:该算法对长作业非常不利该算法对长作业非常不利.可能长期得不到调可能长期得不到调度度.该算法完全未考虑作业的紧迫程度该算法完全未考虑作业的紧迫程度,不能保证不能保证紧迫性作业或进程会得到及时处理紧迫性作业或进程会得到及时处理.由于作业由于作业(进程进程)的长短只是根据用户所提供的的长短只是
49、根据用户所提供的估计执行时间而定估计执行时间而定,而用户又可能估计不准而用户又可能估计不准,致致使该算法不一定能真正作到短作业使该算法不一定能真正作到短作业(进程进程)优先优先调度调度.46Process ArrivalTime BurstTimeP10.07P22.04P34.01P45.04SJF(non-preemptive非抢占非抢占)Averagewaitingtime=(0+6+3+7)/4=4P1P3P273160P481247Process ArrivalTime BurstTimeP10.07P22.04P34.01P45.04SJF(preemptive抢占抢占)Avera
50、gewaitingtime=(9+1+0+2)/4=3P1P3P242110P457P2P11648 此调度的算法是：当进程调度时，把处理机此调度的算法是：当进程调度时，把处理机分配给就绪队列中优先权最高的进程。分配给就绪队列中优先权最高的进程。1 1 优先权调度算法类型优先权调度算法类型 a.a.非强占式非强占式:系统按照优先权的高低进行调度系统按照优先权的高低进行调度,进程调度时进程调度时把处理机分配给具有高优先权的进程把处理机分配给具有高优先权的进程,直到该进程直到该进程完成后才放弃处理机完成后才放弃处理机.适用于实时性要求不严的实时系统中适用于实时性要求不严的实时系统中.b.b.强占式