《银行家算法课程设计报告(共25页).docx》由会员分享，可在线阅读，更多相关《银行家算法课程设计报告(共25页).docx（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上银行家算法一 需求分析1. 在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁
2、的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。2. 银行家算法是一种最有代表性的避免死锁的算法。 要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。 不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资
3、源量不超过系统当前剩余资源量与所有进程Pj(j进行安全性检测-分配成功当然，进行安全性检测后，如果不安全，我们要记得数据重置，也是资源的回收。for (i = 0; i ava; i+)/假设分配 availablei = availablei - requestri;allocationri = allocationri + requestri;needri = needri - requestri;/int ret=check();if (check() = 0 )/安全检测 printf(安全检测失败,可能发生死锁,数据重置n);for (i = 0; i ava; i+)/重置数据 a
4、vailablei = availablei + requestri;allocationri = allocationri - requestri;needri = needri + requestri;elseint key = 0;for (j = 0; j ava; j+)if (needrj = 0)key+;if (key = ava)for (j = 0; j ava; j+)availablej += allocationrj;allocationrj = 0;printf(n进程顺利执行.nn);return;如果安全检测时安全的，则程序就会找出一个安全的序列，例如：p0,p
5、1,p2,p3,p4。此程序在找安全序列的时候每次都是从头开始找的for (i = 0; i process; i+)for (j = 0; j ava; j+)/寻找条件 Needi workj)break;if (j = ava) & (finishi = 0)/寻找条件 Finishi=false ，每次从头开始找安全序列finishi = 1;for (k = 0; k ava; k+)workk = workk + allocationik;pl = i;/记录安全序列 l+;/i = -1;/重置i，为了寻找安全序列 elsecontinue;if (l = process)/可以
6、找到安全序列，输出并结束 printf(n系统安全!n);printf(安全序列为：);for (k = 0; k );return 1;printf(n系统不安全，不能满足你的要求！n);return 0;最后一步是调用显示函数showdate()函数，此函数让我们更加直观的看到银行家算法的运行过程，printf(P(%d) , i);for (j = 0; j ava; j+)printf(%d , claimij);printf(n);printf(nAllocationn);printf( );ava_xh();for (i = 0; i process; i+)printf(P(%d
7、) , i);for (j = 0; j ava; j+)printf(%d , allocationij);printf(n);printf(nNeedn);printf( );ava_xh();for (i = 0; i process; i+)printf(P(%d) , i);for (j = 0; j ava; j+)printf(%d , needij);printf(n);printf(nAvailablen);ava_xh();for (i = 0; i ava; i+)printf(%d , availablei);显示了分配资源过后的needSIZESIZE矩阵和avail
8、ableSIZE和allocationSIZESIZE矩阵。四测试初始化输入：正常的分配成功，及其安全序列：请求的资源造成了系统的不安全，存在安全隐患：五总结在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如已分配资源数allocation、仍需求资源数need、以及系统可利用的资源数available、申请各类资源request、进程个数r等数组,其中每一个进程还使用了结构体。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。安全性检测我们
9、是用check()函数来实现的。除此之外，在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些比如进程号本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。设计的存
10、在着以下不足：一、不能实现并发操作，即当总资源同时满足几个进程所需要的资源数时，这些进程不能同时进行，只能一一按进程顺序执行。二、扫描进程顺序单一，只能按进程到来的顺序（即编号）来扫描，从而产生的安全顺序只能是在这个顺序的基础上产生的，而其实安全顺序是有多个的。三、对进程数和资源数进行的数量进行了限制，都只能最多有十个。四、运行程序后，界面较差，进程数，所需要资源数，已分配资源数，能用资源数，不能一目了然。总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。附录：程序代码：#define _CRT_SECURE_NO_WARNINGS#include #includ
11、e #include #include #define SIZE 11int availableSIZE; int claimSIZESIZE;int allocationSIZESIZE;int needSIZESIZE;int requestSIZESIZE = 0 ;/记录某个进程申请各个资源类中的资源实例的数量 int finishSIZE = 0 ;/工作变量，用于判断进程是否已经执行过，初始状态全部为0，即未执行 int pSIZE;/记录序列执行顺序 int ava;/记录系统有多少个资源类 int process;/记录进程数量int r;/记录当前要申请资源的进程的序号 in
12、t key = 1;void showdate();void allot();int init();int check();void ava_xh()/输出资源序号 int k;for (k = 0; k ava; k+)printf(%c , k + 65);printf(n);int main(void)int t;char ch;while (1)/声明循环 system(cls);t = init();if (t = 1)break;do/资源申请循环 allot();showdate();printf(还要申请对进程分配资源吗？(请按Y键):);scanf( %c, &ch); wh
13、ile (ch = y | ch = Y);return 0;int init()int i, j, k;printf(请输入资源类数量(1-%d)：, SIZE);while (1)scanf(%d, &ava);if (ava = 1)break;printf(输入错误，请重新输入：);printf(请依次输入各资源类的个数（中间用空格分开）：n);while (1)ava_xh();for (i = 0; i ava; i+)scanf(%d, &availablei);for (i = 0; i ava; i+)if (availablei )printf(有错误的输入,重新开始吧。n
14、);break;if (i = ava)break;printf(请输入进程数量：, SIZE);while (1)scanf(%d, &process);if (process = 1)break;printf(输入错误，请重新输入：);printf(=n);for (i = 0; i process; i+)/输入及检测进程所需各类资源的资源实例最大量printf(请输入进程P(%d)所需各类资源的资源最大量Max:n, i);ava_xh();for (j = 0; j ava; j+)scanf(%d, &claimij);for (j = 0; j availablej)printf
15、(有数据超过系统实例最大量，退出)。nnnn);system(pause);getchar();return 0;/输入及检测进程占有各资源类中资源实例的数量printf(请输入进程P(%d)已分配各类资源的数量Allocation:n, i);ava_xh();for (j = 0; j ava; j+)scanf(%d, &allocationij);for (j = 0; j ava; j+)if (claimij allocationij)printf(有数据超过进程所需资源最大量。nnnn);system(pause);getchar();return 0;/输入进程还需各个资源类中
16、资源实例的数量printf(下面是进程P(%d)还需各个资源类中资源的数量Need:n, i);ava_xh();for (j = 0; j ava; j+)needij = claimij - allocationij;printf(%d , claimij - allocationij);printf(n=n);printf(n下面是目前系统剩余的各个资源类的实例数量：n);ava_xh();for (i = 0; i ava; i+)for (j = 0; j process; j+)availablei = availablei - allocationji;printf(%d , a
17、vailablei);printf(n=n);if (check() = 0)/安全检测 printf(安全检测失败,可能发生死锁,数据重置n);for (i = 0; i ava; i+)/重置数据 availablei = availablei + requestri;allocationri = allocationri - requestri;needri = needri + requestri;elseprintf(n进程顺利执行.nn);showdate();return 1;void allot()int i, j, k;printf(n请输入当前要申请资源的进程的序号(0-%
18、d):, process - 1);while (1)scanf(%d, &r);if (r = 0)break;printf(输入错误，请重新输入：);printf(请输入要申请的各个资源实例的数量：n);ava_xh();for (j = 0; j ava; j+)scanf(%d, &requestrj);for (i = 0; i needri)printf(n申请资源量超过所声明的最大资源需求量Maxn);return;for (i = 0; i availablei)printf(剩余资源实例不足，需要等待,重来一次.n);return;for (i = 0; i ava; i+)
19、/假设分配 availablei = availablei - requestri;allocationri = allocationri + requestri;needri = needri - requestri;/int ret=check();if (check() = 0 )/安全检测 printf(安全检测失败,可能发生死锁,数据重置n);for (i = 0; i ava; i+)/重置数据 availablei = availablei + requestri;allocationri = allocationri - requestri;needri = needri +
20、requestri;elseint key = 0;for (j = 0; j ava; j+)if (needrj = 0)key+;if (key = ava)for (j = 0; j ava; j+)availablej += allocationrj;allocationrj = 0;printf(n进程顺利执行.nn);return;int check()int i, j, k, l = 0;int workSIZE = 0 ;/工作数组 for (i = 0; i ava; i+)/初始化 worki = availablei;for (i = 0; i process; i+)
21、 /初始化 finishi = 0;for (i = 0; i process; i+)for (j = 0; j ava; j+)/寻找条件 Needi workj)break;if (j = ava) & (finishi = 0)/寻找条件 Finishi=false ，每次从头开始找安全序列finishi = 1;for (k = 0; k ava; k+)workk = workk + allocationik;pl = i;/记录安全序列 l+;/i = -1;/重置i，为了寻找安全序列 elsecontinue;if (l = process)/可以找到安全序列，输出并结束 pr
22、intf(n系统安全!n);printf(安全序列为：);for (k = 0; k );return 1;printf(n系统不安全，不能满足你的要求！n);return 0;void showdate()/显示现在所有数据 int i, j, k;printf(当前所有数据！n);printf(nMaxn);printf( );ava_xh();for (i = 0; i process; i+)printf(P(%d) , i);for (j = 0; j ava; j+)printf(%d , claimij);printf(n);printf(nAllocationn);printf
23、( );ava_xh();for (i = 0; i process; i+)printf(P(%d) , i);for (j = 0; j ava; j+)printf(%d , allocationij);printf(n);printf(nNeedn);printf( );ava_xh();for (i = 0; i process; i+)printf(P(%d) , i);for (j = 0; j ava; j+)printf(%d , needij);printf(n);printf(nAvailablen);ava_xh();for (i = 0; i ava; i+)printf(%d , availablei);printf(n=n);printf(nnn);return;专心-专注-专业