《《精编》死锁与银行家算法介绍》由会员分享，可在线阅读，更多相关《《精编》死锁与银行家算法介绍（28页珍藏版）》请在金锄头文库上搜索。
1、死锁 银行家算法 1 死锁概念 指多个进程因竞争共享资源而造成的一种僵局 若无外力作用 这些进程都将永远不能再向前推进 即 一组进程中 每个进程都无限等待被该组进程中另一进程所占有的资源 因而永远无法得到的资源 这种现象称为进程死锁 这一组进程就称为死锁进程 思考 如果系统中有n个进程 则在等待队列中进程的个数最多为 个有n个进程的系统出现死锁时 死锁进程的个数k应满足的条件是 产生死锁的原因 1 竞争资源 资源不足 2 进程的推进顺序不当 1 竞争系统资源 若系统中只有一台打印机R1和一台读卡机R2 可供进程P1和P2共享 若形成环路 这样会产生死锁 由于进程的调度是独立的 请求和释放操作可
2、按如下序列进行 Ar1 Ar2 Ar3 Ar4 Br1 Br2 Br3 Br4Br1 Br2 Br3 Br4 Ar1 Ar2 Ar3 Ar4Ar1 Ar2 Br1 Ar3 Ar4 Br2 Br3 Br4Ar1 Br1 Ar2 Br2 Ar3 Ar4 Br3 Br4对序列 三个进程都能顺利进行 则会产生死锁 进程A B对资源的请求和释放 2 进程推进顺序不当引起死锁 思考 某系统中有3个并发进程都需要4个同类资源 该系统不会发生死锁的最少资源是 个P341例8 2 死锁避免 死锁避免定义 在系统运行过程中 对进程发出的每一个系统能够满足的资源申请进行动态检查 并根据检查结果决定是否分配资源 若分
3、配后系统可能发生死锁 则不予分配 否则予以分配 由于在避免死锁的策略中 允许进程动态地申请资源 因而 系统在进行资源分配之前预先计算资源分配的安全性 若此次分配不会导致系统进入不安全状态 则将资源分配给进程 否则 进程等待 其中最具有代表性的避免死锁算法是银行家算法 3 安全状态与不安全状态 安全状态指系统能按某种进程顺序 P1 Pn 来为每个进程Pi 1 i n 分配其所需资源 直至最大需求 使每个进程都可顺序完成 若系统不存在这样一个序列 则称系统处于不安全状态 如果存在 则称序列为安全序列 说明 并非所有的不安全状态都必然会转为死锁状态 但当系统进入不安全状态后 便有可能进入死锁 安全状
4、态一定是没有死锁发生的 避免死锁的实质 系统进行资源分配时 如何使系统不进入不安全状态 2 安全状态之例 假定系统中有三个进程P1 P2和P3 共有12台磁带机 进程P1总共要求10台磁带机 P2和P3分别要求4台和9台 假设在T0时刻 进程P1 P2和P3已分别获得5台 2台和2台磁带机 尚有3台空闲未分配 如下表所示 问 T0时刻是否安全 3 由安全状态向不安全状态的转换 如果不按照安全序列分配资源 则系统可能会由安全状态进入不安全状态 例如 在T0时刻以后 P3又请求1台磁带机 若此时系统把剩余3台中的1台分配给P3 则系统便进入不安全状态 因为 此时也无法再找到一个安全序列 例如 把其
5、余的2台分配给P2 这样 在P2完成后只能释放出4台 既不能满足P1尚需5台的要求 也不能满足P3尚需6台的要求 致使它们都无法推进到完成 彼此都在等待对方释放资源 即陷入僵局 结果导致死锁 P3的请求应拒绝 安全状态与不安全状态 不安全状态 不存在一个安全序列 不安全状态不一定导致死锁 4 利用银行家算法避免死锁 1 银行家算法中的数据结构 1 可利用资源向量Available 这是一个含有m个元素的数组 其中的每一个元素代表一类可利用的资源数目 其初始值是系统中所配置的该类全部可用资源的数目 其数值随该类资源的分配和回收而动态地改变 如果Available j K 则表示系统中现有Rj类资
6、源K个 2 最大需求矩阵Max 这是一个n m的矩阵 它定义了系统中n个进程中的每一个进程对m类资源的最大需求 如果Max i j K 则表示进程i需要Rj类资源的最大数目为K 3 分配矩阵Allocation 这也是一个n m的矩阵 它定义了系统中每一类资源当前已分配给每一进程的资源数 如果Allocation i j K 则表示进程i当前已分得Rj类资源的数目为K 4 需求矩阵Need 这也是一个n m的矩阵 用以表示每一个进程尚需的各类资源数 如果Need i j K 则表示进程i还需要Rj类资源K个 方能完成其任务 Need i j Max i j Allocation i j 2 银
7、行家算法设Requesti是进程Pi的请求向量 如果Requesti j K 表示进程Pi需要K个Rj类型的资源 当Pi发出资源请求后 系统按下述步骤进行检查 1 如果Requesti j Need i j 便转向步骤2 否则认为出错 因为它所需要的资源数已超过它所宣布的最大值 2 如果Requesti j Available j 便转向步骤 3 否则 表示尚无足够资源 Pi须等待 3 系统试探着把资源分配给进程Pi 并修改下面数据结构中的数值 Available j Available j Requesti j Allocation i j Allocation i j Requesti j
8、 Need i j Need i j Requesti j 4 系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 若安全 才正式将资源分配给进程Pi 以完成本次分配 否则 将本次的试探分配作废 恢复原来的资源分配状态 让进程Pi等待 3 安全性算法 1 设置两个向量 工作向量Work 它表示系统可提供给进程继续运行所需的各类资源数目 它含有m个元素 在执行安全算法开始时 Work Available Finish 它表示系统是否有足够的资源分配给进程 使之运行完成 开始时先做Finish i false 当有足够资源分配给进程时 再令Finish i true 2 从进程集合中找到
9、一个能满足下述条件的进程 Finish i false Need i j Work j 若找到 执行步骤 3 否则 执行步骤 4 3 当进程Pi获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 故应执行 Work j Work i Allocation i j Finish i true gotostep2 4 如果所有进程的Finish i true都满足 则表示系统处于安全状态 否则 系统处于不安全状态 4 银行家算法之例 假定系统中有五个进程 P0 P1 P2 P3 P4 和三类资源 A B C 各种资源的数量分别为10 5 7 在T0时刻的资源分配情况如图3 16所示 图3 1
10、6T0时刻的资源分配表 1 T0时刻的安全性检查 图3 17T0时刻的安全序列 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 16中的圆括号所示 再利用安全性算法检查此时系统是否安全 如图3 18 图3 18P1申请资源时的安全性检查 3 P4请求资源 P4发出请求向量Request4 3 3 0 系统按银行家算
11、法进行检查 Request4 3 3 0 Need4 4 3 1 Request4 3 3 0 Available 2 3 0 让P4等待 4 P0请求资源 P0发出请求向量Requst0 0 2 0 系统按银行家算法进行检查 Request0 0 2 0 Need0 7 4 3 Request0 0 2 0 Available 2 3 0 系统暂时先假定可为P0分配资源 并修改有关数据 如图3 19所示 图3 19为P0分配资源后的有关资源数据 5 安全性检查 Available 2 1 0 不能满足任何进程的需求 系统进入不安全状态 不能分配资源 思考 P0请求改为Request0 0 1 0 系统是否能分配资源
