没什么，就想探讨一下“银行家算法”-≮电脑知识|网络技术≯-碧海潮声大学生网

墙角野猫 发表于 2006-1-7 01:01

没什么，就想探讨一下“银行家算法”

貌似它是一个避免死锁的算法

墙角野猫 发表于 2006-1-7 01:10

一．算法介绍: **数据结构: 1.可利用资源向量Available 2.最大需求矩阵Max 3.分配矩阵Allocation 4.需求矩阵Need **功能介绍: 模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成: 第一部分:银行家算法(扫描) 1．如果Request<=Need,则转向2;否则,出错 2．如果Request<=Available,则转向3,否则等待 3．系统试探分配请求的资源给进程 4．系统执行安全性算法 第二部分:安全性算法 1.设置两个向量 (1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目) (2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False 2.若Finish=False&&Need<=Work,则执行3;否则执行4(I为资源类别) 3.进程P获得第i类资源,则顺利执行直至完成!并释放资源: Work=Work+Allocation; Finish=true; 转2 4. 若所有进程的Finish=true,则表示系统安全;否则,不安全!

随风发表于 2006-1-7 14:05

看得头都大了

无魂发表于 2006-1-7 19:17

我看笨笨最清楚,我已经发了好多关于银行的文章了,就是没人顶,郁闷,呵...

我是誰 发表于 2006-1-8 19:50

楼主是讨论一种算法，可不是论坛的“银行”问题哦，楼上的，没看清楚吧。 银行家算法
1. 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的. 所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi(j<i)所占的资源之和. 2.不安全状态可能产生死锁. 目前状态最大需求尚需 P1 3 9 6 P2 5 10 5 P3 2 4 2
在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全. 3.银行家算法的思路: 1),进程一开始向系统提出最大需求量. 2),进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量. 3),若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的 剩余资源量,若不超出,则分配,否则等待. 4.银行家算法的数据结构. 1),系统剩余资源量A,其中A表示第I类资源剩余量. 2),各进程最大需求量,B,其中B表示进程j对i 类资源最大需求. 3),已分配资源量C,其中C表示系统j程已得到的第i资源的数量. 4),剩余需求量.D,其中D对第i资源尚需的数目. 5.银行家算法流程:当某时刻,某进程时,提出新的资源申请,系统作以下操作: 1),判定E是否大于D,若大于,表示出错. 2),判定E是否大于系统剩余量A,若大于,则该进程等待. 3),若以上两步没有问题,尝试分配,即各变量作调整. 4),按照安全性推测算法,判断,分配过后,系统是否安全,若安全,则实际分配,否则,撤消分配,让进程等待. 6."安全性检测"算法 1),先定义两个变量,用来表示推算过程的数据. F=A,表示推算过程中,系统中剩余资源量的变化. J=False表示推算过程中各进程是否假设"已完成" 2),流程: 在"剩余"的进程中(在推算)过程中,一些进程假设已完成,查找D<=F的进程,找到后令J=True (假设该进程完成),F+D(该进程所占资源释放),如此循环执行. 若最后,所有的F=True(在推算过程中,所有进程均可以完成),则表示(分配过后)系统是安全的,否则系统是不安全的.

系统结构 发表于 2006-1-10 22:48

一头雾水 发表于 2006-1-11 15:01

什么叫银行家算法啊.我想听下

浪子回头了 发表于 2006-1-11 21:27

墙角野猫 发表于 2006-2-28 18:06

