银行家算法

计算机操作系统2死锁的“3W”WhatWhyHow什么是死锁？为什么会发生死锁？怎么解决死锁？3死锁的处理方法（1）预防死锁：通过某些限制条件的设置，去破坏产生死锁的四个必要条件；（2）避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态；（3）检测死锁：及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施清除死锁；（4）解除死锁：撤消或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。4避免死锁—银行家算法设银行家有10万周转资金，P,Q,R分别需要8,3,9万元搞项目，如果P已申请到了4万，Q要申请2万，R要申请4万.Q1：客户要求分期贷款，一旦得到每期贷款，就能够归还贷款Q2：银行家应谨慎的贷款，防止出现坏帐什么是银行家问题？银行家-操作系统周转资金-系统资源贷款客户-进程当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待。银行家算法的实现思想5表示形式含义Available（可用资源数组）Available[j]＝k现有资源j的数目为kMax（最大需求矩阵）Max[i,j]＝k进程i对资源j的最大需求数目为kAllocation（分配矩阵）Allocation[i,j]＝k进程i当前已分得的资源j的数目为kNeed（需求矩阵）Need[i,j]＝k进程i尚需分配的资源j的数目为k银行家算法中的数据结构6银行家算法当Pi发出资源请求，分配一个Request向量然后系统按下述流程进行执行：Requesti：是进程Pi的请求向量如果Requesti[j]=K，表示进程i需要K个Rj类型的资源。银行家算法实现过程78安全性算法实现过程安全性算法两个向量：Work和FinishWork表示系统可提供给进程继续运行所需的各类资源数目（即在分配过程中，系统的可用资源数）。初始值Work∶=Available;Finish表示系统是否有足够的资源分配给进程i，使之运行完成。初始值Finish[i]:=false当有足够资源分配给进程时Finish[i]:=true910假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示。P4P3P2P1P0AvailableA,B,CNeedA,B,CAllocationA,B,CMaxA,B,C进程资源情况7,5,33,2,29,0,22,2,24,3,30,1,02,0,03,0,22,1,10,0,27,4,31,2,26,0,00,1,14,3,13,3,2银行家算法实例11（1）T0时刻系统是否安全？执行安全性算法进行检查：①向量初值Work:＝Available＝(3,3,2)；Finish[i]:＝false；（i＝0,1,…,4）②在进程集合中找到Need1＝(1,2,2)≤Work且Finish[1]＝false；③则设P1顺利执行完成，从而有：Work:＝Work＋Allocation1＝(3,3,2)＋(2,0,0)＝(5,3,2)Finish[1]:＝true银行家算法实例12Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243113Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue743532211011P3true532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243114Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue753743010743true743211011532true532200122332P0P3P1AllocationNeedP0010743P1200122P2302600P3211011P400243115Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P1AllocationNeedP0010743P1200122P2302600P3211011P400243116Chapter3处理机调度与死锁AllocationNeedP0010743P1200122P2302600P3211011P4002431true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P117④发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量Finish[i]＝true；且对应于该向量置为“true”的进程编号依次为：1→3→0→2→4，故：系统存在安全序列{P1，P3，P0，P2，P4}所以，T0时刻系统处于安全状态！银行家算法实例18Chapter3处理机调度与死锁由分析知：执行完P1、P3的资源分配请求之后，系统可用的资源数量可以满足其它3个进程的资源请求，则此时的资源分配顺序已无关紧要。所以：安全序列可以不唯一！true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P119（2）P1发出请求Request(1,0,2)，系统能分配资源吗？执行银行家算法：①Request1(1,0,2)≤Need1(1,2,2)；②Request1(1,0,2)≤Available(3,3,2)；③系统为P1进行预分配，并修改Available，Allocation1和Need1向量：银行家算法实例Request1(1,0,2)，Need1，Available20Available:＝Available－Request1＝(3,3,2)－(1,0,2)＝(2,3,0)Allocation1:＝Allocation1＋Request1＝(2,0,0)＋(1,0,2)＝(3,0,2)Need1:＝Need1－Request1＝(1,2,2)－(1,0,2)＝(0,2,0)银行家算法实例21④执行安全性算法：a.Work:＝Available＝(2,3,0)；Finish[i]:＝false；b.在进程集合中找到Need1＝(0,2,0)≤Work；b’.在进程集合中找到Need3＝(0,1,1)≤Work（5，3，2）且Finish[3]＝false；c.则设P1可顺利执行完成，从而有：Work:＝Work＋Allocation1＝(2,3,0)＋(3,0,2)＝(5,3,2)Finish[1]:＝true银行家算法实例22c’.则设P3顺利执行完成，从而有：Work:＝Work＋Allocation3＝(5,3,2)＋(2,1,1)＝(7,4,3)Finish[3]:＝true………执行安全性算法检查时，仍能够得到安全序列{P1，P3，P0，P2，P4}，故请求向量Request1(1,0,2)发出时系统安全！银行家算法实例23（3）P4发出请求Request(3,2,1)，系统能分配资源吗？执行银行家算法进行检查：①Request4(3,2,0)≤Need4(4,3,1)；②Request4(3,2,1)Available(2,3,0)故：P4资源请求失败，让其等待！＞银行家算法实例24（4）P0发出请求Request(0,2,0)，系统能分配资源吗？执行银行家算法进行检查：①Request0(0,2,0)≤Need0(7,4,3)；②Request0(0,2,0)≤Available(2,3,0)；③系统为P0作预分配，并修改有关数据：银行家算法实例25Available:＝Available－Request0＝(2,3,0)－(0,2,0)＝(2,1,0)Allocation0:＝Allocation0＋Request0＝(0,1,0)＋(0,2,0)＝(0,3,0)Need0:＝Need0－Request0＝(7,4,3)－(0,2,0)＝(7,2,3)银行家算法实例26MaxAllocationNeedAvailableP0753030723210P1322302020P2902302600P3222211011P4433002431显然，对于所有进程，条件Needi≤Available，均不成立。因此，P0此次资源请求预分配的结果，使系统进入不安全状态，故应撤消此次预分配。银行家算法实例27练习资源进程AllocationNeedAvailabler1r2r3r1r2r3r1r2r3P0P1P2P3P4311000110101000100012300010210120在银行家算法中，若出现下面的资源分配情况：28试问：1)该状态是否安全？2)如果进程P2提出请求Request(0，1，0)，系统能否将资源分配给它？3)如果系统立即满足P2的上述请求，则系统是否立即进入死锁状态？练习