银行家算法精选ppt课件.ppt

计算机操作系统 银行家算法 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 银行家算法中的数据结构 6 银行家算法当Pi发出资源请求 分配一个Request向量然后系统按下述流程进行执行 Requesti 是进程Pi的请求向量如果Requesti j K 表示进程i需要K个Rj类型的资源 银行家算法实现过程 7 8 安全性算法实现过程 安全性算法 两个向量 Work和Finish Work表示系统可提供给进程继续运行所需的各类资源数目 即在分配过程中 系统的可用资源数 初始值Work Available Finish表示系统是否有足够的资源分配给进程i 使之运行完成 初始值Finish i false当有足够资源分配给进程时Finish i true 9 10 假定系统中有五个进程 P0 P1 P2 P3 P4 和三类资源 A B C 各种资源的数量分别为10 5 7 在T0时刻的资源分配情况如下图所示 7 5 33 2 29 0 22 2 24 3 3 0 1 02 0 03 0 22 1 10 0 2 7 4 31 2 26 0 00 1 14 3 1 3 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 银行家算法实例 12 true 532 P1 13 true 743 532 14 true 753 743 15 true 1055 753 16 17 发现 目前可执行的所有资源分配工作完成之后 各个进程对应的状态向量Finish i true 且对应于该向量置为 true 的进程编号依次为 1 3 0 2 4 故 系统存在安全序列 P1 P3 P0 P2 P4 所以 T0时刻系统处于安全状态 银行家算法实例 18 由分析知 执行完P1 P3的资源分配请求之后 系统可用的资源数量可以满足其它3个进程的资源请求 则此时的资源分配顺序已无关紧要 所以 安全序列可以不唯一 19 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 Available 20 Available 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 在进程集合中找到Need1 0 2 0 Work b 在进程集合中找到Need3 0 1 1 Work 5 3 2 且Finish 3 false 银行家算法实例 22 执行安全性算法检查时 仍能够得到安全序列 P1 P3 P0 P2 P4 故请求向量Request1 1 0 2 发出时系统安全 银行家算法实例 23 3 P4发出请求Request 3 2 1 系统能分配资源吗 执行银行家算法进行检查 银行家算法实例 24 4 P0发出请求Request 0 2 0 系统能分配资源吗 执行银行家算法进行检查 Request0 0 2 0 Need0 7 4 3 Request0 0 2 0 Available 2 3 0 系统为P0作预分配 并修改有关数据 银行家算法实例 25 Available 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 银行家算法实例 26 显然 对于所有进程 条件Needi Available 均不成立 因此 P0此次资源请求预分配的结果 使系统进入不安全状态 故应撤消此次预分配 银行家算法实例 27 练习 在银行家算法中 若出现下面的资源分配情况 28