银行家算法安全性序列分析

银行家算法安全性序列分析银行家算法安全性序列分析 摘要 摘要 在操作系统的处理机调度的过程中 由于竞争资源或者进程间推进 顺序非法 都会导致死锁的发生 本文主要研究如何利用银行家算法可以避免 死锁 并分析银行家算法安全性序列 关键词 银行家算法 安全性序列 避免死锁关键词 银行家算法 安全性序列 避免死锁 引言引言 处理死锁的方法主要包括预防死锁 避免死锁 检测死锁和解除死锁 而 利用银行家算法可以避免死锁 在这一避免死锁的过程中 银行家算法安全性 序列分析是尤为重要的 1 银行家算法中的数据结构银行家算法中的数据结构 1 空闲资源向量 Available 这是一个数组 它里面包括 m 个元素 这 些元素都可以分别用来表示一种空闲的资源的数量的多少 系统中存储的这种 全部空闲的资源的数量的多少为它的初始值 随该类资源的分配和回收 其数 值发生动态地改变 如果 Available j K 那么 系统中当前存在 K 个 Rj 类 资源 2 最大需求矩阵 Max Max 矩阵是 n m 维的 该矩阵定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求 如果 Max i j K 那么 进程 i 需要 Rj 类资源的最大数量的多少为 K 3 分配矩阵 Allocation Allocation 矩阵是 n m 维的 该矩阵定义了 系统中每一类资源当前已分配给每一进程的资源数 如果 Allocation i j K 那么 进程 i 当前已分得 Rj 类资源的数量的多少为 K 4 需求矩阵 Need Need 矩阵是 n m 维的 该矩阵定义了所有进程仍 然需求的各类资源数 如果 Need i j K 那么 为了能够完成其任务 进程 i 还需要 Rj 类资源 K 个 Need i j Max i j Allocation i j 2 银行家算法银行家算法 设 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 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 从进程集合中找到一个能满足下述条件的进程 Finish i false Need i j Work j 如果找到 那么 执行步骤 3 否则 执行步骤 4 3 当进程 Pi 获得资源后 可顺利执行 直至完成 并释放出分配给它 的资源 故应执行 Work j Work i Allocation i j Finish i true go to step 2 4 如果所有进程的 Finish i true 都满足 则表示系统处于安全状 态 否则 系统处于不安全状态 4 银行家算法安全性序列分析之例银行家算法安全性序列分析之例 假定系统中有五个进程 P0 P1 P2 P3 P4 和三类资源 A B C 各种 资源的数量分别为 10 5 7 在 T0 时刻的资源分配情况如表 1 所示 表 1 T0 时刻的资源分配表 MaxAllocationNeedAvailable资源情况 进程 A B CA B CA B CA B C P07 5 30 1 07 4 3 P1 3 2 22 0 01 2 2 P2 9 0 23 0 26 0 0 P3 2 2 22 1 10 1 1 P4 4 3 30 0 24 3 1 3 3 2 1 T0 时刻的安全性 表 2 T0 时刻的安全序列 WorkNeedAllocationWork Allocatio n 资源情况 进程 A B CA B CA B CA B C Finish P13 3 21 2 22 0 05 3 2TRUE P3 5 3 20 1 12 1 17 4 3 TRUE P4 7 4 34 3 10 0 27 4 5 TRUE P2 7 4 56 0 03 0 210 4 7 TRUE P0 10 4 77 4 30 1 010 5 7 TRUE 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 向量 由此形成的资源变化情况如表 2 所示 表 2 系统先假定可为 P1 分配资源时刻的资源分配表 MaxAllocationNeedAvailable资源情况 进程 A B CA B CA B CA B C P07 5 30 1 07 4 3 P1 3 2 23 0 20 2 0 P2 9 0 23 0 26 0 0 P3 2 2 22 1 10 1 1 P4 4 3 30 0 24 3 1 2 3 0 再利用安全性算法检查此时系统是否安全 表 3 P1 申请资源时的安全性检查 WorkNeedAllocationWork Allocatio n 资源情况 进程 A B CA B CA B CA B C Finish P12 3 00 2 03 0 25 3 2TRUE P3 5 3 20 1 12 1 17 4 3 TRUE P4 7 4 34 3 10 0 27 4 5 TRUE P2 7 4 56 0 03 0 210 4 7 TRUE P0 10 4 77 4 30 1 010 5 7 TRUE 3 P4 请求资源 P4 发出请求向量 Request4 3 3 0 系统按银行家 算法进行检查 Request4 3 3 0 Need4 4 3 1 Request4 3 3 0 Available 2 3 0 让 P4 等待 参考文献 参考文献 1 崔建平 深入探讨银行家算法 J 科技信息 学术研究 2008 17 2 侯刚 深入解