实验二 银行家算法.doc

实验二实验二 银行家算法银行家算法 一 一 实验目的实验目的 1 理解死锁避免相关内容 2 掌握银行家算法主要流程 3 掌握安全性检查流程 操作系统中的死锁避免部分的理论进行实验 要求实验者设计一个程序 该程序可对每一次资源申请采用银行家算法进行分配 二 实验设备二 实验设备 PC 机 windows2000 操作系统 Turbo C 2 0 三 三 实验要求实验要求 本实验要求 4 学时完成 1 设计多个资源 3 2 设计多个进程 3 3 设计银行家算法相关的数据结构 4 动态进行资源申请 分配 安全性检测并给出分配结果 5 撰写实验报告 并在实验报告中画出银行家和安全性检查函数流程图 四 四 预备知识预备知识 死锁避免定义 在系统运行过程中 对进程发出的每一个资源申请进行动 态检查 并根据检查结果决定是否分配资源 若分配后系统可能发生死锁 则 不予分配 否则予以分配 由于在避免死锁的策略中 允许进程动态地申请资源 因而 系统在进行 资源分配之前预先计算资源分配的全安性 若此次分配不会导致系统进入不安 全状态 则将资源分配给进程 否则 进程等待 其中最具有代表性的避免死 锁算法是银行家算法 1 系统安全状态 1 安全状态 所谓系统是安全的 是指系统中的所有进程能够按照某一种次序分配资源 并且依次地运行完毕 这种进程序列 P1 P2 Pn 就是安全序列 如果存在 这样一个安全序列 则系统是安全的 并非所有的不安全状态都会转为死锁状态 但当系统进入不安全状态后 便有可能进入死锁状态 反之 只要系统处于安全状态 系统便可避免进入死 锁状态 所以避免死锁的实质 系统在进行资源分配时 如何使系统不进入不 安全状态 2 安全状态之例 假设系统有三个进程 共有 12 台磁带机 各进程的最大需求和 T0 时刻已 分配情况如下表 进程最大需求已分配可用 P1 P2 P3 10 4 9 5 2 2 3 问 T0 时刻是否安全 答 T0 时刻是安全的 因为存在安全序列 P2 P1 P3 不安全序列 P1 P3 P2 P3 P1 3 由安全状态向不安全状态的转换 如果不按照安全序列分配资源 则系统可能会由安全状态进入不安全状态 例如 在 T0 时刻以后 P3 又请求 1 台磁带机 若此时系统把剩余 3 台中的 1 台分配给 P3 则系统便进入不安全状态 因为 此时也无法再找到一个安全 序列 例如 把其余的 2 台分配给 P2 这样 在 P2 完成后只能释放出 4 台 既不能满足 P1 尚需 5 台的要求 也不能满足 P3 尚需 6 台的要求 致使它们都 无法推进到完成 彼此都在等待对方释放资源 即陷入僵局 结果导致死锁 2 利用银行家算法避免死锁 1 银行家算法中的数据结构 可利用资源向量 Available 这是一个含有m个元素的数组 其中的每一个元素代表一类可利用的 资源数目 其初始值是系统中所配置的该类全部可用资源的数目 其数值 随该类资源的分配和回收而动态地改变 如果 Available j K 则表示 系统中现有 Rj 类资源K个 最大需求矩阵 Max 最大需求矩阵 Max 这是一个n m的矩阵 它定义了系统中n个进程 中的每一个进程对m类资源的最大需求 如果 Max i j K 则表示进程 i 需要 Rj 类资源的最大数目为 K 分配矩阵 Allocation 这也是一个n m的矩阵 它定义了系统中每一类资源当前已分配给每 一进程的资源数 如果 Allocation i j K 则表示进程 i 当前已分得 Rj 类资源的数目为K 需求矩阵 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 设置两个向量 结束 否是 申请失败 以上分配作废 恢复原来的分配状态 Available j Available j Request i j Allocation i j Allocation i j Request i j Need i j Need i j Request i j N Y N Y Request i j Need i j 出错返回 return error Request i j Available j 出错返回 进程阻 塞 return error Available j Available j Request i j Allocation i j Allocation i j Request i j Need i j Need i j Request i j 假定分配 输入初始参数 资 源分配及请求情况 开始 假定分配之后 系统安 全吗 申请成功 输出各种 数据的变化 图 银行家算法流程图 工作向量 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 都满足 则表示系统处于安全状 态 否则 系统处于不安全状态 安全性算法的参考流程图如下 Y 所有 finish 都为 true 输出安全序列 N Y N 存在 Finish i false res ava 最大需求矩阵 struct Max int max THREAD MAXNUM RESOURCE MAXNUM res max 已分配矩阵 struct Allocation int allocation THREAD MAXNUM RESOURCE MAXNUM res all 需求矩阵 struct Need int need THREAD MAXNUM RESOURCE MAXNUM res nee 临时进程的资源分配序列 int tmpSequence THREAD MAXNUM 可能的一个安全序列 int secSequence THREAD MAXNUM 找到一个安全执行序列的标志 int isFindSecQue 0 定义一系操作方法 进行显式地初始化操作 void init 打印操作 void printInfo 输入操作 void input 检测条件 Need Max Allocation int check 测试可得到的资源能否江足要求 int check int threadID int need THREAD MAXNUM 当前待分配的进程需求 void curThreadNeed 更新操作 void update int thredID int need THREAD MAXNUM 释放操作 void release int threadID 安全性算法 int security int sequence THREAD MAXNUM 回溯得到进程执行序列 并执行安全性算法 void backtrack 交换数组中指定的两个值 void swapArray int arr THREAD MAXNUM int pos1 int pos2 拷贝数组 void copyArray int arr1 THREAD MAXNUM int arr2 THREAD MAXNUM int main init input int checkres check if checkres 0 printf 输入有问题 确认后重新输入 n exit 1 printInfo curThreadNeed printInfo printf 执行安全性算法 nENTER 键继续 n n getch backtrack if isFindSecQue 0 printf 未找到一个安全的进程执行序列 n return 0 void init int i j for i 0 i THREAD MAXNUM i for j 0 j RESOURCE MAXNUM j res all allocation i j 0 res max max i j 0 res nee need i j 0 tmpSequence i i secSequence i i for j 0 j RESOURCE MAXNUM j res ava available j 0 void printInfo int i j printf 当前资源分配 n printf 最大需求矩阵 t t 分配矩阵 t t 需求矩阵 n for i 0 i THREAD MAXNUM i for j 0 j RESOURCE MAXNUM j printf d t res max max i j for j 0 j RESOURCE MAXNUM j printf d t res all allocation i j for j 0 j RESOURCE MAXNUM j printf d t res nee need i j printf n printf n printf 可利用资源向量 t n for j 0 j RESOURCE MAXNUM j printf d t res ava available j printf n void input int i j printf 输入当前可利用资源 n for j 0 j RESOURCE MAXNUM j scanf d printf 输入分配矩阵 n for i 0 i THREAD MAXNUM i for j 0 j RESOURCE MAXNUM j scanf d printf 输入最大需求矩阵 n for i 0 i THREAD MAXNUM i for j 0 j RESOURCE MAXNUM j scanf d printf 输入需求矩阵 n for i 0 i THREAD MAXNUM i for j 0 j RESOURCE MAXNUM j scanf d int check int i j for i 0 i THREAD MAXNUM i for j 0 j RESOURCE MAXNUM j if res nee need i j res max max i j res all allocation i j return 0 return 1 int check int threadID int need THREAD MAXNUM int i for i 0 i res ava available i need i res nee need threadID i return 0 return 1 void curThreadNeed printf 输入当前进程的编号及所需的资源向量 n int need scanf d int res need RESOURCE MAXNUM int i for i 0 i RESOURCE MAXNUM i scanf d printf 进程 d 需要的资源向量为 n need for i 0 i RESOURCE MAXNUM i printf d t res need i printf n if check need res need 0 printf 需求大于可获得的资源 请确定后再输入 n exit 1 更新操作 update need res need void update int thredID int need THREAD MAXNUM int j for j 0 j RESOURCE MAXNUM j res ava available j need j res nee need thredID j need j res all allocation thredID j need j void release int threadID int i for i 0 i RESOURCE MAXNUM i res ava available i res max max threadID i int security int sequence THREAD MAXNUM 工作向量 int Work RESOURCE MAXNUM int i for i 0 i RESOURCE MAXNUM i Work i res ava available i for i 0 i THREAD MAXNUM i 判断当前能否分配资源 int canAllFlag 1 能分配的标志 int j for j 0 j Work j canAllFlag 0 break if canAllFlag 0 r