银行家算法课程设计报告

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+)/重置数据 availablei = a

4、vailablei + 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,p1,p2,p3,p4。此程

5、序在找安全序列的时候每次都是从头开始找的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) , i);for (j

7、 = 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矩阵和availablesize和allo

8、cationsizesize矩阵。四测试初始化输入：正常的分配成功，及其安全序列：请求的资源造成了系统的不安全，存在安全隐患：五总结在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如已分配资源数allocation、仍需求资源数need、以及系统可利用的资源数available、申请各类资源request、进程个数r等数组,其中每一个进程还使用了结构体。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。安全性检测我们是用check()函数来实

9、现的。除此之外，在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些比如进程号本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。设计的存在着以下不足：一、不能实现

10、并发操作，即当总资源同时满足几个进程所需要的资源数时，这些进程不能同时进行，只能一一按进程顺序执行。二、扫描进程顺序单一，只能按进程到来的顺序（即编号）来扫描，从而产生的安全顺序只能是在这个顺序的基础上产生的，而其实安全顺序是有多个的。三、对进程数和资源数进行的数量进行了限制，都只能最多有十个。四、运行程序后，界面较差，进程数，所需要资源数，已分配资源数，能用资源数，不能一目了然。总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。附录：程序代码：#define _crt_secure_no_warnings#include #include #include #i

11、nclude #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;/记录当前要申请资源的进程的序号 int key = 1;voi

12、d 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); while (ch = y |

13、 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 2147483647)printf(有错误的输入,重新开始吧。n);b

14、reak;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 , avai

17、lablei);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-%d):

18、, 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 + req

20、uestri;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+) /初始化 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，为了寻找安全序列 else