最后去年我交上去的
#include<stdio.h> #define N 5 /*进程数，N的可扩充性已完善*/ #define M 3 /*资源数，M的可扩充性基本完善，若使用输出推荐3~5*/
struct claim { int user; int num; }claims;
int input() { int i; printf("请输入申请分配资源的进程号(0~%d):\n",N-1);/*进程号是0至N-1*/ scanf("%d",&claims.user); for(i=0;i<M;i++) { printf("请输入%c类资源所需的数量:\n",65+i);/*A的ASC2码值是65*/ scanf("%d",&claims.num); } return 1;
}
int safety_chk(int allocation[],int need[],int available) { int work,finish,p,i,j; for(p=0;p<M;p++)work=available;/*初始化work*/ for(p=0;p<N;p++)finish=0;/*初始化finish*/ for(i=0;i<N;i++) { if(finish==0) { for(j=0,p=0;j<M;j++)if(need<=work)p++; if(p==M) { for(j=0;j<M;j++) work=allocation+work; finish=1; i=-1;/*重头再来*/ } } } for(i=0;i<N;i++) { if(finish==0) return 0; } return 1; }
int process(int allocation[],int need[],int available) { int ret,i; input(); for(i=0;i<M;i++) { if(claims.num>need)/*检查*/ { printf("所需资源超过已宣布的最大值！\n"); return 0; } } for(i=0;i<M;i++) { if(claims.num>available)/*检查*/ { printf("尚无足够资源，进程须等待！\n"); return 0; } } for(i=0;i<M;i++)/*尝试分配*/ { available=available-claims.num; allocation=allocation+claims.num; need=need-claims.num; } if(ret=safety_chk(allocation,need,available)==0) {
 printf("安全检查结果：系统处于不安全状态！\n"); for(i=0;i<M;i++) { available=available+claims.num; allocation=allocation-claims.num; need=need+claims.num; } return 0; } else {
 printf("安全检查结果：系统处于安全状态！\n"); } return 1; }
void output(int allocation[],int need[],int available) { int i,j; printf("\tMax最大需求\tAllocation分配\tNeed还需要\tAvailable可用\n");/*为保持每个表项长度基本一致故加中文*/ for(j=0;j<4;j++) { printf("\t");for(i=0;i<M;i++)printf("%-3c",65+i); } printf("\n"); for(i=0;i<N;i++) { printf("P%d\t",i); for(j=0;j<M;j++)printf("%-3d",allocation+need); printf("\t"); for(j=0;j<M;j++)printf("%-3d",allocation); printf("\t"); for(j=0;j<M;j++)printf("%-3d",need); printf("\t"); if(i==0)for(j=0;j<M;j++)printf("%-3d",available); printf("\n"); } }
void firdo(int allocation[],int need[],int available)/*M、N扩展时，各矩阵通过输入的初始*/ { int i,j; for(i=0;i<N;i++) { printf("初始进程%d的分配矩阵Allocation\n",i); for(j=0;j<M;j++) { printf("%c类资源\n",65+j); scanf("%d",&allocation); } printf("初始进程%d的需求矩阵Need\n",i); for(j=0;j<M;j++) { printf("%c类资源\n",65+j); scanf("%d",&need); } } printf("初始可利用资源向量available\n"); for(j=0;j<M;j++) { printf("%c类资源\n",65+j); scanf("%d",&available); } }
void main() { int allocation={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}}; int need={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}}; int available={3,3,2}; int xz; /*下面注释内程序是M、N扩展时，各矩阵通过输入的初始化*/ /*firdo(allocation,need,available); while(safety_chk(allocation,need,available)==0) { printf("\nT0时刻的安全检查结果：系统处于不安全状态！\n请重新进行初始化：\n"); firdo(allocation,need,available); }*/ while(1) { printf("1.申请分配资源\n"); printf("2.导出当前资源状况\n"); printf("3.退出\n"); scanf("%d",&xz); if(xz==3){printf("A03计算机（2）班李宁 0505030208\n");break;} else switch(xz) { case 1:{ if(process(allocation,need,available)==0) printf("资源分配失败！\n"); else printf("资源分配成功！\n"); break; } case 2:output(allocation,need,available); } printf("\n"); }
 return; }

墙角野猫 发表于 2006-2-28 18:07

是用C++模拟的一个

页: [1]

碧海潮声大学生网's Archiver

没什么，就想探讨一下“银行家算法”