c实现银行家算法.docx

《c实现银行家算法.docx》由会员分享，可在线阅读，更多相关《c实现银行家算法.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、c实现银行家算法银行家算法 银行家算法是一种最有代表性的避免死锁的算法。 要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。 不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。 那么什么是安全序列呢？ 安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和。 银行家算法： 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作

2、系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 算法： n：系统中进程的总数 m：资源类总数 Available: ARRAY1.m of integer; Max: ARR

3、AY1.n,1.m of integer; Allocation: ARRAY1.n,1.m of integer; Need: ARRAY1.n,1.m of integer; Request: ARRAY1.n,1.m of integer; 符号说明： Available 可用剩余资源 Max 最大需求 Allocation 已分配资源 Need 需求资源 Request 请求资源 当进程pi提出资源申请时，系统执行下列 步骤：(“=”为赋值符号，“=”为等号) step（1）若Request=Need, goto step（2）；否则错误返回 step（2）若Request=Avail

4、able, goto step（3）；否则进程等待 step（3）假设系统分配了资源，则有： Available=Available-Request; Allocation=Allocation+Request; Need=Need-Request 若系统新状态是安全的，则分配完成 若系统新状态是不安全的，则恢复原状态，进程等待 为进行安全性检查，定义数据结构： Work:ARRAY1.m of integer; Finish:ARRAY1.n of Boolean; 安全性检查的步骤： step (1): Work=Available; Finish=false; step (2) 寻找满足

5、条件的i： a.Finish=false; b.Need=Work; 如果不存在，goto step(4) step(3) Work=Work+Allocation; Finish=true; goto step(2) step (4) 若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态 /* 银行家算法，操作系统概念(OS concepts Six Edition) reedit by Johnny hagen，SCAU，run at vc6.0 */ #include malloc.h #include stdio.h #include stdlib.h #defi

6、ne alloclen sizeof(struct allocation) #define maxlen sizeof(struct max) #define avalen sizeof(struct available) #define needlen sizeof(struct need) #define finilen sizeof(struct finish) #define pathlen sizeof(struct path) struct allocation int value; struct allocation *next; ; struct max int value;

7、struct max *next; ; struct available /*可用资源数*/ int value; struct available *next; ; struct need /*需求资源数*/ int value; struct need *next; ; struct path int value; struct path *next; ; struct finish int stat; struct finish *next; ; int main() int row,colum,status=0,i,j,t,temp,processtest; struct alloca

8、tion *allochead,*alloc1,*alloc2,*alloctemp; struct max *maxhead,*maxium1,*maxium2,*maxtemp; struct available *avahead,*available1,*available2,*workhead,*work1,*work2,*worktemp,*worktemp1; struct need *needhead,*need1,*need2,*needtemp; struct finish *finihead,*finish1,*finish2,*finishtemp; struct pat

9、h *pathhead,*path1,*path2; printf(n请输入系统资源的种类数:); scanf(%d,&colum); printf(请输入现时内存中的进程数:); scanf(%d,&row); printf(请输入已分配资源矩阵:n); for(i=0;irow;i+) for (j=0;jnext=alloc2-next=NULL; scanf(%d,&allochead-value); status+; else alloc2=(struct allocation *)malloc(alloclen); scanf(%d,%d,&alloc2-value); if(st

10、atus=1) allochead-next=alloc2; status+; alloc1-next=alloc2; alloc1=alloc2; alloc2-next=NULL; status=0; printf(请输入最大需求矩阵:n); for(i=0;irow;i+) for (j=0;jnext=maxium2-next=NULL; scanf(%d,&maxium1-value); status+; else maxium2=(struct max *)malloc(maxlen); scanf(%d,%d,&maxium2-value); if(status=1) maxhe

11、ad-next=maxium2; status+; maxium1-next=maxium2; maxium1=maxium2; maxium2-next=NULL; status=0; printf(请输入现时系统剩余的资源矩阵:n); for (j=0;jnext=available2-next=NULL; work1-next=work2-next=NULL; scanf(%d,&available1-value); work1-value=available1-value; status+; else available2=(struct available*)malloc(avale

12、n); work2=(struct available*)malloc(avalen); scanf(%d,%d,&available2-value); work2-value=available2-value; if(status=1) avahead-next=available2; workhead-next=work2; status+; available1-next=available2; available1=available2; work1-next=work2; work1=work2; available2-next=NULL; work2-next=NULL; stat

13、us=0; alloctemp=allochead; maxtemp=maxhead; for(i=0;irow;i+) for (j=0;jnext=need2-next=NULL; need1-value=maxtemp-value-alloctemp-value; status+; else need2=(struct need *)malloc(needlen); need2-value=(maxtemp-value)-(alloctemp-value); if(status=1) needhead-next=need2; status+; need1-next=need2; need

14、1=need2; maxtemp=maxtemp-next; alloctemp=alloctemp-next; need2-next=NULL; status=0; for(i=0;inext=finish2-next=NULL; finish1-stat=0; status+; else finish2=(struct finish*)malloc(finilen); finish2-stat=0; if(status=1) finihead-next=finish2; status+; finish1-next=finish2; finish1=finish2; finish2-next

15、=NULL; /*Initialization compleated*/ status=0; processtest=0; for(temp=0;temprow;temp+) alloctemp=allochead; needtemp=needhead; finishtemp=finihead; worktemp=workhead; for(i=0;istat=0) for(j=0;jnext,worktemp=worktemp-next) if(needtemp-valuevalue) processtest+; if(processtest=colum) for(j=0;jvalue+=a

16、lloctemp-value; worktemp1=worktemp1-next; alloctemp=alloctemp-next; if(status=0) pathhead=path1=path2=(struct path*)malloc(pathlen); path1-next=path2-next=NULL; path1-value=i; status+; else path2=(struct path*)malloc(pathlen); path2-value=i; if(status=1) pathhead-next=path2; status+; path1-next=path

17、2; path1=path2; finishtemp-stat=1; else for(t=0;tnext; finishtemp-stat=0; else for(t=0;tnext; alloctemp=alloctemp-next; processtest=0; worktemp=workhead; finishtemp=finishtemp-next; path2-next=NULL; finishtemp=finihead; for(temp=0;tempstat=0) printf(n系统处于非安全状态!n); exit(0); finishtemp=finishtemp-next; printf(n系统处于安全状态.n); printf(n安全序列为: n); do printf(p%d ,pathhead-value); while(pathhead=pathhead-next); printf(n); return 0;