2022年银行家算法实现.docx

《2022年银行家算法实现.docx》由会员分享，可在线阅读，更多相关《2022年银行家算法实现.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 银行家算法的模拟实现一、设计目的1 、明白多道程序系统中,多个进程并发执行的资源安排；2 、把握死锁的产生的缘由、产生死锁的必要条件和处理死锁的基本方法；3 、把握预防死锁的方法,系统安全状态的基本概念；4 、把握银行家算法,明白资源在进程并发执行中的资源安排策略；5 、懂得死锁防止在当前电脑系统不常使用的缘由；二、设计任务在 Windows7系统的 VS 环境下运行程序；试验三通过最有代表性的防止死锁的算法Dijkstra的银行家算法程序实现来懂得进程并发中的资源安排,死锁防止在死锁解决中的可行性； 设计程序在自动、手动方式下运行,懂得银行家

2、算法的实质；三、设计内容与步骤 A、银行家算法设计的学问预备；1 、死锁概念；在多道程序系统中,虽可借助于多个进程的并发执行,来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危急 死锁； 所谓死锁 Deadlock,是指多个进程在运行中因争夺资源而造成的一种僵局Deadly_Embrace,当进程处于这种僵持状态时,假设无外力作用,它们都将无法再向前推动；一组进程中,每个进程都无限等待被该组进程中另一进程 所占有的资源,因而永久无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程；2 、关于死锁的一些结论：参加死锁的进程最少是两个两个以上进程才会显现死锁参加死锁的进程至少有两

3、个已经占有资源 参加死锁的全部进程都在等待资源 参加死锁的进程是当前系统中全部进程的子集注：假如死锁发生,会铺张大量系统资源,甚至导致系统崩溃；3 、资源分类；永久性资源：可以被多个进程多次使用可再用资源可抢占资源 不行抢占资源暂时性资源：只可使用一次的资源；如信号量“ 申请 - 安排- 使用 - 释放” 模式,中断信号,同步信号等可消耗性资源4 、产生死锁的四个必要条件：互斥使用资源独占、不行强占不行剥夺、恳求和保持部分安排,占有申请、循环等 待；1 互斥使用资源独占一个资源每次只能给一个进程使用名师归纳总结 - - - - - - -第 1 页,共 5 页精选学习资料 - - - - -

4、- - - - 2 不行强占不行剥夺资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放 3 恳求和保持部分安排,占有申请一个进程在申请新的资源的同时保持对原有资源的占有只有这样才是动态申请,动态安排4 循环等待 存在一个进程等待队列 P1 , P2 , , Pn, 其中 P1 等待 P2 占有的资源, P2 等待 P3 占有的资源, ,5 、 死锁的解决方案 5.1 产生死锁的例子 申请不同类型资源产生死锁 P1：申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪P2：申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪申请同类资源产生死锁如内存Pn 等待 P1 占有的资

5、源,形成一个进程等待环路设有资源 R,R 有 m 个安排单位,由n 个进程 P1,P2, ,Pn n m共享；假设每个进程对R 的申请和释放符合以下原就：* 一次只能申请一个单位 * 满意总申请后才能使用 * 使用完后一次性释放 m=2 ,n=3 资源安排不当导致死锁产生 5.2 死锁预防 : 定义 : 在系统设计时确定资源安排算法,保证不发生死锁；详细的做法是破坏产生死锁的四个必要条件之一破坏“ 不行剥夺” 条件在答应进程动态申请资源前提下规定,一个进程在申请新的资源不能立刻得到满意而变为等待状态之前,必需释放已占有的全部资源,假设需要再重新申请破坏“ 恳求和保持” 条件 要求每个进程在运行

6、前必需一次性申请它所要求的全部资源,且仅当该进程所要资源均可满意时才赐予一次性安排破坏“ 循环等待” 条件 采纳资源有序安排法：名师归纳总结 - - - - - - -第 2 页,共 5 页精选学习资料 - - - - - - - - - 把系统中全部资源编号,进程在申请资源时必需严格按资源编号的递增次序进行,否就操作系统不予安排6 安全状态与担心全状态安全状态：假如存在一个由系统中全部进程构成的安全序列 P1, Pn,就系统处于安全状态；一个进程序列 P1 , , Pn 是安全的,假如对于每一个进程 Pi1 in ,它以后尚需要的资源量不超过系统当前剩余资源量与全部进程 Pj j i 当前占

7、有资源量之和,系统处于安全状态 安全状态肯定是没有死锁发生的 担心全状态 : 不存在一个安全序列,担心全状态肯定导致死锁；B、银行家算法一、银行家算法中的数据结构1 可利用资源向量 Available 它是一个含有 m 个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源数目；其数值随该类资源的安排和回收而动态地转变；假如 Availablej=K, 就表示系统中现有 Rj 类资源 K 个；2 最大需求短阵 Max 这是个 n m 的矩阵,它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求；假如 Maxi ,j K,表示进程 i 需要

8、Rj 类资源的最大数目为 K；3 安排短阵 Allocation 这是一个n m 的矩阵,它定义了系统中每一类资源当前已安排给每个进程的资源数；假如Allocationi,jK,表示进程 i 当前已分得 Rj 类资源的数目为K；4 需求矩阵 Need 它是一个 n m 的矩阵, 用以表示每一个进程尚需的各类资源数,假如 Needi,j=K,就表示进程 i 仍需要 Rj 类资源 k个,方能完成其任务；上述三个矩阵间存在下述关系：Needi,j=Maxi,j-Allocationi,j 二、银行家算法设 Requesti是进程 Pi 的恳求向量；假如Requestijk ,表示进程只需要k 个 R

