计算机操作系统李翠霞os3复习

第3章小结,理解处理机调度的三级调度各自的含义，会区分这三种调度；理解抢占式调度和非抢占调度这两种调度方式的概念了解调度算法的准则掌握常见的几种调度算法，做到能根据系统中各个进程的属性和到达情况按常见的调度算法调度多个进程执行的顺序理解等待时间、周转时间、带权周转时间的含义，会计算它们了解实时调度（EDF和LLF）理解死锁发生的四个必要条件，做到能举例说明如何限制这些条件不成立，能判断当前系统有没有发生死锁理解处理死锁的几个方法，尤其是死锁预防和死锁避免的区别掌握死锁避免的重要算法银行家算法，做到能用银行家算法调度一个系统的资源分配了解死锁检测和解除的概念和方法,用高级语言模拟各种不同的调度算法；用高级语言模拟银行家算法；,知识结构图,处理机调度,调度级别,调度队列,选择调度方式和算法的准则,调度算法,实时调度,作业调度,中级调度,低级调度,先来先服务,短作业优先,时间片轮转,多级反馈队列,最高相应比优先,优先级,死锁,概念,产生原因,必要条件,竞争资源,进程推进顺序不当,互斥条件,请求和保持条件,不剥夺条件,环路等待条件,处理方法,预防死锁,限制条件,避免死锁,银行家算法,死锁检测与解除,本章重难点提示,三级调度之间的比较和含义常见的调度算法的比较用常见的调度算法调度当前系统，并计算平均周转时间，平均加权周转时间，平均等待时间用死锁发生的必要条件来分析系统是否会死锁，提出解决方案用银行家算法判断系统是否处于安全状态，是否应该同意一个进程的资源申请,4,调度算法比较,预防死锁,1）摒弃“请求和保持”条件-资源的静态分配要求每个进程在运行前必须一次性申请它所要求的所有资源，当且仅当该进程所要资源均可满足时才给予一次性分配,2）摒弃“不可剥夺”条件在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。,3）摒弃“环路等待”条件采用资源有序分配法把系统中所有资源顺序编号：r1，r2，rn各进程按资源编号递增次序申请资源,银行家算法,n：系统中进程的总数；m：资源种类可用资源向量Available:ARRAY1.mofinteger;最大需求矩阵Max:ARRAY1.n,1.mofinteger;,已分配矩阵Allocation:ARRAY1.n,1.mofinteger;需求矩阵（各进程的需求下限）Need:ARRAY1.n,1.mofinteger;请求向量Request:ARRAY1.n,1.mofinteger;,银行家算法符号简记：,Available、MaxiAllocationiNeedi、Requesti,当进程Pi提出资源申请时，系统执行下列步骤：（1）若RequestiNeedi,转（2）；否则错误返回（2）若RequestiAvailable,转（3）；否则进程等待,(3）假设系统分配了资源，则有：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，进程等待,银行家算法安全性检查,定义数据结构：工作向量Work:ARRAY1.mofinteger;结束向量Finish:ARRAY1.nofBoolean;,安全性检查的步骤：(1)Work:=Available;Finish:=false;(2)寻找满足条件的i：Finishi=false;NeediWork;如果不存在，则转(4)(3)Work:=Work+Allocationi;Finishi:=true;转(2)(4)若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态,思考题,（1）3个进程共享4个同种类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？（2）n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n。说明该系统不会因竞争该资源而阻塞。（3）在（2）中，如果没有“每个进程都需要用该类资源”的限制，情况又会如何？,作业：1，5，7，13，16，17，18，21，22,思考题,假设一个系统中有6个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销时间，若分别按先来先服务（FCFS）、非抢占的短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列（FB，第i级队列的时间片=3i-1）以及立即抢占的多级反馈队列（FB，第i级队列的时间片=3i-1）调度算法进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。,表进程到达时间和需服务时间,FCFS的进程完成时间和周转时间,12,9,8,6,2,2,周转时间,2.4,3,2,1,2,1,带权周转时间,21,16,13,9,3,2,完成时间,F,E,D,C,B,A,进程,进程调度顺序：A，B，C，D，E，F,T=6.5W=1.9,SPF（非抢占）的进程完成时间和周转时间,12,5,11,6,2,2,周转时间,2.4,1.67,2.75,1,2,1,带权周转时间,21,12,16,9,3,2,完成时间,F,E,D,C,B,A,进程,进程调度顺序为：A，B，C，E，D，F,T=6.33W=1.80,HRRN的进程完成时间和周转时间,1.8,4,5,9,F,3,9,16,13,3,6,3,7,E,5,1.73,6.3,2.4,12,21,16,2.4,7,5,9,F,6,1,0,5,9,F,1.67,2,3,7,E,2,8,13,9,2,4,4,5,D,4,1,6,9,3,1,0,6,3,C,3,2,2,3,2,2,1,1,1,B,2,1,2,2,0,1,0,2,0,A,1,wi,ti,tc,tb,Rp,tw,ts,ta,作业,调度次序,ta到达时间、tb开始时间、tc完成时间,进程调度顺序为：A，B，C，D，E，F,A,B,A,C,C,D,C,D,E,C,D,F,E,C,D,F,E,C,F,F,就绪队列,就绪队列,调度,时间片轮转调度算法执行过程,F,RR的进程完成时间和周转时间,12,10,10,15,1,3,周转时间,2.4,3.3,2.5,2.5,1,1.5,带权周转时间,21,17,15,18,2,3,完成时间,F,E,D,C,B,A,进程,进程调度顺序：A,B,A,C,C,D,C,D,E,C,D,F,E,C,D,F,E,C,F,F,F,T=8.5W=2.2,A,B,C,C,D,E,F,E,C,调度,非抢占多级反馈队列调度算法执行过程q=3i-1,A,A,B,C,C,F,D,D,E,C,DE,1级,2级,3级,DEF,EF,CF,F,A,F,D,F,FB的进程完成时间和周转时间,进程调度顺序：（以时间片为准）A,B,A,C,C,C,C,D,E,F,D,D,D,E,E,F,F,F,C,C,F,T=8.0W=2.08,A,B,A,C,D,E,D,C,E,13,14,15,16,17,18,调度,抢占多级反馈队列调度算法执行过程q=3i-1,A,A,B,C,D,F,20,19,C,D,E,F,1级,2级,3级,DF,C,C,CD,C,DC,DCE,F,CED,CEDF,EDF,21,F,F,F,死锁问题思考题,（1）3个进程共享4个同种类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？,答：该系统不会因为竞争该类资源而死锁。因为，必有一个进程可获得2个资源，故能顺利完成，并释放出其所占有的2个资源给其他进程使用，使它们也顺利完成。,（2）n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n。说明该系统不会因竞争该资源而阻塞。,答：用Maxi，Needi和Allocationi来分别表示第i个进程对该类资源的最大需求量，还需要量和已分配到的量，根据题意它们将满足下述条件：,若系统已因竞争该类资源而进入死锁状态，则意味着已有一个以上的进程因申请不到该类资源而无限阻塞，而m个资源肯定已全部分配出去，即,因此：,即：,这样，至少必须存在一个进程，其Needi0，这显然与题意不符，所以该系统不可能因竞争该类资源而进入死锁状态。,（3）在（2）中，如果没有“每个进程都需要用该类资源”的限制，情况又会如何？,答：此时系统可能发生死锁。如n=4，m=3时，若P1的Max为0，而其余三个进程的Max都为2，则仍然满足最大需求量之和（即6）小于m+n的要求，但当除P1以外的其余三个进程各得到一个资源时，这三个进程将进入死锁状态。,银行家算法之例（P110课后21题）,进程P0,1,2,3,4共享A、B、C三类资源A，B，C=10，5，7T0时刻，资源的分配情况如下图所示。（1）该状态是否安全？若安全，请找出安全序列。（2）在此基础上，P1申请（1，0，2）能否分配？为什么？（3）P4申请（3，3，0）能否分配？为什么？（4）P0申请（0，1，0）能否分配？为什么？,P0请求Request010P1分配后Available=230假设把010分配给P0，则：Available=220用算法检查。,True,302,600,755,P2,True,020,733,735,P0,True,002,431,733,P4,True,211,011,522,P3,False,302,600,522,P2,True,302,020,220,P1,False,020,733,220,P0,finishi,Work+alloc,alloc,need,work,有安全序列，可以分配给P0,522,733,735,755,1057,22.进程P0,1,2,3,4共享A、B、C、D四类资源资源的分配情况如下图所示。（1）该状态是否安全？若安全，请找出安全序列。（2）P2申请（1,2,2,2）能否分配？为什么？,True,1354,2356,29910,P2,True,1000,1750,19910,P1,True,0014,0656,1986,P4,True,0332,0652,1654,P3,False,1354,2356,1654,P2,False,1000,1750,1654,P1,True,0032,0012,1622,P0,finishi,Work+alloc,alloc,need,work,有安全序列，该状态是安全的。,1986,19910,29910,3121414,1654,False,0014,0656,0400,P4,False,0332,0652,0400,P3,False,2576,1134,0400,P2,False,1000,1750,0400,P1,