辅修第二章作业、处理机调度

第二章处理机管理教学内容:1、调度的类型和模型、调度算法2、多处理机调度3、线程与进程的区别4、进程的通信5、管程机制6、死锁在多道程序系统中，一个作业从提交到执行通常要经历多级调度，系统的运行性能在很大程度上取决于调度。CPU调度使得多个进程有条不紊地共享一个CPU。CPU调度为每个用户都提供了一个虚拟处理机。一个好的调度策略对于加快作业总的周转时间、提高单位时间内的作业吞吐量、实现系统总的设计目标十分重要。一、作业的状态及其转换§2.1分级调度进程的三种状态?①提交状态：作业被提交给机房后或用户通过终端键盘想计算机键入其作业时的状态.②后备状态：作业的全部信息都已通过输入机输入，并由操作系统将其存在磁盘的某些分区（存放作业的输入井）中等待运行.③运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行.④完成状态：作业完成其全部运行，释放出其所占用的全部资源。准备退出系统时的作业.二、调度的层次在多道程序环境下，操作系统中面对众多进程，为了提高调度效率，也实行分级调度。高级调度（作业调度、宏观调度、长期调度、收容调度）按一定原则对外存输入井上的作业进行调度，从作业后备队列中选择作业进入主存并建立进程PCB。它决定允许哪些作业竞争系统资、决定哪些作业可以进入系统。负责进程在内存和辅存对换区之间的对换。一些进程处于阻塞状态而暂时不能运行，中级调度将进程暂时移到辅存对换区，对换区的进程若其等待的事件已发生，则它们要由阻塞状态变为就绪，为了继续这些进程的继续进行，则由中级调度再度把它们调入内存。中级调度（交换调度、中程调度）决定允许哪些进程竞争处理机一个进程在其运行期间有可能多次调进调出低级调度（进程调度、短期调度）决定存在就绪进程时，哪一个就绪进程将分配到中央处理机，并且把中央处理机实际分配给这个进程（即低级调度是将处理机分配给进程）。低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。作业调度的功能：按某种算法从后备队列中挑选一个或一批作业调入内存，并创建PCB。一、后备作业队列与作业控制块系统中有若干作业在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。§2.2作业的调度作业名作业类型资源要求资源使用情况优先级当前状态其它二、作业控制块JCB三、作业调度应完成的工作①按照某种调度算法从后备作业队列中选取作业。②为被选取的作业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程序和外设分配程序。③为选中的作业建立相应的进程。④为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。⑤在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还有完成作业的善后处理工作，如收回分配给他的全部资源，它们将从系统中抹去四、作业调度目标与转换过程1、调度目标a.对所有作业应该是公平合理b.应使设备有高的利用率c.每天执行尽可能多的作业d.有快的响应时间2、作业调度的转换过程a.作业从后备状态到执行状态b.作业从执行状态到完成状态后备作业队列空按调度算法从作业中选出一作业调用存储、设备管理程序，审核资源要求资源要求能满足？放弃该作业否分配资源调用进程管理程序建立进程进程调度否是出口作业从后备状态到执行状态撤销该作业的所有进程及作业的JCB调用存储管理，设备管理回收分配给该作业的全部资源调用会计程序，计算该作业的执行费用调度下一个作业作业从执行状态到完成状态§2.3中级调度引入中级调度后，进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现具有三级调度时的调度队列模型§2.4调度算法一、周转时间：作业i从提交时刻Tsi到完成时刻Tei称为作业的周转时间。Ti=Tei(完成时刻)-Tsi(提交时刻)一个作业的周转时间说明该作业在系统内停留的时间包含两部分：等待时间和执行时间Ti=Twi+Tri二、平均周转时间为（有n个作业，n=1)nT=1/n∑Tii=1三、带权周转时间Wi：Wi=Ti(周转时间)/Tri(执行时间)平均带权周转时间为：nW=1/n∑Wii=1四、好的调度算法要求：CPU利用率高、吞吐量大、T和W小1、先来先服务（FCFS）调度算法将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理。优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短，是不可抢占策略。作业进入时刻运行时间完成时刻周转时间带权周转时间1１０：003010：302１０：10603１０：20404１０：3020作业1:周转时间T1＝10:30－10:00＝30先来先服务算法分析结果301801.331102.75120611：3012：1012：30作业2:周转时间T2＝11:30－10:10＝80带权周转时间W1＝30/30＝1带权周转时间W2＝80/60＝1.33作业3:周转时间T3＝12.10－10.20＝110带权周转时间W3＝110/40＝2.75作业4:周转时间T4＝12.30－10.30＝120带权周转时间W4＝120/20＝6平均周转时间:T＝(T1+T2+T3+T4)/4平均带权周转时间:W＝(W1+W2+W3+W4)/4T＝(30+80+110+120)/4=85(min)W＝(1+1.33+2.75+6)/4=2.77(min)作业号1234到达时间8.008.509.009.50运行时间2.000.500.100.20调度顺序1234作业号1234到达时间8.008.509.009.50开始时间8.0010.0010.5010.60结束时间10.0010.5010.6010.80周转时间2.002.001.601.30加权周转时间14166.5例3-1：有下述作业序列：T1=10.00-8.00=2.00W1=2.00/2.00=1T2=10.50-8.50=2.00W2=2.00/0.50=4T3=10.60-9.00=1.60W3=1.60/0.10=16T4=10.80-9.50=1.30W4=1.30/0.20=6.5平均周转时间T=（T1+T2+T3+T4）/4=1.73加权平均周转时间W=(W1+W2+W3+W4)/4=6.88算法评价：这种算法按先来后到原则调度，比较公平，但是不利于短作业。此算法有利于CPU繁忙型作业，而不利于I/O繁忙型作业。CPU繁忙型作业：指CPU进行处理时，不需频繁的请求I/O，而每次I/O的操作时间又很短。I/O繁忙型作业：指该类作业无需大量的CPU时间进行计算，但要频繁地请求I/O。2、最短作业优先法（SJF）：该算法总是优先调度要求运行时间最短的作业，是非抢占策略。选中某个短作业后，就保证该作业尽可能快地完成运行并退出系统，运行中不允许被抢占。作业进入时刻运行时间完成时刻周转时间带权周转时间1１０：00302１０：10603１０：20404１０：302010:3012:3011:3010:5030207014011.752.331平均带权周转时间W＝1.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：有下述作业序列：作业号1234到达时间8.008.509.009.50运行时间2.000.500.100.20调度顺序1234作业号1342到达时间8.009.009.508.50开始时间8.0010.0010.1010.30结束时间10.0010.1010.3010.80周转时间2.001.100.802.30加权周转时间11144.6周转时间：加权周转时间：T=结束时间-到达时间T1=10.00-8.00=2.00T2=10.80-8.50=2.30T3=10.10-9.00=1.10T4=10.30-9.50=0.80W=周转时间+运行时间W1=2.00/2.00=1W2=2.30/0.50=4.6W3=1.10/0.10=11W4=0.80/0.20=4平均周转时间：T=(T1+T2+T3+T4)/4=1.55加权平均周转时间：W=(1+4.6+11+4)/4=5.15算法评价：优点:有利于短作业。因而在给定的时限内可以完成更多的作业，增加系统的吞吐量，改善调度性能。缺点：（1）对长作业不利。（2）完全没考虑作业的紧迫程度，不能保证紧迫作业会得到及时处理。（3）由于作业的长短只根据用户提供的估计执行时间而定,而用户又有可能会有意无意的缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。五、高优先权优先调度算法1．优先权调度算法的类型为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。1)非抢占式优先权算法在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。2)抢占式优先权调度算法系统把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。*:在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是PiPj，则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。2．优先权的类型(1)静态优先权静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，如，0～7或0～255中的某一整数，又把该整数称为优先数，只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。确定进程优先权的依据：1)进程类型。系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权。2)进程对资源的需求。如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予较高的优先权。3)用户要求。是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。静态优先权法简单易行，系统开销小，但不够精确，很可能出现优先权低的作业(进程)长期没有被调度的情况。因此，仅在要求不高的系统中才使用静态优先权。(2)动态优先权动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初