银行家算法课程设计报告_第1页
银行家算法课程设计报告_第2页
银行家算法课程设计报告_第3页
银行家算法课程设计报告_第4页
银行家算法课程设计报告_第5页
已阅读5页,还剩20页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、精选优质文档-倾情为你奉上银行家算法一 需求分析1. 在多道程序系统中,多个进程的并发执行来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险死锁。所谓死锁(Deadlock),是指多个进程在运行过程中因争夺资源而造成的一种僵局(DeadlyEmbrace),当进程处于这种状态时,若无外力作用,他们都无法在向前推进。  要预防死锁,有摒弃“请求和保持”条件,摒弃“不剥夺”条件,摒弃“环路等待”条件等方法。 但是,在预防死锁的几种方法之中,都施加了较强的限制条件;而在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方法中把系统状态分

2、为安全状态和不安全状态,便可避免死锁的发生。 而最具代表性的避免死锁的算法,便是Dijkstra的银行家算法。 利用银行家算法,我们可以来检测CPU为进程分配资源的情况,决定CPU是否响应某进程的的请求并为其分配资源,从而很好避免了死锁的产生。2. 银行家算法是一种最有代表性的避免死锁的算法。    要解释银行家算法,必须先解释操作系统安全状态和不安全状态。   安全状态:如果存在一个由系统中所有进程构成的安全序列P1,Pn,则系统处于安全状态。安全状态一定是没有死锁发生。    不安

3、全状态:不存在一个安全序列。不安全状态不一定导致死锁。   那么什么是安全序列呢? 安全序列:一个进程序列P1,Pn是安全的,如果对于每一个进程Pi(1in),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。   银行家算法: 我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该

4、进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。3.设计要求:设计一n个并发进程共享m个系统资源的程序实现银行家算法。要求包括: (1) 简单的初始化界面; (2) 系统资源的占用和剩余情况; (3) 为进程分配资源,用银行家算法

5、对其进行检测,分为以下三种情况:        A. 所申请的资源大于其所需资源,提示分配不合理不予分配并返回;         B. 所申请的资源未大于其所需资源,但大于系统此时的可利用资源,提示分配不合理不予分配并返回;  C. 所申请的资源未大于其所需资源,亦未大于系统此时的可利用资源,预分配并进行安全性检查:     &

6、#160;  a. 预分配后系统是安全的,将该进程所申请的资源予以实际分配并打印后返回;        b. 与分配后系统进入不安全状态,提示系统不安全并返回; (4) 对输入进行检查,即若输入不符合条件,应当报错并返回重新输入; (5) 撤销作业,释放资源。二概要设计(一)算法思路: 先对用户提出的请求进行合法性检查,即检查请求是否大于需要的,是否大于可利用的。若请求合法,则进行预分配,对分配后的状态调用安全性算法进行检查。若安全,则

7、分配;若不安全,则拒绝申请,恢复到原来的状态,拒绝申请。(二)算法步骤:(1)如果Requestior =Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过它所宣布的最大值。 (2)如果Requestor=Available,则转向步骤(3);否则,表示系统中尚无足够的资源,进程必须等待。 (3)系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的值:Available=Available-Requesti;      Allocation=Allocation+Request;

8、    Need=Need-Request; (4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。三详细设计#define SIZE 11int availableSIZE; int claimSIZESIZE;int allocationSIZESIZE;int needSIZESIZE;int requestSIZESIZE = 0 ;/记录某个进程申请各个资源类中的资源实例的数量 int finishSIZE = 0 ;/工作变量,用于判断进程是否已经执行过,初始状态全部为0,即未执行 int pSIZE;/记录序列执行顺序 int

9、 ava;/记录系统有多少个资源类 int process;/记录进程数量int r;/记录当前要申请资源的进程的序号 int key = 1;这部分程序一开始定义了程序所需要的矩阵,资源类,进程数等等,用来记录进程资源的分配情况,可见的显示了银行家算法。void showdate();void allot();int init();int check();这些事主函数运行时所要调用的函数,首先要调用的是init()函数,这个函数初始化了claimSIZESIZE矩阵和allocationSIZESIZE矩阵,初始化成功以后就开始给进程分配资源,开始调用allot()函数,银行家算法的核心之一

10、就是进行资源类的分配,下面是分配的过程: 试分配->进行安全性检测->分配成功当然,进行安全性检测后,如果不安全,我们要记得数据重置,也是资源的回收。for (i = 0; i < ava; i+)/假设分配 availablei = availablei - requestri;allocationri = allocationri + requestri;needri = needri - requestri;/int ret=check();if (check() = 0 )/安全检测 printf("安全检测失败,可能发生死锁,数据重置n");fo

11、r (i = 0; i < ava; i+)/重置数据 availablei = 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进程顺

12、利执行.nn");return;如果安全检测时安全的,则程序就会找出一个安全的序列,例如:p0,p1,p2,p3,p4。此程序在找安全序列的时候每次都是从头开始找的for (i = 0; i < process; i+)for (j = 0; j < ava; j+)/寻找条件 Needi<=Worki if (needij > workj)break;if (j = ava) && (finishi = 0)/寻找条件 Finishi=false ,每次从头开始找安全序列finishi = 1;for (k = 0; k < ava;

13、k+)workk = workk + allocationik;pl = i;/记录安全序列 l+;/i = -1;/重置i,为了寻找安全序列 elsecontinue;if (l = process)/可以找到安全序列,输出并结束 printf("n系统安全!n");printf("安全序列为:");for (k = 0; k < l; k+)printf("P(%d)", pk);if (k != l - 1)printf("->");return 1;printf("n系统不安全,不能满

14、足你的要求!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) &q

