处理机调与死锁part4.pptx

第三章 处理机调度与死锁 1*安全性算法 (1)设置两个向量：设置两个向量：工作向量工作向量Work:Finish:(2)从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：Finishi=false;Needi,jWorkj；若若找到，找到，执行步骤执行步骤(3)，否则，执行步骤否则，执行步骤(4)。(3)当当进进程程Pi获获得得资资源源后后，可可顺顺利利执执行行，直直至至完完成成，并并释释放出分配给它的资源，故应执行：放出分配给它的资源，故应执行：Workj=Workj+Allocationi,j;Finishi=true;go to step 2;(4)如如果果所所有有进进程程的的Finishi=true都都满满足足，则则表表示示系系统处于安全状态；否则，系统处于不安全状态。统处于安全状态；否则，系统处于不安全状态。第三章 处理机调度与死锁 2利用银行家算法避免死锁利用银行家算法避免死锁 1.银行家算法中的数据结构银行家算法中的数据结构 (1)可可利利用用资资源源向向量量Available。这这是是一一个个含含有有m个个元元素素的的数数组组，其其中中的的每每一一个个元元素素代代表表一一类类可可利利用用的的资资源源数数目目，其其初初始始值值是是系系统统中中所所配配置置的的该该类类全全部部可可用用资资源源的的数数目目，其其数值随该类资源的分配和回收而动态地改变。数值随该类资源的分配和回收而动态地改变。如果如果Availablej=K，则表示系统中现有，则表示系统中现有Rj类资源类资源K个个。第三章 处理机调度与死锁 3 (2)最最大大需需求求矩矩阵阵Max。这这是是一一个个nm的的矩矩阵阵，它它定定义义了了系系统统中中n个个进进程程中中的的每每一一个个进进程程对对m类类资资源源的的最最大大需需求求。如如果果Maxi,j=K，则则表表示示进进程程i需需要要Rj类类资资源源的的最最大大数数目目为为K。(3)分分配配矩矩阵阵Allocation。这这也也是是一一个个nm的的矩矩阵阵，它它定定义义了了系系统统中中每每一一类类资资源源当当前前已已分分配配给给每每一一进进程程的的资资源源数数。如如果果Allocationi,j=K，则则表表示示进进程程i当当前前已已分分得得Rj类类资资源源的的数数目目为为K。(4)需需求求矩矩阵阵Need。这这也也是是一一个个nm的的矩矩阵阵，用用以以表表示示每每一一个个进进程程尚尚需需的的各各类类资资源源数数。如如果果Needi,j=K，则则表表示示进进程程i还需要还需要Rj类资源类资源K个，方能完成其任务个，方能完成其任务。Needi,j=Maxi,j-Allocationi,j 第三章 处理机调度与死锁 4 2.银行家算法银行家算法 设设Requesti是是进进程程Pi的的请请求求向向量量，如如果果Requestij=K，表表示示进进程程Pi需需要要K个个Rj类类型型的的资资源源。当当Pi发发出出资资源源请请求求后后，系系统按下述步骤进行检查：统按下述步骤进行检查：(1)如如果果RequestijNeedi,j，便便转转向向步步骤骤2；否否则则认为出错，因为它所需要的资源数已超过它所宣布的最大值。认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如如果果RequestijAvailablej，便便转转向向步步骤骤(3)；否则，否则，表示尚无足够资源，表示尚无足够资源，Pi须等待。须等待。第三章 处理机调度与死锁 5 (3)系系统统试试探探着着把把资资源源分分配配给给进进程程Pi，并并修修改改下下面面数数据据结结构中的数值：构中的数值：Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;(4)系系统统执执行行安安全全性性算算法法，检检查查此此次次资资源源分分配配后后，系系统统是是否否处处于于安安全全状状态态。若若安安全全，才才正正式式将将资资源源分分配配给给进进程程Pi，以以完完成成本本次次分分配配；否否则则，将将本本次次的的试试探探分分配配作作废废，恢恢复复原原来来的的资源分配状态，让进程资源分配状态，让进程Pi等待。等待。第三章 处理机调度与死锁 64.银行家算法之例银行家算法之例 假假定定系系统统中中有有五五个个进进程程P0,P1,P2,P3,P4和和三三类类资资源源A,B,C，各各种种资资源源的的数数量量分分别别为为10、5、7，在在T0时时刻刻的的资资源分配情况如图源分配情况如图 3-15 所示。所示。图 3-15 T0时刻的资源分配表 第三章 处理机调度与死锁 7(1)T0时刻的安全性：图 3-16 T0时刻的安全序列 第三章 处理机调度与死锁 8 (2)P1请请求求资资源源：P1发发出出请请求求向向量量Request1(1，0，2)，系统按银行家算法进行检查：系统按银行家算法进行检查：Request1(1,0,2)Need1(1,2,2)Request1(1,0,2)Available1(3,3,2)系系统统先先假假定定可可为为P1分分配配资资源源，并并修修改改Available,Allocation1和和Need1向向量量，由由此此形形成成的的资资源源变变化化情情况况如如图图 3-15 中的圆括号所示。中的圆括号所示。再利用安全性算法检查此时系统是否安全。再利用安全性算法检查此时系统是否安全。第三章 处理机调度与死锁 9图 3-17 P1申请资源时的安全性检查 第三章 处理机调度与死锁 10 (3)P4请请求求资资源源：P4发发出出请请求求向向量量Request4(3，3，0)，系统按银行家算法进行检查：系统按银行家算法进行检查：Request4(3,3,0)Need4(4,3,1);Request4(3,3,0)剩余资源数（剩余资源数（2,2,32,2,3），所以不能分），所以不能分配。配。（3 3）在（）在（2 2）的基础上，若进程）的基础上，若进程P4P4请求资源（请求资源（2,0,12,0,1），按银），按银行家算法进行检查：行家算法进行检查：P4P4请求资源（请求资源（2,0,12,0,1）=P4=P4资源需求量（资源需求量（2,2,12,2,1）P4P4请求资源（请求资源（2,0,12,0,1）=剩余资源数（剩余资源数（2,3,32,3,3）试分配并修改相应数据结构，资源分配情况如下：试分配并修改相应数据结构，资源分配情况如下：AllocationAllocationNeedNeedAvailableAvailableA AB BC CA AB BC CA AB BC CP1P12 21 12 23 34 47 70 03 32 2P2P24 40 02 21 13 34 4P3P34 40 05 50 00 06 6P4P44 40 05 50 02 20 0P5P53 31 14 41 11 10 0第三章 处理机调度与死锁 16再利用安全性算法检查系统是否安全，可得此时刻的安全性再利用安全性算法检查系统是否安全，可得此时刻的安全性分析情况：分析情况：WorkWorkNeedNeedAllocationAllocationWork+Work+AllocatioAllocation nFinisFinish hA AB BC CA AB BC CA AB BC CA AB BC CfalsefalseWorkWorkNeedNeedAllocationAllocationWork+Work+AllocatioAllocation nFinisFinish hA AB BC CA AB BC CA AB BC CA AB BC CP4P40 03 32 20 02 20 04 40 05 54 43 37 7truetrueP5P54 43 37 71 11 10 03 31 14 47 74 41111TrueTrueP3P37 74 411110 00 06 64 40 05 511114 41616TrueTrueP2P211114 416161 13 34 44 40 02 215154 41818TrueTrueP1P115154 418183 34 47 72 21 12 217175 52020TrueTrue此时，存在此时，存在1 1个安全序列个安全序列 P4,P5,P3,P2,P1，故该状态，故该状态是安全的，可以立即将是安全的，可以立即将P4P4所申请的资源分配给它。所申请的资源分配给它。第三章 处理机调度与死锁 17（4 4）再（）再（3 3）的基础上，若进程）的基础上，若进程P1P1请求资源（请求资源（0,2,00,2,0），按银），按银行家算法检查：行家算法检查：P1P1请求资源（请求资源（0,2,00,2,0）=P1=P1资源需求量（资源需求量（3,4,73,4,7）P1P1请求资源（请求资源（0,2,00,2,0）=剩余资源数（剩余资源数（0,3,20,3,2）试分配并修改相应数据结构，资源分配情况如下：试分配并修改相应数据结构，资源分配情况如下：AllocationAllocationNeedNeedAvailableAvailableA AB BC CA AB BC CA AB BC CP1P12 23 32 23 32 27 70 01 12 2P2P24 40 02 21 13 34 4P3P34 40 05 50 00 06 6P4P44 40 05 50 02 20 0P5P53 31 14 41 11 10 0 再利用安全性算法检查系统是否安全，可用资源再利用安全性算法检查系统是否安全，可用资源AvailableAvailable（0,1,20,1,2）已不能满足任何进程的资源需求，故）已不能满足任何进程的资源需求，故系统进入不安全状态，此时系统不能将资源分给系统进入不安全状态，此时系统不能将资源分给P1P1。第三章 处理机调度与死锁 183.7 死锁的检测与解除死锁的检测与解除 3.7.1 死锁的检测死锁的检测 1.资源分配图资源分配图(Resource Allocation Graph)图 3-19 每类资源有多个时的情况 第三章 处理机调度与死锁 19 (2)凡凡属属于于E中中的的一一个个边边eE，都都连连接接着着P中中的的一一个个结结点点和和R中中的的一一个个结结点点，e=pi,rj是是资资源源请请求求边边，由由进进程程pi指指向向资资源源rj，它它表表示示进进程程pi请请求求一一个个单单位位的的rj资资源源。e=rj,pi是是资资源源分分配配边边，由由资资源源rj指指向向进进程程pi,它它表表示示把把一一个个单单位位的的资资源源rj分配给进程分配给进程pi。第三章 处理机调度与死锁 202.死锁定理死锁定理 图 3-20 资源分配图的简化 第三章 处理机调度与死锁 213.死锁检测中的数据结构死锁检测中的数据结构 (1)可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。(2)把不占用资源的进程(向量Allocation=0)记入L表中，即LiL。(3)从进程集合中找到一个RequestiWork的进程，做如下处理：将其资源分配图简化，释放出资源，增加工作向量Work=Work+Allocationi。将它记入L表中。第三章 处理机调度与死锁 22 (4)若若不不能能把把所所有有进进程程都都记记入入L表表中中，便便表表明明系系统统状状态态S的的资资源源分分配配图图是是不不可可完完全全简简化化的的。因因此此，该该系系统统状状态态将将发发生生死锁。死锁。Work=Available;L=Li|Allocationi=0Requesti=0 for all Li L do begin for all RequestiWork do begin Work=Work+Allocationi;LiL;end end deadlock =(L=p1,p2,pn);第三章 处理机调度与死锁 23试化简下图的进程试化简下图的进程-资源图，并利用死锁定理给出相应的结论。资源图，并利用死锁定理给出相应的结论。P3P1P2结论：产生死锁结论：产生死锁第三章 处理机调度与死锁 24试化简下图的进程试化简下图的进程-资源图，并利用死锁定理给出相应的结论。资源图，并利用死锁定理给出相应的结论。P3P1P2第三章 处理机调度与死锁 25P3P1P2第三章 处理机调度与死锁 26P3P1P2结论：不产生死锁结论：不产生死锁第三章 处理机调度与死锁 273.7.2 死锁的解除死锁的解除(1)剥夺资源。(2)撤消进程。第三章 处理机调度与死锁 28图 3-21 付出代价最小的死锁解除方法 为把系统从死锁状态中解脱出来，所花费的代价可表示为：为把系统从死锁状态中解脱出来，所花费的代价可表示为：R(S)min=minCui+minCuj+minCuk+