《辅修第二章作业、处理机调度课件》由会员分享，可在线阅读，更多相关《辅修第二章作业、处理机调度课件（137页珍藏版）》请在金锄头文库上搜索。
1、第二章 处理机管理,教学内容: 1、调度的类型和模型、调度算法 2、多处理机调度 3、线程与进程的区别 4、进程的通信 5、管程机制 6、死锁,在多道程序系统中，一个作业从提交到执行通常要经历多级调度，系统的运行性能在很大程度上取决于调度。CPU调度使得多个进程有条不紊地共享一个CPU。CPU调度为每个用户都提供了一个虚拟处理机。一个好的调度策略对于加快作业总的周转时间、提高单位时间内的作业吞吐量、实现系统总的设计目标十分重要。,一、作业的状态及其转换,2.1 分级调度,提交状态：作业被提交给机房后或用户通 过终端键盘想计算机键入其作业时的状态. 后备状态：作业的全部信息都已通过输入 机输入，
2、并由操作系统将其存在磁盘的某些 分区（存放作业的输入井）中等待运行.,运行状态：作业一旦被作业调度程序选 中而被送入主存中投入运行. 完成状态：作业完成其全部运行，释放 出其所占用的全部资源。准备退出系统时 的作业.,二、调度的层次 在多道程序环境下，操作系统中面对众多进程，为了提高调度效率，也实行分级调度。 高级调度（作业调度、宏观调度、长期调度、收容调度） 按一定原则对外存输入井上的作业进行调度，从作业后备队列中选择作业进入主存并建立进程PCB。,它决定允许哪些作业竞争系统资、决定哪些作业可以进入系统。,负责进程在内存和辅存对换区之间的对换。 一些进程处于阻塞状态而暂时不能运行，中级调 度
3、将进程暂时移到辅存对换区，对换区的进程若 其等待的事件已发生，则它们要由阻塞状态变为 就绪，为了继续这些进程的继续进行，则由中级 调度再度把它们调入内存。,中级调度（交换调度、中程调度）,决定允许哪些进程竞争处理机,一个进程在其运行期间有可能多次调进调出,低级调度（进程调度、短期调度） 决定存在就绪进程时，哪一个就绪进程将分配到中央处理机，并且把中央处理机实际分配给这个进程（即低级调度是将处理机分配给进程）。,低级调度是由每秒可操作许多次的处理机调 度程序执行，处理机调度程序应常驻内存。,作业调度的功能：按某种算法从后备队列中挑选一个或一批作业调入内存，并创建PCB。 一、后备作业队列与作业控
4、制块 系统中有若干作业在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。,2.2 作业的调度,二、 作业控制块JCB,三、作业调度应完成的工作 按照某种调度算法从后备作业队列中选取作业。 为被选取的作业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程序和外设分配程序。 为选中的作业建立相应的进程。,为作业开始运行做好一切准备工作。如构 造和读写作业运行时所需要的有关表格及建立 负责其运行控制的作业运行控制程序。 在作业运行完毕或运行过程中因某种原因 需要撤离时，作业调度程序还
5、有完成作业的善 后处理工作，如收回分配给他的全部资源，它 们将从系统中抹去,四、作业调度目标与转换过程 1、调度目标 a.对所有作业应该是公平合理 b.应使设备有高的利用率 c.每天执行尽可能多的作业 d.有快的响应时间,2、作业调度的转换过程 a.作业从后备状态到执行状态 b.作业从执行状态到完成状态,后备作业队列空,按调度算法从作 业中选出一作业,调用存储、设备管理 程序，审核资源要求,资源要求能满足？,放弃该 作业,否,分配资源,调用进程管理 程序建立进程,进程调度,否,是,出 口,作业从后备状态到执行状态,撤销该作业的所有进程及作业的JCB,调用存储管理，设备管理回收 分配给该作业的全
6、部资源,调用会计程序，计算该作业的执行费用,调度下一个作业,作业从执行状态到完成状态,2.3 中级调度,引入中级调度后，进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。,具有三级调度时的调度队列模型,2.4 调度算法 一、周转时间： 作业i从提交时刻Tsi到完成时刻Tei称为作业的周转时间。Ti=Tei(完成时刻)-Tsi(提交时刻) 一个作业的周转时间说明该作业在系统内停留
7、的时间包含两部分：等待时间和执行时间 Ti=Twi+Tri,二、平均周转时间为（有n个作业，n=1) n T=1/n Ti i=1,三、带权周转时间Wi： Wi=Ti(周转时间)/Tri(执行时间) 平均带权周转时间为： n W=1/n Wi i=1,四、好的调度算法要求： CPU利用率高、吞吐量大、T和W小 1、先来先服务（FCFS）调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理。优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短，是不可抢占策略。,作业 进入时刻 运行时间 完成时刻 周转时间 带权周转时间 1 ：00 30
8、 10：30 2 ：10 60 3 ：20 40 4 ：30 20,作业1:周转时间T110:3010:0030,先来先服务算法分析结果,30,1,80,1.33,110,2.75,120,6,11：30,12：10,12：30,作业2:周转时间T211:3010:1080,带权周转时间W130/301,带权周转时间W280/601.33,作业3:周转时间T312.1010.20110 带权周转时间W3110/402.75 作业4: 周转时间T412.3010.30120 带权周转时间W4120/206,平均周转时间: T(T1+T2+T3+T4)/4,平均带权周转时间: W(W1+W2+W3
9、+W4)/4,T(30+80+110+120)/4=85(min),W(1+1.33+2.75+6)/4=2.77(min),例3-1：有下述作业序列：,算法评价： 这种算法按先来后到原则调度，比较公平，但是不利于短作业。此算法有利于CPU繁忙型作业，而不利于I/O繁忙型作业。,CPU繁忙型作业：指CPU进行处理时，不需频繁的请求I/O，而每次I/O的操作时间又很短。 I/O繁忙型作业：指该类作业无需大量的CPU时间进行计算，但要频繁地请求I/O。,2、最短作业优先法（SJF）：该算法总是优先调度要求运行时间最短的作业，是非抢占策略。选中某个短作业后，就保证该作业尽可能快地完成运行并退出系统，
10、运行中不允许被抢占。 作业 进入时刻 运行时间 完成时刻 周转时间 带权周转时间 1 ：00 30 2 ：10 60 3 ：20 40 4 ：30 20,10:30,12:30,11:30,10:50,30,20,70,140,1,1.75,2.33,1,平均带权周转时间 W1.55 (T=1+2.33+1.75+1)/4=1.52(min) 平均周转时间 T=4.65 (T=30+140+70+20)/4=65(min),例3-2：有下述作业序列：,算法评价： 优点:有利于短作业。因而在给定的时限内可以完成更多的作业，增加系统的吞吐量，改善调度性能。 缺点： （1）对长作业不利。（2）完全没
11、考虑作业的紧迫程度，不能保证紧迫作业会得到及时处理。（3）由于作业的长短只根据用户提供的估计执行时间而定,而用户又有可能会有意无意的缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。,五、高优先权优先调度算法 1优先权调度算法的类型 为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算
12、法分成如下两种。,1) 非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。,2) 抢占式优先权调度算法 系统把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。,*:在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时
13、，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果PiPj，原进程Pj便继续执行；但如果是PiPj，则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。,2优先权的类型 (1) 静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，如，07或0255中的某一整数，又把该整数称为优先数，只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相
14、反。,确定进程优先权的依据： 1)进程类型。系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权。 2)进程对资源的需求。如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予较高的优先权。 3)用户要求。是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。,静态优先权法简单易行，系统开销小，但不够精确，很可能出现优先权低的作业(进程)长期没有被调度的情况。因此，仅在要求不高的系统中才使用静态优先权。,(2) 动态优先权 动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规
15、定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。,若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进 程，在等待了足够的时间后，其优先权 便可能升为最高，从而可以获得处理机 采用抢占式优先权调度算法时，如果 再规定当前进程的优先权以速率b 下， 则可防止一个长作业长期地垄断处理机。,在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级
16、随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为： 3、最高相应比作业优先算法（HRN） R=（等待时间+要求服务时间）/要求服务时间 =响应时间/要求服务时间,R=（等待时间+要求服务时间）/要求服务时间 =响应时间/要求服务时间 (1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。,(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获
