实验银行家算法Word版

1、实验三 银行家算法一、 实验目的和意义了解掌握银行家算法，学会模拟实现资源分配，同时有要求编写和调试一个系统分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生二、方案设计及开发过程1.实验背景在多道程序系统中，虽可借助与多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险-死琐。产生死锁的原因可归结为两点：1：竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。2：进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。

2、最有代表性的避免死锁的算法，是Dijkstra的银行家算法。这是由于该算法能用与银行系统现金贷款的发放而得名的。 2.算法描述 设Requesti 是进程Pi的请求向量，如果Requestij=K,表示进程Pi需要K个Rj类型的资源，当Pi发出资源请求后，系统按下面步骤进行检查：（1）如果Requestij=Needi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestij=Availablej,便转向步骤3；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej:=Avail

3、ablej-Requestij;Allocationi,j:=Allocationi,j+Requestij;Needi,j:=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。3.数据结构1 / 11银行家算法中的数据结构：（1） 可利用资源向量Available。这是一个含有n个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变

4、。如果Availablej=K,则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个m*n的矩阵，它定义了系统中n个进程中每一个进程对m类资源的最大需求。如果Maxi,j=K,则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation。这也是一个m*n的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K,则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K,则表示进程i还需要Rj类资源K个，方能完成其任务。(5) 工作数组

5、Work.。这是一个含有n个元素的数组，它代表可以提供分配的资源数，初始值是Available中的数值，随着资源的回收，它的值也会改变，公式是Worki=Worki+Allocationi。4.主要函数说明主要函数主要有四个：（1） Main() 主函数：用来显示资源的分配情况和提示信息，同时用Main函数来调用其它子程序。 （2）Safe() 函数：用来检查是否有安全序列，如果存在则返回一个1给主函数，否则返回0。(3) Disp() 函数：用来显示随机生成的资源包括Max、Need、Allocation、Available。(4) Request() 函数：用来进行资源请求，分为手动的和随

6、机申请。同时对申请的资源进行判断，检查申请是否有效，如果有效则返回一个1给主函数，否则返回0。程序初始化随机分配资源并显示在屏幕检查安全序列是否要申请资源退出程序输入RequestRequestNeedRequestAvailableNeedij=Needij-RequestjAvailablej=Availablej-Requestj报错检查安全序列保留原始Available、Request恢复原始Available、Request判Allocation=MaxAvailablej=Maxij+workjFinishi=1输出结果5.算法流程图 N Y Y N N Y N Y Y 三、调试记

7、录与分析 在调试过程中为了显示安全序列的检查状况，在检查Available是否满足Need时要检查m*n遍，并存在表达有歧异，经过修改后，就不需要全部检查，而是Available只要有一个不满足Need就停止检查。图3.1修改前图3.2修改后四、运行结果及说明图4.1.不存在安全序列随机分配完资源后，进行安全检查，在检查过程中在屏幕上显示检查信息，上图为资源分配不安全时显示的信息。图4.2.存在安全路径存在安全路径后，在屏幕上显示变化过程和安全路径。提示是否申请资源图4.3.申请资源提出申请后，询问进行随机分配资源还是手动分配图4.4 手动分配图4.5.随机分配五、实验总结附录#include

8、#include #include#define M 3#define N 3int NeedMN,AllocationMN,AvalibleN,MaxMN,finishN;/Need :进程需要的资源数Allocation:进程已分配的资源; Avalible:进程可供分配的资源void display(int *a,int n) /显示一维数组 int i; for(i=0;in;i+) printf(%3d,ai); void disp() /显示资源列表 int i,j,k,h,l; printf(Nnumbert Maxtt needtt allocationt avaliblen)