15、uot;, 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");prin

16、tf("nAvailablen");ava_xh();for (i = 0; i < ava; i+)printf("%d ", availablei);显示了分配资源过后的needSIZESIZE矩阵和availableSIZE和allocationSIZESIZE矩阵。四测试初始化输入:正常的分配成功,及其安全序列:请求的资源造成了系统的不安全,存在安全隐患:五总结在银行家算法这个系统之中,所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储,比如已分配资源数allocation 、仍需求资源数ne

17、ed 、以及系统可利用的资源数available 、申请各类资源request 、进程个数r 等数组,其中每一个进程还使用了结构体。 数据结构虽然重要但却只是基础,而最主要的用以实现系统功能的应该有两个部分,一是用银行家算法来判断,二是用安全性算法来检测系统的安全性。 安全性检测我们是用check( )函数来实现的。 除此之外,在程序当中,我们也得强调一下对输入的合法性的判断。比如,我们输入的欲申请资源的进程号没有在系统已存在的进程当中,或者进程号定义为整型,但是却错输成字母等情况,我们需要对这些情况进行判断,让程

18、序报错返回而并非因错误而中断。 这样的情况处理起来比较麻烦,相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入,仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断,并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些比如进程号本来设定就是整型,因此对输入的是字母的判别因比较复杂而未能加上。设计的存在着以下不足:一、不能实现并发操作,即当总资源同时满足几个进程所需要的资源数时,这些进程不能同时进行,只能一一按进程顺序执行。二、扫描进程顺序单一,只能按进程到来的顺序(即编号)来扫描,从而产生的安全顺序只能是在这个顺序

19、的基础上产生的,而其实安全顺序是有多个的。三、对进程数和资源数进行的数量进行了限制,都只能最多有十个。四、运行程序后,界面较差,进程数,所需要资源数,已分配资源数,能用资源数,不能一目了然。 总之,银行家算法是避免死锁的主要方法,其思路在很多方面都非常值得我们来学习借鉴。附录:程序代码:#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <windows.h>#define SIZE 11int a

20、vailableSIZE; int claimSIZESIZE;int allocationSIZESIZE;int needSIZESIZE;int requestSIZESIZE = 0 ;/记录某个进程申请各个资源类中的资源实例的数量 int finishSIZE = 0 ;/工作变量,用于判断进程是否已经执行过,初始状态全部为0,即未执行 int pSIZE;/记录序列执行顺序 int ava;/记录系统有多少个资源类 int process;/记录进程数量int r;/记录当前要申请资源的进程的序号 int key = 1;void showdate();void allot();i

21、nt 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(

22、" %c", &ch); while (ch = 'y' | ch = 'Y');return 0;int init()int i, j, k;printf("请输入资源类数量(1-%d):", SIZE);while (1)scanf("%d", &ava);if (ava <= SIZE) && (ava >= 1)break;printf("输入错误,请重新输入:");printf("请依次输入各资源类的个数(中间用空格分开

23、):n");while (1)ava_xh();for (i = 0; i < ava; i+)scanf("%d", &availablei);for (i = 0; i < ava; i+)if (availablei < 0) | (availablei > )printf("有错误的输入,重新开始吧。n");break;if (i = ava)break;printf("请输入进程数量:", SIZE);while (1)scanf("%d", &proce

24、ss);if (process <= SIZE) && (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

25、= 0; j < ava; j+)if (claimij > availablej)printf("有数据超过系统实例最大量,退出)。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

26、; j < ava; j+)if (claimij < allocationij)printf("有数据超过进程所需资源最大量。nnnn");system("pause");getchar();return 0;/输入进程还需各个资源类中资源实例的数量printf("下面是进程P(%d)还需各个资源类中资源的数量Need:n", i);ava_xh();for (j = 0; j < ava; j+)needij = claimij - allocationij;printf("%d ", cla

27、imij - 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 ", availablei);printf("n=n");if (check() = 0)/安全检测 printf("安全检测失败,可能发

28、生死锁,数据重置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):", process - 1);while (1)

29、scanf("%d", &r);if (r <= process - 1) && (r >= 0)break;printf("输入错误,请重新输入:");printf("请输入要申请的各个资源实例的数量:n");ava_xh();for (j = 0; j < ava; j+)scanf("%d", &requestrj);for (i = 0; i < ava; i+)if (requestri > needri)printf("n申请资源量

30、超过所声明的最大资源需求量Maxn");return;for (i = 0; i < ava; i+)if (requestri > availablei)printf("剩余资源实例不足,需要等待,重来一次.n");return;for (i = 0; i < ava; i+)/假设分配 availablei = availablei - requestri;allocationri = allocationri + requestri;needri = needri - requestri;/int ret=check();if (check

31、() = 0 )/安全检测 printf("安全检测失败,可能发生死锁,数据重置n");for (i = 0; i < ava; i+)/重置数据 availablei = 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+)avail

32、ablej += 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<=Worki if (needij > 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,为了寻找安全序列 elseco

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论