(24)--6.4操作系统原理课件.ppt

6.4 死锁避免死锁避免2-资源分配拒绝资源分配拒绝 资源分配拒绝资源分配拒绝银行家算法主要思想：动态的检测资源分配状态以确保循环等待条件不可能成立。银行家算法银行家算法银行家拥有一笔周转资金；客户要求分期贷款；银行家应谨慎的贷款，防止出现坏帐。如果客户能够得到各期贷款，就一定能够归还贷款，否则就不能归还贷款。用银行家算法避免死锁用银行家算法避免死锁操作系统（银行家）操作系统管理的资源(周转资金)进程（要求贷款的客户）系统状态安全状态不安全状态 假设：某个系统具有固定数量的进程和资源，任何时候一个进程可能分配到零个或多个资源。系统状态当前给进程分配的资源情况；安全状态存在一个安全序列，按照这个顺序去为进程分配资源，则所有进程都能运行直到结束，不会导致死锁。不安全状态不满足安全状态，则为不安全状态。安全安全状态例状态例最大需求最大需求 当前占有当前占有P0 10 5P1 4 2P2 9 2说明：某系统有说明：某系统有12台磁带驱台磁带驱动器动器P0：最多要求：最多要求10台台P1：最多要求：最多要求4台台P2：最多要求：最多要求9台台安全状态安全状态P1 分配分配2；用完释放；用完释放4；则系统剩余；则系统剩余5P0 分配分配5；用完释放；用完释放10；则系统剩余；则系统剩余10P2 分配分配7；用完释放；用完释放9；则系统剩余；则系统剩余12存在安全序列存在安全序列当前系统状态是否安全是否满足进程提出的新的资源需求发生死锁 拒绝为进程分配资源 否否安全、不安全和死锁状态空间安全、不安全和死锁状态空间死锁死锁不安全不安全安全安全结论：安全状态不是死锁状态死锁状态是不安全状态不是所有不安全状态都是死锁状态银行家算法银行家算法四个数据结构：Available：系统可用资源数量 Claim：进程对资源的最大需求量 Allocation：进程已经分配到的资源数量 Need：进程完成其工作还需要的资源数量Needi,j=Claimi,j-Allocationi,j 银行家算法安全性算法资源请求算法安全性算法安全性算法用于确定计算机系统是否处于安全状态1)设Work和Finish分别是长度为m和n的向量，初始化Work:=Available，Finishi=false(i=1,2,n)2)查找 i 使其满足a.Finishi=falseb.Needi=Work 若没有这样的 i 存在，转到4）。安全性算法安全性算法3)Work:=Work+Allocationi Finishi:=true 返回到2）4)如果对所有 i，Finishi=true，则系统处于安全状态资源请求算法资源请求算法设设Requesti 为进程为进程Pi的请求向量的请求向量1)如果Requesti=Needi，那么转到第2）步。否则，产生出错条件，因为进程已超过了其请求。2)如果Requesti=Available，那么转到第3）步。否则，Pi等待，因为没有可用资源。资源请求算法资源请求算法1)假定系统可以分配给进程Pi 所请求的资源，并按如下方式修改状态：Available:=Available Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi Requesti;4)调用安全性算法确定新状态是否安全安全操作完成且进程Pi分配到其所需要的资源不安全进程Pi必须等待，并将数据结构恢复到原状态（即 3）的逆操作）死锁避免死锁避免的缺点的缺点事先声明每个进程请求的最大资源进程必须是无关的，其执行的顺序必须没有任何同步要求的限制分配的资源数目必须是固定的在占有资源时，进程不能退出死锁避免死锁避免的优点的优点不需要死锁预防中的抢占和回滚进程比死锁预防的限制少