1、银行家算法参考3 课程设计三 银行家算法（参考1）1设计目的（1）了解多道程序系统中，多个进程并发执行的资源分配。（2）掌握死锁产生的原因、产生死锁的必要条件和处理死锁的基本方法。（3）掌握预防死锁的方法以，系统安全状态的基本概念。（4）掌握银行家算法，了解资源在进程并发执行中的资源分配策略。（5）理解避免死锁在当前计算机系统不常使用的原因。2算法描述 Dijkstra(1965年)提出了一种能够避免死锁的调度方法，称为银行家算法，它的模型基于一个小城镇的银行家，现将该算法描述如下：假定一个银行家拥有资金，数量为，被N个客户共享。银行家对客户提出下列约束条件：（1） 每个客户必须预先说明自已所
2、要求的最大资金量；（2） 每个客户每次提出部分资金量申请各获得分配；（3） 如果银行满足了客户对资金的最大需求量，那么，客户在资金动作后，应在有限时间内全部归还银行。 只要每个客户遵守上述约束，银行家将保证做到：若一个客户所要求的最大资金量不超过，则银行一定接纳该客户，并可处理他的资金需求；银行在收到一个客户的资金申请时，可能因资金不足而让客户等待，但保证在有限时间内让客户获得资金。在银行家算法中，客户可看做进程，资金可看做资源，银行家可看做操作系统。3. 环境 操作系统Windows XP SP2,开发工具VC+6.0或者BCB6.0。4 功能模块说明 1.银行家所能够提供的资源 typed
3、ef struct nodeint a;int b;int c;int remain_a;int remain_b;int remain_c;bank;2.进程所占用的资源typedef struct node1char name20;int a;int b;int c;int need_a;int need_b;int need_c;process; main()函数：完成对系统运行环境的初始化，定义了简单的选择菜单，调用各功能函数。 initial（）函数：对银行家结构体（银行家所拥有的资源种类和资源数目）初始化，对进程结构体（进程所需要的资源数目）进行初始化。 add()函数：创建进程，
4、定义进程运行所需的资源，检查系统提供的资源是否满足进程所需要的资源，如果满足则分配成功；不满足则分配失败。 bid()函数：给进程分配资源，检查系统提供的资源是否满足分配进程的资源，如果满足则分配成功；不满足则分配失败。 finished()函数：撤销进程，释放进程所占有的全部资源。 view()函数：查看当前系统进程占用的资源情况和系统中空闲的资源情况。5 参考源代码 #include #include #include #include #include #include const int MAX_p=20; const int MAXA=10;/定义A类资源的数量 const int
5、MAXB=5; const int MAXC=7; typedef struct nodeint a;int b;int c;int remain_a;int remain_b;int remain_c;bank;typedef struct node1char name20;int a;int b;int c;int need_a;int need_b;int need_c;process;bank banker;process processesMAX_p;int quantity;/初始化函数void initial()int I;banker.a=MAXA;banker.b=MAXB;
6、banker.c=MAXC;for(i=0;iMAX_p;i+)strcpy(processesi.name,”);processesi.a=0;processesi.b=0;processesi.c=0;processesi.need_a=0;processesi.need_b=0;processesi.need_c=0;/新加作业void add()char name20;int flag=0;int t;int need_a,need_b,need_c;int I;coutendl;cout“新加作业”endl;cout“-”endl;coutname;for(i=0;iquantity
7、;i+)if(!strcmp(processesi.name,name)flag=1;break;if(flag)cout“错误，作业已存在”enl;elsecoutneed_a;coutneed_b;coutneed_c;t=1;coutneed_abanker.remain_a)cout“错误，所需A类资源大于银行家所剩A类资源”banker.remain_b)cout“错误，所需B类资源大于银行家所剩B类资源”banker.remain_c)cout“错误，所需C类资源大于银行家所剩C类资源”endl;t=0;if(t)strcpy(processesquantity.name,name
8、);processesquantity.need_a=need_a;processesquantity.need.b=need.b;processesquantity.need_c=need_c;quantity+;cout“新加作业成功”endl;elsecout“新加作业失败”endl;/为作业申请资源void bid()char name20;int I,p;int a,b,c;int flag;coutendl“为作业申请资源”endl;cout“-”endl;coutname;p=-1;for(i=0;iquantity;i+)if(!strcmp(processesi.name,n
9、ame)p=I;break;if(p!=-1)couta;coutb;coutc;flag=1;if(abanker.remain_a|(aprocessesp.need_a-processesp.a)cout“错误，所申请A类资源大于银行家所剩A类资源或该进程还需数量”banker.remain_b|(bprocessesp.need_b-processesp.b)cout“错误，所申请B类资源大于银行家所剩B类资源或该进程还需数量”banker.remain_c|(cprocessesp.need_c-processesp.c)cout“错误，所申请C类资源大于银行家所剩C类资源或该进程还
10、需数量”endl;flag=0;if(flag)banker.remain_a-=a;banker.remain_b-=b;banker.remain_c-=c;processesp.a+=a;processesp.b+=b;processesp.c+=c;cout“为作业申请资源成功”endl;elsecout“为作业申请资源失败”endl;elsecout“该作业不存在”endl;/ 撤销作业void finished() char name20;int I,p;coutendl“撤销作业”endl;cout“-”endl;coutname;p=-1;for(i=0;iquantity;i
11、+)if(!strcmp(processesi.name,name)p=I;break;if(p!=-1)banker.remain_a+=processesp.a;banker.remain_b+=processesp.b;banker.remain_c+=processesp.c;for(i=p;iquantity-1;i+)processesi=processesi+1;strcpy(processesquantity-1.name,”);processesquantity-1.a=0;processesquantity-1.b=0;processesquantity-1.c=0;pro
12、cessesquantity-1.need_a=0;processesquantity-1.need_b=0;processesquantity-1.need_c=0;quantity-;cout“撤销作业成功”endl;elsecout“撤销作业失败”endl;/查看资源情况void view()int I;coutendl“查看资源情况”endl；cout“-”endl;cout“银行家所剩资源（剩余资源/总共资源）”endl;cout“A类：”banker.remain_a“/”banker.a;cout“B类：”banker.remain_b“/”banker.b;cout“C类：”b
13、anker.remain_c“/”banker.c;coutendlendl“作业占用情况（已占用资源/所需资源）”endl0)cout“作业名：”processesi.nameendl;cout“A类：”processesi.a“/”processesi.need_a;cout“B类：”processesi.b“/”processesi.need_b;cout“C类：”processesi.c“/”processesi.need_c;coutendl;elsecout“当前没有作业”endl;void main()int chioce;int flag=1;initial();while(f
14、lag)cout“-”endl;cout“1.新加作业 2.为作业申请资源 3.撤销作业”endl;cout“4.查看资源情况 0.退出系统”endl;coutchioce;switch(chioce)case 1:add();break;case 2:bid();break;case 3:finished();break;case 4:view();break;case 0:flag=0;break;default:cout“选择错误”endlendl;课程设计2 银行家算法（参考2）一、 背景知识在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否
15、分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。在分配资源时判断是否会出现死锁，如不会死锁，则分配资源。死锁检测算法保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。主要是检查是否有循环等待.1 系统安全状态1）安全状态所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列 P1 ，P2 Pn就是安全序列。如果存在这样一个安全序列，则系统是安全的。2）安全状态之例进程最大需求已分配可用P1P2P310495223安全序列：P2 P1 P3不安全序列：P1 P3 P2P3P1 3）由安全状态向不安全状态的转换2
16、 利用银行家算法避免死锁1）银行家算法中的数据结构 可利用资源向量Available。 最大需求矩阵Max。 分配矩阵Allocation 需求矩阵Need2）银行家算法 一个银行家拥有一定数量的资金，有若干个客户要贷款，每个客户须在一开始就声明他所需贷款的总额，若该客户贷款总额不超过银行家的资金总额，银行家可以接受客户的要求。客户贷款是以每次一个资金单位（如1万RMB等）的方式进行的，客户在借满所需的全部单位款额之前可能会等待，但银行家须保证这种等待是有限的，可完成的。 安全性算法利用安全性算法进行检查，如果分配是安全的，则执行分配；否则，分配不安全，不予分配。具体地，1） 当进程pi提出资
17、源申请时，按照银行家算法分配资源，系统执行下列步骤：（1）若RequestNeed,转（2）；否则错误返回（2）若RequestAvailable,转（3）；否则进程等待（3）假设系统分配了资源，则有： Available:=Available-Request; Allocation:=Allocation+Request; Need:=Need-Request2）若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待为进行安全性检查，定义数据结构： Work:ARRAY1.m of integer; Finish:ARRAY1.n of Boolean;安全性检查的
18、步骤：（1） Work:=Available; Finish:=false;（2） 寻找满足条件的i： a.Finish=false; b.NeedWork; 如果不存在，则转(4)(3) Work:=Work+Allocation; Finish:=true;转(2)(4) 若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态。二、 实验目的通过模拟实现银行家算法，深入理解死锁避免的意义。 三、 实验要求1 充分理解死锁避免的意义。2 理解银行家算法和安全性检查算法的实质3 编写银行家算法模拟程序，实现银行家算法原理。四、 实验步骤1 编写程序，模拟银行家算法。2 在上
19、机环境中输入程序，调试，编译。3 运行程序，得出结果。2.算法描述 设Requesti 是进程Pi的请求向量，如果Requestij=K,表示进程Pi需要K个Rj类型的资源，当Pi发出资源请求后，系统按下面步骤进行检查：（1）如果Requestij=Needi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestij=Availablej,便转向步骤3；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej:=Availablej-Requestij;Allocationi,j:
20、=Allocationi,j+Requestij;Needi,j:=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。3.数据结构银行家算法中的数据结构：（1） 可利用资源向量Available。这是一个含有n个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K,则表示系统中现有Rj类资源K个。（2）最
21、大需求矩阵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) 工作数组Work.。这是一个含有n个元素的数组，它代表可以提供分配的资源数，初始
22、值是Available中的数值，随着资源的回收，它的值也会改变，公式是Worki=Worki+Allocationi。五、附录：参考源程序#include #include#include#include#define null 0#define M 3#define N 5int mem3=10,5,7;typedef struct proc int maxM; int NeedM; int AllM; int WAM; int finish; proc; int Ava3; proc pN;void creat() int i,j,sum;int args153=7,5,3,3,2,2,9
23、,0,2,2,2,2,4,3,3;int args253=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2;int args353=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;int args45=0,0,0,0,0; for(i=0;iN;i+) pi.finish=args4i; for(j=0;jM;j+) pi.maxj=args1ij; pi.WAj=args3ij; for(i=0;iN;i+) for(j=0;jM;j+) pi.Allj=args2ij; pi.Needj=pi.maxj-pi.Allj; for(i=0;iM;i+) sum=0; f
24、or(j=0;jN;j+) sum+=pj.Alli; Avai=memi-sum; void print(int i) int j;printf(nP%d ,i); for(j=0;jM;j+) printf(%2d,pi.maxj); printf( ); for(j=0;jM;j+) printf(%2d,pi.Needj); printf( ); for(j=0;jM;j+) printf(%2d,pi.Allj); printf( ); for(j=0;jM;j+) printf(%2d,pi.WAj); printf( ); printf(%d,pi.finish); printf
25、(n);void bank(int t) int i,j,flag,k=0,m=0; int a5; printf(Available=); for(i=0;iM;i+) printf( %d ,Avai); printf(n Max Need Allocation word+Allocation finishn); for(j=0;jM;j+) pt.WAj=Avaj; i=t; while(k5&m5) flag=1; for(j=0;jpt.WAj) flag=0; if(flag=1) for(j=0;j=5) i=0;m+; /*flag=1; for(i=0;i5;i+) if(!pi.finish) flag=0; break;