9、j 类型的资源；当Pi 发出资源恳求后,系统按下述步骤进行检查：1 假如 Requestij=Needi,j,就转向步骤 2 ；否就,认为出错,由于它所需要的资源数已超过它所宣布的最大值；2 假如 Requestij=Availablej ,就转向步骤 3 ；否就,表示系统中尚无足够的资源,Pi 必需等待；3 系统摸索把要求的资源安排给进程 Pi,并修改下面数据结构中的数值：Availablej:=Availablej-Requestij; Allocationi,j:=Allocationi,j+Requestij; Needi,j:=Needi,j-Requestij; 4 系统执行安全性

10、算法,检查此次资源安排后,系统是否处于安全状态；假设安全,才正式将资源安排给进程 Pi,以完成本次安排；否就,将摸索安排作废,复原原先的资源安排状态,让进程 Pi 等待；三、安全性算法系统所执行的安全性算法可描述如下：1 设置两个向量、工作向量 Work ；它表示系统可供应应进程连续运行所需要的各类资源数目,它含有 m 个元素,执行安全算法开头时,Work = Available；、 Finish ；它表示系统是否有足够的资源安排给进程,使之运行完成,开头时先做 Finishi:=false ；当有足够资源安排给进程时,令 Finishi:=true；2 从进程集合中找到一个能满意下述条件的进

11、程：、 Finishi=false; 、 Needi,j=Workj;如找到,执行步骤3 ；否就,执行步骤4 ；3 当进程 Pi 获得资源后,可顺当执行,直至完成,并释放出安排给它的资源,故应执行：名师归纳总结 - - - - - - -第 3 页,共 5 页精选学习资料 - - - - - - - - - Workj:=Worki+Allocationi,j; Finishi:=true; goto step 2；4 假如全部进程的 Finishi:=true,就表示系统处于安全状态；否就,系统处于担心全状态；四、银行家算法之例假定系统中有五个进程：P0 ,P1,P2,P3,P4 和三种类型

12、的资源A , B, C ,每一种资源的数量分别为10 、5 、7, 在 T0 时刻的资源安排情形如以下图所示；资 源 情 况 进 程1 T0 时刻的安全性：2 利用安全性算法对T0 时刻的资源安排情形进行分析可知,在T0 时刻存在着一个安全序列P1, P3, P4,P2,P0,故系统是安全的；2 P1 恳求资源： P1 发出恳求向量Request11,0,2,系统按银行家算法进行检查：Request11,0,2=Need11,2,2 Request11,0,2=Available13,3,2 系统先假定可为P1 安排资源,并修改Available,Allocation1和 Need1向量,由此

13、形成资源变化情形如图1 中的圆括号所示；再利用安全性算法检查此时系统是否安全；如图 3 所示；资 源 情 况 进 程由所进行的安全性检查得知,可以找到一个安全序列P1,P3,P4,P2,P0；因此系统是安全的,可以立刻将P1所申请的资源安排给它；名师归纳总结 3 P4 恳求资源： P4 发出恳求向量Request43,3,0,系统按银行家算法进行检查：第 4 页,共 5 页- - - - - - -精选学习资料 - - - - - - - - - Request43,3,0Need44,3,1; Request43,3,0不小于等于 Available2,3,0,让 P4 等待；系统相应如图：

14、4 P0 恳求资源： P0 发出恳求向量Request00,2,0,系统按银行家算法进行检查；Request00,2,0 Need07,4,3; Request00,2,0 Available2,3,0; 故可将资源安排给它,但将会显现死锁情形 系统反应如下：5进行安全性检查：可用资源Available2,1,0已不能满意任何进程的需要,故系统进入担心全状态,此时系统不安排资源；6四、测试与评判 1 、程序运行及结果测评：在自动、手动方式下都能正确得出结果,但在自动模式下,当值 MYMAX 增大时,运算时间长,增加了系统的开销,这也就 说明白在实际系统中不常用银行家算法死锁防止在死锁解决中的这

15、一缘由；2 、程序框架测评：主要使用了函数将每个模块分开,便于懂得；但由于,程序设计了自动实现模式,导致程序显得过长；每个模块之间的信息交 换主要通过全局变量平实现,从这个角度讲,模块的划分并不严格；对于自动与手动这两种工作方式,解题思路是冗余的,但 程序却为了防止之间的干扰冗余设计了函数,因而各个函数内聚度不高,功能也仍有相容点,所以在函数设计也不非常合理；尽管如此,本设计严格从银行家算法动身,能很好地帮忙读者懂得银行家算法在多进程并行为死锁防止实行的资源安排、安全 性检测的策略；特殊,在自动方式下,资源安排利用第一次安全检测的结果防止了后继执行进程的不确定,有效地解决了自动 恳求的过重盲目

16、的特点；当然,这部分有违银行家算法,但并没有增加额外的空间开销,仍削减了时间上的开销,个人觉得是 胜利的；3 、设计特点数据结构：数组；条件 以保证进程能够推动；对于键的接收不好确定,而getche就一按即可；全局变量在自动方式下,采纳dowhilegetche在调试时产生Warnings但能编译通过, getchar4 、设计心得：为精确懂得,应当以手动模式下运行为准,这样的交互性较好！特殊是单步实现的情形下,全部的数据能够使用一些交互性较 好的数据；而自动实现下,更接近于机器的工作方式,且自动设计的情形下,由于生成的随机数随机性不强,通常需要在转变 MAX 值后才能转变生成随机数的；程序在设计初,只是用了手动这一模式,后来听取同学的看法以随机数实现自动模式,在设 计时出了好些问题,但想多了问题也就通了,而新的问题又显现,却总能解决；在这种模式下能更完全懂得银行家算法中的资 源安排策略；名师归纳总结 - - - - - - -第 5 页,共 5 页