35产生死锁的原因和必要条件

35产生死锁的原因和必要条件内容摘要：

存在一个安全序列 P2， P1， P3 32 安全状态的例子 例：假定系统有三个进程 P P P3，共有 12台磁带机。 进程 P1总共要求 10台磁带机， P2和 P3分别要求 4台和九台。 设在 T0时刻，进程 P P2和 P3已经获得 5台、 2台和2台，还有 3台空闲没有分配。 进程 最大需求 已分配 可用 P1 10 5 3 P2 P3 4 2 2 9 T0时刻系统时安全的。 这时存在一个安全序列 P2， P1， P3 33 • 虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。 因此，避免死锁的实质是如何使系统不进入不安全状态。 • 系统的状态可能通过下述来描述： 进程剩余申请数＝最大申请数－占有数。 可分配资源数＝总数－占有数之和。 34 • 银行家算法 – 银行家拥有一笔周转资金 – 客户要求分期贷款 ， 如果客户能够得到各期贷款 ， 就一定能够归还贷款 ， 否则就一定不能归还贷款 – 银行家应谨慎的贷款 ， 防止出现坏帐 • 用银行家算法避免死锁 – 操作系统 （ 银行家 ） – 操作系统管理的资源 (周转资金 ) – 进程 （ 要求贷款的客户 ） 35 银行家算法 • 银行家算法是最有代表性的避免死锁算法，是 Dijkstra提出的银行家算法。 这是由于该算法能用于银行系统现金贷款的发放而得名。 为实现银行家算法，系统中必须设置若干数据结构。 36 • 一 、 银行家算法中的数据结构 • 1 可利用资源向量 Available • 是一个含有 m个元素 ， 其中的每一个元素代表一类可利用的资源数目 ， 其初值是系统中所配 置 的 该 类 全 部 可 用 资 源 数 目。 如果Available[j]=k， 表示系统中现有 Rj类资源 k个。 • 2 最大需求矩阵 Max • 是一个含有 nm的矩阵 ， 它定义了系统中 n个进程中的每一个进程对 m类资源的最大需求。 如果 Max(i,j)=k， 表示进程 i需要 Rj类资源的最大数目为 k。 Available= 3 5 4 2 8 3 8 6 1 37 • 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) 38 • 二 、 银行家算法 设 Requesti是进程 Pi的请求向量 ， 如果进程 Pi需要 K个Rj类资源 ， 当 Pi发出资源请求后 ， 系统按下述步骤进行检查： 1 如果 Requesti≤ Needi,则转向步骤 2；否则认为出错。 （ 因为它所需要的资源数已超过它所宣布的最大值。 2如果 Requesti≤ Available,则转向步骤 3；否则 ， 表示系统中尚无足够的资源 ， Pi必须等待 3 系统试探把要求的资源分配给进程 Pi， 并修改下面数据结构中的数值： Available:=AvailableRequesti。 Allocation:=Allocation+Requesti。 Needi:= Needi Requesti。 4 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。 若安全，正式将资源分配给进程 Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程 Pi等待。 39 三 、 安全性算法 系统所执行的安全性算法可描述如下： 1 设置两个向量 ① 工作向量 源 的 数 目 ， 它 含 有 m 个 元 素 ， 执 行 安 全 算 法 开 始 时 ，Work:=Available。 ② ， 使之运行完成。 开始时先做 Finish[i]:=false；当有足够的资源分配给进程时 ，令 Finish[i]:=true. 2 从 进 程 集 合 中 找 到 一 个 能 满 足 下 述 条 件 的 进 程 ： ①Finish[i]=false。 ② Needi≤Work . 如找到 ， 执行步骤 3；否则执行步骤 4。 3 当进程 Pi获得资源后 ， 可顺利执行 ， 直至完成 ， 并释放出分配给它的资源 ， 故执行： Work:=Work+Allocation。 Finish[i]:=true。 Goto step2。 4 如果所有进程的 Finish[i]=true，则表示系统处于安全状态；否则，系统处于不安全状态。 40 要记住的一些变量的名称 1 Available（ 可利用资源向量 ） 某类可利用的资源数目 ， 其初值是系统中所配置的该类全部可用资源数目。 2 Max最大需求矩阵 某个进程对某类资源的最大需求数 3 Allocation分配矩阵 某类资源当前非配给某进程的资源数。 4 Need需求矩阵 某个进程还需要的各类资源数。 Need= MaxAllocation 系统把进程请求的资源分配给它以后要修改的变量 Available:=AvailableRequest。 Allocation:=Allocation+Request。 Need:= Need Request。 41 银行家算法之例 • 假。