用c语言实现和改进银行家算法

《用c语言实现和改进银行家算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第29卷第8期2008年8月通化师范学院学报JOURNALOFTONGHUATEACHERSCOU点GEV01．29№8Aug．2008用C语言实现和改进银行家算法赵艳，陈光兴(通化师范学院物理系，吉林通化134002)摘要：银行寥算法能够根据计算机系统的需要，判断计算机新申请的进程是否安全，进而避免死锁问题的发生。该文运用c语言实现该算法，同时针对算法中存在的安全隐患进行改进．关键词：银行家算法；C语言；死锁；安全中图分类号：TP301．6文献标志码：A文章编号：1008—7974(2008)08—00”一03收稿日期：2008—04—06作

2、者简介：赵艳(1984一)，女，吉林通化人．通化师范学院物理系教师，硕士．1引言在计算机系统中，安全问题一直为用户所关注．资源分配如果可以保证所用进程在有效时间内得到所要资源则称其为安全．各进程在使用系统资源时，应注意系统产生死锁问题．所谓死锁，是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态．银行家算法是针对计算机系统上述安全问题进行的设计，可以判断新申请的进程是否安全，避免死锁问题的发生．传统银行家算法在程序执行

3、过程中，要求逐条输入所需进程数，但由于计算机执行速度较快，在输入进程数的过程中，如果有其他进程申请资源，计算机可分配的资源可能会发生一定的改变，使得原本安全的系统变得不安全，笔者就这一问题对银行家算法进行改进，在系统把需求的资源分配给进程并修改数据结构值以前，对需求进程与可利用资源重新进行比较，确保系统在安全条件下进行资源分配．2算法总体设计2．1算法说明在实际生活中，银行家问题即银行家对申请资金的顾客进行分配资金，以确保最大限度地满足所有顾客的要求，但同时也要保证银行家本身资金正常的流通，避免破产．与之类似，在计算机系统中，银行家相当于系统，

4、资金相当于资源，顾客则相当于进程，银行家问题即指系统对于申请资源的进程进行资源分配，最大限度地满足所有进程的需要，同时，也要保证系统有空余资源以保证计算机能正常工作。2．2算法所需要的数据结构①可利用资源向量available，n个元素的数组，每个元素代表一类可用资源的数目，available[i]=k表示系统中有Rj类资源k个；②最大需求矩阵MAX，n木m矩阵定义n个进程时，m类资源的最大需求max(i，j)=k表示进程需要Rj类资源最大数目为k；③分配矩阵allocation，n掌m矩阵，表示n个进程的每个进程已分配资源情况，allocti

5、on(i，j)=k表示进程i已分配Rj类资源k个；④需求矩阵need，n木m矩阵，表示各进程仍需要各类资源，need(i，j)=k表示进程i仍需要资源Rj的数目为k．由上述分析可知needi=maxi—allocationi．2．3算法的流程设requesti是进程P的请求向量，如果request[j]=k表示进程P需K个Rj类资源，当进程P发出请求时，系统按下述步骤检查．步骤一：如果requesti<=needi则转向步骤二，否则出错，因为它所需要的资源已超过它宣布的最大值；步骤二：如果requesti<=available则转向步骤三，否则

6、表示系统没有足够的资源，进程必须等待；步骤三：系统试探把需求的资源分配给进程，并修改以下的数据结构值．available=available—requestiallocation=allocation+requestineedi=needi—requesti步骤四：此时进入算法关键时刻，即检查系统是否安全．系统执行安全算法，检查此次资源分配后系统是否处于安全状态，如果安全才正式将资源分配给进程P，以完成此次分配，否则试探分配作废，恢复原来资源分配的状态，让进程P等待。·27·2．4判断系统是否安全步骤一：设置两个向量，work表示系统可提供进程

7、继续运行所需各类资源数目，开始时work=avail-able；finish表示系统是否有足够资源分配给进程使之运行完成，开始时finish[i]=false．步骤二：进程集合找到一个满足下列条件的进程finish[i]=false；neecl[i]<=work；如果找到执行步骤三，否则执行步骤四．步骤三：当P获得资源后可顺利执行直至完成，并释放资源，所以执行work=aUoeation+workfimish[i]=true转向步骤二．步骤四：如果所有进程finish[i]均为true，则表示系统处于安全状态，否则系统处于不安全状态．2．5安全

8、性算法流程图(如图1)图1安全性算法流程图3算法程序实现对于银行家算法所需要的已知条件有：系统总资源w=(w1，w2，⋯⋯wn)，已分配资源aUoca