9、; for(i=0;iM;i+) printf(p%dt,i); display(Maxi,N); printf(t); display(Needi,N); printf(t); display(Allocationi,N); printf(t); if(i=0) display(Avalible,N); printf(n); int grand(int *a,int *b,int n) /分配资源 int i; for(i=0;in;i+) ai=bi; int check(int *a,int *b,int n) /检查Allocation是否与Max相等 int i; for(i=0;i

10、n;i+) if(aibi) return 0; return 1; int compare(int *a,int *b,int n) /比较数组的大小 int i; char flag; for(i=0;in;i+) if (aibi) return 0; return 1; int comp(int *a,int *b,int n,int m) /比较数组 int i; for(i=0;ibi) if(m=1) printf(request Number%d resouce have an error request overflow avalible%dn,i+1,i); if(m=2)

11、 printf(request Number%d resouce have an error request overflow Need%dn,i+1,i); return 0; return 1; void dec(int *a,int *b,int n) /数组相减 int i; for(i=0;in;i+) ai-=bi; char input() /输入数据 char c; c=getchar()-0x30; return c; void add(int *a,int *b,int n,int m) /数组相加 int i ; for(i=0;in;i+) ai+=bi; for(i=

12、0;in;i+) if(m=0) printf(Avalible%d=%d ,i,ai); if(m=3)printf(n); if(m=1) printf(work valuese changed work%d=%dn,i,ai); printf(n);/检查安全序列 int safe() int i,count=0,n,j,r1=1; int workN,srM,flag; int finish1N; grand(work,Avalible,N); printf(check safe list.n); for(i=0;iN;i+) finish1i=-1; for(n=0;nM;n+) f

13、or(i=0;ineed%d ,n,i);break; if(finish1i=-1&flag=1&finishi=-1) printf(find a right need-process%d-need%dn,n,i); add(work,Allocationi,N,r1); finish1i=1; srcount=i; count+; /记录安全序列 if(count=M) printf(-have an safe list-n); for(i=0;i,sri); else printf(p%dn,sri); return 1; else printf(after check there n

14、o safe list.n); printf(cant apply resoucen); return 0; /随机请求资源int ran_request() int i,flag1,flag2,r1=1,r2=2,r3=3; int requestN,pn; pn=rand()%2; printf(Process%d call for resoucen,pn); for(i=0;iN;i+) requesti=rand()%5; for(i=0;iM-1) printf(input error!); else printf(nplease input the request number:n

15、); for(i=0;iN;i+) getchar(); printf(The %d rquest:n,i); rti=input(); printf(Your request is锛歕n); display(rt,N); if(finishpn=-1) flag1=comp(rt,Avalible,N,r1); flag2=comp(rt,Needpn,N,r2); if(flag1=1&flag2=1) printf(call for request avalible); dec(Avalible,rt,N); dec(Needpn,rt,N); add(Allocationpn,rt,N

16、,r3); disp(); if(safe()=1) if(check(Allocationpn,Maxpn,N)=1) add(Avalible,Allocationpn,N,0); finishpn=1; k+; return 1; else return 0; else printf(The resouce have assignedn); int main() int i,j,s_flag; char c,s; int avN,s_llMN; for(i=0;iM;i+) finishi=-1; srand(time(NULL); for(i=0;iM;i+) for(j=0;jN;j

17、+) Allocationij=rand()%10; Needij=rand()%10; Maxij=Allocationij+Needij; for(i=0;iN;i+) Avaliblei=rand()%12; disp();s_flag=safe(); if(s_flag=1) printf(是否申请资源-(Y/N)n); c=getchar(); if(c=Y|c=y) N1: printf(1-random request resoucen); printf(2-request resouce by mann); grand(av,Avalible,N); /保存原始的availab

18、le的值 for(i=0;iM;i+) grand(s_lli,Allocationi,N); getchar(); Mnu: s=getchar(); switch(s) case 1:if(ran_request()=1) printf (continue request(Y/N)n); getchar();c=getchar(); if(c=Y|c=y) goto N1; else grand(Avalible,av,N); for(i=0;iM;i+) grand(Allocationi,s_lli,N); break; case 2:if(request()=1) printf(continue request(Y/N)n);