1、银行家算法报告银行家算法报告LT摘 要随着时代的发展，对生活的追求越来越高，生活品质也越来越好。在学习方面的研究也越来越有成效。Dijkstra提出的银行家算法，是最具代表性的避免死锁的算法。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用：第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源：第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会产
2、生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等。 本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的说明，包括需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。首先做了需求分析，解释了什么是银行家算法，并指出它在资源分配中的重要作用。然后给出了银行家算法的概要设计，包括算法思路、步骤，以及要用到的主要数据结构、函数模块及其之间的调用关系等。在概要设计的基础上，又给出了详细的算法设计，实现概要设计中定义的所有函数,对每个函数写出核心算法，并画出了流程图。接着对编码进行了测试与分析。最后对整个设计过程进行了总结。关键字：死锁 安全序列 银行家算法 进程引 言Dijk
3、stra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行
4、家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中
5、把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁1、课程设计的目的和要求目的：银行家算法是避免死锁的一种重要方法，本设计要求用C语言（或高级语言）编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。通过对这个算法的设计,让学生能够对书本知识有更深的理解,在操作和其它方面有更高的提升,同时对程序设计的水平也有所提高。要求：设计一个n个并发进
6、程共享m个系统资源的程序实现银行家算法。要求包含：1）、简单的选择界面。2）、前系统资源的占用和剩余情况。 3）、为进程分配资源，如果进程要求的资源大于系统剩余的资源，不与分配并且提示分配不成功。4）、撤销作业，释放资源。2、课程设计的环境奔腾以上计算机，装有Turbo C 2.0软件3、课程设计的主要内容3.1 项目名称 银行家算法程序设计3.2 项目的主要内容（1）设计银行家算法，能够检测系统某一时刻是否安全，输出安全序列。（2）实现安全性检测算法。即在某一进程在某时刻提出Request时，检测系统是否能够满足该进程的请求，并得到一个安全序列，若能够得到一个安全序列，则系统能够满足它的请求
7、，同意分配资源。若不能够满足，则回到请求前状态。（3）对于此次课程设计通过需求分析、概要设计、详细设计、测试与分析、总结、源程序清单等模块进行全面分析，以加深对死锁概念的理解，以及银行家算法避免死锁的过程。能够利用银行家算法，有效避免死锁的发生，或检测死锁的存在。4、系统的组成及工作原理4.1系统主要过程流程图4.1.1初始化算法流程图图4.1初始化算法流程图 4.1.2 银行家算法流程图图4.2银行家算法流程图4.2 系统的设计方法根据设计任务书的要求，画出程序设计流程图，确定程序的功能，把整个程序根据功能要求分解为各个子程序，利用TC语言分编写程序代码，然后进行上机调试、修改、进行连接，测
8、试，写出设计总结报告。主要函数的核心代码：1.进行初始化输入的函数2.打印输出的函数3.利用安全性算法进行检测的函数4.进行资源分配的函数5.利用行家算法进行判定的函数void mainenter()/主要的输入部分代码printf(请输入系统总共有的资源数：);scanf(%d,&n);printf(请输入总共有多少个进程：);scanf(%d,&m);for(i=1;i=n;i+) printf(第%d类资源有的资源实例：,i); scanf(%d,&Availablei);for(i=1;i=m;i+) for(j=1;j=n;j+) printf(进程P%d对第%d类资源的最大需求量：
9、,i,j); scanf(%d,&Maxij); Needij=Maxij; 5、模块划分第一部分:银行家算法(扫描)1如果Request=Need,则转向2;否则,出错2如果Request=Available,则转向3,否则等待3系统试探分配请求的资源给进程4系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finishi=False&Need=Work,则执行3;否则执行4(I
10、为资源类别)3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:Work=Work+Allocation; Finishi=true;转24. 若所有进程的Finishi=true,则表示系统安全;否则,不安全!5.1各模块间的调用关系：主函数void main()要调用： printFrame()，print()，Safty()，mainenter() 安全性检测函数Safty()要调用：print() 银行家算法函数mainenter()要调用print()、Safty()、和mainenter()本身void main() int k,h=1; while(h) system(cl
11、s); printf(nn 欢迎使用本程序 n); printf(nn 1:输入系统的资源数、申请进程数、每个类资源的实例数); printf(n 2: 输入进程的资源申请); printf(n 3: 输出系统状态); printf(n 4: 退出程序); printf(nn please choose ); scanf(%d,&k); switch(k) case 1:mainenter(); break; case 2:mainrequest(); break; case 3:mainprint(); break; case 4:h=0; break; printf(n); system(
12、pause); system(cls); printf(nn 谢谢使用 n); printf(nn See you next time!nnn);5.2安全性算法流程图图5.1安全性算法流程图6运行与测试结果6.1运行程序成功之后的欢迎界面图6.1欢迎界面6.2初始化程序图6.2初始化界面图6.3输入数据图6.4申请进程1图6.5申请进程2图6.6申请进程3图6.7申请进程56.3界面显示图6.8界面显示6.4出错界面图图6.9出错界面6.5程序运行结束图6.10程序结束画面7、总结在本程序代码中，银行家算法用数组函数来实现。首先，输入欲申请资源的进程以及其所申请的资源数，存放在Request
13、数组中。然后，判断进程请求的资源数是否大于其所需的资源数，若大于则报错并返回，若不大于则继续判断它是否大于系统在此时刻可利用的资源数，同样，如果大于则报错并反回，如果不大于则调用函数来进行预分配，之后再调用安全型算法safty检查。最后，无论此次分配是否成功，我们都可以选择继续分配或者退出系统。在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如最大需求量Max、已分配资源数Allocation、仍需求资源数Need、以及系统可利用的资源数、申请各类资源等数组。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两
14、个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。除此之外，在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些比如进程号本来设定就是整型，因此对输入的是字母
15、的判别因比较复杂而未能加上。通过对本次银行家算法的程序进行修改对其结构更加明确。8、课程设计的心得体会操作系统的基本特征就是并发和共享，系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足、分配不当而引起“死锁”。本次课程设计就是用银行家算法来避免“死锁”。 该算法就是一在程序进行编写之前，先对程序的要求进行分析，弄清楚程序所需要的功能，然后将每个功能分成一个功能模块即调用函数来实现，无需过多的画蛇添足。编写这个简易的银行家算法让我知道了在资源一定的条件下为了让多个进程都能使用资源完成任务，避免死锁的产生可以
16、从一开始就对系统进行安全性检查来判断是否将资源分配给正在请求的进程。但是银行家算法会加大系统的开销。在资源分配过程，使分配序列不会产生死锁。此算法的中心思想就是，每次分配后总存在着一个进程，如果让它单独的运行下去，一周的操作系统课程设计，我学到了很多课本上没有的知识。想要完成模拟银行家算法的C语言程序，首先就是要彻底熟悉算法，了解算法的基本原理，才能开始着手程序设计在程序设计设计过程中，遇到了一些困难，通过向同学询问，翻阅资料等问题被一一解决了。首先就是在知识层面上了解了银行家算法这种进程调度和避免死锁的算法，并用C语言程序真正模拟出安全性检查和银行家算法过程，复习了之前所学C语言和数据结构的
17、知识；在编程过程中虽然遇到很多困难，解决问题的过程中，同时也锻炼了我不怕困难，勇于迎接挑战的精神，为以后的工作打下了坚实的基础。9、参考文献1汤小丹等，计算机操作系统第三版，西安电子科技大学出版社，2007年2塔嫩鲍姆等，操作系统设计与实现，电子工业出版社，20073罗宇等，操作系统课程设计，机械工业出版社，20054郑扣根著，操作系统概念，高等教育出版社，20105严蔚敏，吴伟明著，数据结构，北京 清华大学出版社，20066斯托林肯著，操作系统：精髓与设计原理，机械工业出版社，2010附录#include#include#includeint Available10; /可使用资源向量int
18、 Max1010; /最大需求矩阵int Allocation1010=0; /分配矩阵int Need1010=0; /需求矩阵int Work10; /工作向量int Finish10; /状态标志int Request1010; /进程申请资源向量int Pause10;int List10;int i,j;int n; /系统资源总数int m; /总的进程数int a; /当前申请的进程号int l,e; /计数器int b=0,c=0,f=0,g; /计数器void mainenter()/主要的输入部分代码printf(请输入系统总共有的资源数：);scanf(%d,&n);pr
19、intf(请输入总共有多少个进程：);scanf(%d,&m);for(i=1;i=n;i+) printf(第%d类资源有的资源实例：,i); scanf(%d,&Availablei);for(i=1;i=m;i+) for(j=1;j=n;j+) printf(进程P%d对第%d类资源的最大需求量：,i,j); scanf(%d,&Maxij); Needij=Maxij; void mainrequest() /进程提出新申请的代码部分 printf(请输入申请资源的进程：); scanf(%d,&a);for(i=1;iNeedai) printf(n出错！进程申请的资源数多于它自己
20、申报的最大量n); if(RequestaiAvailablei) printf(nP%d必须等待n,a);/以下是试探性分配 Availablei=Availablei-Requestai; Allocationai=Allocationai+Requestai; Needai=Needai-Requestai; Worki=Availablei;for(i=1;i=m;i+) Pausei=Availablei;/Pausei只是一个暂时寄存的中间变量，为防止在下面 /安全性检查时修改到Availablei而代替的一维数组 Finishi=false;for(g=1;g=m;g+) for
21、(i=1;i=m;i+) b=0; /计数器初始化 for(j=1;j=n;j+) if(Needij=Pausej) b=b+1; if(Finishi=false&b=n) for(l=1;l=n;l+) Pausel=Pausel+Allocationil; Finishi=true; printf($ %d ,i);/依次输出进程安全序列之一中每个元素 printf(n);for(i=1;i=m;i+) if(Finishi=true) f=f+1;/统计Finishitrue的个数if (f=m) printf(safe static); f=0;/将计数器f重新初始化，为下一次提出
22、新的进程申请做准备else printf( unsafe static );/以下代码为当系统被判定为不安全状态时 /返回提出申请前的状态 for(i=1;i=n;i+) Availablei=Availablei+Requestai; Allocationai=Allocationai-Requestai; Needai=Needai+Requestai; void mainprint()printf(当前的系统状态n);printf( 目前占有量 最大需求量 尚需要量 n进程);for(i=1;i=n;i+) for(j=1;j=n;j+) printf( %d类,j); for(i=1;
23、i=m;i+) printf(nP%d,i); for(j=1;j=n;j+) printf( %d ,Allocationij); for(j=1;j=n;j+) printf( %d ,Maxij); for(j=1;j=n;j+) printf( %d ,Needij); printf(nn系统剩余资源量： ); for(i=1;i=n;i+) printf( %d ,Availablei);printf(n);void main() int k,h=1; while(h) system(cls); printf(nn 欢迎使用本程序 n); printf(nn 1:输入系统的资源数、申
24、请进程数、每个类资源的实例数); printf(n 2: 输入进程的资源申请); printf(n 3: 输出系统状态); printf(n 4: 退出程序); printf(nn please choose ); scanf(%d,&k); switch(k) case 1:mainenter(); break; case 2:mainrequest(); break; case 3:mainprint(); break; case 4:h=0; break; printf(n); system(pause); system(cls); printf(nn 谢谢使用 n); printf(nn See you next time!nnn);
