银行家算法短小版

1、1简介银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系   银行家算法统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列p1，pn是安全的，即对于每一个进程pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程pj (j < i )当前占有资源量之和。安全状态如果存在一个由系统中所有进程构成的安全序列p1，pn，则系统处于安全状态。安全

2、状态一定是没有死锁发生。不安全状态不存在一个安全序列。不安全状态不一定导致死锁。2数据结构1）可利用资源向量available是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果availablej=k，则表示系统中现有rj类资源k个。2）最大需求矩阵max这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果maxi,j=k，则表示进程i需要rj类资源的最大数目为k。3）分配矩阵allocation这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果allocationi,j=k，则表示进程i当

3、前已分得rj类资源的 数目为k。4）需求矩阵need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果needi,j=k，则表示进程i还需要rj类资源k个，方能完成其任务。needi,j=maxi,j-allocationi,j3算法原理我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全，银行家规定：(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；(3) 当银行家现有的资金不能满足顾客尚需的贷款

4、数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。4算法实现初始化由用户输入数据，分别对可利用资源向量矩阵available、最大需求矩阵max、分配矩阵allocat

5、ion、需求矩阵need赋值。银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求request i，则银行家算法按如下规则进行判断。(1)如果request cusneed i<= needcusneedi，则转（2)；否则，出错。(2)如果request cusneed i<= availablecusneedi，则转

6、（3)；否则，出错。(3)系统试探分配资源，修改相关数据：availablei-=requestcusneedi;allocationcusneedi+=requestcusneedi;needcusneedi-=requestcusneedi;(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。安全性检查算法（1)设置两个工作向量work=available;finish(2)从进程集合中找到一个满足下述条件的进程，finish=false;need<=work;如找到，执行（3)；否则，执行（4)(3)设进程获得资源，可顺利执行，直至完成，从而

7、释放资源。work=work+allocation;finish=true;goto 2(4)如所有的进程finish= true，则表示安全；否则系统不安全。银行家算法流程图算法（c语言实现）#include <string.h>#include <stdio.h>#include <stdlib.h>#include <conio.h> /*用到了getch()*/#define m 5 /*进程数*/#define n 3 /*资源数*/#define false 0#define true 1/*m个进程对n类资源最大资源需求量*/int

8、 maxmn=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/*系统可用资源数*/int availablen=15,10,13;/*m个进程对n类资源最大资源需求量*/int allocationmn=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;/*m个进程已经得到n类资源的资源量 */int needmn=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/*m个进程还需要n类资源的资源量*/int requestn=0,0,0;void main()int i=0,j=0;char flag;void showdata();void changda

9、ta(int);void rstordata(int);int chkerr(int);showdata();enter:printf("请输入需申请资源的进程号（从0到");printf("%d",m-1);printf("）:");scanf("%d",&i);if(i<0|i>=m)printf("输入的进程号不存在，重新输入!n");goto enter;err:printf("请输入进程");printf("%d",i);pr

10、intf("申请的资源数n");printf("类别: a b cn");printf(" ");for (j=0;j<n;j+)scanf("%d",&requestj);if(requestj>needij)printf("%d",i);printf("号进程");printf("申请的资源数 > 进程");printf("%d",i);printf("还需要");printf(&quo

11、t;%d",j);printf("类资源的资源量!申请不合理，出错!请重新选择!n");goto err;elseif(requestj>availablej)printf("进程");printf("%d",i);printf("申请的资源数大于系统可用");printf("%d",j);printf("类资源的资源量!申请不合理，出错!请重新选择!n");goto err;changdata(i);if(chkerr(i)rstordata(i);show

12、data();elseshowdata();printf("n");printf("按'y'或'y'键继续,否则退出n");flag=getch();if (flag='y'|flag='y')goto enter;elseexit(0);/*显示数组*/void showdata()int i,j;printf("系统可用资源向量:n");printf("*available*n");printf("资源类别: a b cn");

13、printf("资源数目:");for (j=0;j<n;j+)printf("%d ",availablej);printf("n");printf("n");printf("各进程还需要的资源量:n");printf("*need*n");printf("资源类别: a b cn");for (i=0;i<m;i+)printf(" ");printf("%d",i);printf("号进程

14、:");for (j=0;j<n;j+)printf(" %d ",needij);printf("n");printf("n");printf("各进程已经得到的资源量: n");printf("*allocation*n");printf("资源类别: a b cn");for (i=0;i<m;i+)printf(" ");printf("%d",i);printf("号进程:");/*p

15、rintf(":n");*/for (j=0;j<n;j+)printf(" %d ",allocationij);printf("n");printf("n");/*系统对进程请求响应，资源向量改变*/void changdata(int k)int j;for (j=0;j<n;j+)availablej=availablej-requestj;allocationkj=allocationkj+requestj;needkj=needkj-requestj;/*资源向量改变*/void rstor

16、data(int k)int j;for (j=0;j<n;j+)availablej=availablej+requestj;allocationkj=allocationkj-requestj;needkj=needkj+requestj;/*安全性检查函数*/int chkerr(int s)int work,finishm,tempm;int i,j,k=0;for(i=0;i<m;i+)finishi=false;for(j=0;j<n;j+)work=availablej;i=s;while(i<m)if (finishi=false&&needij<=work)work=work+allocationij;finishi=true;tempk=i;k+;i=0;elsei+;for(i=0;i<m;i+)if(finishi=false)printf("n");printf("系统不安全! 本次资源申请不成功!n");printf("n&q