操作系统讲稿 - 西安电子科技大学出版社.ppt
第四章 处理机调度与死锁,掌握调度的层次及进程调度与作业调度的关系掌握各种作业调度算法及每种算法的作业周转时间和带权平均周转时间死锁的原因，产生死锁的四个必要条件以及死锁的解决。,本章重点：,各种作业调度算法及每种算法的作业周转时间和带权平均周转时间死锁的解决,本章难点：,分级调度作业调度进程调度死锁小结,41分级调度,作业的状态及转换,处理机调度：如何从众多的作业队列中选择一道或几道进入内存，进入内存的若干进程又如何去竞争CPU的使用权，这称为处理机调度。,处理机调度分4级：作业调度、交换调度、进程调度、线程调度。,作业调度：负责从后备队列中选择作业投入运行。将作业从运行状态变成完成状态。,进程调度：则将进程从就绪状态变为运行状态。,交换调度：负责将外存交换区中的进程调入内存。将内存进程调入外存交换区。,四者关系,作业调度,提交,收容,内存,就绪,就绪,执行,交换调度,等待,等待,进程调度,完成,线程调度,作业调度：,又称高级调度，,宏观调度。,其主要任务是对大量的后备作业以一定的原则进行挑选，给选中的作业分配内存、I/O设备等必要的资源，建立相应的进程，这时该作业所对应的进程具有使用CPU的权力。作业完成时负责收回资源,进程调度：,又称低级调度，,微观调度。,其任务是按照某种原则将CPU分配给某一就绪进程，即确定哪个进程在什么时候获得处理机，使用多长时间。,二者联系：作业调度创建进程调度所需要进程。,二者区别：,处理对象不同；,完成任务不同。,交换调度：,又称中级调度，,其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪进程或等待进程调入内存，或者把内存中的就绪进程或等待进程交换到外存中。,42作业调度,一、作业调度功能,1.数据结构：JCB用于记录作业相关信息,2.从后备队列中挑选一部分作业投入运行,3.为被选中的作业做好执行前的准备工作：建立进程分配资源,4.作业完成后做善后处理工作：收回资源，输出执行时间等作业管理信息,二、作业调度目标及性能衡量标准,1.调度目标：,对所有的作业应该是公平合理的,设备利用率高,单位时间内执行尽可能多的作业,每个作业有尽可能快的响应时间,2.调度衡量标准：,周转时间 Ti=Tfi-Tsi Ti =Twi+Tri,平均周转时间T=,带权周转时间wi=,带权平均周转时间w=,=,=1+,三、作业调度算法,1.先到先服务FCFS ：优先选择最先到达的作业,T=175/5=35,W=10.2/52.04,2.短作业优先SJF ：优先选择最少运行时间的作业,T=33,W=1. 8,3.响应比高者优先考虑 ：,T=34,W=1. 91,响应比=等待时间/运行时间,43进程调度,一、进程调度功能,1.记录系统中所有进程的执行情况,2.从就绪进程中选择占有处理机的进程,3.进行进程上下文（进程状态、有关变量、数据结构的值、硬件寄存器值、PCB等）切换,二、进程调度的时机,1.正在执行的进程运行完毕,2.执行中的进程变成阻塞状态,3.分时系统中时间片用完,4.可剥夺调度方式中有优先级高的进程进入就绪队列,三、进程调度性能衡量标准,1.定性标准：,（1）可靠性：一次进程调度是否能引起数据结构的破坏,（2）简洁性：调度程序的国度繁琐将引起较大的系统开销,2.定量标准,（1）CPU的利用率,（2）进程在就绪队列中的等待时间与执行时间之比,四、进程调度调度方式,1.可剥夺 ：,2.不可剥夺：,五、进程调度算法,1.先到先服务FCFS：优先调度最先进入就绪队列的进程,2.轮转法 （Round Robin）：将CPU的处理时间分成固定大小的时间片，一个进程在被调度程序选中后用完了系统规定的时间片但未完成要求的任务，自动到就绪队列队尾,3.多级反馈队列法（ Round Robin with Multiple Feedback）：,优先级,高,低,RL1,RL2,RLn,时间片,短,长,4.优先数法 ：优先调度优先级最高的进程,动态优先数：优先数随着进程的执行而发生变化,5. SCBF(Short CPU Burst First),静态优先数：进程的执行期间优先数不变,六、进程调度与作业调度的比较,4.4进程死锁,例： P1 打印机 绘图仪 P2 绘图仪 打印机,Pi思考P（S(i+1) mod 5）拿左叉P（S(i) ）拿右叉；吃饭；放左叉；V（ S(i+1) mod 5 ）放右叉V（S(i)）;,例：哲学家就餐问题,0,1,2,3,4,思考,吃饭,0,1,2,3,4,例：P2、P1都需3台打印机 ，系统中有4台打印机，其中P1和P2各分得2台。,P2 P1,一、死锁的定义：,死锁：指各并发过程彼此互相等待对方所使用的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，从而造成了一种僵局。如果无外力作用，这些进程永远不能再向前推进。,二、死锁产生的原因,竞争资源,进程推进顺序不当,P2(Rel(R1)P2(Rel(R2)P2(Req(R1)P2(Req(R2),P1Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2),三、产生死锁的四个必要条件,1.互斥条件,2.部分分配,3.不剥夺条件（不可抢占）,4.环路条件,四、死锁的解决,1.死锁的预防：打破死锁存在条件中的一个或几个有三种方法：,1）打破互斥和不剥夺条件：一个已保持了某些资源的进程。若新的资源要求不能立即得到满足，它必须释放已保持的所有资源，以后需要时再重新申请，这意味着一个进程已占有的资源，在运行过程中可能暂时地释放或说被剥夺。,2）打破部分分配条件：系统要求所有进程一次性申请所需的全部资源。若系统有足够的资源分配给一个进程时，便一次把所需资源分配给该进程。这样，进程在整个运行期间为会提出任何要求，但系统浪费严重，降低了并发性。,3）打破环路条件：将所有资源编号，申请时按顺序申请，先申请小号，再申请大号，这样，能保证申请到最大号者，肯定运行完成。,2、死锁的避免,1）安全与不安全状态：允许进程动态申请资源，系统进行资源分配前先计算资源分配的安全性，若此次分配不会导致 进入不安全状态，则将资源分配给进程，否则进程等待。,安全状态：指将系统按照某种顺序如来为每一个进程分配其所需资源，直到最大需求使每个进程可顺序完成，若系统不存在这样一个安全系列，则系统处于不安全状态。只要系统处于安全状态，便可避免进死锁状态。,例：三个进程P1,P2,和P3所需要磁带机10，4，9系统中其12台。,T0时刻 最大需求P110P24P39,T0时刻存在一个安全序列 所以系统安全。,如果 P3 请求 1 台, 状态发生变化.,已分配 522,可用3,还需527,找不到一个安全序列. 状态不安全. 请求不能满足。,如果 P1 请求 1 台, 状态发生变化. 结果如何？,如果 P2 请求 1 台, 状态发生变化. 结果又如何？,2）数据结构,（1） 可用资源向量 availablem: availablei 代表资源i的可用资源数。初值为系统中所配置的该类资源的全部可用资源数。availablej=k; Rj类资源有k个。,(2)Maxm,n: maxi,j=k 表示进程i最多需要k个Rj资源。,(3)Allocationm,n: allocationi,j=k 表示进程i已分得k个Rj资源。,(4)Needm,n: needi,j=k 表示进程i还需要k个Rj资源。,存在关系：Need=Max-Allocation,3) 银行家算法,requesti 进程Pi的请求向量。 requesti j=k 进程Pi申请k个Rj ，Pi发出请求后，系统按如下方法做.,(1) if requesti <=Needi, then go to (b) else error,(2) if requesti <=Available, then go to (c) else Pi waits,(3)系统试分配, 修改数据结构。,Available= Available- requestiNeedi= Needi- requestiallocationi= allocationi + requesti,(4)系统执行安全性算法，若安全，正式分配，否则，试探作废，Pi等待,恢复原来的数据结构。,4)安全性算法,设置两个向量：工作向量work,表示系统能够提供给进程的资源数；Finish，表示系统是否有足够的资源满足每个进程，初始时Work=Available，Finish=false,(2)从进程集合中找满足下列条件的进程： Finishi=false 且 Needi<=work,(3)如果找到：,Work=work+allocationiFinishi=trueGoto b),(4)如果对所有进程都有 finishi=true 则系统安全，否则系统不安全。,5)银行家算法的例,进程 p0,p1,p2,p3,p4 资源A,B,C 最大可用资源 10,5,7At the moment T0:,Maxallocationneedavailable ABCABCABCABCP0 7 5 30 1 07 4 33 3 2P1 3 2 22 0 01 2 2P2 9 0 23 0 26 0 0P3 2 2 22 1 10 1 1P4 4 3 30 0 24 3 1,R,T0时刻的安全性:,work needallocationwork+allocation finish,ABC ABC ABCABC,P1 3 3 2 1 2 22 0 05 3 2 true,P3 5 3 2 0 1 12 1 17 4 3 true,P4 7 4 3 4 3 10 0 27 4 5 true,P0 7 4 5 7 4 30 1 07 5 5 true,P2 7 5 5 6 0 03 0 210 5 7 true,找到了安全序列，所以该时刻系统安全,P1 请求： request1(1,0,2),MaxallocationneedavailableABCABCABCABCP07 5 30 1 07 4 32 3 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1,（1）request1<=need1,（4）运行安全性算法.,（2）request1<=available,（3）试分配，修改数据结构,1 2 2,3 3 2,R,T1时刻的安全性:,workneedallocationwork+allocationfinish,ABCABCABCABC,P12 3 00 2 03 0 25 3 2 true,P35 3 20 1 12 1 17 4 3 true,P47 4 34 3 10 0 27 4 5 true,P07 4 57 4 30 1 07 5 5 true,P27 5 56 0 03 0 210 5 7 true,找到了安全序列，所以该时刻系统安全,P4 请求 request4(3,3,0),（1）request4<=need4,（2）request4<=available is not satisfied.,4 3 1,2 3 0,P4 wait,P0 请求 request0(0,2,0),MaxallocationneedavailableABCABCABCABCP07 5 30 3 07 2 32 1 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1,（1）request0<=need0,（2）request0<=available.,（3）试分配，修改数据结构.,7 4 3,2 3 0,（4）运行安全性算法.,找不到安全序列，所以不安全，恢复数据结构，P0等待,五、死锁的检测和恢复,当系统为进程分配资源时，若未采取任何限制性措施保证不进入死锁状态，则系统必须提供解除死锁的手段。,1.资源分配图,2死锁定理,当且仅当S的资源分配图是不可完全简化的，S为死锁状态。,死的解除：,1.终止死锁进程；,2.按一定顺序中止进程直至释放到有足够的资源来完成剩下的进程为止；,3.从被锁住进程中强迫剥夺资源以解除死锁。,45 小结,处理机调度定义、层次、四者所在位置作业调度与进程调度的任务、功能、关系 作业调度功能、衡量标准作业调度算法 进程调度功能、时机、衡量标准、方式进程调度算法两类调度算法的比较死锁定义 死锁产生原因；产生死锁的四个必要条件；死锁的解决： 预防、 避免 、检测和恢复,1.银行家算法中出现下述资源分配：,作业,allocationneedavailableABCDABCDABCDP0003200121622P110001750P213542356P303320652P400140656,（1）该状态是否安全？,（2）如果P2提出请求Request2（1，2，2，2）后，系统能否将资源分配给它？,2.有相同类型的5个资源被4个进程所共享，且每个进程最多需要2个这样的资源才可以运行完毕，试问系统是否会由于这种资源的竞争而产生死锁。,3. 已知某系统中的所有资源都是相同的，系统中的进程严格按照一次一个的方式申请或者释放资源。在此系统中，没有进程所需要的资源数超过系统的资源总拥有量，试对下面列出的各种情况说明是否会发生死锁，为什么？,情况序号系统中进程数 资源总量A12B21C22D23,4.系统中有3种资源A、B、C，5个进程P1、P2、P3、P4、P5，系统中有A、B、C的数量分别是17、5、20，T0时刻系统状态如下：,MaxAlocationABCABCP15 5 92 1 2P25 3 64 0 2P34 0 114 0 5P44 2 52 0 4P54 2 43 1 4,（1）该状态是否安全？为什么？,（2）如果P2提出请求Request2（0，3，4）后，系统能否将资源分配给它？为什么？,（3）在（2）的基础上，如果P4提出请求Request4（2，0，1）后，系统能否实施分配？为什么？,（4）在（3）的基础上，如果P1提出请求Request1（0，2，0）后，系统能否实施分配？为什么？,求FCFS,SJF和HRN三种算法的T和W。,二、批处理作业,submit,输入设备,输出设备,键盘,作业调度程序,作业终止程序,输出程序,OS中输入程序 作业注册程序,后备状态,运行状态,完成状态,
